我的数论模板
最大公因数
int gcd(int a,int b)
{
return b>0?gcd(b,a%b):a;
}
扩展欧几里得
int exgcd(int a,int b,long long &d,long long &x,long long &y)
{
if(!b)
d=a,x=1,y=0;
else
exgcd(b,a%b,d,y,x),y-=(a/b)*x;
}
线性筛
bool isprime[100000005];
int prime[10000000];
const long long maxn=1e8;
void Prime()
{
memset(isprime,1,sizeof(isprime));
mu[1]=1;a[1]=1;
int temp=0;
for(int i=2;i<maxn;i++)
{
if(isprime[i]) prime[++temp]=i;
for(int j=1;j<=temp&&prime[j]*i<maxn;j++)
{
isprime[i*prime[j]]=0;
if(i%prime[j]==0)
{
break;
}
}
}
}
void Mu()
{
memset(isprime,1,sizeof(isprime));
mu[1]=1;a[1]=1;
int temp=0;
for(int i=2;i<maxn;i++)
{
if(isprime[i]) prime[++temp]=i,mu[i]=-1;
for(int j=1;j<=temp&&prime[j]*i<maxn;j++)
{
isprime[i*prime[j]]=0;
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
else mu[i*prime[j]]=-mu[i];
}
a[i]=a[i-1]+mu[i];
}
}
快速幂
int qpow(int a,int b,long long mod)
{
long long ans=1;
long long base=a;
while(b)
{
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
质数分解
int factor[100000000][2];
int getFactor(int x)
{
int cnt=0;
for(int i=1;prime[i]*prime[i]<=x;i++)
{
if(x%prime[i]==0)
{
factor[cnt][0]=prime[i];
int temp=0;
while(x%prime[i]==0)
{
x/=prime[i];
temp++;
}
factor[cnt++][1]=temp;
}
}
if(x!=0)
{
factor[cnt][0]=x;
factor[cnt++][1]=1;
}
return cnt;
}
乘法逆元
int inv(int x,long long mod)
{
return qpow(x,mod-2);
}
int inv(int x)
{
int x,y;
if(exgcd(x,mod,x,y)!=1)
{
return -1;
}
return ((x%mod)+mod)%mod
}
中国剩余定理
复习的话可以看这里
long long China(int n,long long a[],long long m[])
{
long long M=1,ret=0;
for(int i=0;i<n;i++) M*=m[i];
for(int i=0;i<n;i++)
{
long long w=M/m[i];
ret=(ret+w*inv(w,m[i])*a[i])%M;
}
return (ret + M)%M;
}