Codeforces Round #554 (Div. 2)-C（gcd应用）

题目链接：https://codeforces.com/contest/1152/problem/C

题意：给定a，b(<1e9)。求使得lcm(a+k,b+k)最小的k，若有多个k，求最小的k。(k>=0）

思路：昨晚打cf因为某些原因，沉不下心来看题，本来是个上分的好机会QAQ。。。所以吸取教训，下次状态好的时候再打比赛。

　　   回到题目，首先给出gcd(a,b)=gcd(a,a-b)，这个很显然，所以有gcd(a+k,b+k)=gcd(a+k,a-b)。而lcm(a+k,b+k)=(a+k)*(b+k)/gcd(a+k,b+k)。所以我们可以枚举a-b的所有因子，通过该因子计算出k，进行判断。不过记得要用LL。

AC代码：

#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;

LL a,b,sub,ans,Min=0x3f3f3f3f3f3f3f3f;

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

void solve(LL x){
    LL k=(x-a%x)%x;
    LL aa=a+k,bb=b+k;
    LL tmp=aa/gcd(aa,bb)*bb;
    if(tmp<Min)
        Min=tmp,ans=k;
    if(tmp==Min&&k<ans)
        ans=k;
}

int main(){
    scanf("%lld%lld",&a,&b);
    if(a==b){
        printf("0
");
        return 0;
    }
    sub=abs(a-b);
    for(LL i=1;i*i<=sub;++i)
        if(sub%i==0){
            solve(i);
            solve(sub/i);
        }
    printf("%lld
",ans);
    return 0;
}