本文共 1170 字，大约阅读时间需要 3 分钟。

一.题目链接

二.题目大意：

frog 从 (sx, sy) 出发.

每次可以从 (x, y) 走到 (x + lcm(x, y), y) 或 (x, y + lcm(x, y)).

现给出终点 (ex, ey)，求可能起点的个数.

三.分析：

结论：

路径唯一

证明：

因此：如果 x > y，则   ; x < y 时同理.

所以当前的点唯一确定上一步的点.

所以路径唯一.

由上述证明可知上一个点唯一，现逆推上一个点的坐标.

假设当前点为 (x, y)，设 k == gcd(x, y)

则 x == nk, y == mk, 其中，gcd(n, m) == 1.

则 lcm(x, y) == xy / gcd == nk * mk / k == nmk.

若下一步增加 x，则坐标变为 (x + lcm(x, y), y)

即 (nk + nmk, mk) == ((m + 1)nk, mk)，其中，gcd((m + 1)n, m) == 1.

所以，gcd(x + lcm(x, y), y) == gcd(x, y) == k.

所以

若 x > y，设 x == (m + 1)nk, y == mk

则，上一个点的坐标为

(nk, mk)

== (x / (m + 1), y)

== (x / (y / k + 1), y)

现讨论结束条件

若存在前一个点 (nk, mk)，则当前点为 ((m + 1)nk, mk) == ((mk + k)n, mk) == ((y + k)n, mk)

所以当前 x 应为 y + k 的整数倍.

四.代码实现：

#include 
   
    using namespace std;int gcd(int a, int b){    return b ? gcd(b, a % b) : a;}int main(){    int T;    scanf("%d", &T);    for(int ca = 1; ca <= T; ++ca)    {        int x, y, p;        scanf("%d %d", &x, &y);        if(x < y)   swap(x, y);        int cnt = 1, k = gcd(x, y);        while(x % (y + k) == 0)        {            cnt++;            x = x / (y / k + 1);            if(x < y)   swap(x, y);        }        printf("Case #%d: %d\n", ca, cnt);    }    return 0;}