HOJ 5584 LCM Walk（GCD）

GCD
题目意思：
从 (x,y) 点出发，可以向上或向右走，每次走的距离为 LCM(x,y)，即移动后的坐标为 (x+LCM(x,y)，y) 或 (x,y+LCM(x,y))，
移动若干次后停止在 (ex,ey) 点，问有多少个点可以移动到点 (ex,ey)

本题要点：
1、加入当前的坐标是 (x1, y1), 那么下一个坐标的位置是 (x1 + lcm(x1, y1), y1) 或者 (x1, lcm(x1, y1) + y1),
记 k = gcd(x1, y1), 那么lcm(x1, y1) = kx1y1。 现在以第2个坐标为例子，
假设(x1, lcm(x1, y1) + y1) = (x, y)， x和 y， 较大的值是有 lcm 累加到的。
gcd(x1, lcm(x1, y1) + y1) = k * gcd(x1, y1 + + x1 * y1), 注意到 gcd(x1, y1 + x1 * y1) = 1，
从而 x / k = x1, y / k = y1 + x1 * y1。
2、解法： 由当前的坐标 (x, y), （假如x < y）递推 回去上一个坐标(x1, y1)的过程
k = gcd(x, y), x1 = x / k, y1 = (y / k) / (x1 + 1);

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int T, x, y, ans;  int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}void solve()
{
    ans = 1;if(x > y)swap(x, y);int k = gcd(x, y), x1 = x / k, Y = y / k, y1;while(Y % (x1 + 1) == 0){
    ++ans;y1 = Y / (x1 + 1);x = x1, y = y1;if(x > y)swap(x, y);k = gcd(x, y), x1 = x / k, Y = y / k;}printf("%d\n", ans);
}int main()
{
    scanf("%d", &T);for(int t = 1; t <= T; ++t){
    scanf("%d%d", &x, &y);printf("Case #%d: ", t);solve();}return 0;
}/* 3 6 10 6 8 2 8 *//* Case #1: 1 Case #2: 2 Case #3: 3 */