hdu 5584 LCM Walk（gcd，逆推）

hdu 5584 LCM Walk

分析：

• 终点为 $(ex,ey)$ , 令上一步为 $(x,y)$

  由倒数第二步到最后一步分为两种情况：$(x,y+z),(x+z,y)，z=lcm(x,y)$

  又因为：$z>=max(x,y)$ , 故可以根据 $ex$ 和 $ey$ 的大小确定是哪一种情况

• 关键一步：$gcd(ex,ey)==gcd(x,y)$ , 因为不管是哪一种情况，加上 $z$ ，$gcd$ 是不变的

• 故此，设 $ex<ey,(ex,ey)=(x,y+z)$

  令 $gcd=d,ey=xy/d+y\to y=ey/(x/d+1)$

  重复最后一步到最后一步的逆推过程（再将倒数第二步当最后一步），便可推回起点

• 最后便是考虑逆推的结束条件：

#include <bits/stdc++.h>
using namespace std;
inline int gcd(int a,int b) { return a%b==0 ?b:gcd(b,a%b); }
signed main()
{
int T,op=0;
scanf("%d",&T);
while(T--)
{
int x,y;
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
int d=gcd(x,y),cnt=1;
while(y%(x+d)==0)
{
cnt++;
y=y/(x/d+1);
if(x>y) swap(x,y);
d=gcd(x,y);
}
printf("Case #%d: %dn",++op,cnt);
}
return 0;
}

最后

以上就是友好月亮为你收集整理的hdu 5584 LCM Walk（gcd，逆推）的全部内容，希望文章能够帮你解决hdu 5584 LCM Walk（gcd，逆推）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。