自由保温杯

文章
6
资源
0
加入时间
2年10月21天

C. Neko does Maths (gcd)

题目链接:哆啦A梦传送门题意:已知 a,b,找一个最小的k,使得(a+k) 与 (b+k)的最小公倍数尽可能的小。题解:假设a>b,那么gcd(a,b)=gcd(a-b,b)。证:设c=a-b,则gcd(a,b)=gcd(b+c,b)=gcd(b,c)=gcd(a-b,b)。即 gcd(a+k,b+k)=gcd(a-b,b+k)=c,最后我们就直接枚举(a-b)的因子,...