hdu 5584 LCM Walk（gcd，逆推）

131 阅读 0 评论 87 点赞

我是靠谱客的博主友好月亮，这篇文章主要介绍hdu 5584 LCM Walk（gcd，逆推），现在分享给大家，希望可以做个参考。

hdu 5584 LCM Walk

分析：

终点为 $(e x, e y)$ , 令上一步为 $(x, y)$

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

又因为： $z > = m a x (x, y)$ , 故可以根据 $e x$ 和 $e y$ 的大小确定是哪一种情况
关键一步： $g c d (e x, e y) = = g c d (x, y)$ , 因为不管是哪一种情况，加上 $z$ ， $g c d$ 是不变的
故此，设 $e x < e y, (e x, e y) = (x, y + z)$

令 $g c d = d, e y = x y / d + y \to y = e y / (x / d + 1)$

重复最后一步到最后一步的逆推过程（再将倒数第二步当最后一步），便可推回起点
最后便是考虑逆推的结束条件：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#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;
}