数论基础 学习笔记

模板及讲解

筛选法求质数

1
2
3
4
5
6
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;
}

欧几里得算法

求$gcd(a, b)$,即$a$和$b$的最大公倍数

欧几里得算法:

$$gcd(a, b) = gcd(b, a \% b)$$

1
2
3
4
int gcd(int a, int b) {
if (b == 0) return a;
gcd(b, a % b);
}

扩展欧几里得算法

求$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*1+b*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$,得出通解

1
2
3
4
5
6
7
8
9
10
11
int egcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;//边界值
return a;//求最大公倍数
}
int temp = x;
int ans = egcd(b, a % b, x, y);
x = y;
y = temp - 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

$ax\equiv 1\pmod n$
由同余性质得,$ax-1=ny$
变形,得 $ax-ny=1$,此时$gcd(a,n)$必须为$1$且只有唯一解, 否则无解
即可使用扩展欧几里得算法求解,最后使解在$[0, n-1]$之间
那么$(a / b) \% k = (a \cdot b^{-1}) \% k$,$b^{-1}$是$b$的乘法逆元
求最小解可用一组特解模$n/gcd(a, n)=n$(此时$gcd(a, n)=1$, 否则无解)即可得到(由通解周期性可以得知)

欧拉函数

(1) 给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $1,2,3…,n$ 中与n互素的数的个数

公式(容斥原理): $$\varphi(n) = \sum_{S\subseteq(p_1,p_2,…p_k)}(-1)^\left|s\right|\frac {n}{\prod_{p_i\subseteq S}p_i}$$
可变形为:$$\varphi(n) = n(1-\frac1{p_1})(1-\frac1{p_2})…(1-\frac1{p_k})$$
即可在$O(k)$的时间复杂度算出$\varphi(n)$

(2) 不给出唯一分解式求$\varphi(n)$:(Poj 2407)

根据变形的公式,可以枚举所有小于$\sqrt n$的因子,然后之后把他”除干净”(为了提取唯一分解式之中的$p_i$)即可

1
2
3
4
5
6
7
8
9
10
int phi(int n) {
int ans = n;//ans为最后的答案
int m = (int)sqrt(n + 0.5);
for (int i = 2; i <= m; i++) if (n % i == 0) {
ans = ans / i * (i - 1);//ans初值为n,因为1-(1/p) = (p-1)/p,由变形后公式可得
while (n % i == 0) n /= i;//除干净
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}

(3) 用筛选法在$O(nloglogn)$时间复杂度求1~n中所有数的欧拉phi函数值:(Poj 2478)

1
2
3
4
5
6
7
8
9
int phitable(int n, int* phi) {
for (int i = 2; i <= n; i++) phi[i] = 0;
phi[1] = 1;
for (int i = 2; i <= n; i++) if (!phi[i])
for (int j = i; j <= n; j += i) {
if (!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
}

求正约数的个数

给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $n$ 的正约数的个数
根据乘法原理,$n$ 的正约数的个数为
$$\prod_{i=1}^{k}(a_i+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$

线性求所有逆元

$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}$

中国剩余定理

设正整数$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$

Poj 1006

1
2
3
4
5
6
7
8
9
10
11
12
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}$
因为$lcm(a1, a2)=\frac{m_1m_2}{g}$, 所以得到
$x \equiv (m_1x_0+a_1) \pmod{lcm(m1, m2)}$
用这个方程继续和下面的方程合并即可

Hdu 3579

分解质因数

给出$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,特判即可

欧拉定理

当$gcd(a,n)=1$且$1 \leq x < n$并且$x$不被$n$整除时:有
$$a^{\varphi(n)} \equiv 1 \pmod n$$

费马小定理

当$gcd(a,p)=1$且$p$为质数时(欧拉定理的特殊情况,$\varphi(n)=n-1$当且仅当$n$为质数):
$$a^{p-1} \equiv 1 \pmod p$$
(1) 快速幂求逆元$a^{-1}=a^{(p-2)} \mod 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$,求$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$判断即可。

poj 2417

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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$小时,不能通过阶乘等方式求解,我们可以运用 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$$

证明:

待更

扩展 Lucas 定理

常见题型

见讲解

------ 本文结束 ------