数论基础篇1

质数及其筛法判断一个数是否是质数判断[1,n]的质数埃式筛法欧拉筛法 最小公倍数和最大公因数最大公因数辗转相除法更相减损术 裴蜀定理引理一推论引理2 费马定理同余等价类、剩余系、缩系欧拉函数求法求一个数的欧拉函数 求$[1,n]$所有数的欧拉函数 欧拉定理扩展欧拉定理逆元定义递推法 扩展欧几里得如何得到特殊解通解 中国剩余定理扩展中国剩余定理

质数及其筛法

判断一个数是否是质数

可以直接枚举 $[2,n-1]$ 中的每个数是否整除 $n$，如果有一个整除 $n$ ,则这个数为合数，反之亦然。 其次，由于 $n$ 的因子是成对出现的，即$i|n$，那么 $(n/i)|n$,所以我们可以只枚举 $[2,\sqrt{n}]$

bool pd(int x){//返回1则为质数，0为合数 for(int i=2;i*i<=x;i++){ if(x%i==0) return 0; } return 1; }

判断[1,n]的质数

如果用上述方法，时间复杂度为 $O(n\sqrt{n})$,显然对于一些$n=1e6$的数据过不去，下面介绍两种更快的筛法

埃式筛法

我们找到一个质数 $p$,并将 $1\ast p,2\ast p\cdots n\ast p$全部打上为合数的标记，那么最终剩下没打标记的就是质数，又因为每个数 $n$ 最多有$logn$个质因数，所以时间复杂度是$O(nlogn)$

bool vis[maxn]; int prime[maxn],cnt; void sieve(int n){ for(int i=2;i<=n;i++){ if(!vis[i]){//是质数 prime[++cnt]=i; for(int j=i*i;j<=n;j+=i)//因为2*i~(i-1)*i都被比i小的质数筛去 vis[j]=i; } } }

欧拉筛法

我们发现上一种筛法来说重复筛了很多合数，所以这种算法是对上一种算法的优化，让每一个数只被筛一遍，所以这个算法规定只被最小的筛数筛掉

int prime[maxn],cnt; bool vis[maxn]; void sieve(){ for(int i=2;i<maxn;i++){ if(!vis[i]){ prime[++cnt]=i; } for(int j=1;j<=cnt&&i*prime[j]<maxn;j++){ vis[prime[j]*i]=1; if(i%prime[j]==0) break; } } }

这其中最重要的优化就是if(i%prime[j]==0) break;，如果当前$i$是扫到的质数的倍数，说明$prime[j+1]$并不是$i\ast prime[j+1]$的最小质因数。即$i\ast prime[j+1]$的时候最小质因数为$prime[j]$

最小公倍数和最大公因数

最大公因数

辗转相除法

先给结论: $gcd(a,b)=gcd(b,a\%b)$ 我们设$gcd(a,b)=k$ 则$a=Pk$ $b=Qk$ $a\%b=(P\%Q)k$ 又因为$P,Q$互质 所以$P\%Q与Q$互质 所以$gcd(b,a\%b)=gcd(Qk,(P\%Q)k)=k=gcd(a,b)$

int gcd(int a,int b){ if(!b) return a; return gcd(b,a%b); }

更相减损术

中国古代，九章算术中提到了一种求最大公约数的方法，即更相减损术.如果要对分式约分，如果$a$，$b$都是偶数，可以将$a$，$b$都折半；否则，将a和b交替地减去对方，直到最后两者相等，那么这个数（乘上原来除掉的2）为原来$a$，$b$的最大公约数. 其证明方法和辗转相除法差不多 即$a\%b=a-k\ast b$

裴蜀定理

$gcd(a,b)=k$且$k|c$，则有$ax+by=c$ 令$a^{\prime }=a/k,b^{\prime }=b/k$,即若满足$a^{\prime }x+b^{\prime }y==1$则裴蜀定理成立，其中$gcd(a,b)=1$ 若$a^{\prime }x\equiv 1$ $(mod$ $b)$，则裴蜀定理成立

引理一

内容：$a\ast k\equiv 0$ $(mod$ $b)$ 不成立. 其中$0<k<b,gcd(a,b)=1$ 若$a\ast k\%b==0$ 因为$gcd(a,b)=1$ 所以$k\%b==0$ 又因为$0<k<b$ 所以$k\%b\ne 0$ 所以引理一得正

推论

内容：若$gcd(a,b)=1$,则$0,a,2\ast a,3\ast a\dots (b-1)\ast a$取模$b$的余数各不相同 反正法： 假设$i\ast a,j\ast a$取模$b$的余数相同 则有$(j-i)\ast a\%b=0$又因为$0<(j-i)<b$，所以与引理一矛盾，故推论得证

引理2

内容: 若$gcd(a,b)=1$ 则$a\ast k\%b=1$其中$0<k<b$ 由推论易得 则裴蜀定理得证

费马定理

当$p$为质数，且$a\%p!=0$ 则有$a^{p-1}\%p=1$ $1\ast a\ast 2\ast a\ast \dots (p-1)\ast a\%p=a^{p-1}\ast (p-1)!\%p$ 由裴蜀定理 $1\ast a,2\ast a\dots (p-1)\ast a$取模$p$得集合为$[1,p-1]$ 所以$1\ast a\ast 2\ast a\ast \dots (p-1)\ast a\%p=(p-1)!\%p$ 所以$a^{p-1}\%p=1$

同余等价类、剩余系、缩系

对于一个正整数$p$，对于$a\%p$，只可能有$p$种结果，并且属于$[0,p-1]$

模$p$的剩余系记作$Z_p$，即小于$p$的所有非负整数

同余等价类，

考虑在模$p$的剩余系下，只有$p$种结果，所以每一个数都代表了$\%p=a$的所有数，对于$a$相同的数，我们称其为同余等价类

如果只考虑$gcd(i,p)=1$的元素，便得到一个子集，称这个子集为缩系，记作$Z_p^{\ast }$

欧拉函数

$\varphi (x)$就是与$[1,x-1]$中与$x$互质的数的个数 欧拉函数就是缩系的大小 当$x$为质数时，$\varphi (x)=x-1$ 当$x$为$a^k$,其中$a$为质数，则$\varphi (x)=a^{k-1}\ast (a-1)=a^k\ast (1-1/a)$ 当$x=a_1^{k_1}\ast a_2^{k_2}\ast \cdots \ast a_m^{k_m}$ 又因为$\varphi (x)$为积性函数(不展开证明不会) 所以 $\varphi (x)=\varphi (a_1^{k_1})\ast \varphi (a_2^{k_2})\ast \cdots \ast \varphi (a_m^{k_m})$ $=a_1^{k_1}\ast (1-1/a_1)\ast a_2^{k_2}\ast (1-1/a_2)\cdots \ast a_m^{k_m}\ast (1-/a_m)$ $=x\ast (1-1/a_1)\ast (1-1/a_2)\ast \dots (1-1/a_m)$

求法

求一个数的欧拉函数

时间复杂度$O(\sqrt{n})$

int getphi(int x){ int ans=x; for(int i=2;i*i<=x;i++){ if(x%i==0){ ans=ans/i*(i-1); while(x%i==0) x/=i; } } if(x>1)//有可能会有质因子大于sqrt(n) ans=ans/x*(x-1); return ans; }

求$[1,n]$所有数的欧拉函数

若用上面的方法,时间复杂度$O(nlogn)$

int phi[maxn]; void init(){ for(int i=2;i<maxn;i++){ if(!phi[i]){ phi[i]=i-1; for(int j=i+i;j<maxn;j+=i){ if(phi[j]==0) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } } }

欧拉定理

内容：如果$gcd(a,p)=1$ 则有$a^{\varphi (p)}\%p=1$ 设集合$x$ 为模 $p$ 意义的缩系,$m$为集合$x$的大小 $x_1\ast a\ast x_2\ast a\ast \cdots \ast x_m\ast a\%p=x_1\ast x_2\ast \cdots \ast x_m\ast a^m$ 又因为$x_1\ast a,x_2\ast a,\dots ,x_m\ast a$取模$p$得到的集合还是缩系 所以$a^{\varphi (p)}=1$

扩展欧拉定理

内容：$a^r\equiv a^{r\%\varphi (p)+\varphi (p)}$ $mod($$p)$ 当且仅当$r>\varphi (p)$

欧拉函数常用来降幂

逆元

定义

$a\ast b\%p=1$,则$b$是$a$的逆元 当且仅当$gcd(a,p)=1$ 因为$a^{p-1}\equiv 1$ 所以$a\ast a^{p-2}\equiv 1$ 所以$a^{p-2}$是$a$的逆元

递推法

$inv[i]=(p-p/i\ast inv[p\%i]+p)\%mo$

扩展欧几里得

如何得到特殊解

这是用来解形如$ax+by=c$不定方程的,其中已知$a,b,c$，且$gcd(a,b)|c$时此方程才有解，因为$ax,by$是$gcd(a,b)$的倍数，如果$c$不是$gcd(a,b)$的倍数，则无解 若$gcd(a,b)|c$,我们把$a,b,c$都除以$gcd(a,b)$， 则变成了一个$a^{\prime }x+b^{\prime }y=c$其中$gcd(a^{\prime },b^{\prime })=1$ 即满足$a^{\prime }x\equiv c$在取模$b^{\prime }$的意义下。 这变到了裴蜀定理的推理了，所以此时有解 我们可以解这个方程$ax+by=gcd(a,b)$，得到答案后再乘上$c/gcd(a,b)$ $ax+by=gcd(a,b)=gcd(b,a\%b)$ 设上式$=b{x}^{\prime }+(a\%b)y^{\prime }=b{x}^{\prime }+(a-a/b\ast b)y^{\prime }$ 两边合并同类项 $(x-y^{\prime })a+(y-x^{\prime }+a/b\ast y^{\prime })b=0$ 所以$x=y^{\prime }$ $y=x^{\prime }-a/b\ast y^{\prime }$ 这本质上是个递归过程 当当前这一层的$b=0$则当前这一层的$x=0,y=1$,然后向上回溯

void exgcd(int a,int b,int &gcd,int &x,int &y){ if(!b){ x=1,y=0,gcd=a; return; } else{ exgcd(b,a%b,gcd,y,x);//因为x=y',不如交换位置 y-=x*(a/b); } }

通解

假设有$ax+by=c$和$a{x}_1+b{y}_1=c$ 则有$a(x_1-x)+b(y_1-y)=0$ 同除$gcd(a,b)$ 则有$\frac{a}{gcd(a,b)}(x_1-x)+\frac{b}{gcd(a,b)}(y_1-y)=0$ 移项得到$\frac{a}{gcd(a,b)}(x_1-x)=-\frac{b}{gcd(a,b)}(y_1-y)$ 因为$gcd(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$ 所以$\frac{b}{gcd(a,b)}|(x_1-x)$ 得出$x_1=x+\frac{b}{gcd(a,b)}\ast t$ 其中$t$为任意整数 $x$的最小正整数解就是特殊解$x\%\frac{b}{gcd(a,b)}$

中国剩余定理

中国剩余定理用于求解 $\{\begin{array}{l}x\equiv r_1(mod{a}_1)\\ x\equiv r_2(mod{a}_2)\\ \dots \\ x\equiv r_m(mod{a}_m)\end{array}$ 其中$r_1,r_2\dots r_m$互质 因为$r_1,r_2\dots r_m$互质，所以我们设$A_i={\prod }_{j=1}^{j<=n\&\&j!=i}{r}_i$,此时$A_i$与$r_i$互质，所以必定存在$c_i$使得$A_i\ast c_i\%r_i=1$(由裴蜀定理的推理得出)。 可以推出$A_i\ast c_i-r_i\ast k=1$ 此时如果$gcd(A_i,r_i)==1$，这个方程组才有解 然后用扩展欧几里得可以求出$c_i$ 所以此时$x_i$=$A_i\ast c_i\ast a_i$ 最终答案$X={\sum }_{i=1}^{i<=m}{x}_i$ 因为$A_i$为其他$r_j$的倍数，所以加起来并不影响答案的正确性 通解$X=X+k\ast {\prod }_{i=1}^{i<=n}{r}_i$

void exgcd(int a,int b,int &gcd,int &x,int &y){ if(!b){ x=1,y=0,gcd=a; return; } else{ exgcd(b,a%b,gcd,y,x); y-=x*(a/b); } } int r[maxn],a[maxn]; int CRT(){ int sum=1; for(int i=1;i<=3;i++){ sum=sum*a[i]; } int ans=0; for(int i=1;i<=3;i++){ int gcd,x,y; int now_m=sum/a[i]; exgcd(now_m,a[i],gcd,x,y); ans=(ans+now_m*x%sum*r[i]%sum)%sum; } if(ans<0) ans=ans+sum; return ans; }

扩展中国剩余定理

$\{\begin{array}{l}x\equiv r_1(mod{a}_1)\\ x\equiv r_2(mod{a}_2)\\ \dots \\ x\equiv r_m(mod{a}_m)\end{array}$ 但是此时$r_1,r_2,\dots ,r_m$并不互质 我们先取出前两个方程 $\{\begin{array}{l}x\equiv r_1(mod{a}_1)\\ x\equiv r_2(mod{a}_2)\end{array}$ 根据方程，我们可以得出 $x=r_1\ast k_1+a_1$ $x=r_2\ast k_2+a_2$ 推出$r_1\ast k_1-r_2\ast k_2=a_1-a_2$ 你会发现这又是一个形如$ax+by=c$的方程 用扩展欧几里得便可以得到$k_1$的通解 $k_1=k_1+t\ast (r_2/gcd(r1,r2))$ 其中$t$为任意实数 将$k_1$代入原式得到 $x=r_1\ast (k1+t\ast (r_2/gcd(r1,r2))+a_1$ $x=r_1\ast k_1+t\ast r_1\ast r_2/gcd(r_1,r_2)+a_1$ $x=r_1\ast k_1+t\ast lcm(r_1,r_2)+a_1$ $x\equiv r_1\ast k_1+a_1(modlcm(r1,r2))$ 这便又是一个方程 这样我们便将两个方程变成一个方程 我们把这个方程再丢回去 方程组便少了一个 我们这样便可以求解$x$

void exgcd(int a,int b,int &gcd,int &x,int &y){ if(!b){ x=1,y=0,gcd=a; return; } else{ exgcd(b,a%b,gcd,y,x); y-=x*(a/b); } } int r[maxn],a[maxn]; int Fabs(int x){ if(x<0) x=-x; return x; } void exCRT(int n){ int gcd,x,y; for(int i=1;i<n;i++){ exgcd(r[i],r[i+1],gcd,x,y); if(Fabs(a[i+1]-a[i])%gcd!=0){ puts("-1"); return; } x=((x*(a[i+1]-a[i])/gcd)%(r[i+1]/gcd)+r[i+1]/gcd)%(r[i+1]/gcd); int lcm=r[i]*r[i+1]/gcd; r[i+1]=lcm; a[i+1]=(x*r[i]+a[i])%lcm; } printf("%lld\n",a[n]); }