最大公约数：gcd(a,b)=gcd(b,a%b);
int gcd(int x,int y){
return !y?x:gcd(y,x%y);
}
lcm(a,b)=a*b/gcd(a,b);
分解质因数：
埃氏筛：O（nloglogn）
a%b=c,ma%b=mc%b
a%c=b%c,c|(b-a)
同余：a%c=b%c,a=b(mod c)
a=b(mod c),k为a,b,c的公因数，a/k=b/k(mod c/k)
ax=1(mod b)
设 k=int(b/a) r=b%a
b=ka+r
ka+r =0 (mod b
kr^(-1)+a^(-1)=0 (mod b
a^-1=b-kr^-1(mod b)
inv[i]=b-b/i*inv[b%i] (b为质数）
inv[a]=a^(p-2)