Codeforces Round #554 (Div. 2) C 数论

https://codeforces.com/contest/1152/problem/C

题意

a和b,找到k,使得lcm(a+k,b+k)最小(a,b:1e9)

题解

设gcd=gcd(a+k,b+k)且\(a<b\),即(a+k)%gcd=0,(b+k)%gcd=0,(a+k)%gcd=(b+k)%gcd,a%gcd=b%gcd
移项得b%gcd-a%gcd=0,(b-a)%gcd=0
枚举b-a的因数即gcd,维护最小值

代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll a,b,ans,ansk,k,tp,x;

int main(){

    scanf("%lld%lld",&a,&b);

    if(a>b)swap(a,b);

    ans=a/__gcd(a,b)*b;

    ansk=0;

    for(ll i=1;i*i<=(b-a);i++){

       //cout<<i<<endl;

        if((b-a)%i)continue;

        x=i;

       if(a%x!=b%x)continue;

       if(a%x){

           k=x-a%x;

           tp=(a+k)/__gcd(a+k,b+k)*(b+k);

           if(tp<ans){

               ans=tp;ansk=k;

           }else if(tp==ans&&k<ansk){

               ansk=k;

           }

       }

       x=(b-a)/i;

       if(a%x!=b%x)continue;

       if(a%x){

           k=x-a%x;

           tp=(a+k)/__gcd(a+k,b+k)*(b+k);

           if(tp<ans){

               ans=tp;ansk=k;

           }else if(tp==ans&&k<ansk){

               ansk=k;

           }

       }

    }

    printf("%lld",ansk);

}

巴特西

Codeforces Round #554 (Div. 2) C 数论

题意

题解

代码

最新文章

热门文章