推荐：数论知识总结——史诗大作（这是一个flag）
【欧几里得算法】辗转相除法
1.被整除数的性质：若c|a,c|b，则c|(ma+nb)
整除数的性质：若a|c,b|c,gcd(a,b)=1，则ab|c。（否则lcm(a,b)|c）
2.gcd的定义
若c|a,c|b，则c为a和b的公因数。当c能被a和b的所有公因数整除时，c是a和b的最大公因数，记为gcd(a,b)。
若c|gcd(a,b)的充要条件是c|a&&c|b。
带余除法：a=bq+r，证明常用。
当gcd(a,b)=1时，称a和b互素。
最小公倍数lcm(a,b)=a*b/gcd(a,b)。
3.证明：gcd(a,b)=gcd(b,a%b)
a可以表示成a=k*b+r，其中r=a%b。
假设d|a,d|b，则r=a-k*b，r/d=a/d-k*b/d=m，m为整数，故d|r。
所以若d是a和b的公因数，则d也是b和a%b的公因数。
必要性同理易证。
4.辗转相除法：根据3递归，终止于gcd(a,0)=a。
更相减损术：gcd(a,b)=gcd(b,a-b)。
感性理解：gcd(a,b)是组成a和b的基本单位，相减或相除都一定不会丢失，直到不能进行为止就是答案。
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);} ll lcm(ll a,ll b) {return 1ll*a/gcd(a,b)*b;}
