1
gcd为两个数的最大公因数
gcd模板

int gcd (a , b ) {
return b ? gcd (b , a % b ) : a ;
} 

2
lcm为两个数的最小公倍数
lcm(a,b)=(a*b)/gcd(a,b)

3
素数打表

//求0~100000以内的素数
//（下标为0的是素数，下标不为0的为合数）
bool str[100010];
void prime()
{
 str[1]=1;
 for(int i=2;i<100010;i++)
 if(!str[i])
 {
  //可以在这里加数组记录素数 
  for(int j=i*2;j<=100010;j=j+i)
  str[i]=1;
 }
}

4
快速幂
求 a^b%c

int ksm(int a,int b,int c)
{
 int ans=1;
 a=a%c;
 while(b>0) 
 {
  if(b%2==1)
  ans=ans*a%c;
  b=b/2;
  a=(a*a)%c;
 }
 return ans;
}