图片手机网站建设/媒体公关

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

题目大意：给你一个点(x，y),你每次可以向前走z，z为x和y的最小公倍数，即走到(x+z,y)或者(x,y+z)，现在给你一个点(x,y)问你可能的出发点有几个（包括自己）

解题思路：
因为z=lcm(x,y)
所以z>=x &&z>=y
所以假设在点（x,y）时，大的点一定是上一步加上z的点。

假设y>x,那么y=y1+z,z=lcm(y1,x) 假设z=k*x

那么 (y1*x)/(gcd(y1,x))=k*x
y1/(gcd(y1,x))=k;

注意到gcd(x,y)=gcd(x,y-k*x) k为整数

gcd(y1,x)=gcd(y-kx,x)=gcd(y,x)

y1=k*gcd(y,x)

y-z=z/xgcd(y,x)
yx-zx=zgcd(x,y)

z=(y*x)/(x+gcd(x,y))
既然求出了z那么剩下的就好做了

我并不是这么AC的，我当时不知道gcd(y1,x)=gcd(y-kx,x)=gcd(y,x)，所以我在这里枚举了k的值，注意到10亿的因子只有100个，所以也没超时。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <functional>
#define RI(N) scanf("%d",&(N))
#define RII(N,M) scanf("%d %d",&(N),&(M))
#define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define mem(a) memset((a),0,sizeof(a))
using namespace std;
const int inf=1e9;
const int inf1=-1*1e9;
double EPS=1e-10;
typedef long long LL;
vector<LL> p;
LL cal(LL x,LL y)
{return x*y/__gcd(x,y);
}
void find_yinshu(LL x)
{p.clear();LL t=floor(sqrt(x)+0.5);for(LL i=1; i<=t; i++){if(x%i==0){p.push_back(i);if(i*i!=x){p.push_back(x/i);}}}sort(p.begin(),p.end());
}
int main()
{int T,cas=1;RI(T);while(T--){LL x,y;scanf("%I64d %I64d",&x,&y);int ans=1;while(1){if(x<y) swap(x,y);//cout<<x<<"    "<<y<<endl;bool mark=false;if(x%y==0){LL d=x/y;while(d%2==0){d/=2;ans++;}break;}else{find_yinshu(x);for(int i=0;i<p.size();i++){if(x-p[i]*y<=0) break;if((p[i]*y)%(x-p[i]*y)==0){LL x1=x-p[i]*y;if(x1+cal(x1,y)==x){x=x1;mark=true;break;}}}if(mark) ans++;else break;}}printf("Case #%d: %d\n",cas++,ans);}return 0;
}