数论模板

exgcd：

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

线性筛质数：

for(int i=2;i<=N;i++){if(!nop[i])pr[++pn]=i;for(int j=1;j<=pn&&i*pr[j]<=N;j++){nop[i*pr[j]]=1;if(!(i%pr[j]))break;} 
}

线性筛莫比乌斯函数：

mu[1]=1;
for(int i=2;i<=N;i++){if(!nop[i])pr[++pn]=i,mu[i]=-1;for(int j=1;j<=pn&&i*pr[j]<=N;j++){nop[i*pr[j]]=1,mu[i*pr[j]]=-mu[i];if(!(i%pr[j])){mu[i*pr[j]]=0;break;}} 
}

线性筛欧拉函数：

eu[1]=1;
for(int i=2;i<=N;i++){if(!nop[i])eu[i]=i-1,pr[++pn]=i;for(int j=1;j<=pn&&i*pr[j]<=N;j++){nop[i*pr[j]]=1,eu[i*pr[j]]=eu[i]*(i%pr[j]?eu[pr[j]]:pr[j]);if(!(i%pr[j]))break;}
}

数论分块：

for(int l=1,r;l<=n;l=r+1){r=n/(n/l);//do sth
}

gcd：

Il int gcd(int x,int y){return y?gcd(y,x%y):x;}

快速幂：

Il int qpow(int x,int y){int t=1;for(;y;y>>=1,x=x*x%mod)if(y&1)t=t*x%mod;return t;}