题解 P1516 【青蛙的约会】

风随逐影 · 2019-02-19 11:53:38 · 题解

简单数论

（我的第一道数论题）

由题意知：

1. x+mt≡y+nt(mod L)
2. x+mt+kL=y+nt
3. (m-n)t+Lk=(y-x)

一定存在一组t,k,使(m-n)t+Lk==gcd(m-n,L)

拓展欧几里德定理求出一组t,k；

如果(y-x)%gcd(m-n,L)!=0,无解

否则t*=((y-x)/gcd(m-n,L))

通过a(x+b/dt)+b(y-b/dt)=c调整t，使t为最小正整数即可

代码：

#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=(a);i<=(b);++(i))
#define com(i,a,b) for(int i=(a);i>=(b);--(i))
#define mem(a,b) memset((a),(b),sizeof(a))
#define inf 0x3f3f3f3f
#define fin freopen("input.txt","r",stdin)
#define fout freopen("output.txt","w",stdout)
typedef long long ll;

void exgcd(ll a,ll b,ll &x,ll& y,ll& d){
    if(b) exgcd(b,a%b,y,x,d),y-=a/b*x;
    else d=a,x=1,y=0;
}

void init(){
    ll x,y,m,n,l;
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    ll d,t,k;
    if(m<n){
        swap(m,n),swap(x,y);
    }
    exgcd(m-n,l,t,k,d);
    if((y-x)%d){
        printf("Impossible");
    }
    else{
        t*=((y-x)/d);
        t=(t%(l/d)+(l/d))%(l/d);
        printf("%lld",t);
    }

}

int main()
{
    //fin;
    init();
    return 0;
}