本文主要是介绍hdu5584 LCM Walk，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 题目链接：
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5584
题意：
两个数 ( a , b ) (a,b) (a,b)，经过一次操作阔以变成(a+lcm,b)或(a,b+lcm)，现在给出(a,b)，问经过有限次的操作（阔以是0次），能变成(aa,bb)的(a,b)有多少种？
重现赛的时候，队友写的搜索，我一直在推，他写的搜索T了，我的样例还没写出来。。。然后又过了一会儿，他优化的记下，结果就过了。。。。。。
我发现这两个好像是相等的：
g c d ( a , b ) = g c d ( a , b + l c m ) gcd(a,b)=gcd(a,b+lcm) gcd(a,b)=gcd(a,b+lcm)
因为：
假如a=kx,b=ky
上面就是 g c d ( k x , k y ) = g c d ( k x , k x y ) gcd(kx,ky)=gcd(kx,kxy) gcd(kx,ky)=gcd(kx,kxy)
很明显应该是相等的
假如说都gcd都等于d
因为lcm肯定是大于等于a,b的，所以假设给的aa,bb都是bb比较大，所以加的lcm都加在bb上
a a = a aa=a aa=a
b b = b + l c m bb=b+lcm bb=b+lcm
a a = a aa=a aa=a
b b = b + a b d bb=b+\frac{ab}{d} bb=b+dab= b ⋅ ( 1 + a d ) b\cdot (1+\frac{a}{d}) b⋅(1+da)
所以：
a = a a a=aa a=aa
b = b b 1 + a d b=\frac{bb}{1+\frac{a}{d}} b=1+dabb（要除得尽才行）
所以根据所给的aa,bb就能找出上一次的a,b了
但是(6,8)这个样例就让把我hack了，明明只到(2,6)就阔以了啊，结果算到了(2,3)，但是我发现(2,3)的gcd不等于原来的，到这里就阔以停止了
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
LL d;
LL dfs(LL x,LL y)
{if(x>y)swap(x,y);LL a1=-1,b1=-1;LL sum=0;if(y%(1+x/d)==0)//要除得尽才行 {a1=x,b1=y/(1+x/d);if(__gcd(a1,b1)==d){sum+=dfs(a1,b1);sum++;//这条路径上的每个点都是一种情况 }}if(__gcd(a1,b1)!=d)return 1;//如果gcd不等于原来的就直接停止了 else return sum;
}
int main()
{int T;cin>>T;for(int Case=1;Case<=T;Case++){LL x,y;cin>>x>>y;d=__gcd(x,y);cout<<"Case #"<<Case<<": "<<dfs(x,y)<<endl;}
}
这篇关于hdu5584 LCM Walk的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
