擴充歐幾裡德

數論四·擴充歐幾裡德

時間限制:10000ms

單點時限:1000ms

記憶體限制:256MB

描述

小Hi和小Ho周末在公園溜達。公園有一堆圍成環形的石闆，小Hi和小Ho分别站在不同的石闆上。已知石闆總共有m塊，編号為 0..m-1，小Hi一開始站在s1号石闆上，小Ho一開始站在s2号石闆上。

小Hi：小Ho，你說我們倆如果從現在開始按照固定的間隔數同時同向移動，我們會不會在某個時間點站在同一塊石闆上呢？

小Ho：我覺得可能吧，你每次移動v1塊，我移動v2塊，我們看能不能遇上好了。

小Hi：好啊，那我們試試呗。

一個小時過去了，然而小Hi和小Ho還是沒有一次站在同一塊石闆上。

小Ho：不行了，這樣走下去不知道什麼時候才彙合。小Hi，你有什麼辦法算算具體要多久才能彙合麼？

小Hi：讓我想想啊。。

提示：擴充歐幾裡德

輸入

第1行：每行5個整數s1,s2,v1,v2,m，0≤v1,v2≤m≤1,000,000,000。0≤s1,s2<m

中間過程可能很大，最好使用64位整型

輸出

樣例輸入

0 1 1 2 6      

樣例輸出

5

      

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(b==0){d=a;x=1;y=0;return ;}
    ex_gcd(b,a%b,d,y,x);y=y-a/b*x;//這一層要返上去，是以現在的x是y，y是x。 
}
LL LLabs(LL v)
{
    if(v<0) return -v;return v;
}
int main()
{
    LL v1,v2,s1,s2,m,d,x,y;
    scanf("%lld%lld%lld%lld%lld",&s1,&s2,&v1,&v2,&m);
    ex_gcd(v1-v2,m,d,x,y);
    if((s1-s2)%d!=0||v1==v2) {
        printf("-1\n");return 0;
    }
     x=x*(s2-s1)/d;//恢複  
     LL mo=LLabs(m/d);  //|x%m0|<|mo|,是以不用一個個個的加 
     printf("%lld\n",(x%mo+mo)%mo);
    return 0;
}      

It is your time to fight！