乘法逆元(快速幂，费马小定理）
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
typedef long long ll;
ll power(ll a, ll b) { // 快速幂计算 (a^b % MOD)
ll res = 1;
while (b > 0) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int main() {
int T;
cin >> T;
while (T--) {
ll N;
cin >> N;
cout << power(N, MOD - 2) << endl;
}
return 0;
}
乘法逆元：
a⋅x≡1(mod m)： a 与 b 在模 m 的意义下同余，这个 x 就被称为 a 在模 p 下的乘法逆元
3⋅5=15≡1(mod 7)： 5 是 3 在模 7 下的乘法逆元
3⋅7≡1(mod10)： 7 是 3 在模 10 下的乘法逆元
根据费马小定理：
对于任意整数 a 和一个质数 p，如果 a 和 p 互质
那么： a^(p−1) ≡ 1 (mod p)
对于：N⋅x ≡ 1(mod p)，设所求为x
显然 x=N^(p-2)
直接通过 快速幂 计算 N^(mod−2)就可以得到乘法逆元