UVA 10627 - Infinite Race

题意：一段跑道，A，B分别在两端，速度为u。v，两个人跑到还有一端立即回头，回头时间不计，问经过单位时间t。两人相遇几次

思路：追及相遇问题。这样计算：

1、迎面相遇次数：第N次迎面相遇，路程和 = 全程*(2N-1)

ans+=((u+v)t+l)/(2l)

2、追及相遇次数：第N次追上相遇，路程差 = 全程*(2N-1)

ans+=((u−v)t+l)/(2l)

3、比較麻烦的是要扣掉边界位置迎面和追及反复的次数

设r为两人到同一端点的最少时间。因此1、t=(2k+1)r

2、ur=k1l 3、vr=k2l

r为l/v和l/u的整数倍,既r为l/gcd(u,v)的整数倍

2式子变形，得到u/gcd(u,v)∗r/(l/gcd(u,v))=k1

因此r取最小的正数解, 得到r=l/gcd(u,v)

1式变形，得到k=(t−r)/(2r),将r带回得到k=(t∗gcd(u,v)+l)/(2l)

可是这样还不算完。因为ur和vr必须差一个奇数个的l。将r带入。得到

(l/gcd(u,v)−l/gcd(u,v))必须为奇数才有反复的情况出现，须要推断

所以最后反复情况为：

if ((u - v) / gcd(u, v) % 2)

ans -= (gcd(u, v) * t + l) / (2 * l)

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;long long l, u, v, t;long long gcd(long long a, long long b) {    if (!b) return a;    return gcd(b, a % b);}int main() {    while (~scanf("%lld%lld%lld%lld", &l, &u, &v, &t) && l) {	if (u == 0 && v == 0) {	    printf("0\n");	    continue;	}	if (u < v) swap(u, v);	long long ans = 0;	ans += ((u + v) * t + l) / (2 * l);	ans += ((u - v) * t + l) / (2 * l);	long long d = gcd(u, v);	if ((u - v) / d % 2)	    ans -= (d * t + l) / (2 * l);	printf("%lld\n", ans);    }    return 0;}