点此看题
我一开始拿到这道题真没有什么思路，我们首先来研究一下这个特殊的走法：每次向右或者下走 l c m \tt lcm lcm步，那么对于一个点 ( x , y ) (x,y) (x,y)，它的前驱一定是固定的，因为如果 x > y x>y x>y那么他就是从 ( x 1 , y ) (x_1,y) (x1,y)走到的（ l c m \tt lcm lcm一定大于等于所有数），否则是从 ( x , y 1 ) (x,y_1) (x,y1)走过来的。
设当前点是 ( x , y ) (x,y) (x,y)，设 x = n k , y = m k x=nk,y=mk x=nk,y=mk（ n , m n,m n,m互质），那么到达的点就是 ( n ( m + 1 ) k , m k ) (n(m+1)k,mk) (n(m+1)k,mk)或 ( n k , m ( n + 1 ) k ) (nk,m(n+1)k) (nk,m(n+1)k)， m m m和 n ( m + 1 ) n(m+1) n(m+1)互质， n n n和 ( n + 1 ) m (n+1)m (n+1)m互质，所以后继的 k k k还是不变的。
结合以上两点，我们可以知道如果我们从终点往回跑，那么这样的路径是固定的。然后因为我们知道 k k k，所以一个点的前驱就很容易算了。
#include <cstdio> #include <iostream> using namespace std; int read() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int Case,T,x,y,k,ans; int gcd(int a,int b) { return !b?a:gcd(b,a%b); } int main() { T=read(); while(T--) { x=read();y=read(); if(x<y) swap(x,y); k=gcd(x,y);ans=1; while(x%(y+k)==0) { ans++; x=x/(y+k)*k; if(x<y) swap(x,y); } printf("Case #%d: %d\n",++Case,ans); } }