0%

p1516 青蛙的约会

题目链接

和上一篇一样,也就是扩欧,先贴下代码,有时间来补。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll x,y,m,n,l,k,r,a,b;
int xx,yy;
ll gcd(ll a,ll b,int &xx,int &yy)//拓欧
{
    if(b==0)
    {
        xx=1;yy=0;
        return a;
    }
    ll r=gcd(b,a%b,xx,yy);
    int t=xx;
    xx=yy;
    yy=t-(a/b)*yy;
    return r;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    a=x-y;b=n-m;//定义A,B
    if(b<0)
    {
        a=-a;
        b=-b;
    }
    r=gcd(b,l,xx,yy);
    if(a%r!=0)
    {
        printf("Impossible");
        return 0;
    }
    printf("%lld",((xx*(a/r))%(l/r)+(l/r))%(l/r));
    return 0;
}