首页 > 代码库 > extended_gcd(扩展欧几里德算法) 青蛙的约会

extended_gcd(扩展欧几里德算法) 青蛙的约会

#include <stdio.h>#include <math.h>long long gcd(long long x,long long y){    if(y==0)    {        return x;    }    return gcd(y,x%y);}void extended_gcd(long long a,long long b,long long &x,long long &y){    long long t;    if(b==0)    {        x = 1;        y = 0;        return;    }    extended_gcd(b,a%b,x,y);    t=x;    x = y;    y = t- a/b*y;    return;}int main( ){    long long x, y, m, n, l;    long long a,b,c,d,p,q;    long long t;    while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!= EOF )    {        a= n-m;        b=l;        c= x-y;        d= gcd(a,b);        if(c%d!=0)        {            puts( "Impossible" );            continue;        }        a/= d,b/= d,c/= d;        extended_gcd(a,b,p,q);        p*= c;        t= p%b;        while(t<0)        {            t+= b;        }        printf("%lld\n",t);    }    return 0;}