模板及讲解
数论常用方法
1、$a\% b = a-\lfloor \frac ab \rfloor\cdot b$
2、设$p=ki+r$，$k=\lfloor \frac pi \rfloor, r = p \mod i$
3、$a|c \Leftrightarrow a \equiv 0 \pmod c \Leftrightarrow c \% a = 0 \Leftrightarrow c = ka$
4、设出最小素因子
积性函数
积性函数：对于正整数$n$的一个算术函数$f(n)$，若$f(1)=1$，且当$a,b$互质时$f(ab)=f(a)f(b)$。
完全积性函数：所有对于任何$a,b$都有性质$f(ab)=f(a)f(b)$的函数。
积性函数有：$\varphi(n), \mu(n),d(n),\gcd(n,k),\sigma(n)$ 等
性质：
1、若$n=p_{1}^{a_{1}}p_{2}^{a_{2}}p_{3}^{a_{3}}…p_{n}^{a_{n}}$, 则$f(n)=f(p_{1}^{a_{1}})f(p_{2}^{a_{2}})f(p_{3}^{a_{3}})…f(p_{n}^{a_{n}})$
2、若$f$为积性函数且$f(p^{n})=f^{n}(p)$，则$f$为完全积性函数
积性函数可以由线性筛$O(n)$筛出。
欧几里得算法
求$\gcd(a, b)$，即$a$和$b$的最大公倍数
欧几里得算法：
$$\gcd(a, b) = \gcd(b, a \% b)$$
int gcd(int a, int b) {
if (b == 0) return a;
gcd(b, a % b);
}
性质：
1、$\gcd(a,b)=c$则$a=k_1c, b=k_2c \Leftrightarrow c | a, c | b, c|(a +b)$
2、$ab/ \gcd(a,b)=\operatorname{lcm}(a,b)$
3、$\gcd(a,b)=\gcd(a+bp,b), p \in N$
4、$a,b$互质$\Leftrightarrow \gcd(a,b)=1 \Leftrightarrow \exists x, ax+by=1$
5、对于两个正整数$a,b$设$\gcd(a,b)=k$则存在$\gcd(\frac ak, \frac bk)=1$。推论$m\cdot \gcd(a, b)=\gcd(ma, mb)$
6、设$b | ac, \gcd(b, c)= 1$，则$b|a$
7、更相减损法：$\gcd(a,b)=\gcd(a, a-b)=\gcd(b, a-b) , a \leq b$
8、因为$\gcd(n, x)=\gcd(n, n - x)$，所以如果$x, n$互质，则$n-x, n$互质，即与$n$互质的数成对出现
引理：
当所有数不全部相同时，$\gcd\left ( i_1, i_2, \dots, i_N \right ) \leq \max\left ( i_1, i_2, \dots, i_N \right ) - \min\left ( i_1, i_2, \dots, i_N \right )$
证明：设$d = \gcd\left ( i_1, i_2, \dots, i_N \right ), a = \min\left ( i_1, i_2, \dots, i_N \right ), b = \max\left ( i_1, i_2, \dots, i_N \right )$
显然$a = k_1d (k_1 \in \mathbb{Z}^+), b = k_2d (k_2 \in \mathbb{Z}^+, k_2 > k_1)$， 所以$b - a \geq d$，证毕。
扩展欧几里得算法
求$ax+by=\gcd(a,b)$的解$x,y$
已求出下一个状态一组解$x1,y1$使得$b\cdot x1+(a\% b) \cdot y1=\gcd(a,b)$
由$a\%b=a-\lfloor \frac ab \rfloor\cdot b$,得
$b \cdot x1 +(a-\lfloor \frac ab \rfloor\cdot b) \cdot y1 = \gcd(a,b)$
$b \cdot x1 + a \cdot y1 - b \cdot y1 \cdot \lfloor \frac ab \rfloor = \gcd(a,b)$
$a \cdot y1 + b\cdot (x1-y1\cdot \lfloor \frac ab \rfloor)= \gcd(a,b)$
对照$ax+by=\gcd(a,b)$，可得
$x = y1, y= x1-y1\cdot \lfloor \frac ab\rfloor$
由欧几里得算法终止条件$a=\gcd(a,b), b=0$得，$a \times 1+b \times 0=\gcd(a,b)$
所以$x,y$的边界值是$1，0$
通解：
$$
x = x_1 + \frac {b}{\gcd(a,b)} \cdot n\\
y = y_1 – \frac {a}{\gcd(a,b)} \cdot n
$$
证明：
在原有方程左右两侧同除一个$g=\gcd(a,b)$, 得$x \cdot \frac{a}{g}+y \cdot \frac{b}{g}=1$
$x \cdot \frac{a}{g} + \frac{ab}{g^2} +y \cdot \frac{b}{g} - \frac{ab}{g^2} =1$
合并同类项，$\frac ag(x+\frac bg) + \frac bg (y - \frac ag)=1$
所以$(x+\frac bg, y-\frac ag), (x+2\cdot\frac bg, y-2 \cdot \frac ag)$都是原不定方程的解，这个方程的解具有周期性
由此可得$x$的周期为$b/g$, $y$的周期为$a/g$，得出通解
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;//边界值
return a;//求最大公倍数
}
int ans = exgcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - y * a / b;//公式计算
return ans;
}
(3) 求不定方程$ax+by=c$的最小一组解$x,y$, (Bzoj 1477)
先求出$g = \gcd(a,b)$
如果$c\%g≠0$,无解
否则，将不定方程两边同时除以$g$，得$a_1x+b_1y=c_1$
此时$\gcd(a_1,b_1)=1$,可用扩展欧几里得算法求出$a_1x_1+b_1y_1=1$的解$x_1,y_1$
即$a_1x+b_1y=c_1$的一组解为$x1\cdot c1, y1\cdot c1$
求最小解可用一组特解模$b/\gcd(a, b)$即可得到(由通解周期性可以得知)
(4) 求$a $关于$ n $的乘法逆元, NOIP2012 D2 T1
$(a / b) \% k = (a \cdot b^{-1}) \% k$，$b^{-1}$是$b$的乘法逆元，只有 $ a, k$ 互质($\gcd(a,k)=1$)，才有逆元
$ax\equiv 1\pmod n$
由同余性质得，$ax-1=ny$
变形，得 $ax-ny=1$，此时$\gcd(a,n)$必须为$1$且只有唯一解, 否则无解
即可使用扩展欧几里得算法求解，最后使解在$[0, n-1]$之间
求最小解可用一组特解模$n/\gcd(a, n)=n$(此时$\gcd(a, n)=1$, 否则无解)即可得到(由通解周期性可以得知)
同余
设$m$为正整数，$a,b$是整数，如果$(a \mod m) =(b \mod m)$(或者$a-b$是$m$的整数倍)，那么就说$a$和$b$关于$m$同余。
(1) 同余定理: 如果$a\equiv b\pmod m$，那么$(a - b) = my(y$是常数，且为整数)
(2) $a\equiv a\pmod m$
(3) 如果$a\equiv b\pmod m$，那么$b\equiv a\pmod m$
(4) 如果$a\equiv b\pmod m, b\equiv c\pmod m$，那么$a\equiv c\pmod m$
中国剩余定理
设正整数$m_1,m_2,…,m_k$两两互素，则同余方程组
$$
\begin{cases}
x&\equiv&a_1&\pmod{m_1}\\
x&\equiv&a_2&\pmod{m_2}\\
&&&\vdots\\
x&\equiv&a_k&\pmod {m_k}
\end{cases}
$$
有整数解。并且在模$M = m_1 \cdot m_2 \cdot …\cdot mk$下有唯一解，
解为
$$x \equiv (a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+…+a_kM_kM_k^{-1}) \pmod M$$
其中$M_i= \frac M{m_i}，M_i^{-1}$是$M_i$模$m_i$下的逆元
解法：先$O(n)$的时间求出$M$，然后求出$M_i$, 用扩展欧几里得算法求出$M_i^{-1}$，根据公式进行计算
证明：
我们先考虑只求出满足一个方程的解$x_i$，其他$a_i$都为$0$, 如下(使这个$x$只在这一维中有余数)
$$
\begin{cases}
x&\equiv&0&\pmod{m_1}\\
x&\equiv&0&\pmod{m_2}\\
&&&\vdots\\
x&\equiv&a_i&\pmod {m_i}\\
&&&\vdots\\
x&\equiv&0&\pmod {m_k}
\end{cases}
$$
这样有些困难，我们先求
$$
\begin{cases}
x&\equiv&0&\pmod{m_1}\\
x&\equiv&0&\pmod{m_2}\\
&&&\vdots\\
x&\equiv&1&\pmod {m_i}\\
&&&\vdots\\
x&\equiv&0&\pmod {m_k}
\end{cases}
$$
然后再乘回$a_i$就能得到前面的解了，现在来解$x \equiv 1 \pmod {m_i}$
设$M=m_1 \cdot m_2 \cdot …\cdot mk, M_i= \frac M{m_i}$，显然$Mi|x$，所以我们可以设$x=yMi$
那么$x \equiv 1 \pmod {m_i} \Leftrightarrow yMi \equiv 1 \pmod {m_i}$
注意到这里$y$为$Mi$在模$m_i$的意义下的逆元，即$y=Mi^{-1}$，那么$x=MiMi^{-1}$那么这个方程组的一个方程的解就算出来了，我们算前面的方程组的那个方程的解，为$x=a_iMiMi^{-1}$
由于这个只能满足一个方程，所以我们要把所有的方程解都算出来求和即可，然后模$M$就能得到最终解，即$x \equiv (a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+…+a_kM_kM_k^{-1}) \pmod M$
int crt(int n, int *a, int *m) {
int ans = 0;
int M = 1;
for (int i = 1; i <= n; i++) M *= m[i];
for (int i = 1; i <= n; i++) {
int Mi = M / m[i];
int x, y;
e_gcd(Mi, m[i], x, y);//求Mi的逆元x
ans = (ans + a[i] * Mi * x) % M;
}
return (ans + M) % M;
}
扩展中国剩余定理
对于正整数$m_1,m_2,…,m_k$不满足两两互素，那就需要每个方程两两合并。合并过程如下
$$
\begin{cases}
x&\equiv&a_1&\pmod{m_1}(1)\\
x&\equiv&a_2&\pmod{m_2}(2)\\
&&&\vdots\\
x&\equiv&a_k&\pmod {m_k}
\end{cases}
$$
由(1)(2)，得
$x=a_1+m_1x_1(3)$
$x=a_2+m_2x_2(4)$
联立，$a_1+m_1x_1=a_2+m_2x_2$
移项，$m_1x_1+m_2x_2=a_2-a_1$
用exgcd判是否有解并解出一个特解$x_0$(只要$x_0$不要$y_0$)
将$x_0$带入(3), 得$x=a_1+m_1x_0$
用通解表示为(其中$g=\gcd(m_1, m_2)$)
$x=a_1+m_1(x_0+\frac{m_2}{g} \cdot n)=m_1x_0+a_1+n \cdot \frac{m_1m_2}{g}$
因为$\operatorname{lcm}(a1, a2)=\frac{m_1m_2}{g}$, 所以得到
$x \equiv (m_1x_0+a_1) \pmod{\operatorname{lcm}(m1, m2)}$
用这个方程继续和下面的方程合并即可
求正约数的个数/正约数和
给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $n$ 的正约数的个数，并且求出正约数和
根据乘法原理，$n$ 的正约数的个数为
$$\prod_{i=1}^{k}(a_i+1)$$
正约数个数的前缀和$\sum_{i=1}^{n} \lfloor \frac ni \rfloor ≈ n\sum_{i=1}^{n} \frac 1i ≈ n(lnn+\gamma )$
根据乘法原理，$n$ 的正约数和为
$$\prod_{i=1}^{k}(\sum_{j=0}^{a_i} p_i^j)$$
线性筛
线性筛可以筛出积性函数。
欧拉筛求质数
时间复杂度 $O(n\log(\log n))$，大约能跑$n=10^7$的数据
int vis[n];
int sx() {
int m = sqrt(n + 0.5);
ms(vis,0);
for (int i = 2; i <= n; i++)
if (!vis[i]) for (int j = i * i; j <= n; j += i) vis[j] = 1;
}
线性筛质数
考虑每个合数被它的最小素因子筛去，所以枚举的每个$i$之后枚举质数来筛去对应合数，并且如果$pri|i$就要break了，这样做到不重不漏。
时间复杂度 $O(n)$
vis[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!vis[i]) pri[++tot] = i;
for (int j = 1; j <= tot && (LL)i * (LL)pri[j] <= (LL)n; ++j) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
线性筛因数个数函数 $d_0(n)$
$d_k(n)$表示$n$因数$k$次方的和。
$d_0(n)$即为因数个数
我们筛选需要$3$个数组，$pri(i)$当前质数数组，$d(i)$因数个数函数，$e(i)$最小质因子个数。
由$n=\prod_{i=1}^{k}(a_i+1)$，我们可以用这个正约数公式来筛选。
对于当前枚举的$i, pri$ ，$pri$不超过$i$, 我们用$pri \cdot i$来顶掉$pri \cdot i$使其不会成为质数。$e(pri \cdot i)=1$为$pri$.
当前数是素数，则$d(i)=2, e(i)=1$
如果$pri\nmid i$，由于$pri$为质数所以$pri,i$互质，利用积性函数性质：$d(i \cdot pri)=d(i)d(pri)=2d(i), e(pri \cdot i)=1$
如果$pri\mid i$，由于$d(i)=\prod_{i=1}^{k}(a_i+1)$，其中$e_i=pri$，所以要把$(a_1+1)$除掉之后再乘上$(a_1+2)$，即$d(i \cdot pri)=d(i)/(e(i)+1)\cdot (e(i)+2)$，显然此时$e(pri \cdot i)=e(i)+1$
线性筛因数和函数 $d_1(n)$
$d_k(n)$表示$n$因数$k$次方的和。
$d_1(n)$即为因数和
运用公式和前因数个数面的推导，不难写出以下程序
vis[1] = 1, d[0] = 0, d[1] = 1;
for (LL i = 2; i <= MAX_N; i++) {
if (!vis[i]) pri[++tot] = i, e[i] = i + 1, d[i] = i + 1;
for (LL j = 1; j <= tot && pri[j] * i <= MAX_N; j++) {
vis[pri[j] * i] = 1;
if (i % pri[j] == 0) {
d[pri[j] * i] = d[i] / e[i] * (e[i] * pri[j] + 1);
e[pri[j] * i] = e[i] * pri[j] + 1;
break;
} else d[pri[j] * i] = d[pri[j]] * d[i], e[pri[j] * i] = 1 + pri[j];
}
}
分解质因数
给出$n$，求出$n=A^{B_1}_1 \times A^{B_2}_2 \times … \times A^{B_k}_k$的$A_i$及$B_i$($A_i$为质数)
从1到$\sqrt n$进行找$n$的因子，找到就除干净，注意最后可能$n$还会大于1，特判即可
$\sqrt n$判断可以是$i^2 \leq x$，$x$是当前的$n$
for (LL i = 2; i * i <= x; i++) {
if (x % i == 0) {
//i 是质因数
while (x % i == 0) x /= i;
}
}
if (x != 1) //x 是质因数
分解因数
for (int i = 1; i <= n; i++) { // 从1开始
for (int j = 1; j * j <= a[i]; j++) if (a[i] % j == 0) {
//j 是因数
if (j != a[i] / j) //a[i] / j 是因数
}
}
线性求所有逆元
$O(n)$求$i$的逆元$i^{-1}=-\lfloor \frac pi \rfloor \cdot (p \mod i)^{-1}$
证明：
设$p=ki+r$, 则$p \equiv 0\pmod p \Leftrightarrow ki+r \equiv 0\pmod p$
两边乘以$i^{-1}r^{-1}$, 得$k \cdot r^{-1}+i^{-1}=0$
移项，得$i^{-1}=-k \cdot r^{-1}$
因为$k=\lfloor \frac pi \rfloor, r = p \mod i$
所以$i^{-1}=-\lfloor \frac pi \rfloor \cdot (p \mod i)^{-1}$
欧拉定理
当$\gcd(a,n)=1$ 时，有
$$a^{\varphi(n)} \equiv 1 \pmod n$$
推论
当$\gcd(a,n)=1$
$$a^b \equiv a^{b \mod \varphi(n)} \pmod n$$
当$a, n$不一定互质时，有
$$a^b \equiv a^{b \mod \varphi(n) + \varphi(n)} \pmod n$$
费马小定理
当$p$为质数时(欧拉定理的特殊情况，$\varphi(n)=n-1$当且仅当$n$为质数)：
$$a^{p-1} \equiv 1 \pmod p$$
(1) 快速幂求逆元$a^{-1}=a^{(p-2)} \mod p$ ($a, p$互质)
因为$a^{(p-1)} \equiv 1 \pmod p$
所以$a^{(p-1)} \mod p = 1 \mod p$
所以$a^{(p-2)} \mod p = a^{-1} \mod p$
所以$a^{(p-2)} \mod p$是$a$的逆元。
大步小步算法(BSGS)
给出$x^y \equiv z \pmod p$中的$x, z, p(p$为质数)，求$y$.($log$过程, 快速幂逆过程，离散对数)
根据费马小定理，$y$只需要枚举到$p-1$，否则会产生循环
设$m=\sqrt n, y=am+b$, 那么$x^{am+b} \equiv z \pmod p$, 只用枚举$a,b$即可
把$a,b$放两边，得$x^b \equiv x^{-ma}z \pmod p$
显然$x^b$最多只有$m$个，那么我们把$x^b$放进map里供查询
接着枚举$a$判断即可。
x %= p;//要先取模
if (!x && !z) return printf("1\n");//注意要特判
if (!x) return printf("no solution\n");//注意要特判
LL m = (LL)ceil(sqrt(p - 1)), whw = x;//必须ceil取大，否则会小
a[1] = m + 1;
for (LL i = 1; i < m; i++) {//求左边的x^b
if (!a.count(whw)) a[whw] = i;
whw = (whw * x) % p;
}
LL ni = ksm(x, m, p); ni = ksm(ni, p - 2, p);//x^{-m}
for (LL i = 0; i < m; i++) {//枚举a
LL j = a[z];
if (j) {
if (j == m + 1) return printf("%lld\n", i * m), 0; else return printf("%lld\n", i * m + j), 0;
}
z = (z * ni) % p;
}
printf("no solution\n");
扩展大步小步算法
Lucas 定理
对于$C^m_n \mod p$, 当$n, m$大$p$小且$p$为质数时，不能通过阶乘等方式求解，我们可以运用 Lucas 定理
把$n, m$写成$p$进制数的样子，形如
$m = (a_0a_1…a_k)_p, n = (b_0b_1…b_k)_p$
那么有 Lucas 定理：
$$C^m_n \equiv \prod_{i=0}^kC^{a_i}_{b_i} \pmod p$$
也可写作(递推 / 递归式)，相当于求上面$p$进制表示的过程 ：
$$C^m_n \equiv C^{\lfloor\frac mp\rfloor}_{\lfloor\frac np\rfloor}C^{ m \% p}_{ n \% p} \pmod p$$
例题：Bzoj 2982
预处理阶乘和阶乘逆元，然后 $ O(1) $ 求得 $C^m_n$
LL lucas(LL n, LL m) {
if (m == 0) return 1;
return (C(n % MO, m % MO) * lucas(n / MO, m / MO)) % MO;
}
扩展 Lucas 定理
快速乘
解决 $a \cdot b \mod c$中间变量爆 long long 的情况。
思路与快速幂类似。快速幂运用性质 $a^{x+y}=a^x \cdot a^y$，快速乘运用$a \cdot (b + c)=a \cdot b +a\cdot c$
LL ksc(LL a, LL b, LL c) { //快速乘
LL ans = 1, bs = a;
while(b){
if(b & 1) ans = (ans + bs) % c;
bs = (bs + bs) % c;
b >>= 1;
}
return ans;
}
常见题型
见讲解
