题解 | #青蛙的约会#

思路

根据题目列出式子：
(x+mt)-(y+nt)=pL
其中：t是跳的次数，p是圈数差
转化为：(n-m)t+Lp=x-y
令a=n-m,b=L,c=GCD(a,b),d=x-y 有
at+b*p=d
要求的是t的最小整数解，转化为扩展欧几里得，
求解同余方程就能得出答案。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
    return d;
}

signed main(){
    int x,y,m,n,l,X,Y,gcd;
    cin>>x>>y>>m>>n>>l;
    int a=n-m,b=l,d=x-y;
    if(a<0){ //数据有加强，如果这里没写的话只能拿70
        a=-a;
        d=-d;
    }
    if(d%(gcd=exgcd(a,b,X,Y))!=0){
        cout<<"Impossible"<<endl;
    }else{
        int mod=l/gcd;
        cout<<(d/gcd*X%mod+mod)%mod<<endl;
    }
    return 0;
}