首页 > 代码库 > 扩张欧几里得

扩张欧几里得

#include <iostream>#include <cstdio>#include <queue>#include <algorithm>#define ll long longusing namespace std;ll ext_gcd(ll a, ll b, ll &p, ll &q){    ll t, r;    if(!b){        p = 1;        q = 0;        return a;    }    r = ext_gcd(b,a%b,p,q);    t = p;    p = q;    q = t -(a/b)*q;    return r;}int main(){    ll x, y, n, m, l;    ll t, a, b, d, r, c;    ll p, q;    scanf("%lld %lld %lld %lld %lld",&x,&y,&n,&m,&l);    a = n-m;    c = y-x;    b = l;    d = ext_gcd(a,b,p,q);    if(c%d != 0)        printf("Impossible");    else {        p = p*(c/d);        p = (p%b+b)%b;        printf("%lld\n",p);    }    return 0;}