数论基础

数学博大精深。近日复习了一些简单的数论,这里再总结一下。


最大公因数

算术基本定理

  • 任何一个大于$1$的正整数都能分解为有限个质数的乘积。

欧几里得算法

原理:$\gcd(a,b)=\gcd(b,a \bmod b)$

复杂度:$O(\log n)$。

代码实现:

1
2
3
int 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
12
int 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
16
int 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
11
int 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
12
int 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$真是美妙的工具。