是不是样例有问题？按题目的算法，就是追击问题吧，右边的与左边的差一个单位，而速度也差一个单位，正好一天可以赶上来啊！为什么要4天？

是不是题目出问题，是应该往右走的？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

好久了, 终于AC了!! 庆祝!

求解线性模方程, 数据有些大, 应用long long存储

还有就是注意正副的问题, 已经取最小的天数.

var

x,y,m,n,l:integer;

a,b,c,t:real;

begin

read(x,y,m,n,l);

b:=x-y;

c:=b*l/360;

t:=c/(m-n);

if t>1000000

then

writeln('impossible');

writeln(t);

end.

显然,原题可化为求P*V MOD L=K 中 Pmin(P>=0)(V为速度差，K为两人的距离)(不妨定义Pmin=F(V,L,K))

设P*V-Q*L=K(Q>=0)则求Pmin相当于求Qmin

又Q*L=P*V-K得Q*L MOD V=(-K) MOD V，

于是F(V,L,K)=(Qmin*L+K) DIV V=(F(L MOD V,V,(-K)MOD V)*L+K)DIV V;

边界条件自己找吧

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

怎么回事？？？？

我RP--，Cheat的……

扩展欧几里德算法?

有没有大牛能讲得我们普通人都懂啊？

如果没有的话，暂时放弃了～～～5555555

本人看不懂扩展欧几里德算法,于是自己编了一个自己推算的程序

a*k=b( mod c)

---|-->a*k=b+c*l---|-->c*l=-b+a*k---|->c*l=-b ( mod a)

把原方程转化为规模较小的方程，递归求解。。。。

边界条件：b mod a=0 时k= b div a;a=0时无解

。。。。。。int64卡了我好久

首先将题目转化为at-kl=b的情况，这里a和k均是未知量，

那么方程无解的情况就是r=gcd(t,l)不能整除b，（即b%r!=0)

如果可以那么分别用t/r,l/r,b/r来代替t, l ,b,

然后利用个扩展欧几里德算法得到c,d使得ct+dl=1,

如果c

还有一种无解情况是两个速度都为偶数，而距离差为奇数。

首先求出相对速度和距离,再和L一起列出vx+ly=c(C是相对距离)

然后是用吴文虎教授黑书上62页的欧几里德推广算法求出一个解.

再求出X的周期,求出X的最小整数值即可.

数据太大了，必须用高效算法。

那些普通的算法不够的。

标称的难度才那么点点，太迷惑人了。

直接说扩展辗转相除法就好了。

根据题意，即有(m-n)*A-l*B≡y-x，即使用扩展欧几里德算法解关于未知整数A和B的同余方程即可。注意处理m-n、y-x和x=y的值小于零的情况，且当m=n时，直接判断其无解。需要注意的是，运算中和结果数据很可能超出231-1，建议使用Int64类型。

#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
ll x,y,n,m,L;
void kzgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(b==0)
    {
        d=a;x=1;y=0;
        return;
    }
    kzgcd(b,a%b,d,y,x);
    y-=a/b*x;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
    ll a=((n-m)%L+L)%L;
    ll b=L;
    ll c=((x-y)%L+L)%L;
    ll d,e,p,q;
    kzgcd(a,b,d,p,q);
    if(c%d)
    {
        printf("Impossible");
        return 0;
    }
    e=b/d;
    printf("%lld",((p*(c/d))%e+e)%e);
}

#include<bits/stdc++.h>
using namespace std;

long long x,y,m,n,l;

void gcd(long long a,long long b,long long& d,long long & x,long long& y)
{
    if(!b)  {d=a;x=1;y=0;}
    else    {gcd(b,a%b,d,y,x);   y-=x*(a/b);}
}

int main()
{
    cin>>x>>y>>m>>n>>l;
    long long a=((n-m)%l+l)%l;  long long b=l;    long long c=((x-y)%l+l)%l;
    long long d;
    gcd(a,b,d,x,y);
    if(c%d)
        cout<<"Impossible"<<endl;
    else
    {
        long long a1=x*(c/d);
        long long a2=abs(l/d);
        while(a1<0)
            a1+=a2;
        while(a1-a2>=0)
            a1-=a2;
        cout<<a1<<endl;
    }
    return 0;
}
     

ooo

1 0000 0000 mod 1 !!!!
看清楚，是模1！
模1就只有零了！

begin
write('Impossible');
end.

两个点···