扩展欧几里得_逆元

扩展欧几里得

三种做法

1.求解ax+by=gcd(a,b) ax+by=b*x1+a%b * y1 ==> x=y1;y=x1-a/b*y1; 若b=0时，x=1,y=0;
2.求解 ax+by=c 求解出 a*x0+b*y0=d (若d|c则优解，不可整除则无解) 然后 x=x0*c/d , y=y0*c/d 只是一个特解，不一定是最优解, 可以求解齐次方程的通解，然后可以
3.求解 a*x≡b(mod m) 解法：求解 ax-km=b 解出 a*x0+b*y0=d 然后同上，若求解最小 x 时，将求解得出的 x0=x0%(b/gcd) (使等式ax-km=b同时除以b/gcd)

例题_acwing_五指山

#include<iostream>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int gcd,x1,y1;
    gcd=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return gcd;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,d,x,y,x1,y1;
        scanf("%d%d%d%d",&n,&d,&x,&y);
        int gcd=exgcd(d,n,x1,y1);
        long long xx=1ll*x1*(y-x)/gcd;
        n/=gcd;
        if((y-x)%gcd==0) printf("%d\n",(xx%n+n)%n);
        else puts("Impossible");
    }
}