hdu5584 LCM Walk

本文主要是介绍hdu5584 LCM Walk，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5584
题意：
两个数 $(a,b)$，经过一次操作阔以变成(a+lcm,b)或(a,b+lcm)，现在给出(a,b)，问经过有限次的操作（阔以是0次），能变成(aa,bb)的(a,b)有多少种？

重现赛的时候，队友写的搜索，我一直在推，他写的搜索T了，我的样例还没写出来。。。然后又过了一会儿，他优化的记下，结果就过了。。。。。。

我发现这两个好像是相等的：
$$gcd(a,b)=gcd(a,b+lcm)$$
因为：
假如a=kx,b=ky
上面就是$$gcd(kx,ky)=gcd(kx,kxy)$$
很明显应该是相等的
假如说都gcd都等于d
因为lcm肯定是大于等于a,b的，所以假设给的aa,bb都是bb比较大，所以加的lcm都加在bb上

$aa=a$
$bb=b+lcm$

$aa=a$
$bb=b+\frac{ab}{d}$=$b\cdot (1+\frac{a}{d})$

所以：
$a=aa$
$b=\frac{bb}{1+\frac{a}{d}}$（要除得尽才行）

所以根据所给的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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---