题意：规定LCM走法：假设现在在(x,y)点，则可以走到(x,y+lcm(x,y))或(x+lcm(x,y),y)两个点。给你一个点，问能有多少个起点走到(x,y)。

比赛的时候看到1e9根本不敢搜，后来还是学长想出了做法。

假设能从(x,y')走到(x,y),那么y'一定是y的约数，暴力枚举所有的约数判断能否走到(x,y)就好了。复杂度O(sqrt(n)*log(n)*log(n))。

#include<cstdio>
int t,x,y,ans;
int gcd(int a,int b)
{
	if (b==0) return a;
	else return gcd(b,a%b);
}
long long lcm(int a,int b)
{
	return (long long )a*b/gcd(a,b);
}
void dfs(int x,int y)
{
	ans++;
	for (int i=1;i*i<=x;i++)
		if (x%i==0)
		{
			int j=x/i;
			if (i+lcm(i,y)==x) dfs(i,y);
			if (j!=i&&j+lcm(j,y)==x) dfs(j,y);
		}
	for (int i=1;i*i<=y;i++)
		if (y%i==0)
		{
			int j=y/i;
			if (i+lcm(x,i)==y) dfs(x,i);
			if (j!=i&&j+lcm(x,j)==y) dfs(x,j);
		}
}
int main()
{
	scanf("%d",&t);
	for (int cas=1;cas<=t;cas++)
	{
		scanf("%d%d",&x,&y);
		ans=0;
		dfs(x,y);
		printf("Case #%d: %d\n",cas,ans);
	}
}