首页 > 其他 > 详细

青蛙的约会

时间:2019-07-10 11:23:25      阅读:100      评论:0      收藏:0      [点我收藏+]

题面

简单扩欧版子,数学推导详见洛谷题解

#include<iostream>
#include<cstdio>
#define ll long long 
using namespace std;
ll ans,x1,y1;

ll exgcd(ll a,ll b,ll &x1, ll &y1)
{
    if(!b)
    {
        x1=1;
        y1=0;
        return a;
    }
    ans=exgcd(b,a%b,x1,y1);
    ll t=x1;
    x1=y1;
    y1=t-a/b*y1;
    return ans;
}

int main()
{
    ll n,m,x,y,l;
    cin>>x>>y>>m>>n>>l;
    ll b=n-m,a=x-y;
    if(b<0)
    {
        b=-b;
        a=-a;
    } 
    exgcd(b,l,x1,y1);
    if(a%ans!=0) 
        cout<<"Impossible";
    else
        cout<<((x1*(a/ans))%(l/ans)+(l/ans))%(l/ans);
}

  

青蛙的约会

原文:https://www.cnblogs.com/ainiyuling/p/11162704.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!