https://vjudge.net/problem/HDU-5584
题意:(x,y)可以走到(x+lcm(x,y),y),或(x,y+lcm(x,y))
给定终点(ex,ey),问从起点到终点走了多少步?
解:
先按照题意模拟:
设d=gcd(x,y),则再设x=md,y=nd
因为lcm(x,y)=x*y/gcd(x,y)=md*nd/d=mnd
所以(x,y)可以走到(x+mnd,y)或(x,y+mnd)
设到达的坐标为(nx,ny)
先假设(nx,ny)=(x+mnd,y)
因为x=md,y=nd
也就是说nx=x+x*n ,ny=nd
x(1+n)=nx --->x=nx/(1+n)
n=ny/d
也就是说x=nx/(1+ny/d)
这样做,我们发现,从x->nx,变成了从nx->x的倒推关系
而我们恰恰只知道终点而不知道起点
我们只需要将这个倒推执行下去,直到不能执行为止,记录这个过程执行了多少步即可
但疑问还没有完全解决,如果他走到(x,y+lcm(x,y))呢?
我们可以看到:
(x+mnd,y)=(md+mnd,nd)=((1+n)*md,nd)
(x,y+mnd)=(md,nd+mnd)=(md,(1+m)*nd)
共同点是d=gcd(x,y)不变
又因为lcm(x,y)>=max(x,y)
所以只需要关注nx,ny哪个更大,我们视nx最大,则只走第一种
这样是不影响结果的,因为d是不变的
#include<bits/stdc++.h> #define IOS std::cin.tie(nullptr)->sync_with_stdio(false) typedef long long ll; int gcd(int a,int b) { return !b?a:gcd(b,a%b); } void solve() { int x,y;std::cin>>x>>y; int ans=1; int d=gcd(x,y); if(x<y)std::swap(x,y); while(x%(y+d)==0) { ans++; x=x/(y+d)*d; if(x<y)std::swap(x,y); } std::cout<<ans<<"\n"; } int main() { IOS; int t;std::cin>>t; for(int i=1;i<=t;i++) { std::cout<<"Case #"<<i<<": "; solve(); } return 0; }
标签:md,HDU,gcd,int,nd,5584,nx,LCM,mnd From: https://www.cnblogs.com/FeiShi/p/17073833.html