把lcm写成 (a+n)*(b+n) / gcd(a+n,b+n).
因为gcd可以辗转相减，所以就成了gcd(abs(a-b),a+n),一个常量一个变量之间的gcd,我们可以直接把abs(a-b)的所有约数找出来，然后看a要有某个约数的话n至少是多少，更新答案即可。(因为1e9以下的数的最多的约数的级别是1e3)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define ll long long
using namespace std;
int A,B,C,N,d[2333],num;
ll ans=1ll<<62ll,w;
//int gcd(int x,int y){ return y?gcd(y,x%y):x;}
inline void solve(){
C=A-B;
for(int i=1;i*(ll)i<=C;i++) if(!(C%i)){
d[++num]=i;
if(i*(ll)i!=C) d[++num]=C/i;
}
// sort(d+1,d+num+1);
for(int i=1,now;i<=num;i++){
now=d[i]-A%d[i];
w=(A+now)*(ll)(B+now)/d[i];
if(w<ans||(w==ans&&now<N)) N=now,ans=w;
}
}
int main(){
freopen("lcm.in","r",stdin);
freopen("lcm.out","w",stdout);
scanf("%d%d",&A,&B);
if(A<B) swap(A,B);
if(A==B){ puts("1"); return 0;}
solve();
cout<<N<<endl;
return 0;
}
原文：https://www.cnblogs.com/JYYHH/p/9097149.html