为确保准确性，本文中的数默认为非负整数
欧拉好闪，拜谢欧拉
素数
基本概念
-
整数集合: \(2 = \{...,-2,-1, 0, 1, 2, ...\}\)
-
自然数集合: \(N = \{0, 1, 2, ...\}\)
-
整除:若 \(a=bk\), 其中 \(a,b,k\) 都是整数, 则 \(b\) 整除 \(a\), 记做 \(b|a\), 否则记做 \(b \nmid a\)。
-
约数:如 \(b|a\) 且 \(b \geq 0\), 则称 \(b\) 是 \(a\) 的约数(因数), \(a\) 是 \(b\) 的倍数。
- \(1\) 整除任何数, 任何数都整除\(0\)。
- 若 \(a|b\), \(a|c\), 则 \(a|(b+c)\), \(a|(b-c)\)。
- 若 \(a|b\), 则对任意整数 \(c\), \(a|(bc)\)。
- 传递性:若 \(a|b\), \(b|c\), 则 \(a|c\)。
素数与合数
-
素数: \(a>1\) 且只能被平凡约数整除的数。
-
合数: \(a>1\) 且不是素数的数称为合数。
-
其他整数( \(0\), \(1\), 负整数)既不是素数也不是合数。
-
素数有无穷多个, 但分布比较稀疏, 不大于\(n\)的素数约有 \(\frac{n}{ln(n)}\) 个。
判定素数
bool isPrime(int n)
{
if (n == 1) return false;
else
{
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return true;
}
}
分解质因数
vector<int> factor(int x)
{
vector<int> ret;
for (int i = 2; i * i <= x; i++)
while (x % i == 0)
{
ret.push_back(i);
x /= i;
}
if (x > 1) ret.push_back(x);
return ret;
}
埃氏筛
bool isPrime[maxn + 10]; // isPrime[i]true表示i为素数
void eratos(int n)
{
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int i = 2; i * i <= n; i++)
if (isPrime[i])
{
for (int j = i * i; j <= n; j += i)
isPrime[j] = false;
}
}
埃氏筛优化质因数分解
bool isPrime[maxn + 10];
int minFactor[maxn + 10]; //记录每个数的最小素因数的数组
void eratos(int n)
{
isPrime[0] = isPrime[1] = false;
minFactor[0] = minFactor[1] = -1;
for (int i = 2; i <= n; i++)
{
isPrime[i] = true;
minFactor[i] = i; //初始化，表示还未找到最小的素因数
}
for (int i = 2; i * i <= n; i++)
{
if (isPrime[i])
{
for (int j = i * i; j <= n; j += i)
{
isPrime[j] = false;
if (minFactor[j] == j) //如果此前尚未找到j的素因数，
//那么将其设为i
minFactor[j] = i;
}
}
}
}
vector<int> factor(int x)
{
vector<int> ret;
while (x > 1)
{
ret.push_back(minFactor[x]);
x /= minFactor[x];
}
return ret;
}
欧拉筛法
void euler_sieve(int n) //每个合数只被它的最小素因数筛除
{
memset(isprime, true, sizeof(isprime));
prime[0] = 0; //记录当前素数个数
for (int i = 2; i <= n; i++)
{
if (isprime[i]) prime[++prime[0]] = i; //把素数保存到素数表prime中，并更新素数个数
for (int j = 1; j <= prime[0] && i * prime[j] <= n; j++)
{
isprime[i * prime[j]] = false; //筛除i*prime[j]
if (i % prime[j] == 0) break;
//当i中含有素因子prime[j]时中断循环,确保每个数只被它的最小素因子筛除
//换言之，i 之前被 pri[j] 筛过了
//由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是pri[j] 的倍数
//它们都被筛过了，就不需要再筛了，所以这里直接 break掉就好了
}
}
}
费马小定理
如果 \(p\) 是素数，且 \(a\) 与 \(p\) 互质，即 \(\gcd(a,p)=1\)
那么 \(a^{p-1} \equiv 1 \pmod p\)
证明：
考虑 \(1a, 2a, 3a, ..., (p-1)a\) 这些数
-
他们两两不同余 $ \pmod p$
-
他们均与 \(p\) 互质
因此可以得到 \((1a)\times(2a)\times(3a)\times...\times((p-1)a) \equiv 1\times 2\times 3\times...\times (p-1) \pmod p\)
又因为 \(\gcd(1 * 2 * 3 *...* (p-1),p)=1\)，所以 \((a^{p-1}) \equiv 1 \pmod p\)
二次探测定理
如果 \(p\) 是素数, \(x\) 是小于 \(p\) 的正整数, 且 \(x^2 \equiv 1 \pmod p\)
那么要么 \(x=1\)，要么 \(x=p-1\) 。
因为 \(x^2 \bmod p = 1\) 相当于 \(p\) 能整除 \(x^2 - 1\)，也即 \(p\) 能整除 \((x+1)(x-1)\)。
由于 \(p\) 是素数且 \(x<p\) ，那么只可能是 \(x-1\) 能被 \(p\) 整除(此时 \(x=1\))或 \(x+1\) 能被 \(p\) 整除(此时 \(x=p-1\))。
Miller-Rabin素数测试
对于要判断的数\(n\)
-
先判断是不是 \(2\)，是的话就返回
true。 -
判断是不是小于 \(2\) 的，或合数，是的话就返回
false。 -
令 \(n-1=d*2^R\) ，求出 \(d，R\), 其中 \(d\) 是奇数。
-
随机取一个 \(a\)，且 \(1<a<n\) 根据费马小定理，如果 \(a^{n-1}≡1 \pmod p\) 那么 \(n\) 就极有可能是素数，如果等式不成立，那肯定不是素数了
-
因为 \(n-1=d*2^R\)，所以 \(a^{n-1}=a^{d*2^R}=(a^d)^{2^R}\) 所以我们令 \(x=a^d \bmod n\)
-
然后是 \(R\) 次循环，每次循环都让 \(y=(x*x) \bmod n, x=y\)，这样 \(R\) 次循环之后 \(x=a^{d*2^R}=a^{n-1}\) 了
-
因为循环的时候 \(y=(x*x) \bmod n\)，且 \(x\) 肯定是小于 \(n\) 的，正好可以用二次探测定理，
如果 \(x^2 \bmod n=1\)，也就是 \(y\) 等于 \(1\) 的时候，假如 \(n\) 是素数，那么 \(x=1||x=n-1\)，如果 \(x \neq 1 \&\& x \neq n-1\)，
那么 \(n\) 肯定不是素数了，返回
false。 -
运行到这里的时候 \(x=an-1\)，根据费马小定理，\(x \neq 1\)的话，肯定不是素数了，返回
false -
因为 \(Miller-Rabin\) 得到的结果的正确率为 \(75\%\)，所以要多次循环步骤 \(4\)~\(8\) 来提高正确率
-
循环多次之后还没返回，那么 \(n\) 很大可能是素数了，返回
true
bool Miller_Rabin(long long n) //测试n是否是素数
{
long long a, x, y, d, R = 0;
if (n == 2)return true;
if (n < 2 || n % 2 == 0)return false;
d = n - 1;
while (d % 2 == 0)
{
d = d / 2; //去掉因子2
R++;
}
for (int i = 1; i <= 10; i++) //进行10次测试，测试次数越多越准确
{
a = rand() % (n - 2) + 2; //随机产生[2,N-1]以内的底数a
x = power_mod(a, d, n); //二分快速幂计算a^d % n
for (int j = 1; j <= R; j++)
{
y = x * x % n;
if (y == 1 && x != 1 && x != n - 1) return false;
x = y;
}
if (x != 1) return false;
}
return true;
}
玄学：
-
\(n ≤ 2^{32}\) 时，只需检测 \(a = 2,7,61\)，即可确保正确，即 \(c = 3\)；
-
\(n ≤ 2^{64}\) 时，只需检测 \(a = 2,3,5,7,11\)，即可确保正确，即 \(c = 5\)。
-
\(n\) 特别大时，随机选一个 \(a\) 进行测试，合数通过测试的概率低于 \(\frac{1}{4}\)
合数通过 \(c\) 轮测试的概率低于 \(\frac{1}{4^c}\)，适当设定测试次数即可。
排列组合
\(A_n^m = n (n - 1) (n - 2) ... (n - m + 1) = \frac{n!}{(n - m)!}\)
\(C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n - m)!}\)
\(C_i^j = C_{i - 1}^{j} + C_{i - 1}^{j - 1}\)
for (int i = 0; i <= k; i++)
{
c[i][0] = 1;
}
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= i; j++)
{
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
也可以 \(O(n)\) 计算出 \(1\) 到 \(n\) 每个数的阶乘和阶乘的逆元，每次使用时 \(O(1)\) 计算
最大公约数
基本概念
-
设 \(a\), \(b\) 是不都为 \(0\) 的整数, \(c\) 为满足 \(c|a\) 且 \(c|b\) 的最大整数, 则称 \(c\) 是 \(a\), \(b\) 的最大公约数, 记为 \(\gcd(a,b)\) 或 \((a,b)\)。
-
最大公约数有如下性质:
-
\(\gcd(a,b) = \gcd(b,a)\)
-
\(\gcd(a,0)= a\)
-
\(\gcd(a,b)= \gcd(-a,b)\)
-
\(\gcd(a,ka)=a\)
-
\(\gcd(a,b) = \gcd(|a|, |b|)\)
-
\(\gcd(an, bn) = n \times \gcd(a, b)\)
-
若 \(d|a\) 且 \(d|b\), 则 \(d|\gcd(a, b)\)
-
\(\gcd(a,b)= \gcd(a,ka + b)\)
-
欧几里得算法
int gcd(int a, int b)
{
return (b == 0) ? a : gcd(b, a % b);
}
扩展欧几里得算法
扩展欧几里德算法是在已知整数 \(a, b\) 情况下求 \(ax+by = \gcd(a,b)\) 的一组整数解 \(x\) 和 \(y\)
对于整数 \(a, b\)，必定存在整数对 \(x\)，\(y\) 满足 \(a*x+b*y=\gcd(a, b)\)
证明：
设 \(a * x1+b * y1= \gcd(a, b)\)
\(b * x2 + (a \bmod b) * y2 = \gcd(b, a \bmod b)\)
\(\because\gcd(a,b)=\gcd(b,a \bmod b)\)
\(\therefore a * x1 + b * y1 = b * x2 + (a \bmod b) * y2\)
\(\therefore a * x1 + b * y1 = b * x2 + (a - b * \lfloor \frac{a}{b} \rfloor) * y2\)
\(\therefore a * x1 + b * y1 = b * x2 + a * y2 - b * \lfloor \frac{a}{b} \rfloor * y2\)
\(\therefore a * x1 + b * y1 = a * y2 + b * (x2 - \lfloor \frac{a}{b} \rfloor * y2)\)
观察上式可知,对于 \((a,b)\) 的不定方程可以转换为 \((b,a \bmod b)\) 的不定方程
\(x1 = y2, y1 = x2 - \lfloor \frac{a}{b} \rfloor * y2\)
由此可知 \(x1, y1\) 可由 \(x2, y2\) 得出来的，由此类推 \(x2, y2\) 可是由 \(x3, y3\) 得出来的，
那什么时候是终止呢？也就是递归 \(\gcd(a,b)\) 中 \(b=0\) 时即 \(\gcd(a,0)\) 此时由 \(a*x+b*y==\gcd(a,b)\)
可知 \(a*x+b*y=a\) 解出 \(x=1, y=0\); 此时就是递归终止的地方
然后根据 \(x1=y2,y1=x2-a/b*y2\) 回溯回去就可求出 \(x\) 和 \(y\) 最初的解了。
所以：\(a*x+b*y=\gcd(a,b)\) 一定有解
int exgcd(int a, int b, int &x1, int &y1) ////求解a*x1+b*y1=gcd(a,b)
{
int d, x2, y2;
if (b == 0)
{
x1 = 1;
y1 = 0;
return a;
}
d = exgcd(b, a % b, x2, y2); //求解b*x2+(a%b)*y2=gcd(b,a%b)
x1 = y2;
y1 = x2 - a / b * y2;
return d;
}
扩欧求解不定方程
如果 \(c \bmod d \neq 0\)，那么 \(ax+by=c\) 一定无解。
当 \(c \bmod d=0\) 时(有解)，
先用扩欧求出 \(ax' +by' = d =\gcd(a,b)\) 的一组解 \(x'\) 和 \(y'\)，
则方程原来的一组解为 \(x=x' \times c/d, y=y' \times c/d\)
原方程的解有无限多组，因为满足下面式子：
\(a \times (x+kb)+b \times (y-ka)=c\)，\(k\) 为整数
于是我们得到 \(ax+by=c\) 的通解：
\(x=x' \times c/d+k \times b/d\)
\(y=y' \times c/d-k \times a/d\)
欧拉函数
对于一个正整数 \(x\)，小于 \(x\) 且和 \(x\) 互质的正整数的个数，记做 \(\varphi(x)\)
其中 \(\varphi(1)\) 被定义为 \(1\)，但是并没有任何实质的意义
通式1：\(\varphi(x)=x \times (1-1/p_1) \times (1-1/p_2) \times (1-1/p_3) \times … \times (1-1/p_n)\)
其中 \(p_1, p_2, p_3...p_n\) 为 \(x\) 的所有质因数
通式2：若 \(x\) 是质数 \(p\) 的 \(k\) 次幂,即 \(x=p^k\),有 \(\varphi(x) = p^k-p^{k-1} = (p-1)\times p^{k-1}\)
程序中我们一般将 \(\varphi(x)\) 写成 \(phi(x)\)
性质1: 欧拉函数是积性函数
若 \(x,y\) 互质(即 \(\gcd(x,y)=1\)),那么 \(\varphi(x \times y)=\varphi(x) \times \varphi(y)\)
性质2: 若 \(x\) 是质数 \(\varphi(x) = x-1\)
int euler(int x) //计算小于x的数中与x互质的数的个数
{
int ans = x, a = x; //找出所有x的质因数
for (int i = 2; i * i <= a; i++) //从2讨论到sqrt(n)即可
{
if (a % i == 0) //i为x的质因数
{
ans = ans - ans / i; //φ(x) = x*(1 - 1/p1)*(1 - 1/p2)......
while (a % i == 0) a = a / i; //算术基本定理，抹掉i^1,i^2,i^3....
}
}
if (a > 1) ans = ans - ans / a; //存在大于sqrt(a)的质因子
return ans;
}
筛法求欧拉函数
预先置所有数的欧拉函数值都为它本身，由定理可知，如果 \(p\) 是一个正整数且满足 \(\varphi(p)=p-1\);那么 \(p\) 是素数。
在遍历过程中如果遇到欧拉函数与自身相等的情况，那么说明该数为素数，把这个数的欧拉函数值改变，同时也把能被素因子整除的数改变。
void selcet_euler(int n) //求 φ(1) ,φ(2),...,φ(n)
{
for (int i = 1; i <= n; i++) phi[i] = i;
for (int i = 2; i <= n; i++)
{
if (phi[i] == i) //表示i未被筛到，i是素数
{
for (j = i; j <= n; j += i) //然后更新含有它的数
phi[j] = phi[j] / i * (i - 1); // x*(1 - 1/p1)....*(1 - 1/pk).先除后乘
} // 此处注意先/i再*（i-1)，否则范围较大时会溢出
}
}
欧拉筛线性求欧拉函数
欧拉\(^{2}\)
利用欧拉函数的性质( \(p\) 为质数 )：
-
\(\varphi(p)=p-1\)
-
如果 \(i \bmod p = 0\), 那么 \(\varphi(i * p)=p * \varphi(i)\)
-
若 \(i \bmod p ≠0\), 那么 \(\varphi( i * p )=\varphi(i) * ( p-1 )\)
void getPhi() //求 φ(1) ,φ(2),...,φ(N)
{
int tot = 0;
phi[1] = 1;
for (int i = 2; i <= N; i++)
{
if (Mark[i] == false)
{
Prime[++tot] = i; //当 i 是素数时 phi[i]=i-1
phi[i] = i - 1;
}
for (int j = 1; j <= tot && i * Prime[j] <= N; j++)
{
Mark[i * Prime[j]] = true;
if (i % Prime[j] == 0)
{
phi[i * Prime[j]] = phi[i] * Prime[j];
break;
} //如果i mod p = 0, 那么 phi[i * p]=p * phi[i]
else phi[i * Prime[j]] = phi[i] * (Prime[j] - 1);
} //其实这里Prime[j]-1就是phi[Prime[j]]，利用了欧拉函数的积性
}
} //时间复杂度O(n)
欧拉定理
若 \(a,n\) 为正整数，且 \(a,n\) 互质(即 \(\gcd(a,n)=1\))，则有：
\(a^{\varphi(n)} \equiv 1 \pmod n\)
证明：
设小于 \(n\) 且与 \(n\) 互质的数为 \(x_1, x_2,...,x_{\varphi(n)}\)
考虑这些数 \(a*x_1,a*x_2,...,a*x_{\varphi(n)}\)
-
他们两两不同余 \(\pmod n\)
-
他们均与 \(n\) 互质
因此可以得到
\((a*x_1)*(a*x_2)*(a*x_3)*...*(a*x_{\varphi(n)})=x_1*x_2*x_3*...*x_{\varphi(n)} \pmod p\)
又因为 \(\gcd(x_1*x_2*x_3*...*x_{\varphi(n)},n)=1\)，所以 \(a^{\varphi(n)}≡ 1 \pmod n\)
利用欧拉定理降幂：
\(a\) 与 \(n\) 互质时，\(a^b \bmod n = a^{b \bmod \varphi(n)} \bmod n\)
\(b \geq \varphi(c)\) 时，\(a^b \bmod c = a^{b \bmod \varphi(c) + \varphi(c)} \bmod c\)
欧拉反演
逆元
如果一个线性同余方程 $ax \equiv 1 \pmod p $，则 \(x\) 称为 \(a \bmod p\) 的逆元，记作 \(a^{-1}\)。在 \([0,p)\) 的范围内，逆元是唯一的。
由扩欧可知，只有 \(\gcd(a,p)=1\) 时 \(a\) 的逆元存在
作用: \(a / b \bmod p = a \times b ^ {-1} \bmod p = (a \bmod p) \times (b ^ {-1} \bmod p) \bmod p\)
扩欧求逆元
int inv(int a, int n)
{
int x, y;
if (exgcd(a, n, x, y) == 1) return (x + n) % n;
else return -1;
}
欧拉定理求逆元
\(a^{\varphi(p)} \equiv 1 \pmod p\)
\(a * a ^ {\varphi(p) - 1} \equiv 1 \pmod p\)
特别地，当 \(p\) 为质数时，\(a\) 的逆元为 \(a^{p - 2}\)
快速幂计算即可
线性求逆元
设 \(k \times a + r \equiv 0 \pmod p\) \((r < a)\)
两边同时乘上 \(a^{-1} \times r^{-1}\) 得 \((k \times a + r) \times a^{-1} \times r^{-1}\equiv 0 \pmod p\)
去括号得 \(k \times r^{-1} + a ^ {-1} \equiv 0 \pmod p\)
移项得 $ a ^ {-1} \equiv -k \times r^{-1} \pmod p$
即 $ a ^ {-1} = -\lfloor \frac{p}{a} \rfloor \times (p \bmod a)^{-1} \bmod p$
即 $ a ^ {-1} = (p-\lfloor \frac{p}{a} \rfloor) \times (p \bmod a)^{-1} \bmod p$
inv[0] = inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = (p - p / i) * inv[p % i] % p;
线性求任意多个数逆元
若需要求 \(a_1, a_2...a_n\) 共 \(n\) 个数的逆元
则设 \(s_i = \prod^{i}_{j=1} a_i\)
再求出 \(s_n\) 的逆元 \(sv_n\)
再依次求出 \(sv_i = sv_{i+1} \times a_{i+1}\)
则有 \(a_i\) 的逆元 \(inv_i = sv_i \times s_{i - 1}\)
其他一些很有用的东西
快速幂
int power_mod(int a, int n, int p)
{
int ans = 1;
a %= p;
while (n)
{
if (n & 1) ans = ans * a % p;
a = a * a % p;
n >>= 1;
}
return ans;
}
快速乘法
long long quick_mul(long long a, long long b, long long mod) //快速计算 (a*b) % mod
{
long long ans = 0; // 初始化
while (b) //根据b的每一位看加不加当前a
{
if (b & 1) //如果当前位为1
{
ans = (ans + a) % mod; //ans+=a
}
b = b >> 1; //b向前移位
a = (a << 1) % mod; //更新a
}
return ans;
} //例如：3*19=3*(10011)=(3*2^4+3*2^1+3*2^0)