傳送門

?題意

　　給出兩個正整數 a,b；

　　求解 k ，使得 LCM(a+k,b+k) 最小，如果有多個 k 使得 LCM() 最小，輸出最小的k；

?思路

時隔很久，又重新做這個題

溫故果然可以知新?

重要知識點

GCD(a,b)=GCD(a,b-a)=GCD(b,b-a) (b>a)

證明：

設GCD(a,b)=c

則a%c=0,b%c=0,(b-a)%c=0

所以GCD(a,b-a)=c

得GCD(a,b)=GCD(a,b-a)

?

gcd(a+k,b-a)肯定是(b-a)的因子

所以gcd(a+k,b+k)是(b-a)的因子，所以我們就枚舉(b-a)的因子(把因子稱為i）

使得 (a+k)為i的倍數

解出k,再判斷lcm是否符合最小

注意這里枚舉的i只是(a+k)和(b+k)的公約數，不一定是最大公約數gcd

兩者的公約數得到的是公倍數? 公倍數=a*b/公約數

如果是最大公約數的話兩者的公倍數一定是最小，

這里是沒有甄別是否是最大公約數而是簡單的得到公約數，然后得到的是公倍數

在所有的公倍數中，最小公倍數是最小的

所以并不影響解最小公倍數的答案

例如：

12 30

12 30

公約數i=1? ? k=1? ?a+k=13? ?b+k=31? ?公倍數=403
公約數i=2? ? k=2? ?a+k=14? ?b+k=32? ?公倍數=224
公約數i=3? ? k=3???a+k=15? ?b+k=33? ?公倍數=165
公約數i=6? ? k=6? ?a+k=18? ?b+k=36? ?公倍數=108
公約數i=9? ? k=6? ?a+k=18? ?b+k=36? ?公倍數=72
公約數i=18? k=6? ?a+k=18? ?b+k=36? ?公倍數=36

最小公約數36，此時k=6

?

另外一個思路可以求最大公約數 然后求最小公倍數，看HHHyacinth的博客

?代碼

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 ll a,b; 5 ll ans,lcm=0x3f3f3f3f3f3f3f3f; 6 int main() 7 { 8 cin>>a>>b; 9 ll d=abs(a-b); 10 for(ll i=1;i*i<=d;i++) 11 { 12 if(d%i==0)//枚舉b-a的因數i 13 { 14 ll k=(i-a%i)%i;//把a湊成i的倍數需要+k 15 ll t=(a+k)*(b+k)/i;// a*b/i得公倍數 16 if(t<lcm) 17 { 18 lcm=t; 19 ans=k; 20 } 21 22 ll ii=d/i; 23 k=(ii-a%ii)%ii; 24 t=(a+k)*(b+k)/ii; 25 if(t<lcm) 26 { 27 lcm=t; 28 ans=k; 29 } 30 } 31 } 32 cout<<ans<<endl; 33 } View Code

?

轉載于:https://www.cnblogs.com/MMMinoz/p/11240607.html

總結

以上是生活随笔為你收集整理的Codeforces Round #554 (Div. 2) C. Neko does Maths （数论 GCD(a,b) = GCD(a,b-a)）的全部內容，希望文章能夠幫你解決所遇到的問題。

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