题解 SP9199 【SPEED - Circular Track】

linyinuo2008 · 2021-01-23 23:02:06 · 题解

说实在的，这其实是SPOJ灰题中较为水的一道。

这题做起来比较简单，但是证明有一点麻烦。

我们一起来看一看。

1、题目大意

有两个人在分别以v1,v2的速度跑圈，问他们一共有几个相交的地点。

注意事项：

• 速度可能为负，因此要考虑是相遇还是追击，然后进行运算。

• 在求出相遇地点后还要进行一次绝对值。

2、解题思路

我们设总路程为1，分两种情况讨论。

1. 相遇

此时我们求出v1,v2的最小公倍数，然后也就是说跑这么多圈是一个周期（因为一圈是1嘛），然后求出这一个循环中两个人的相遇次数，也就是他们跑的圈数相加（因为每个人跑一圈都能与对方相遇一次）。

2. 追击

其中思路与相遇一样，但是追上次数为两人跑的圈数相减，因为快的每追上慢的一次，就多跑一圈。

最小公倍数求法：

最小公倍数=两数乘积 \div 两数最大公约数

3、代码

贴上代码：

#include <iostream>
#include <cmath>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,max(a,b)%min(a,b)); 
}
int main()
{
    int va,vb,i,t,na,nb,meet;
    cin>>t;
    for(i=1;i<=t;i++)
    {
        cin>>va>>vb;
        na=abs(va);
        nb=abs(vb);
        int num=na*nb/gcd(na,nb);
        if(va*vb>0)
        {
            meet=num/na-num/nb;
        }
        else if(va*vb<=0)
        {
            meet=num/na+num/nb;
        }
        cout<<abs(meet)<<endl;
    }   
    return 0;
} 

管理员大大求通过！

若有错误，欢迎指出！