原题链接：

同样是用扩展的欧几里得算法。A = 9973k+n = xB，从而转化为：xB-9973k=n求解x即可。

具体扩展欧几里得算法请参考：

代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define     MOD 9973 6 using namespace std; 7 typedef long long LL; 8 void exgcd(LL a, LL b, LL &d, LL &x, LL&y) 9 {10     if( b == 0 )11     {12         d = a;13         x = 1;14         y = 0;15     }16     else17     {18         exgcd(b, a%b, d, x, y);19         int t = x;20         x = y;21         y = t - (a/b)*y;22     }23 }24 int main(int argc, char *argv[])25 {26     int T;27     scanf ( "%d", &T );28     int n, a, b;29     LL d, x, y;30     while( T-- )31     {32         scanf("%d%d", &n, &b);   33         a = MOD;34         exgcd(a, b, d, x, y);35         y = (y%MOD)*(n/d)%MOD;36         y = (y+MOD)%MOD;37         cout<
         
          <