题目描述：
在一个长度为L的环上的有两点x,y。点A的速度是m，点B的速度是n。请问二者相遇的最小整数时间。保证m,n,x,y,l都是int型正整数。
吐槽：
1. 虽然题目说了x!=y，但是没有说x,y<L ??? 所以还是加了一堆判断...... 特判了速度/坐标相等的情况......
2. 大早上来刷水题 ?? 拖出去打..... 不过好像还是很经典的说....
3. 听说长春邀请赛卖的那套书里面(基础算法)中图论那章是我写的.... 擦擦擦擦... 丢人了..
算法分析：
不考虑“吐槽1”的情况，那么两个点就变成了一个追击问题.... 判断一下需要追击的距离是 abs(x-y) 还是 L-abs(x-y) ,速度差是 v=abs(m-n)
有了需要追击的距离差 dis 和速度差 v，那么需要解的就是 v*x = dis (mod L) 的最小整数解
大家去看算法导论或者具体数学去吧....
说一下简单思路：
1. 如果 dis = 0 (mod gcd(v,L)) 那么有解，反之无解。
2. 0 mod m , n mod m , 2*n mod m ... k*n mod m 的循环节是 m/gcd(m,n)
3. v*x = gcd(L,v) (mod L) 可以用拓展欧几里得算法解， 解是 X，那么x0 = X*(dis/gcd(L,v)) 一定是一个可行解。
4. 根据(2)可得，X'是原方程的解当且仅当 x0 + i*m/gcd(m,n) 所以最小整数解就是 X mod (m/gcd(m,n)) 了....
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 using namespace std;
5 typedef long long ll;
6 char *fail = "Impossible";
7 ll exgcd(ll &x,ll &y,ll a,ll b){
8 if(!b) {
9 x = 1, y = 0; return a;
10 }
11 ll d = exgcd(x,y,b,a%b);
12 ll t = y; y = x - a/b*y; x = t;
13 return d;
14 }
15 ll cal (ll v,ll l,ll dis){
16 // cout<<v<<" "<<l<<" "<<dis<<endl;
17 if(dis == 0 || dis == l) return 0;
18 ll x,y;
19 ll d = exgcd(x,y,v,l);
20 // cout<<x<<" "<<y<<endl;
21 if(dis % d) return -1;
22 x = (x + l) % l;
23 x = x * (dis/d) % l;
24 return x % (l/d);
25 }
26 int main(){
27 int dis,v,a,b,l,x,y;
28 while(cin >> x >> y>> a >> b >> l){
29 v = abs(a-b);
30 x %= l, y %=l;
31 if(a > b) {
32 if(y > x) dis = y-x;
33 else dis = l - (x-y);
34 }
35 else if( a < b){
36 if(x > y) dis = x - y;
37 else dis = l - (y-x);
38 }
39 else if(x == y){ puts("0"); continue;}
40 else { puts(fail); continue; }
41 ll __ans = cal (v,l,dis);
42 if(__ans == -1) puts(fail);
43 else cout<<__ans<<endl;
44 }
45 }
46
posted on 2012-05-04 11:20
西月弦 阅读(443)
评论(0) 编辑 收藏 引用 所属分类:
解题报告 、
经典题目