扩展欧几里得-白红宇

扩展欧几里得

阅读量：6672 次

发布时间：2019-06-25

本文共 1522 字，大约阅读时间需要 5 分钟。

#1297 : 数论四·扩展欧几里德

时间限制:

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位整型

输出

第1行：每行1个整数，表示解，若该组数据无解则输出-1

样例输入 0 1 1 2 6 样例输出 5

#define ll long long#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  #include
                   
                    using namespace std;ll gl() { ll res=0,f=1; char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f;}ll exgcd(ll a,ll b,ll& x,ll& y) { if(!b) { x=1,y=0; return a; } ll d=exgcd(b,a%b,x,y); ll tmp=x; x=y; y=tmp-a/b*y; return d;}ll solve() { ll s1=gl(),s2=gl(),v1=gl(),v2=gl(),m=gl(); ll x,y,a=v1-v2,b=m,c=s2-s1; if(a<0) a+=m; ll z=exgcd(a,b,x,y); if(c%z) return -1; x/=z; x*=c; while(x<0) x+=b; x%=b; return x;}int main() {// please remember :infer other things from one fact freopen("Alan.in","r",stdin); freopen("Alan.out","w",stdout); printf("%lld",solve()); return 0;}

转载于:https://www.cnblogs.com/ypz999/p/6640712.html

你可能感兴趣的文章