数论 学习笔记

模板及讲解

1、筛选法求质数

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

2、欧几里得算法
(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);
}

(2) 求$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 t\\
y = y_1 – \frac {a}{gcd(a,b)} \cdot t
$$

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$, 否则无解)即可得到(由通解可以得知)

3、欧拉函数

(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
10
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);
}
}

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

5、同余
设$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$

6、中国剩余定理
设正整数$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}$,根据公式进行计算
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;
}

7、分解质因数
给出$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,特判即可

8、费马小定理
当$gcd(a,p)=1$且$p$为质数时:
$$a^{(p-1)} \equiv 1 \pmod p$$
(1) 快速幂求逆元
因为$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$的逆元。

常见题型:

见讲解

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