问题链接：

问题简述：参见上述链接。

问题分析：这个问题可以用解整数的不定方程来解决，即使用扩展欧几里德算法。

根据题意，输入的n=A%9973（没有输入A）,A%B=0（A必能被B整除），B与9973互素（GCD(B,9973)=1）。

解题过程首先是建立方程，然后才能编写程序。

设x=(A/B)%9973（x是最终想计算的值），则9973k+x=A/B（k为整数），得A=9973Bk+xB。

因为n=A%9973与A=9973Bk+xB，所以xB%9973=n，得xB=n+9973y。

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

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

最后,x=X*n。

需要注意的是，求得的x有可能是负值，需要进行调整。

不过，这个计算方法好像比较花时间。

程序说明：（略）。

AC的程序如下：

#include 
    
     // 递推法实现扩展欧几里德算法long exgcd(long a, long b, long *x, long *y){    long x0=1, y0=0, x1=0, y1=1;    long r, q;    *x=0;    *y=1;    r = a % b;    q = (a - r) / b;    while(r)    {        *x = x0 - q * x1;        *y = y0 - q * y1;        x0 = x1;        y0 = y1;        x1 = *x;        y1 = *y;        a = b;        b = r;        r = a % b;        q = (a - r) / b;    }    return b;}int main(void){    int t, i;    long n, b, a=9973, x, y;    scanf("%d", &t);    for(i=0; i