求逆元的三种方法

法一：费马小定理：a^p(mod p)等价于1(mod p)，前提为a,p互质；当p为质数时，a^(p-2)(mod p) 为a的逆元，快速幂求解下

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL a, p;

LL pow_mod(int x, int num, int y){
	LL res = 1 % y;
	x %= y;
	while(num){
		if(num & 1) res = res * x % y;
		x = x * x % y;
		num >>= 1;
	}
	return res;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld %lld", &a, &p);
	LL t = pow_mod(a, p - 2, p);
	printf("%lld\n", t);

	return 0;
}
/**/

法二：扩展欧几里德：ax+by=gcd(x,y)；

我们这里用的是ax+by=1时的情况，就是x与y互质时。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL a, p;

void ex_gcd(LL x, LL y, LL &A, LL &B, LL &G){
	if(!y) A = 1, B = 0, G = x;
	else {
		ex_gcd(y, x % y, B, A, G);
		B -= A * (x / y);
	}
}

LL get_inv(LL x, LL y){
	LL A, B, GCD;
	ex_gcd(x, y, A, B, GCD);
	return GCD == 1 ? (A % y + y) % y : -1;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld %lld", &a, &p);
	LL t = get_inv(a, p);
	if(t == -1) printf("No Inv\n");
	else printf("%lld\n", t);

	return 0;
}
/**/

第三种公式法；

假如求a%p的a的逆元:

设 x = p % a, y = p / a;

那么p = x + y * a;

两边同时mod p得

0 = x % p + y * a % p;

(-y) * a % p = x % p;

把a移到右边得

inv(a) * x % p = (-y) % p;

再把x移过去

inv(a) % p = inv(x) *(-y) % p;

inv(a) = (p-y) * inv(x) % p;

所以: inv(a) = (p - p / a) * in(p % a) % p;

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL a, p;

LL get_inv(LL x, LL y){
	return x == 1 ? 1 : get_inv(y % x, y) * (y - y / x) % p;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld %lld", &a, &p);
	LL t = get_inv(a % p, p);
	printf("%lld\n", t);

	return 0;
}
/**/