求乘法逆元

拓展欧几里得法

证明不再赘述,直接上我的代码——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <cstdio>
#include <cstring>
#include <cstdlib>
typedef long long ll;
using namespace std;
inline void (ll a, ll b, ll &d, ll &x, ll &y)
{
if (!b) d = a, x = 1, y = 0;
else exgcd(b, a % b, d, y, x), y -= x * (a / b);
}
inline ll inv(ll a, ll p)
{
ll d, x, y;
exgcd(a, p, d, x, y);
return d == 1 ? (x + p) % p : -1;
}
int main(int argc, char **argv)
{
ll a, b;
cin >> a >> b;
cout << inv(a, b) << endl;
return 0;
}

求的是ax≡1(mod p)的逆元

费马小定理法

lyj的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
using namespace std;

const int p = 1e9 + 7;

int power(int a, int b)
{
int ans = 1;
for (; b; (a *= a) %= p, b >>= 1)
if (b & 1) (ans *= a) %= p;
return ans % p;
}

int main()
{
int a;
scanf("%d", &a);
printf("%dn", power(a, p - 2));
}