P1516 青蛙的约会

问题可以转化成一个同余方程ax+by=c(a>0)(如果a是负的，要将a和c都变号)
关于这个方程的求解，可以用拓展欧几里得算法解决

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
#include<set>
using namespace std;
//#define int long long
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
ll xx,yy,m,n,l;
int gcd(int a,int b)
{
    if(b==0)
    {
        return a;

    }
    return gcd(b,a%b);
}
void Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) x = 1, y = 0;
else Exgcd(b, a % b, y, x), y -= a / b * x;
} 
signed main()
{
    ll x,y;
    cin>>xx>>yy>>m>>n>>l;
    int a=n-m;
    int b=l;
    int c=xx-yy;
    if(a<0)
    {
        a=-a;
        c=-c;
    }
    Exgcd(a,b,x,y);
    int g=gcd(a,l);
    if(c%g!=0)
    {
        cout<<"Impossible";
    }
    else{
        cout<<(c/g*x%(b/g)+b/g)%(b/g)<<endl;
    }


    return 0;
}