数论相关 学习笔记

发表于
基础数论模板。

实在不想挂一堆链接了。还是自己写个文章把各种知识点归纳一下吧。

gcd/exgcd

求exgcd的过程就是在求gcd的过程中，同步维护两个变量，以求得不定方程
$$
ax+by=\gcd(a,b)
$$

的一组特解。显然我们通过这组特解可以求得对应的最小非负整数解。当然我们也同样能解决
$$
ax+by=c
$$
这样的不定方程。

算法最关键的步骤就是 $x,y$ 在递归过程中的维护。先放代码：

1
2
3
4
5
6
7
8
9
10
11
int gcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int d,tx,ty;
	d=gcd(b,a%b,tx,ty);
	x=ty;
	y=tx-a/b*ty;
	return d;
}

怎么理解？首先递归到边界时，问题变成 $ax=\gcd(a,b)$，所以答案比较显然。

第二个就是递归过程中。其实更新 $x,y$ 和求gcd的 $a,b$ 道理是一样的，我们更新 $a,b$ 的时候是变成了 $b,a% b$ 往下递归，其中 $a% b$ 可以理解成 $a-(\left \lfloor \frac{a}{b} \right \rfloor \times b)$ 。所以我们就用 $ty,tx-(\left \lfloor \frac{a}{b} \right \rfloor \times ty)$ 来更新 $x,y$。

注意：该算法求得的特解的绝对值不会超过 $a,b$ 的绝对值，但是过程中仍然需要开long long。

逆元

当模数为质数的时候，可以用费马小定理求，原因不解释。逆元的结果是 $a^{p-2}% p$。

一般情况下，可以利用exgcd构造求方程
$$
ax+bp=1
$$

的解，变成最小非负整数解即为 $a$ 在模 $p$ 意义下的逆元。

当然，在求组合数等情况下，也可以利用阶乘求得阶乘的逆元。

CRT/exCRT

中国剩余定理

该算法能给出形如 $x\equiv a_i \pmod{p_i}$ 线性同余方程组的（模数两两互质）的一组解。

求解方法如下：

  • 算得 $M=\prod_{i=1}^n p_i$
  • 算得 $M_i=\frac{M}{p_i}$
  • 用exgcd求得 $M_i$ 在模 $p_i$ 意义下的逆元 $t_i$
  • $ans\equiv \sum_{i=1}^n a_iM_it_i \pmod{M}$

注意：上面的几个式子模数不太一样！

代码：

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++){
	cin>>m[i]>>a[i];
	M*=m[i];
}
for(int i=1;i<=n;i++){
	Mi[i]=M/m[i];
	int x=0,y=0;
	gcd(Mi[i],m[i],x,y);
	ans+=x*a[i]*Mi[i];
	ans=(ans+M)%M;
}

扩展中国剩余定理

该算法用于解决上述问题中模数不保证两两互质的情形。

先考虑只有两个方程的简单情况。
$$
\begin{cases}
x\equiv a_1 \pmod{p_1} \
x\equiv a_2 \pmod{p_2}
\end{cases}
$$
我们可以写成不定方程的形式：
$$
\begin{cases}
x=a_1+p_1m_1\
x=a_2+p_2m_2
\end{cases}
$$
移项得
$$
m_1p_1-m_2p_2=a_2-a_1
$$
用exgcd可以求得一组 $(p_1,p_2)$ 的解，这样我们就将两个不定方程合并成了这个不定方程
$$
x\equiv m_1p_1+a_1 \pmod{\operatorname{lcm}(p_1,p_2)}
$$
多组的问题也像这么合并就行了。

放代码：

1
2
3
4
5
6
7
8
9
10
11
12
int excrt(){
	int M=m[1],ans=a[1];
	for(int i=2;i<=n;i++){
		int x,y,c=(a[i]-ans%m[i]+m[i])%m[i];
		int gc=gcd(M,m[i],x,y);
		x=x*(c/gc)%(m[i]/gc);
		ans+=x*M;
		M*=(m[i]/gc);
		ans=(ans+M)%M;
	}
	return ans;
}

Lucas 定理

感觉说了跟没说一样。
$$
\begin{pmatrix}
n\
m
\end{pmatrix}\bmod p=
\begin{pmatrix}
\lfloor\frac{n}{p}\rfloor \
\lfloor\frac{m}{p}\rfloor
\end{pmatrix}\times
\begin{pmatrix}
n\bmod p \
m\bmod p
\end{pmatrix}
$$