最大公因数
算术基本定理
- 任何一个大于$1$的正整数都能分解为有限个质数的乘积。
欧几里得算法
原理：$\gcd(a,b)=\gcd(b,a \bmod b)$
复杂度:$O(\log n)$。
代码实现：1
2
3int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
更相减损术
原理：$\gcd(a,b)=\gcd(b,a-b)$
高精度取余不好做时可用这个代替，实现与欧几里得算法相似。
质数
Eratosthenes筛法
对于每一个质数，除了自己以外，它的倍数一定不是质数，需要筛去，留下的都是质数。
复杂度$O(n\log\log n)$。（不会证明）
代码实现：1
2
3
4
5
6
7
8
9
10
11
12int pri[N];
bool vis[N];
void Eratosthenes(int n)
{
for (int i = 2; i * i <= n; ++i)
if (!vis[i])
for(int j = i + i; j <= n; j += i)
vis[i] = 1;
for (int i = 2; i <= n; i++)
if(!vis[i])
pri[++cnt] = i;
}
欧拉筛
线性筛法。对于每一个数从最小的质因数从小到大开始筛去，保证分解是唯一的，避免重复筛除。用途不仅仅是筛质数哟！
复杂度$O(n)$。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int cnt, pri[N];
bool vis[N];
void prime(int n)
{
for (int i = 2; i <= n; i++)
{
if (!vis[i])
pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
{
vis[j * pri[j]] = 1;
if (i % pri[j] == 0) //说明有比pri[j]更小的质数已经筛过它了
break;
}
}
}
当$n>5$时，质数总是出现在$6$的倍数的两侧，可以让$i$每次自增$6$进行优化。此外，当提问次数很大时，还可用$Miller-Rabin$算法进一步降低复杂度。
方程
裴蜀定理
- 关于$x$和$y$的线性丢番图方程$ax+by=d$有解当且仅当$\gcd(a,b)|d$。
扩展欧几里得算法
求出两个数的最大公因数，并求出方程$ax+by=\gcd(a,b)$的一组绝对值最小的整数解或判断它无解。
当我们用欧几里得算法求解最大公因数的最后一步，
即$a=\gcd(a,b),b=0$时，
方程$ax+by=\gcd(a,b)$的解为$x=1,y=0$，
即$$a’\times1+b’\times0=\gcd(a,b)$$
对于每一个已知解的方程，设此时的两个数为$a’,b’$，
则有$a’x+b’y=\gcd(a,b)$，
此时的$a’,b’$时由上一步的$b,a\bmod b$计算得来，
即$a’=b,b’=a\mod b$，
$$\Longrightarrow bx+(a\bmod b)y=\gcd(a,b)$$
$$\Longrightarrow bx+(a- \lfloor \frac{a}{b} \rfloor \times b)y=\gcd(a,b)$$
（$\lfloor \rfloor$为向下取整）
$$\Longrightarrow ay+b(x- \lfloor \frac{a}{b} \rfloor y)=\gcd(a,b)$$
设此时的解为$x’,y’$，则$x’=y,y’=x- \lfloor \frac{a}{b} \rfloor y$
一层层向上递归可得原方程的解。
代码实现：1
2
3
4
5
6
7
8
9
10
11int exgcd(int a, int b, int &x, int &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(a, b, y, x);
y -= (a / b) * x;
return d;
}
此时求出的解为$ax+by=\gcd(a,b)$的一组解$x_0,y_0$，若要求$ax+by=d(\gcd(a,b)|d)$的解，
设$c=\gcd(a,b)$，方程的通解为
$$x=x_0\frac{d}{c}+k\frac{b}{c},y=y_0\frac{d}{c}-k\frac{a}{c}(k\in\mathbb{Z})$$
一次同余方程
一元一次同余方程
$ax\equiv b\pmod m$
转化为$ax+my=b$即可。
多元一次同余方程
使用中国剩余定理或者多次$exgcd$。
中国剩余定理
方程组
$$\left\{\begin{aligned}x\equiv a_1\pmod {m_1} \\x\equiv a_2\pmod {m_2}\\……\\x\equiv a_n\pmod {m_n}\end{aligned}\right.$$
（其中$m$两两互质）的通解为$ \sum_{i=1}^{n}M_ia_it_i $，设$ M=\sum_{i=1}^{n} m_i $，其中$M_i=\frac{M}{m_i} $，$t_i$为$M_i$模$m_i$的乘法逆元。
证明：乘$M_i$则整除其他的$m$，乘$t_i$则整除$m_i$，乘$a_i$则模$m_i$为$a$。
扩展中国剩余定理
模数$m$不是两两互质，此时扩展中国剩余定理不再适用。
考虑两个不定方程，可用$exgcd$求出他们的通解，将这两个方程转化为一个，模数变成他们的最小公倍数。进行n次即可。
快速幂
快速求出$a^b\bmod p$。
有递归和位运算两种实现，每次将指数$b$降低为$\frac{b}{2}$。快速乘同理。
复杂度$O(\log n)$。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12int qpow(int a, int b, int p)
{
int ans = 1;
while(b)
{
if(b & 1)
ans = (long long)ans * a % p;
a = (long long)a * a % p;
b >>= 1;
}
return ans;
}
还有很多，待更。$\LaTeX$真是美妙的工具。