1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int Fermat_inverse(int a,int mod)
{
int res = 1;
for(int i = 1;i < mod - 1;++i) res *= a;
return res;
}
long long fast_pow_mod(long long a,long long b,long long mod)
{
long long res = 1;
while(b){
if(b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
long long Fermat_inverse(long long a,long long mod)
{
return fast_pow_mod(a,mod - 2,mod);
}
|