最大公约数

最大公约数

欧几里得算法

对于两个数 \(a,b\)，设 \(a>b\)，当 \(a\%b==0\) 时，答案为 \(b\)。

否则，设 \(a=b*q+r,r<b\)，则 \(gcd(a,b)=gcd(b,a\%b)\) ，时间复杂度 \(O(\log N)\)

递归写法

int gcd(int x,int y){
    return y?gcd(y,x%y):x;
}

循环写法，需要特判0

inline int gcd(int x,int y){
    if(!y)return y;
    while(y^=x^=y^=x%=y);/*新的x为旧的y，新的y为旧的x%y*/
    return x;
}

最小公倍数

对于两个数 \(a,b\)，进行质因数分解后可以得到，\(gcd(a,b)*lcm(a,b)=a*b\).

假设某个质因数的指数分别为 \(k_1,k_2\)，\(gcd\) 的该质因数的指数为 \(min(k_1,k_2)\)，\(lcm\) 的该质因数的指数为 \(max(k_1,k_2)\)，\(min(k_1,k_2)+max(k_1,k_2)=k_1+k_2\).

inline int lcm(int x,int y){
    return x*y/gcd(x,y);
}

对于求多个数的最小公倍数或最大公约数，可以求到相邻两个数的答案后再放回去，不会对答案有影响。

扩展欧几里得算法

用于求解 \(ax_1+by_1=gcd(a,b)\) 的一组可行解。

int exgcd(int a,int b,int&x,int &y){
    if(!b)return x=1,y=0,a;
    int g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}