1.欧几里得算法

可以通过欧几里得算法求出最大公因子。

int gcd(int x, int y) //欧几里得算法 
{ return y==0 ?  x : gcd(y, x%y);
}

2.扩展欧几里得

可以通过扩展欧几里得求出 $ax+by=d$
不定方程的一组整数解。（$a,b,d$为正整数）

void exgcd(int a, int b, int& x, int& y) //扩展欧几里得 
{if(!b){x=1; y=0;return ;}exgcd(b, a%b, y, x);y-=(a/b)*x; 
}

3.快速幂

可以通过快速幂在 $O(logn)$
的复杂度下求出 $xy\text{mod}p$

LL ksm(LL x, LL y, int p) //快速幂 
{LL ans=1;while(y){if(y&1) ans=(ans*x)%p;y>>=1; x=(x*x)%p;}return ans%p;
}

4.质因数分解

可以求出一个整数的所有质因数（没有去重）

void factor(int num) //质因数分解 
{int fac[MAXN],cnt;while(num!=1)for(int i=2; i<=num; i++) if(num%i==0){fac[++cnt]=i;num/=i; i=1;}for(int i=1; i<=cnt; i++) printf("%d ",fac[i]);
}

5.费马小定理求组合数

可以求 $C_m^n\mathrm{mod}p$，其中需要 $n,m$较小，较大时要用卢卡斯定理优化。

LL combine(LL x, LL y)   //费马小定理求组合数 
{  LL up=1, down=1;  for(LL i=0; i<y; i++){  up=up*(x-i)%p;  down=down*(i+1)%p;  }  return up*ksm(down, p-2, p)%p;  //可以直接使用上文给出的ksm()
}  

6.卢卡斯定理求组合数

同样可以求 $C_m^n\mathrm{mod}p$，其中 $p<=10^5，n,m<=10^{18}$。

LL lucas(LL x, LL y) //卢卡斯定理求组合数 
{  if(!y) return 1;  return combine(x%p, y%p)*lucas(x/p, y/p)%p;  //可以直接使用上文给出的combine()
}  

7.中国剩余定理
可以求解一元线性同余方程组。

LL china(int n, int *a, int *m) //中国剩余定理 
{LL p=1, ret=0, x, y;for(int i=1; i<=n; i ++) p*=m[i];for(int i=1; i<=n; i ++){LL w=p/m[i];exgcd(m[i], w, x, y); //可以直接使用上文的exgcd()ret=(ret+w*y*a[i])%p;}return (ret+p)%p;
}

8.线性素数筛
可以求出 $1\to num$ 内所有的素数。

void prime(int num) //素数筛 
{int cnt=0, check[MAXN], pri[MAXN];sizeof(check, true, sizeof(check));check[1]=false;for(int i=2; i<=num; i++){if(check[i]) pri[++cnt]=i;for(int j=0; j<cnt && i*pri[j]<=num; j++){check[i*pri[j]]=false;if(i%pri[j]==0) break;}}
} 

9.欧拉函数筛
可以求出 $1\to num$ 内的欧拉函数。

void euler(int num) //欧拉函数筛 
{     int cnt=0, check[MAXN], eul[MAXN], pri[MAXN];sizeof(check, true, sizeof(check));  check[1]=false; eul[1]=1;  for(int i=2; i<=num; i++){if(check[i]){pri[++cnt]=i;eul[i]=i-1;}for(int j=0; j<cnt && i*pri[j]<=num; j++){check[i*pri[j]]=false;if(i%pri[j]==0){eul[i*pri[j]]=eul[i]*pri[j];break;}eul[i*pri[j]]=eul[i]*(pri[j]-1);}}      
}

10.莫比乌斯函数筛

可以求出 $1\to num$ 内的莫比乌斯函数

void mobius(int num) //莫比乌斯函数筛 
{int cnt=0, check[MAXN], mob[MAXN], pri[MAXN];sizeof(check, true, sizeof(check));check[1]=false; mob[1]=1;  for(int i=2; i<=num; i++){if(check[i]){pri[++cnt]=i;mob[i]=-1;}for(int j=0; j<cnt && i*pri[j]<=num; j++){check[i*pri[j]]=false;if(i%pri[j]==0){mob[i*pri[j]]=0;break;}mob[i*pri[j]]=-mob[i];}}  
}