题目链接在这里:Problem - E - Codeforces
这道题跟Day1的A类似,都是给数加上了同一个数然后问gcd(lcm)问题。与上次一样,这道题也是要把两者相减。按照辗转相除法的思路,lcm(gcd)一定是两者之差的因数的倍数,我们要让lcm尽量的小,那就让两个数除以gcd之后的数尽量的小。所以我们枚举因数就行了
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=1e6+5; 5 LL a,b,c,anl,ans,lc; 6 LL d[MAX]; 7 int main(){ 8 freopen ("e.in","r",stdin); 9 freopen ("e.out","w",stdout); 10 LL i,j; 11 scanf("%lld%lld",&a,&b); 12 if (a>b) swap(a,b);c=b-a; 13 d[0]=0; 14 if (c==0){ 15 printf("0"); 16 return 0; 17 } 18 for (i=1;i*i<=c;i++) 19 if (c%i==0){ 20 d[++d[0]]=i; 21 d[++d[0]]=c/i; 22 } 23 anl=ans=5e18; 24 for (i=1;i<=d[0];i++){ 25 lc=((a-1)/d[i]+1)*((b-1)/d[i]+1)*d[i]; 26 if (anl>lc){ 27 anl=lc; 28 ans=((a-1)/d[i]+1)*d[i]-a; 29 } 30 else if (anl==lc){ 31 ans=min(ans,((a-1)/d[i]+1)*d[i]-a); 32 } 33 } 34 printf("%lld",ans); 35 return 0; 36 }