• 周二. 9月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

扩展欧几里得

admin

11月 28, 2021

#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<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<ctime>
#include<cmath>
#include<stack>
#include<map>
#include<set>
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;
}

发表回复

您的电子邮箱地址不会被公开。