HDU 5584 青蛙跳跳跳 小小的数论题

          题目大意：设青蛙的起点是在（x，y）上，每一次青蛙可以跳到（x，y + z）或者（x + z，y）上面去（其中z = LCM（x ，y），LCM是最小公倍数的意思）青蛙在跳了很多步之后停在了（a，b）点处，现在告诉你（a，b），让你求可能的起始点的数量

          我没有发现这个题目的一个性质。。用的暴力搜索。果断超时。。。

          设 k = GCD（x , y），x = a * k , y = b * k ，所以LCM（x , y）= a * b * k，所以接下来跳到的点是 ( a * k + a * b * k , b * k ）或者是 ( a * k , b * k + a * b * k)，无妨假设是第二种情况 ，因此第二种情况就是 ( a * k , ( 1 + a ) * b * k），也就是说，终点可以表示成这样的情况，我们也能够发现，a 和 b 是互质的，同时 a 和 1 + a 也是互质的，因此终点的GCD依然是 k，我们可以把终点的 GCD求出来，可以把 a 求出来，再判断 y 能不能被 ( 1 + a）* k整除掉，假若可以整除，那么这个情况是可以还有一个起点的，假若不能，则停止迭代，以下是代码：

#include<cstdio>
using namespace std;
int t,x,y,k,ans=1;
int gcd(int a,int b){return (a%b==0)?b:gcd(b,a%b);}
int main(){
scanf("%d",&t);
for(int i=1;i<=t;++i){
scanf("%d%d",&x,&y);
if(x>y)
x^=y^=x^=y;
k=gcd(y,x);
while(y%(x+k)==0){
++ans;
y=y/(x/k+1);
if(x>y)
x^=y^=x^=y;
k=gcd(y,x);
}
printf("Case #%d: %dn",i,ans);
ans=1;
}
return 0;
}

最后

以上就是纯真大地为你收集整理的HDU 5584 青蛙跳跳跳 小小的数论题的全部内容，希望文章能够帮你解决HDU 5584 青蛙跳跳跳 小小的数论题所遇到的程序开发问题。

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