学步园

求出b的逆元就可以了。。费马小定理

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define LL long long
int const mod = 9973;
LL Quick_Mod(LL a,LL b){
    LL r = 1;
    while(b){
        if(b & 1)  r = (r * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return r;
}
int main(){
    LL b;
    int T,n;
    while(~scanf("%d",&T)){
        while(T--){
           scanf("%d%I64d",&n,&b);
            LL b1 = Quick_Mod(b,mod - 2);
            printf("%I64d\n",(b1 * n) % mod);
        }
    }
    return 0;
}