8
HDU 5584 LCM Walk（数学）
source link: https://arminli.com/hdu5584/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU 5584 LCM Walk（数学）
November 30, 2015
题意：当前的位置为(x, y)，设 l = LCM(x, y)，下一步可以到达(x+l, y)和(x, y+l)。已知终点的位置，问起点有多少种方案。
题解：若 x<y，那么上一个点必为(x, y′)，其中 y=y’+z, z=LCM(x, y’), z=k∗x .易知 GCD(x, y) = GCD(x, y’)，由于“两个数的积是这两个数 GCD 和 LCM 的积”得出 x*(y-z) = GCD(x, y)*z，化简得 z=xy/(x+GCD(x, y)).
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
//freopen("a.txt", "r", stdin);
int T;
cin >> T;
for(int k = 1; k <= T; k++){
long long a, b;
int ans = 1;
scanf("%lld %lld", &a, &b);
if(a > b)
swap(a, b);
while(1){
if(a <= 0) break;
if( a*b%(a+__gcd(a, b)) != 0)
break;
long long z = a*b/(a+__gcd(a, b));
if(z > b) break;
b -= z;
if(z%a != 0 || z%b != 0) break;
ans++;
if(a > b)
swap(a, b);
}
printf("Case #%d: %dn", k, ans);
}
return 0;
}
比赛时这题没做出来，原因是忘了“两个数的积是这两个数 GCD 和 LCM 的积”。。。:(
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK