【算法】数论 - 暮无雪代码博客

参考资料

讲课资料

算法学习笔记：快速幂

一、基本概念

$\tiny\text{(其中 a,b,c 都为正整数，p 为质数，下面定理同理)}$

• 整除

当 a 为 b 的倍数，即 $a\pmod b=0$ 时，称 b 整除 a，记作 $b\mid a$. (被除数在后，除数在前)

• 逆元

当 $a \times b\equiv1\pmod{p}$时，称 a,b 在模 p 剩余系中互为逆元.或者说，如果 $(a \times b) \pmod p=1$，则 a,b为逆元.

不难发现，一对倒数也互为逆元.

• 同余

当 $a\pmod c=b\pmod c$ 时，称 a,b 在模 c 意义下同余，记作 $a\equiv b\pmod{c}$ .

二、快速幂

\[a^b = \begin{cases} a^{\frac{b}{2}} \cdot a^{\frac{b}{2}}& \text{b为偶数} \\ a^{b-1} \cdot a & \text{b为奇数} \\ 1 & \text{b=0} \end{cases}\]

总而言之就是一个简单的二分思想.

例子：

$2^{20}=2^{10} \times 2^{10}\Longrightarrow 2^{10}=2^{5} \times 2^5\Longrightarrow2^5=2^4 \times 2$

$2^4=2^2 \times 2^2\Longrightarrow2^2=2^1 \times 2^1\Longrightarrow2^1=2^0 \times 2$

板子：

int qpow(int x,int y,int z){//x^y mod z
	int cur=1;
	while(y!=0){
		if(y%2==1) cur=1ll*cur*x%z;
		x=1ll*x*x%z;
		y/=2;
	}
	return cur;
}

三、唯一分解定理

任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积 $\qquad$——百度百科

其实就是小学学过的分解质因数.

例子：

$24=2^3 \times3$

证明：

1. 可分解性

假设 $n$ 是最小的不能被表示为若干个质数的乘积的自然数,

$\because n \ne 1$ 且 $n$ 不为质数

$\therefore n$ 为合数

$\therefore n=a \cdot b\;(a,b \in Z^+)$

又$\because n$ 是最小的不满足条件的自然数

$\therefore a,b$ 都可以被若干个质数分解

$\therefore n$ 也可以被若干个质数分解，不符合假设.

2. 唯一性

引理 1：如果 $p\nmid a$，则 $(p,a)=1$.
证： $\because p\nmid a$
$\qquad\therefore (p,a)\ne p$
$\quad$又 $\because (p,a) \mid p$
$\qquad\therefore (p,a)=1$
引理 2：如果 $p\mid ab$，则 $p\mid a$ 或 $p\mid b$.
证：分类讨论 $p\mid a$ 和 $p\nmid a$ 的情况即可.

假设 $n=p_1\cdot p_2\,...\,p_s=q_1\cdot q_2\,...\,q_t\,(s \le t$ 且 $p,q$为质数 )

$\therefore p_1\mid q_1\cdot q_2\,...\,q_t$

由引理 2，令 $p_1\mid q_1$

$\because q_1$ 为质数且 $p_1 > 1$

$\therefore p_1=q_1$

同理可得，$p_2=q_2,\,...\,p_s=q_s$

若 $t>s$，则 $q_{s+1}+...+q_t=1$，不符合题意.

得证.

四、费马小定理

$p\mid(a^p-a )$ ，且当 $p \nmid a$ 时，$p\mid(a^{p-1}-1)$
或者表述为
$a^p \equiv a \pmod p$，且当 $p \nmid a$ 时，$a^{p-1}\equiv1 \pmod p$

费马小定理可以帮助我们求逆元.

由于 $a \cdot a^{p-2} \equiv 1 \pmod p$

故 $a^{-1} \equiv a^{p-2} \pmod p$.

例子：

当 $a=4,p=5$ 时，

$a^p-a=4^5-4=1020$ 且 $1020 \pmod 5=0$，式子一成立.

$a^{p-1}-1=4^4-1=255$ 且 $255 \pmod 5=0$，式子二成立.

当 $a=6,p=3$ 时，

$a^p-a=6^3-6=210$ 且 $210 \pmod 3=0$，式子一成立.

$a^{p-1}-1=6^2-1=35$ 且 $35 \pmod3 =2$，式子二不成立.

板子：

//求 n 在 mod p 意义下的逆元
int qpow(int x,int y,int p){}//见快速幂模板

int main(){
	cin>>n>>p;
	cout<<qpow(n,p-2,p);
	return 0;
}

五、欧拉定理

当 $n$ 和 $a$ 互质时，$ n\mid(a^{\varphi(n)}-1)$ 或表述为 $a^{\varphi(n)}\equiv1 \pmod n$

关于 $\varphi(n)$：

$\varphi(n)$：所有小于 $n$ 且与 $n$ 互质的数，成为欧拉函数.

如果 $n$ 和 $m$ 互质，$\varphi(n\cdot m) = \varphi(n) \cdot \varphi(m)$.

如果 $n$ 为质数，那么 $\varphi(n)=n-1$.

求欧拉函数的公式： $\varphi(n) = \prod_{i = 1}^n p_i^{a_i - 1}(p_i -1) = n \prod_{i = 1}^n (1 - \frac{1}{p_i})$

至于证明？我不会.

不难发现，当 $n$ 为质数时，此时欧拉定理也是费马小定理.

同费马小定理，欧拉定理也可以求出逆元.

$a^{-1}\equiv a^{\varphi(n)-1} \pmod n$

例子：

当 $a=3,n=8$ 时，

$\varphi(n)=4,\;a^{\varphi(n)}-1=80$ 且 $80\pmod 8=0$，定理成立.

板子：

//求 n 在 mod p 意义下的逆元
int qpow(int x,int y,int p){}//见快速幂模板

void varphi_all(){//求 1~n 的所有数的欧拉函数
	vis[1]=true;
	for(int i=2;i<=n;i++){
		if(vis[i]==false){
			phi[i]=i-1;
			prime.push_back(i);
		}
		for(int j=0;j<prime.size();j++){
			int v=prime[j];
			if(i*v>n) break;
			vis[i*v]=true;
			phi[i*v]=phi[i]*phi[v];
			if(i%v==0){
				phi[i*v]=phi[i]*v;
				break;
			}
		}
	}
}

int varphi_one(int x){//只求 x 的欧拉函数
	int cur=n;
	for(int i=2;i*i<=n;i++){
		if(x%i==0){
			cur-=cur/i;
			while(x%i==0) x/=i;
		}
	}
	if(x>1) cur-=cur/x;
	return cur;
}

int main(){
	cin>>n>>p;
	cout<<qpow(n,varphi_one(n)-1,p);
	return 0;
}

六、扩展欧拉定理

\[a^b \pmod n = \begin{cases} a^b \pmod n & b < \varphi(n) \\ a^{b \pmod \varphi(n) + \varphi(n)} \pmod n & b \geq \varphi(n) \end{cases}\]

欧拉定理最普遍的情况，当模数没有任何限制时考虑该定理.

例子：

当 $a=6,b=16,n=9$ 时，

$\varphi(n)=6,\;a^{b \pmod\varphi(n)+\varphi(n) }\equiv a^{10} \mod n=0$，成立.

板子：【模板】扩展欧拉定理

//还要开个 long long
inline int varphi(int x){}//见求单个的欧拉函数模板

inline int qpow(int x,int y,int p){}//见快速幂模板

signed main(){
	ios::sync_with_stdio(false);
	string s;
	cin>>a>>n>>s;
	int m=varphi(n);
	bool f=false;
	for(int i=0;i<s.size();i++){
		int x=s[i]-'0';
		b=b*10+x;
		if(b>=m){
			b=b%m;
			f=true;
		}
	}
	if(f==true) b+=m;
	cout<<qpow(a,b,n);
	return 0;
}

七、欧几里得算法

$\gcd(a,b)=\gcd(b,a\pmod b)$

就是辗转相除法啦！

例子：

$136\div85=1\,...\,51\Longrightarrow85\div51=1\,...\,34$

$51\div 34=1\,...17\Longrightarrow34\div 17=2$

故 $(136,85)=17$

板子：

int gcd(int a,int b){//手写gcd
	if(b==0) return a;
	return gcd(b,a%b);
}

int main(){
	cin>>a>>b;
	cout<<__gcd(a,b)<<" "<<gcd(a,b);//__gcd为c++自带求最大公因数的函数
	return 0;
}

八、扩展欧几里得算法

扩展欧几里得可以在求 $\gcd(a,b)$ 的同时求出 $ax+by=\gcd(a,b)$ 的一组解

令求出来的特解为 $x_0,y_0$.

通解为 $\begin{cases} x=x_0+k b\\ y=y_0-ka\end{cases}$

例子： 求 $135x+85y=17$ 的一组解

先按上面的辗转相除，这里只展示代入部分.

$17=51-1\times 34\Longrightarrow51-1\times(85-1\times51)\Longrightarrow2\times 51-1\times 85$

$2\times(136-1\times 85)-1\times 85\Longrightarrow2\times 136-3\times 85$

故该不定方程的一组解为$\begin{cases} x=2 \\ y=-3 \end{cases}$

板子： 【模板】二元一次不定方程 (exgcd)

八. 五、线性求逆元

$\tiny\text{为什么叫8.5呢？因为这个东西既没有特别重要，也没有特别不重要(}$

在 $a\div b=q\,...\,r$ 这个余式中，$b^{-1}\equiv (b-q)\cdot r^{-1}\pmod a$

证明：

$r+q\cdot b\equiv0\pmod a$

等式两边同时乘以 $r^{-1}\cdot b^{-1}$.

$b^{-1}+q\cdot r^{-1}\equiv0 \pmod a$

$b^{-1}\equiv -q\cdot r^{-1} \pmod a$

板子：【模板】乘法逆元

inv[1]=1;
for(int i=1;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;

八.七、阶乘逆元

求 $1!\rightarrow n!$ 的逆元，有 $\dfrac{1}{n!}=\dfrac{1}{(n+1)!}\cdot (n+1)$

证明： 不需要证，很显然
板子： 【模板】乘法逆元2