逆元(数论)

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-21 00:54:21
 7  * @LastEditTime: 2019-10-21 01:41:14
 8  */
 9 #include<iostream>
10 using namespace std;
11 int mod = 9973;
12 
13 inline int quick_pow(int a, int b) {
14     int res = 1, base = a%mod;
15     while(b) {
16         if(b&1) res = (base*res)%mod;
17         base = (base*base)%mod;
18         b >>= 1;
19     }
20     return res;
21 }
22 
23 int main() {
24     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
25     int T;
26     cin >> T;
27     int n, a;
28     while(T--) {
29         cin >> n >> a;
30         int x = quick_pow(a, mod-2);
31         cout << n*x%mod << "\n";
32     }
33     return 0;
34 }

#include<iostream>
using namespace std;
typedef long long ll;
int mod = 9973;

inline int exgcd(int a, int b, int &x, int &y) {
    if(!b) {
        x = 1; y = 0;
        return a;
    }
    int ans = exgcd(b, a%b, x, y);
    int t = x;
    x = y;
    y = t - a/b*y;
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    int n, a;
    int x, y;
    while(T--) {
        cin >> n >> a;
        exgcd(a, mod, x, y);
        x = (x%mod + mod) % mod; // while(x < 0) x += mod;
        cout << n*x%mod << "\n";
    }
    return 0;
}

LL inv[N];
void Inv(int n, int p) {
    inv[1] = 1;
    for(int i = 2; i <= n; ++i) {
        inv[i] = (p-p/i)*inv[p%i]%p;
    }
}