同余方程

源代码：

#include<cstdio>
int A,B,X,Y;
int GCD(int t1,int t2)
{
    return t2?GCD(t2,t1%t2):t1;
}
void ExGCD(int t1,int t2) //裸扩展欧几里得。
{
    if (!t2)
    {
        X=1;
        Y=0;
    }
    else
    {
        ExGCD(t2,t1%t2);
        int t=X;
        X=Y;
        Y=t-(t1/t2)*Y;
    }
}
int main()
{
    scanf("%d%d",&A,&B);
    int D=GCD(A,B);
    A/=D;
    B/=D;
    ExGCD(A,B);
    while (X<=0)
      X+=B;
    printf("%d",X);
    return 0;
}

/*
    什么逆元老子不知道。
    Ax mod B=1 --> Ax-By=1 --> 扩展欧几里得求解最小x即可。
*/