问题标题: 酷町堂:1576 跑步

0
0
已解决
王紫馨
王紫馨
高级守护
高级守护

1576   跑步

题目描述 Description

假设圆形跑道的长度为 L,出发点的位置为原点 0,顺时针方向为正方向。这样我们就得到了一条首尾相接的数轴。设小明的出发点坐标是 x,小白的出发点坐标是 y。小明一步能走 m 米,小白一步能走 n 米。现在请你来算一算,它们走了多少步以后才会碰面。

输入描述 Input Description

输入一行,输入 5 个整数x,y,m,n,L,其中 x≠y<2×10^​9,0 < m, 0<m,n<2×10^9, 0<L<2.1*10^9, 0<L<2.1×10^9​​ 。x 和 y 分别表示小明和小白出发的位置,m 和nn 分别表示小明和小白每一步走的步长,L 表示圆形跑道的长度。

输出描述 Output Description

输出一行,如果小明和小白永远不可能碰面,则输出Impossible,否则输出它们需要走多少步才会碰面。

样例输入 Sample Input

 

1 2 3 4 5

样例输出 Sample Output

 

4

 

题目网址:

http://judge.codingtang.com/problem/1576/

 

错误原因:??(是超时吗?)

错误程序:

#include <iostream>
using namespace std;

int main(){
    long long x,y,m,n,l,s=0;
    //x表示小明的出发坐标点 
    //y表示小白的出发坐标点
    //m表示小明走一步的米数 
    //n表示小白走一步的米数 
    //l表示环形跑道的总路程 
    //s表示碰面需要走的步数 
    cin>>x>>y>>m>>n>>l;
    if(m==n){
        cout<<'Impossible';
        return 0;
    } else{
        while(x!=y){
            x+=m;
            y+=n;
            if(x>=l)
                x-=l;
            if(y>=l)
                y-=l;
            s++;
            if(x==y){
                cout<<s;
                return 0;
            }
        }
        cout<<s;
    }
    return 0;
}

这段程序为什么错了?错在哪里?


0
已采纳
梁彦博
梁彦博
初级光能
初级光能

公式(y-x)/(m-n或n-m) 可以,但是这是编程题哦

0
0
0
阮俊雄
阮俊雄
新手光能
新手光能

大王老师说过,可以套公式(y-x)/(m-n或n-m)就可以求出步数。

求采纳

0
0
洪朝阳
洪朝阳
修练者
修练者

列一个线性同余方程 x + km ≡ y + kn (mod L)

转换一下:(m - n)k ≡ y - x (mod l)

就相当于解线性同余方程 ax≡c (mod b)

用扩展欧几里得求解

我要回答