本文共 1044 字，大约阅读时间需要 3 分钟。

Euclidean Algorithm:

#include
   
    using namespace std;#define LL long longLL a,b;LL minlsm,mink;void doit(LL i){    // 找到 大于 a 且是 i 的最小倍数，即 a+k    LL aa = ( a + i - 1) / i * i;    // 找到 大于 b 而且 i 的最小倍数，即 b+k    LL bb = ( b + i - 1) / i * i;    /*    这里要说明，根据Euclidean Algorithm，    gcd( a+k , b+k ) = gcd( a+k , b-a )    此时 aa = a + k , bb = b + k 的k一定是同一个k    */    // 计算最小公倍数    LL lsm = aa * bb / i;    // 计算k    LL k = aa - a;    // 更新答案    if( lsm < minlsm || (lsm == minlsm && k < mink)){        minlsm = lsm;        mink = k;    }}int main(){    scanf("%I64d%I64d",&a,&b);    if(b < a) swap(a,b);    minlsm = a*b;    mink = minlsm - a;    LL c = b - a;    if(c == 0){        printf("0\n");        return 0;    }    // gcd( a+k , b+k ) = gcd( a+k , b-a )    // b-a 不能为0    // 枚举 b-a 的所有因子    for(int i=1 ; i*i <= c ; i++ ){        if( c % i ) continue; // i 不是 c 的因子        doit(i);        doit(c/i);    }    printf("%I64d\n",mink);    return 0;}
   

转载地址：http://rfwji.baihongyu.com/