题意：当前的位置为(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 的积”。。。:(