| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 104278 | Accepted: 20356 |
Description
Input
Output
Sample Input
1 2 3 4 5
Sample Output
4
题解：设t次跳跃后想遇，我们可以列出如下式子(x + mt) % L = (y + nt) % L 然后通过化简我们可以得到如下方程 (n-m)*t+k*L = (x-y).然后我们发现这个式子就是扩展欧几
里德，如果gcd(n-m,L)|(x-y)那么此式子有解，如果有解的话 设当前解为 X0，那么式子ax+by=c的通解为 {X0*c/gcd(a,b)+k*b/gcd(a,b)}(k属于整数)。此题的最小
正整数解为 mod =b/gcd(a,b) t=t*(x-y)/gcd(n-m,L); t = (t%mod+mod)%mod.
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; LL extend_gcd(LL a,LL b,LL &x,LL &y){ if(!b){ x=1,y = 0; return a; }else{ LL x1,y1; LL d = extend_gcd(b,a%b,x1,y1); x = y1; y = x1 - a/b*y1; return d; } } int main() { LL x,y,m,n,L,t,k; scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L); LL d = extend_gcd(n-m,L,t,k); if((x-y)%d!=0){ printf("Impossible\n"); } else{ t = t*((x-y)/d); LL mod = L/d; printf("%lld\n",(t%mod+mod)%mod); } return 0; }
原文：http://www.cnblogs.com/liyinggang/p/5528283.html