求素数（单个&线性筛）
单个素数判断
枚举看n是否能整除i。(O(sqrt{n}))
bool Prime(int x) {
if (x < 2) return 0;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0) return 0;
return 1;
}
线性筛
保证每个和数只被最小的质因子筛掉。(O(n))
int prime[N], tot;//记录素数
bool v[N];//被标记说明不是素数
void Primes(int n) {
v[0] = v[1] = 1;//0和1不是素数
for (int i = 2; i <= n; ++i) {
if (!v[i]) prime[++tot] = i;//没有被标记过，是素数
for (int j = 1; j <= tot && i * prime[j] <= n/*这里比限制n大的就不用筛了*/; ++j) {
v[i*prime[j]] = 1;
if (i % prime[j] == 0) break;//只被最小的质因子筛掉。
}
}
}
求欧拉函数（单个&线性筛）
欧拉函数
- 1～N 中与 N 互质的数的个数称为欧拉函数，记为 (varphi (N))
- 根据算术基本定理 (N=p_1^{c_1}p_2^{c_2}...p_m^{c_m})，则
[varphi (N)=N imes frac{p_1-1}{p_1} imes frac{p_2-1}{p_2} imes ... imesfrac{p_m-1}{p_m}=N imes prod_{质数p|N}(1-frac{1}{p})
]
单个求法
- 根据欧拉函数的计算式，分解质因数即可进行求解。(O(sqrt{n}))
int Phi(int n) {
int ans = n;
for (int i = 2; i * i <= n; ++i)
if (n % i == 0) {
ans = ans / i * (i - 1);//根据计算式计算
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
//如果最后n>1，则为一个大于根号n的一个质因子
return ans;
}
线性筛欧拉函数
-
首先看两个性质
- 若 (p|n) 且 (p^2spacespace|spacespace n)，则 (varphi (n)=varphi (frac{n}{p})*p)
- 若 (p|n) 且 (p^2 ot| spacespace n),则(varphi (n)=varphi (frac{n}{p})*(p-1))
-
第一条
- 若 (p|n) 且 (p^2|n)，则证明 (n) 和 (frac{n}{p}) 有相同的质因子，只是 (p) 这一项的指数不同
- 那么我们可以将其按照欧拉函数的计算式展开，并相除，可得：
[frac{nprod_{i=1}^m(1-frac{1}{p_i})}{frac{n}{p}prod_{i=1}^{m}(1-frac{1}{p_i})}=frac{n}{frac{n}{p}}=p
]
-
第二条
- 若 (p|n) 且 (p^2 ot|spacespace n)，则说明 (p) 与 (frac{n}{p})互质（因为p为素数）
- 那么根据欧拉函数为积性函数的这个性质即可证得：
[varphi(n)=varphi(frac{n}{p})*varphi(p)=varphi(frac{n}{p})*(p-1)
]
- 由上面的两条性质可以线性算出 1~N 的欧拉函数值（在线性筛素数的基础上计算欧拉函数）
void Euler(int n) {
phi[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!v[i]) prime[++tot] = i, phi[i] = i - 1;
for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
v[i*prime[j]] = 1;
if (i % prime[j] == 0) {//性质1
phi[i*prime[j]] = phi[i] * prime[j];
break;
}
else phi[i*prime[j]] = phi[i] * (prime[j] - 1);//性质2
}
}
}
扩展欧几里得算法
- 用途：求 (ax+by=gcd(a, b)) 的特解
- 证明：
[bx'+amod bcdot y'=gcd(b,amod b)
]
[bx'+(a-left lfloor frac{a}{b}
ight
floor)y'=gcd(b,amod b)
]
[ay'+b(x'-left lfloor frac{a}{b}
ight
floor y')=gcd(b,amod b)
]
所以得出
[x=y',y=x'-left lfloor frac{a}{b}
ight
floor y'
]
Code
int Exgcd(int a, int b, int &x, int &y) {
if (b == 0) return x = 1, y = 0, a;
int d = Exgcd(b, a % b, x, y);
int z = x; x = y; y = z - a / b * y;
return d;
}
- 上述代码 x,y 是以引用的方式传递的，此函数求出方程 (ax+by=gcd(a, b)) 的一组特解并返回 a,b 的最大公约数。还有一种较为简便的写法，将上述最后一个式子的x'替换成y'，y'替换成x'。得出以下结论：
[x=x',y=y'-left lfloor frac{a}{b}
ight
floor x'
]
int Exgcd(int a, int b, int &x, int &y) {
if (!b) return x = 1, y = 0, a;
int d = Exgcd(b, a % b, y, x);//这里x，y是反着的
y -= a / b * x;
return d;
}
乘法逆元
- 定义：若整数 (a,m) 互质，并且 (b|a)，则存在一个 (x)，使得 (a/bequiv a cdot xpmod{m})，称 (x) 为 (b) 的模 (m) 乘法逆元，记为 (b^{-1}pmod{m})
- 求法：(b^{-1} = b^{varphi (p)-1})
- 线性求法：
- 推导：
[ ext{设 } m=qcdot b+r
]
[qcdot b+requiv 0pmod{m}
]
[qcdot r^{-1}+b^{-1}equiv 0pmod{m}
]
[b^{-1}equiv -qcdot r^{-1}pmod{m}
]
[ ext{由 }q=m/b, r=mmod b ext{ 得}
]
[b^{-1}equiv -m/bcdot (mmod b)^{-1}pmod{m}
]
写出来就是inv[i] = (-M / i * inv[M%i] % M + M) % M;