UMR 現(xiàn)在手里有 n 張康納的表情，最上面一張是瑪吉呀巴庫乃。現(xiàn)在 UMR 如果每次把最上面的 m 張牌移到最下面而不改變他們的順序及朝向，那么至少經(jīng)過多少次移動(dòng)瑪吉呀巴庫乃才會(huì)又出現(xiàn)在最上面呢？

Input

多組輸入。

對(duì)于每組數(shù)據(jù)，輸入以空格分隔的兩個(gè)整數(shù) n 和 m (1 <= n, m <= 10^9)。

Output

對(duì)于每組數(shù)據(jù)，輸出一個(gè)整數(shù)，表示至少移動(dòng)的次數(shù)。

Sample Input

54 12

Sample Output

9

解題思路：當(dāng)時(shí)這道題在組隊(duì)賽中是我看的，碰巧之前有一個(gè)同學(xué)問過我一個(gè)約瑟夫環(huán)的問題我就把這道題當(dāng)做了類似約瑟夫環(huán)的問題，用隊(duì)列寫了一發(fā)，時(shí)間超限，看了看數(shù)據(jù)量10^9，覺得這可能是一道找規(guī)律的題目，于是想了想，找到了這樣一個(gè)規(guī)律。想讓這一張紙牌再次出現(xiàn)在最上面我們需要移動(dòng)的總的牌數(shù)一定是紙牌數(shù)的倍數(shù)，也一定是每次移動(dòng)牌數(shù)的倍數(shù)，于是求兩者的最小公倍數(shù)就一定是最少的移動(dòng)總牌數(shù)，再用移動(dòng)的總牌數(shù)除以每次移動(dòng)的牌數(shù)，就可以得到最少的移動(dòng)次數(shù)。

這里需要用到一個(gè)公式：lcm(n,m)*gcd(n,m)=n*m

所以 lcm(n,m) = (n*m)/gcd(n,m)
counts = lcm(n,m)/m
最后整理得到
counts = n/gcd(n,m)

1 #include<algorithm> 2 #include<cstdio> 3 using namespace std; 4 int main() 5 { 6 int n,m; 7 while(~scanf("%d%d",&n,&m)) 8 printf("%d\n", m/__gcd(n,m)); 9 return 0; 10 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/wkfvawl/p/9350662.html

總結(jié)

以上是生活随笔為你收集整理的康纳的表情包（思维）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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