本文主要讲了逆元、（扩展）欧拉定理。
快速模幂
假设\(p\)为奇数，则\(b^p=b^{2\lfloor\frac{p}{2}\rfloor+1}=(b^2)^{\lfloor\frac{p}{2}\rfloor}\times b\)，否则\(b^p=b^{2\lfloor\frac{p}{2}\rfloor}=(b^2)^{\lfloor\frac{p}{2}\rfloor}\)
这样可以写一个循环来实现，在\(p=0\)时结束循环即可。
#include <bits/stdc++.h>
using namespace std;
int a,b,c,x,y,p,m=1;
int main() {
for(scanf("%d%d%d",&a,&b,&p),x=a,y=b; b; b>>=1) {
if(b&1)m=(m*1ll*a)%p;//b为奇数
a=(a*1ll*a)%p;//将a平方
}
printf("%d^%d mod %d=%d\n",x,y,p,m);
return 0;
}
乘法逆元
对于关于\(x\)的同余方程\(ax\equiv1\pmod p\)，当且仅当\(\gcd(a,p)=1\)时有解，有解时最小正整数解即为\(a\)在模\(p\)意义下的逆元，记号为\(a^{-1}\)。
例如\(3\)在模\(10\)意义下的逆元即为\(7\)。
线性筛逆元
首先\(1\)在模\(p\)意义下的逆元必定为\(1\)
我们考虑\(n\ge2\)模\(p\)意义下的逆元。
设\(q=\lfloor\dfrac{p}{n}\rfloor,r=p\%n\)，则\(p=nq+r\)（带余除法的性质）
则\(nq+r\equiv0\pmod p\)
把\(nq\)移项到右边，两边同时乘上\(n^{-1}r^{-1}\)
\(n^{-1}\equiv-q\times r^{-1}\pmod p\)
把\(q=\lfloor\dfrac{p}{n}\rfloor,r=p\%n\)代入
\(n^{-1}\equiv(-\lfloor\dfrac{p}{n}\rfloor)(p\%n)^{-1}\pmod p\)
\(n^{-1}\equiv(p-\lfloor\dfrac{p}{n}\rfloor)(p\%n)^{-1}\pmod p\)
代码：
#include <bits/stdc++.h>
using namespace std;
int mod,n,inv[20000528];
int main() {
scanf("%d%d",&n,&mod),inv[1]=1,printf("1\n");
for(int i=2; i<=n; ++i) {
inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
printf("%d\n",inv[i]);
}
return 0;
}
欧拉定理
若\(\gcd(a,p)=1\)，则\(a^{\varphi(p)}\equiv1\pmod p\)
证明：（可不看）
剩余类
剩余类，亦称同余类。
我们把（所有）对模\(n\)同余的整数构成的一个集合叫做模\(n\)的一个剩余类。
即\(qn+r\)（\(q,r\)为任意整数）所表示的所有数就是与\(r\)模\(n\)同余的剩余类
例如\(\cdots,-11,-5,1,7,13,\cdots\)就是与\(1\)模\(6\)同余的剩余类
简化剩余系
简化剩余系也称既约剩余系或缩系
在与 与\(n\)互素的整数 模\(n\)同余的所有剩余类中，从每一个类中各任取一个数作为代表组成的集合，叫做模\(n\)的一个简化剩余系。
例如模\(5\)的一个简化剩余系是\(1,2,3,4\)，模\(30\)的一个简化剩余系是\(1,7,11,13,17,19,23,29\)
根据\(\varphi(n)\)的定义，模\(n\)的简化剩余系有\(\varphi(n)\)个元素。
根据简化同余系的定义，每个模\(n\)的简化剩余系的所有元素的乘积模\(n\)相等。
证明
设\(x_1,x_2,\cdots,x_{phi(p)}\)是一个以\(p\)为模的缩系。
而且\(\gcd(a,p)=1\)，则\(\gcd(ax_i,p)=1\)
所以\(ax_1,ax_2,\cdots,ax_{phi(p)}\)也是一个以\(p\)为模的缩系。
所以\(\prod\limits_{i=1}^{\varphi(p)}ax_i\equiv\prod\limits_{i=1}^{\varphi(p)}x_i\pmod p\)。
所以\(a^{\varphi(p)}\equiv 1\pmod p\)
费马小定理
当\(p\)为质数时，\(a^p\equiv a\pmod p\)
证明：
当\(a,p\)不互质时即\(p|a\)，显然成立
当\(a,p\)互质时，根据欧拉定理得\(a^{\varphi(p)}\equiv1\pmod p\)
而且\(p\)为质数时，\(\varphi(p)=p-1\)，代入上式后两边同时乘\(a\)即可得证。
变式
当\(\gcd(a,p)=1\)时，\(a\times a^{\varphi(p)-1}\equiv1\pmod p\)
即\(a\)模\(p\)意义下的逆元为\(a^{\varphi(p)-1}\)(当\(p\)为质数时，\(a\)的逆元为\(a^{p-2}\))
快速幂求逆元
直接用欧拉定理的式子即可
#include<bits/stdc++.h>
using namespace std;
int getphi(int n) {
int tmp=n,ans=n;
for(int i=2; i*i<=tmp; ++i)
if(!(tmp%i)) {
ans-=ans/i;
while(!(tmp%i))tmp/=i;
}
return tmp>1?ans-ans/tmp:ans;
}
int a,b,p,m=1;
int main() {
for(scanf("%d%d",&a,&p),b=getphi(p)-1; b; b>>=1) {
if(b&1)m=(m*1ll*a)%p;
a=(a*1ll*a)%p;
}
printf("%d\n",m);
return 0;
}
求多个数的逆元
我们这题要求\(a_1,a_2,\cdots,a_n\)模\(p\)意义下的逆元，我们可以试着用\(O(n+\log p)\)求
设\(s_i=\prod\limits_{i=1}^ia_i\mod p\)，可以\(O(n)\)预处理出\(s_i\)
再设\(b_{i+1}=\prod\limits_{i=1}^i(a_i)^{-1}\pmod p\)，可得\((a_i)^{-1}\equiv b_{i+1}\times s_{i-1}\pmod p\)
接下来就是要考虑如何处理\(b_{i+1}\)：
预处理\(s_i\)后，\(b_{n+1}=s_n^{-1}\pmod p\)，是\(O(\log p)\)
之后\(i\)从\(n\)到\(1\)的循环，算出\(a_i^{-1}\equiv b_{i+1}\times s_{i-1}\pmod p\)，同时算出\(b_i\equiv b_{i+1}\times a_i\pmod p\)即可。
总复杂度\(O(n+\log p)\)
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x=0,c=getchar();
for(; c<=47||c>=58; c=getchar());
for(; c>=48&&c<=57; c=getchar())x=(x<<3)+(x<<1)+(c&15);
return x;
}
const int MAXN=1<<23;
int n,mod,k,b[MAXN],s[MAXN],a[MAXN],inv[MAXN],ans;
int fastpow(int a,int k) {
int base=1;
for(; k; a=((0ll+a)*a)%mod,k>>=1)
if(k&1)
base=((0ll+base)*a)%mod;
return base;
}
int main() {
s[0]=1;
n=read(),mod=read(),k=read();
for(int i=1; i<=n; ++i) {
a[i]=read();
s[i]=s[i-1]*1ll*a[i]%mod;//预处理si
}
b[n+1]=fastpow(s[n],mod-2);
for(int i=n; i>=1; --i) {
inv[i]=b[i+1]*1ll*s[i-1]%mod;//逆元
b[i]=b[i+1]*1ll*a[i]%mod;//bi
}
int tmp=k;
for(int i=1; i<=n; i++) {
ans=(ans+inv[i]*1ll*tmp)%mod;//计算答案
tmp=(tmp*1ll*k)%mod;
}
printf("%d\n",ans);
return 0;
}
有理数取余
\(\dfrac{a}{b}\equiv a\times b^{-1}\pmod p\)
直接用上面说的求逆元即可。
#include<bits/stdc++.h>
using namespace std;
const int mod=19260817;
inline int read() {
int x=0,c=getchar();
for(; c<=47||c>=58; c=getchar());
for(; c>=48&&c<=57; c=getchar())x=((x<<3)+(x<<1)+(c&15))%mod;
return x;
}
int fastpow(int a,int k) {
int base=1;
while(k) {
if(k&1) base=base*1ll*a%mod;
a=a*1ll*a%mod;
k>>=1;
}
return base;
}
int a,b;
int main() {
a=read(),b=read();
printf("%d\n",a*1ll*fastpow(b,mod-2)%mod);
return 0;
}
扩展欧拉定理
当\(b\ge\varphi(m)\)时，\(a^{b}\equiv a^{(b\mod \varphi(m))+\varphi(m)}\pmod m\)
证明：
首先\(m=1\)时，\(\varphi(m)=1\)，结论成立。
任取一个质数\(p\)，\(m\)就可以写成\(p^r\times s\)，其中\(r\ge0,\gcd(p,s)=1\)。
则\(\varphi(p^r)\times \varphi(s)=\varphi(m)\)（\(\varphi\)是积性函数）
由欧拉定理得\(p^{\varphi(s)}\equiv 1\pmod s\)，则\(p^{\varphi(m)}\equiv1\pmod s\)
可以设\(p^{\varphi(m)}=ts+1\)，将式子两边乘上\(p^r\)：
\(p^{\varphi(m)+r}=tm+p^r\)，即\(p^{\varphi(m)+r}\equiv p^r\pmod m\)
当\(b\ge r\)时，\(p^{b}\equiv p^{b-r}p^r\equiv p^{b-r}p^{\varphi(m)+r}\equiv p^{b+\varphi(m)}\pmod m\)
且\(r\leq \varphi(p^r)\leq \varphi(m)\)，所以在\(b\geq\varphi(m)\)时，上式成立。
改写一下上面的结论：
当\(b\ge2\varphi(m)\)即\(b-\varphi(m)\ge\varphi(m)\)时，\(p^{b}\equiv p^{b-\varphi(m)}\pmod m\)
也就是\(p^{b}\equiv p^{(b\mod \varphi(m))+\varphi(m)}\pmod m\)
把\(a\)分解质因数后得到的所有质数都会满足上式，把它们乘起来就是\(a\)也满足。
模板题代码：
#include <bits/stdc++.h>
using namespace std;
int m,a,b,phi;
int getphi(int n) {//求phi
int tmp=n,ans=n;
for(int i=2; i*i<=tmp; ++i)
if(!(tmp%i)) {
ans-=ans/i;
while(!(tmp%i))tmp/=i;
}
return tmp>1?ans-ans/tmp:ans;
}
void read(int&b) {
bool gt=0;
char c=getchar();
for(; c<'0'||c>'9'; c=getchar());
for(; c>='0'&&c<='9'; c=getchar()) {
b=(b<<3)+(b<<1)+(c^48);
gt|=b>=phi;//判断b是否大于phi
b%=phi;
}
if(gt)b+=phi;//不大于就不能加
}
int quickpow(int a,int b,int p) {//快速幂
int m=1;
while(b) {
if(b&1)m=(m*1ll*a)%p;
a=(a*1ll*a)%p;
b>>=1;
}
return m;
}
int main() {
scanf("%d%d",&a,&m),phi=getphi(m),read(b);
printf("%d\n",quickpow(a,b,m));
return 0;
}
一道题
这个\(2^{2^{2\cdots}}\)明显大于\(\varphi(p)\)，根据扩展欧拉定理
\(2^{2^{2\cdots}}\equiv 2^{2^{2^{2\cdots}}\mod \varphi(p)+\varphi(p)}\pmod p\)
这样就可以递归，直到\(p=1,2\)时返回\(0\)即可。
#include<bits/stdc++.h>
using namespace std;
int fastpow(int a,int k,const int mod) {
int base=1;
while(k) {
if(k&1)base=base*1ll*a%mod;
a=a*1ll*a%mod;
k>>=1;
}
return base;
}
int phi(int n) {
int tmp=n;
for(int i=2; i*i<=n; ++i)
if(!(n%i))
for(tmp-=tmp/i; !(n%i); n/=i);
return n>1?tmp-tmp/n:tmp;
}
int solve(int mod) {
int t=phi(mod);
return mod==1||mod==2?0:fastpow(2,solve(t)+t,mod);//递归
}
int n,t;
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
printf("%d\n",solve(n));
}
return 0;
}