首页 > 代码库 > uva 10627 - Infinite Race(数论)

uva 10627 - Infinite Race(数论)

题目链接:uva 10627 - Infinite Race

题目大意:一段路,两个人在这条路上来回走,求相遇次数

解题思路:相遇有两种,一种是追击,一种是相对

追击:t?(u?v)=(2?k+1)?L
相对:t?(u+v)=(2?k+1)?L

但是有一种特殊情况,就是在边界相遇的时候,会被考虑两次,所以要减掉一次。
那么如何考虑边界相遇的时间:找到一篇详解

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;

ll gcd (ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

int main () {
    ll L, u, v, t;
    while (scanf("%lld%lld%lld%lld", &L, &u, &v, &t) == 4 && L + u + v + t) {

        if (u == 0 && v == 0) {
            printf("0\n");
            continue;
        }

        ll ans = 0;
        if (u < v)
            swap(u, v);

        ans += (t * (u+v) + L) / (2*L);
        ans += (t * (u-v) + L) / (2*L);

        ll d = gcd(u, v);

        if ((u-v) / d % 2)
            ans -= (d * t + L) / (2*L);
        printf("%lld\n", ans);
    }
    return 0;
}