【题目链接】:http://hihocoder.com/problemset/problem/1297

【题意】

【题解】



问题可以转化为数学问题

即(s1+v1*t)%m == (s2+v2*t)%m···①

也即

(s1+v1*t-(s2+v2*t))%m==0

也即

(s1-s2)+(v1-v2)*t=k*m

也即

(v2-v1)*t+m*k=(s1-s2)

与

A*X+B*y=C对应;

这里如果C是gcd(A,B)的倍数,则有解;

为了方便起见

我们在A<0的时候,把A和C都取相反数(相当于①式在移项的时候把左边的项移到右边来了)

(这样等下求出来的gcd就不会是负数了)

然后求出t=gcd(A,B)

如果有解的话

A/=t,B/=t,C/=t;

这时

新的A和B就互质了,即gcd(A,B)==1;

也求

A’x+B’y=C’···②

的解;

我们可以先求出

A’x+B’y=1···③

的解x0和y0;

然后把x0和y0都乘上C’是②的解了

但是这里必须要求x>0

这里有个知道特解求②的通解的公式;

推导过程如下

    先考虑③的通解

    A'x'+B'y'+(u+(-u))A'B'=1

    => (x' + uB')*A' + (y' - uA')*B' = 1

    然后两边同时乘上C'

    =>(X'*C'+C'*u*B')*A'+(y'*C'-u*C'*A')*B' = C'

    =>  X = X'*C'+C'*u*B', Y =X'*C'+C'*u*B'

    也即x = x0*C'+C'*u*B',y = y0*C'-C'*u*A'

则x的最小正数解为(x0*C’%B+B)%B;

加上B’是为了保证x大于0





【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

LL s1,s2,v1,v2,m;

LL gcd(LL a,LL b)

{

    if (b==0)

        return a;

    else

        return gcd(b,a%b);

}

void ex_gcd(LL a,LL b,LL &x,LL &y)

{

    if (b==0)

    {

        x = 1;y = 0;

        return;

    }

    ex_gcd(b,a%b,x,y);

    LL temp = y;

    y = x-(a/b)*temp;

    x = temp;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use

    cin >> s1 >> s2 >> v1 >> v2 >> m;

    LL A = v1-v2,B = m,C = s2-s1;

    if (A<0) A=-A,C=-C;

    LL t = gcd(A,B);

    if (C%t!=0) return cout << -1 << endl,0;

    A/=t,B/=t,C/=t;

    LL tx,ty;

    ex_gcd(A,B,tx,ty);

    tx = (tx*C%B+B)%B;

    cout << tx << endl;

    return 0;

}