前言

同学们，我们来把欧几里得拓展一下——区欠 ⺁乚 ?? 彳㝵
欧几里得：“mdzz…”

1.模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
long long expgcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	long long ret=expgcd(b,a%b,x,y);
	long long temp=x;
	x=y;
	y=temp-a/b*y;
	return ret;
}
long long cal(long long a,long long b)
{
	long long x,y;
	long long ret=expgcd(a,b,x,y);
	long long ans=x%b;
	while(ans<0) ans+=b;
	return ans;
}

2.Exgcd联赛例题之同余方程（noip2012）

【题目链接】
洛谷【1082】
【题目描述】
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
【输入格式】
输入只有一行，包含两个正整数 a, b，用一个空格隔开。
【输出格式】
输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。
【输入样例】

3 10

【输出样例】

7

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<iostream>
#include<cmath>
#define M 500500
#define LL long long
using namespace std;
LL n,m,MOD;
LL sum;
LL expgcd(LL a,LL b,LL &x,LL &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	LL ans=expgcd(b,a%b,x,y);
	LL temp=x;
	x=y;
	y=temp-a/b*y;
	return ans;
}
LL cal(LL a,LL b)
{
	LL x,y;
	LL gcd=expgcd(a,MOD,x,y);
	if(1%gcd!=0) return -1;
	x*=1/gcd;
	LL ans=x%(LL)abs(b);
	while(ans<0) ans+=b;
	return ans;
}
LL power(LL x,LL y)
{
	LL ans=1;
	for(;y;y>>=1,x*=x%MOD)
	{
		if(y&1)
			ans*=x%MOD;
		x=x%MOD;
	}
	return ans;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	MOD=m;
	printf("%lld",cal(n,m));
	return 0;
}

来自naivekun的拓展欧几里得讲解

先膜一发
Orz Orz Orz
Click Here