找到一个k使得a+k与b+k的最大公倍数lcm最小
欧几里得算法：gcd(a,b) = gcd(b,a mod b)。
gcd是b-a的除数。 让我们迭代b-a的所有除数q。 这也意味着a（modq）= b（modq）。 如果a（modq）= 0，我们可以使用k = 0。
否则，相应的k应为q-a（modq）。 最后，我们需要检查lcm（a + k，b + k）的值是否是迄今为止找到的最小值。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a,b; int main() { ios::sync_with_stdio(false); cin>>a>>b; ll d=abs(a-b); ll ans=0; ll h=a/__gcd(a,b)*b; if(b==a){ cout<<"0"<<endl; return 0; } else{ ll k,v; for(int i=1;i*i<=d;i++){ if(d % i != 0) continue; k=i; k=(k-(a%k))%k;//保证k为满足当前情况的最小值 v= (a+k)/__gcd(a+k,b+k)*(b+k); if(v<h){ h=v; ans=k; } if(v==h) ans=min(ans,k); k=d/i; k=(k-(a%k))%k; v= (a+k)/__gcd(a+k,b+k)*(b+k); if(v<h){ h=v; ans=k; } if(v==h) ans=min(ans,k); } cout<<ans<<endl; } return 0; }
codeforce 1152C. Neko does Maths（欧几里得算法）
原文：https://www.cnblogs.com/Fy1999/p/10776343.html