題目描述：
在一個長度為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
西月弦 閱讀(473)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告 、
經典題目