input
T 1<=T<=1000
x y
output
有多少个起点可以走n(n>=0)步走到(x,y),只能从(x,y)走到(x,y+lcm(x,y))/(x+lcm(x,y),y)
标准解：从(x,y0)走到(x,y),则设x=ag,y0=bg,g=gcd(x,y0),有y=bg+abg=(a+1)bg,因为a,b互质,a,(a+1)互质,所以a和(a+1)b互质,所以若可以从(x,y0)走到(x,y),有gcd(x,y0)=gcd(x,y),然后将x和y中gcd(x,y)除去之后不断除以(x+1)即可
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm> using namespace std; typedef long long LL; //求最大公约数
LL gcd(LL a, LL b) { if(!b) return a; else return gcd(b,a%b); } int main()
{
int t,Case = ;
scanf("%d",&t);
while(t--)
{
LL ex,ey; //终点坐标 scanf("%lld%lld",&ex,&ey);
LL GCD = gcd(ex,ey);
ex/=GCD,ey /=GCD;
int ans = ;
while()
{
if(ey < ex) swap(ex,ey);
ans++;
if(ey % (ex+)) break;
ey /= (ex+);
} printf("Case #%d: %d\n",++Case,ans);
}
}
answer
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
#define MAX 100000
#define LL long long
int cas=,T,x,y,d[],dn;
void find(int x,int *d,int& dn)
{
dn=-;
int m=sqrt(x);
for(int i=;i<=m;i++) if(x%i==) d[++dn]=i;
for(int i=dn;i>=;i--) d[++dn]=x/d[i];
}
int gcd(int a,int b) { return b==?a:gcd(b,a%b); }
int main()
{
// freopen("in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&x,&y);
int step=,flag=;
while(flag&&x!=y)
{
flag=;
if(x>y) std::swap(x,y);
int g=gcd(x,y);
find(g,d,dn);
for(int i=dn;i>=;i--)
{
if(y%(d[i]+x)==)
{
int y1=y/(d[i]+x)*d[i];
if(gcd(x,y1)==d[i]) { y=y1;step++;flag=;break; }
}
}
}
printf("Case #%d: %d\n",cas++,step);
}
//printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
return ;
}
My Code