gcd,lcm

定理：gcd(a,b)*lcm(a,b)=a*b;

更相损减术：gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)

欧几里得算法：gcd(a,b)=gcd(b,a mod b)

复杂度O(log(a+b))

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

 

转载于:https://www.cnblogs.com/zsben991126/p/10232621.html