HDU 5584 LCM Walk(数学)

题目链接

Source:2015ACM/ICPC亚洲区上海站

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

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 数学