题目

A/9973=n

那么：n= A - A / 9973 * 9973   ……①

设：A/B=x  则A=B*x,代入①  得  n=B*x-A/9973*9973

然后这个方程中的A/9973不要去纠结它，A就当不知道，然后，方程可变成二元方程 B * x - 9973 * y = n ;

故：(x/n)B+(-y/n)9973=1=GCD(B,9973)，该方程有解。

　　要求x和y，先求X=x/n和Y=-y/n,即先解方程BX+9973Y=1。

　　最后,x=X*n。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

const int m = 9973;

void gcd(int a,int b,int &x,int &y)

{

    if(b==0)

    {

        x=1;y=0;

        return ;

    }

     gcd(b,a%b,x,y);

    int t = x;

        x = y;

        y = t - (a/b)*y;

}

int main()

{

    int n,a,b,x,y;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d%d",&a,&b);//a=A%9973

        gcd(b,m,x,y);

        x=(x%m+m)%m;

        x = x*a%m;

        printf("%d\n",x);

    }

    return 0;

}

其实就是数学当中的类似化简方程之类的题。化简成exgcd可以解决的形式。