数论基础 学习笔记

模板及讲解

数论常用方法

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\equiv b\pmod m$,那么$(a - b) = my(y$是常数,且为整数)
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)$$

1
2
3
4
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)=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$

扩展欧几里得算法

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

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 = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $n$ 的正约数的个数,并且求出正约数和
根据乘法原理,$n$ 的正约数的个数为
$$\prod_{i=1}^{k}(a_i+1)​$$
根据乘法原理,$n$ 的正约数和为
$$\prod_{i=1}^{k}(\sum_{j=1}^{a_i} p_i^j)$$

线性筛

线性筛可以筛出积性函数。

欧拉筛求质数

时间复杂度 $O(nlog(logn))$,大约能跑$n=10^7$的数据

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

线性筛质数

Luogu 3383

考虑每个合数被它的最小素因子筛去,所以枚举的每个$i$之后枚举质数来筛去对应合数,并且如果$pri|i$就要break了,这样做到不重不漏。
时间复杂度 $O(n)$

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

线性筛因数个数函数 d0(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$

线性筛因数和函数 d1(n)

$d_k(n)$表示$n$因数$k$次方的和。
$d_1(n)$即为因数和
运用公式和前因数个数面的推导,不难写出以下程序

1
2
3
4
5
6
7
8
9
10
11
12
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$

1
2
3
4
5
6
7
for (LL i = 2; i * i <= x; i++) {
if (x % i == 0) {
//i 是质因数
while (x % i == 0) x /= i;
}
}
if (x != 1) //x 是质因数

分解因数

1
2
3
4
5
6
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= a[i]; j++) if (a[i] % j == 0) {
//j 是因数
if (j != a[i] / j) //a[i] / j 是因数
}
}

欧拉函数

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

线性求所有逆元

$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$且$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$互质)

因为$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$判断即可。

poj 2417

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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$

1
2
3
4
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$

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

常见题型

见讲解

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