题目大意:
给出两个数的GCDGCD和LCMLCM,求这两个数的最小差值。 IuputIuput6 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#include #include 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; //判断是否成立 }}