HDU - 5584-LCM Walk (gcd应用)

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5584

题目大意：
在一个无限大的棋盘上，若起点为$(x,y)$，则人每次可以选择向上走或者向右走，长度为$lcm(x,y)$， 即走到$(x+lcm(x,y),y)$或者$(x,y+lcm(x,y))$,给定一个终点的坐标，求可以走到此处的合法起点有多少个

分析：

$$lcm(x,y) = \frac{x*y}{gcd(x,y)}$$

由于$x = pgcd(x,y) , y = qgcd(x,y) $ 所以$lcm(x,y) = p*q*gcd(x,y)$，每次加上一个$gcd(x,y)$后，两坐标的gcd值不改变

根据此性质，我们可以列出方程，若向右走，则有

$$\left\{ \begin{array}{c} x +lcm(x,y) = a \\ y= b \\ \end{array} \right.$$

代入可得

\begin{align*}x+x*b/gcd(x,y) =a \Longleftrightarrow x = \frac{a}{1+\frac{b}{gcd(x,y)}}\end{align*}

由于之前推得$gcd(x,y)=gcd(a,b)$
已知落点为$(a,b)$，可以推得两种之前一步的位置，当$gcd(x,y)\not= gcd(a,b)$ 或者$x<1 $或$y<1$时，即为退出条件，因此直接dfs即可

类似gcd，由于每一次$x$或者$y$都会减小为之前的$\frac{1}{1+\frac{b}{gcd(x,y)}}\leq \frac{1}{2}$，所以这至多是一个指数级的递归深度，况且实际上远小于$log_2{n}$，所以可以放心dfs

代码：

#include<bits/stdc++.h>

using namespace std;

int x,y,g;

int dfs(int x,int y)
{
    if (x<=0||y<=0||__gcd(x,y)!=g)
        return 0;
    int res = 1;
    int a = y/g+1 , b = x/g+1;
    if (x%a==0)
        res += dfs(x/a,y);
    if (y%b==0)
        res += dfs(x,y/b);
    return res;
}

int main()
{
    int T,t=1;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&x,&y);
        g = __gcd(x,y);
        printf("Case #%d: %d\n",t++,dfs(x,y));
    }
    return 0;
}