题意：
一个坐标系,每次可以从(x,y)走到(x,y+lcm(x,y))或者(x+lcm(x,y),y),给你一个坐标点(n,m),问有多少个点为起点可以到达该点
题解:
因为每次可以在x,y坐标中加上lcm,所以当前x,y中较小的哪一个肯定是x'或y'.
(x,y) 设gcd(x,y)=f x=m1f y=m2f
那么下一个点的坐标为(m1f+m1m2f+m2f)或者(m2f,m1m2f+m1f)
如果只走一步,那么只有一个点可以到达当前点,也就是说这是一一对应的关系,通过上式可以计算出前一个点坐标
#include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<bitset> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define PB push_back #define MP make_pair #define ll long long #define MS(a,b) memset(a,b,sizeof(a)) #define LL (rt<<1) #define RR (rt<<1|1) #define lson l,mid,LL #define rson mid+1,r,RR #define pii pair<int,int> #define pll pair<ll,ll> #define lb(x) (x&(-x)) void In(){freopen("in.in","r",stdin);} void Out(){freopen("out.out","w",stdout);} const int N=1e5+10; const int M=3e5+10; const int Mbit=1e6+10; const int inf=0x3f3f3f3f; const ll mod=1e9+7; const double pi=acos(-1); const double eps=1e-8; int main() { int T,kase=0,x,y; scanf("%d",&T); while(T--){ cin>>x>>y; printf("Case #%d: ",++kase); int cnt=0; while(1){ cnt++; if(x>y)swap(x,y); int f=__gcd(x,y); if(y/f%(1+x/f))break; y=y/(x/f+1); } printf("%d\n",cnt); } return 0; }