求乘法逆元

两种方法

拓展欧几里得法

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
typedef long long ll;
using namespace std;
inline void exgcd(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的代码

#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("%d\n", power(a, p - 2));
}