数论相关 学习笔记

发表于 更新于
基础数论模板。

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

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} \]