HDU1576 A/B（逆元）

题目链接

欧拉函数方法求逆元。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
const int MOD = 9973;

long long quickmod(long long a, long long n, long long MOD){
    long long r = 1;
    while(n){
        if(n&1){
            r = (a*r)%MOD;
        }
        a = (a*a)%MOD;
        n >>= 1;
    }
    return r;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int n; cin >> n;
    while(n--){
        long long a, b;
        scanf("%lld %lld", &a, &b);
        long long ans = (a*quickmod(b, MOD-2, MOD))%MOD;
        cout << ans << endl;
    }
    return 0;
}