欧几里德

学习自http://blog.csdn.net/lulipeng_cpp/article/details/7612490
/*
题解：
1.
n = A%9973;
n = A-a/9973*9973;
设：B*x=A;
n = B*x - a/9973*9973,n = B*x-9973y;
2.
问题就转化为求X.
gcd(B,9973) = B*x1+9973y1 = 1;
同乘N，B*(n*x1) - 9973*(-y1*n)=n;
即 x = n*x1;
3.为了防止x为负数，k = (x%9973 + 9973)%9973;
*/

#include<stdio.h>
#include<string.h>
int exgcd(int a,int b,int &x,int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b,a%b,x,y);
    int t = x;
    x = y;
    y = t-(a/b)*y;
    return r;    
}
int main()
{
    int n,B,x,y,t;
    int i,j,k;
    while(~scanf("%d",&t))
    {
        while(t --)
        {
            scanf("%d %d",&n,&B);
            k = exgcd(B,9973,x,y);
            x *= n;
            k = (x%9973 + 9973)%9973;
            printf("%d
",k);
        }
    }
    return 0;
}