网站流量图怎么做/疫情最新动态

题意：求(A/B)%9973，可以转换为A*x(B关于9973的逆元，即Bx%9973=1)%9973,
由于9973是质数，所以可以用费马小定理求逆元

#include<iostream>
#include<string.h>
#include<string>
#include<sstream>
#include<vector>
#include<deque>
#include<map>
#include<algorithm>
#include<iomanip>
#include<math.h>
#include<set>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int mod = 9973;

ll quickmod(ll a,ll b)
{
    ll ans=1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a%mod;
        }
        b = b / 2;
        a = a * a%mod;
    }
    return ans;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n, b;
        cin >> n >> b;
        cout<<n*quickmod(b,mod-2)%mod<<endl;
    }
    return 0;
}