【HDU - 5584】LCM Walk（数论）

这道题是为了记录一下这个差点被忘记，但是十分重要的数学结论：

gcd(X,Y) = gcd(X, Y - K*X)  = gcd(X - K * Y,  Y)

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
//gcd(x, y) = gcd(x, y - k *x) = gcd(x - k * y, y)
//其实这个就是欧几里得算法求GCD的主要思想
typedef long long ll;
ll gcd(ll n, ll m)
{
if(n % m == 0) return m;
return gcd(m, n % m);
}
int main()
{
int CASE;
scanf("%d", &CASE);
for(int cas = 1; cas <= CASE; ++cas)
{
ll x, y;
scanf("%lld%lld", &x, &y);
int ans = 1;
while(x != y)
{
if(x > y) swap(x, y);
ll pre = y;
ll g = gcd(x, y);
y = y / (1 + x / g);
if(y + x * y / gcd(x, y) != pre) break;
ans += 1;
}
printf("Case #%d: %dn", cas, ans);
}
return 0;
}

最后

以上就是贪玩发夹最近收集整理的关于【HDU - 5584】LCM Walk（数论）的全部内容，更多相关【HDU内容请搜索靠谱客的其他文章。