数论，但是板子
你猜为什么我数学那么差？1. 从欧几里得算法到扩展欧几里得算法我们一般用欧几里得算法求最大公约数，它差不多就这样\(\gcd(m, n) = \begin{cases}n&m = 0\\\gcd(n, m \bmod n) & (m \not = 0)\end{cases}\)扩欧可...
Leading and Trailing （数论）
Leading and Trailinghttps://vjudge.net/contest/288520#problem/EYou are given two integers: n and k, your task is to find the most significant three di...
[BZOJ2186][Sdoi2008]沙拉公主的困惑（数论）
题目描述 传送门 题解 首先如果 (a,b)=1 ，则 (a+b,b)=1 因为n>m，所以m!|n! φ(m!) 表示1~m!中与m!互质的数的个数，那么如果将这些数都加上m!的倍数也一定与m!互质 所以答案为 φ(m!)∗n!m! ...
[BZOJ2186][SDOI2008]沙拉公主的困惑（数论）
设 f[i] 表示 [1,i!] 的数中与 i! 互质的数的个数。边界为 f[0]=1 。 首先介绍一个性质：当 (a,x)=1 时， (k∗x+a,x)=1 。 当 i 不为质数时， (i−1)! ...
【数论】【欧拉函数】【筛法求素数】【乘法逆元】【快速幂取模】bzoj2186 [Sdoi2008]沙拉公主的困惑
http://www.cnblogs.com/BLADEVIL/p/3490321.html http://www.cnblogs.com/zyfzyf/p/3997986.html 翻了翻题解，这两个合起来比较明白…… 题意：求1~n!中与m!互质的数的数量(mod R)。 ∵由欧几里得算法得...
【BZOJ2186】沙拉公主的困惑（数论）
【BZOJ2186】沙拉公主的困惑（数论） 题面 BZOJ 题解 考虑答案是啥 先假设\(n=m\) 现在求的就是\(\varphi(m!)\) 但是现在\(n!\)是\(m!\)的若干倍 我们知道\(gcd(x,y)=gcd(x+ky,y)\) 所以，相当于 每隔\(m!\)，答案增长的值都是\(...
bzoj2186 沙拉公主的困惑 数论
填坑……链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2186 题意：求出$n!$中与$m!$互质数数目。 这个思路……看完之后仍然难以平静…… 首先我们想一想一些小数据就会发现，如果$x$与$m!$不互质，那么$x+km!$也与$m!$不互质...
数论 ： 模运算法则（poj 1152）
题目：An Easy Problem!题意：求给出数的最小进制。思路：暴力WA；discuss中的idea：给出数ABCD，若存在n 满足(A* n^3 +B*n^2+C*n^1+D*n^0)%(n-1) == 0则((A* n^3)%(n-1) +(B*n^2)%(n-1)+(C*n^1)%(n-...
数论-莫比乌斯函数
1.单个函数值：#include <iostream>using namespace std;typedef long long ll;//计算a是否可以mod bint MOD(int a,int b){ return a-a/b*b;}//计算莫比乌斯函数//如果一个数包含平方...
快速傅里叶变换FFT& 数论变换NTT
相关知识时间域上的函数f(t)经过傅里叶变换（Fourier Transform）变成频率域上的F(w)，也就是用一些不同频率正弦曲线的加 权叠加得到时间域上的信号。\[F(\omega)=\mathcal{F}[f(t)]=\int\limits_{-\infty}^\infty f(t)e^{-...
Algorithm: 多项式乘法 Polynomial Multiplication: 快速傅里叶变换 FFT / 快速数论变换 NTT
Intro:本篇博客将会从朴素乘法讲起，经过分治乘法，到达FFT和NTT旨在能够让读者（也让自己）充分理解其思想模板题入口：洛谷 P3803 【模板】多项式乘法（FFT）朴素乘法约定：两个多项式为\(A(x)=\sum_{i=0}^{n}a_ix^i,B(x)=\sum_{i=0}^{m}b_ix^...
BZOJ3601 一个人的数论 【数论 + 高斯消元】
题目链接BZOJ3601题解挺神的首先有\[\begin{aligned}f(n) &= \sum\limits_{x = 1}^{n} x^{d} [(x,n) = 1] \\&= \sum\limits_{x = 1}^{n} x^{d} \sum\limits_{c|(x,n)...
POJ 2109 Power of Cryptography(数论)
Power of Cryptography Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 12219 Accepted: 6251 Description Cu...
BZOJ-2242 计算器 快速幂+拓展欧几里得+BSGS（数论三合一）
污污污污2242: [SDOI2011]计算器 Time Limit: 10 Sec Memory Limit: 512 MB Submit: 2312 Solved: 917 [Submit][Status][Discuss]Description 你被要求设计一个计算器完成以下三项任务： 1...
（数论 欧拉筛法）51NOD 1106 质数检测
给出N个正整数，检测每个数是否为质数。如果是，输出"Yes"，否则输出"No"。 Input第1行：一个数N，表示正整数的数量。(1 <= N <= 1000)第2 - N + 1行：每行1个数(2 <= S[i] <= 10^9)Output输出共N行，每行为 Yes 或 ...
POJ 1775 Sum of Factorials 数论，基础题
输入一个小于1000000的正整数，是否能表达成式子：a1!+a2!+a3!+...+an (a1~an互不相等)。因为10!>1000000，所以先打1~10的阶乘表。从a[10]开始递减判断。(a[0]=0!=1)#include <iostream>#include <...
uva 11526 H(n) (数论)
转载自 http://blog.csdn.net/synapse7/article/details/12873437这道题我自己做的时候没有想到好的优化方法，提交的时候借鉴这篇文章的内容，转载如下：---------------------------------------------------...
Codeforces 515C 题解(贪心+数论)(思维题)
题面传送门:http://codeforces.com/problemset/problem/515/CDrazil is playing a math game with Varda.Let’s define f(x)f(x)for positive integer x as a product ...
RSA简介(一)——数论原理
RSA是最常用的非对称加密算法。所谓非对称加密，就是说有两个密钥，一个密钥加密只可以用另外一个密钥解密，一般一个作为公钥，公开给所有人用来加密用，而另一个用来解密其他拥有公钥的加密结果，叫做私钥。另外，拥有私钥者可以用私钥加密信息，公钥可以解密获得加密内容，从而验证私钥拥有者的身份，这是一种特殊的加...
数学 in OI-数论-1
\(1.\) 质数定义就不说了吧。\(\&\) 定理质数 \(p\) 有且仅有两个质因子 \(1\) 和 \(p\) 。质数有无穷个。\([1,\, n]\) 中的质数个数约为 \(\dfrac{n}{\ln n}\) (此结论可用来大致估算某些数论题的数据范围)。任何一个大于 \(1\) ...