数论的板子

辗转相除法

原始版本

inline int gcd(x,y){
return (y==0)?x:gcd(y,x%y);
}

高级版本

inline void gcd(int x,int y){
int i,j;
if(!x)return y;if(!y)return x;
for(i=0;!(x&1);i++)x>>=1;
for(j=0;!(j&1);j++)j>>=1;
while(true){
if(x<y){x^=y;y^=x;x^=y;}
if(!(x-=y))return y<<i;//这里也可以减法改成模
while(!(x&1))x>>=1;//消除所有的2
}
}

扩展欧几里得

int exgcd(int a,int b,int &x,int &y){
if(!b){x=1;y=0;return a;}
int gcd=exgcd(b,a%b,x,y);
int t=x;x=y;y=t-b/a*y;
return gcd;
}

逆元

int inv(int n,int p){
//这里面求的是n在mod p情况下的逆元
if(n==1)return 1;
else return -(p/n)*inv(p%n,p);
}

欧拉筛

int prm[maxn],cnt=0;
bool isp[maxn]={1,1};//记录哪一些数不是质数
void Eular_Sieve(){
for(int i=2;i<maxn;i++){
if(!isp[i])prm[++cnt]=i;
for(int j=0;j<cnt and i*prm[j]<maxn;j++){
isp[i*prm[j]]=true;
if(!(i%prm[j]))break;
}
}
}

欧拉函数

int prm[maxn],phi[maxn],cnt=0;
bool isp[maxn]={1,1};//记录哪一些数不是质数
void Eular_Sieve(){
phi[1]=1;
for(int i=2;i<maxn;i++){
if(!isp[i])prm[++cnt]=i,phi[i]=i-1;//质数的phi值等于他自己减去1
for(int j=0;j<cnt and i*prm[j]<maxn;j++){
isp[i*prm[j]]=true;
if(!(i%prm[j])){
phi[i*p[j]]=phi[i]*prm[j]
break;
}
else phi[i*p[j]]=phi[i]*(prm[j]-1);
}
}
}

Lucas

非递归形式

int Lucas(int n,int m,int p){
int res=1,a,b;
while(n&&m){
int a=n%p,b=b%p;
if(a<b)return 0;
(res*=C(a,b,p))%=p;
n/=p;m/=p;
}
return res;
}

递归形式

long long qkpow(long long b,int p,int mod){
long long res=1;
while(p){
if(p&1){
(res*=b)%=mod;
}
(b*=b)%=mod;
p>>=1;
}
return res;
}
long long C(int n,int m,int p){
if(n<m)return 0;
if(n==m)return 1;
if(m>n-m)m=n-m;//约掉
long long s1=1,s2=1;
for(int i=0;i<m;i++){
s1=s1*(n-i)%p;
s2=s2*(i+1)%p;
}
return s1*qkpow(s2,p-2,p)%p;
}
long long Lucas(int n,int m,int p){
if(m==0)return 1;
return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}

Catalan Number

f[0]=1
for(int i=1;i<=N;i++){
for(int j=0;j<i;j++){
f[i]=f[j]*f[i-1-j];
}
}
f[0]=1;
for(int i=1;i<=N;i++){
f[i]=((4*i-2)*f[i-1])/(i+1);
}