正題

---

大意

給出某對數(shù)a,b的gcd和lcm，然后求b-a的最小值

---

解題思路

我們定義A為gcd(a,b)gcd(a,b)，B為lcm(a.b)lcm(a.b)
首先我們拿出推lcm的公式

B=ab/AB=ab/A
然后移項得
ab=AB(A≤a,b≤B)ab=AB(A≤a,b≤B)
之后我們就可以枚舉了。首先因為只有 AA的倍數(shù)gcd(a,b)gcd(a,b)才可能等于 AA，所以我們枚舉的時候可以一次增加AA，然后就可以了。

---

代碼

#include<cstdio> #include<algorithm> #define minx(x,y) x>y:y?x using namespace std; long long A,B,C,mins; int main() {scanf("%lld%lld",&A,&B);C=A*B;mins=1e18;for (long long i=A;i<=B;i+=A){long long w=C/i;if (i>w) break; if (i*w==B*A&&__gcd(i,w)==A){mins=min(mins,abs(C/i-i));}}printf("%lld",mins); }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。