记录一个菜逼的成长。。
题目链接
题目大意： 从一个点(x,y)可以跳到(x+lcm,y)或(x,y+lcm) 给你一个点，问有几个点能够跳到这个点，包括当前点。
我们假设当前点为 (x,y) ,上一个跳到这个点的点为 (x′,y′) 首先 (x,y)<==>(x/gcd,y/gcd) ，先让两个数互质 那么他们的 lcm 为 xy 以下点的坐标都已互质 我们假设 (x′>y′),(x′,y′)−>(x′+lcm,y′)−>(x′y′+x′,y′)−>(x′(y′+1),y′)−>(x,y) 可以得到 x′(y′+1)=x,y′=y 所以 x′=xy+1,(x′,y′)=(x/y+1,y) 由当前步可以推到上一步，直接搜索即可
#include <bits/stdc++.h> using namespace std; int ans; void solve(int x,int y) { ans++; if(x < y)swap(x,y); if(x % (1+y) == 0)solve(x/(1+y),y); } int main() { int T,cas = 1;scanf("%d",&T); while(T--){ int x,y; ans = 0; scanf("%d%d",&x,&y); int g = __gcd(x,y); x /= g,y /= g; solve(x,y); printf("Case #%d: %d\n",cas++,ans); } return 0; }