首页 > 其他 > 详细

uva 10627 - Infinite Race(数论)

时间:2014-07-08 17:33:51      阅读:345      评论:0      收藏:0      [点我收藏+]

题目链接: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;
}

uva 10627 - Infinite Race(数论),布布扣,bubuko.com

uva 10627 - Infinite Race(数论)

原文:http://blog.csdn.net/keshuai19940722/article/details/37508157

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!