題目大意：
給出兩個數的GCDGCD和LCMLCM，求這兩個數的最小差值。
IuputIuput

6 36

OutputOutput

6

---

思路：
一道數論題。
我們設這兩個數分別為xx和yy且x≤yx≤y，g=gcd(x,y)g=gcd(x,y)，l=lcm(x,y)l=lcm(x,y)，那么必然有

l=xg×yg×gl=xg×yg×g
即l=xygg2l=xygg2
約分得l=xygl=xyg
移項得lg=xylg=xy
由于gg必然是xx的因數，所以可以設k=gxk=gx,則x=kgx=kg帶入上式，得lg=kgylg=kgy,
根據等式的性質，得lg=kglklg=kglk
那么只要枚舉kk,我們就可以求出正確答案了。

---

代碼：

#include <cstdio> #include <iostream> #include <algorithm> using namespace std;long long g,l,x,y,z,ans;int main() {scanf("%d%d",&g,&l);for (long long i=1;1;i++){if (g*i>l/i) return printf("%d\n",ans)&0; //當a>b時，程序結束if (l%i) continue; //l不能整除i（即上文所述k）x=g*i;y=l/i; //求出兩數的值z=__gcd(x,y); if (z==g&&x*y==g*l) ans=l/i-i*g; //判斷是否成立} }

轉載于:https://www.cnblogs.com/hello-tomorrow/p/9313038.html

總結

以上是生活随笔為你收集整理的GCD与LCM【数论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。