exGCD

File

int GCD(int a,int b){
	if(b==0)return a;
	return GCD(b,a%b);
}

Question 01 [贝祖定理]

根据 ax+by=GCD(a,b)
a,b均为正整数
求x,y的整数值。

Solution

因为ax+by=GCD(a,b)
并且GCD(a,b)=GCD(b,a%b)
所以ax+by=GCD(b,a%b)
由贝祖定理GCD(b,a%b)=bX+a%bY
我们求出x,y和下一层X,Y的关系扔到递归里求解即可
等量代换ax+by=bX+a%bY
又因为a%b=a-(a/b)b (C++向下取整)
所以
ax+by=bX+[a-(a/b)b]Y
=bX+aY-b(a/b)Y
=aY+b[X-(a/b)Y]
所以得到
x=Y
y=X-(a/b)Y
但是递归需要出口
当b=0时GCD(a,b)=a
即当b等于0时,ax+by=a
把b代入 ax+0y=a
显然此时x=1
y可以取任意整数
我们根据大多数代码的习惯将其取0

Code

//求解
//exGCD 函数的返回值是GCD(a,b)
//x,y 用引用的方式取回x,y的结果
int exGCD(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	//刚才得到的式子
	int X,Y;
	int GCD_answer=exGCD(b,a%b,X,Y);
	x=Y;
	y=X-(a/b)*Y;
	return GCD_answer;
}

当然，该式子不是常见形式
我们可以直接把形参中的x,y传进去
用y记录Answer中“X”的值,x记录“Y”的值
此时
x=Y(correct)
y=X
显然y应该-=(a/b)Y
而Y的值被x所记录
所以 y-=(a/b)x

Code Improved

int exGCD(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int GCD_answer=exGCD(b,a%b,y,x);
	y-=(a/b)*x;
	return GCD_answer;
}

Question 02 [线性同余方程]

根据 ax%m=b
a,b,m均为正整数
求 x
无解输出“Shit!”

Solution

因为 ax%m=b
其等价于 ax=b+km
所以 ax-mk=b
定义 y=-k
所以 ax+my=b
而 Question 01 则是根据 ax+by=GCD(a,b) 求x,y的整数值。
这就要求 b=GCD(a,m)
但是显然有时b不等于GCD(a,b)却仍然有解

example a=3 m=5 b=3
GCD(a,m)=1
但 x=6 是不定方程的解

注意到若 b%GCD(a,b)==0
则 b=BGCD(a,b) B为整数
ax+my=b 变为 ax+my=BGCD(a,b)
已知求法的是 aX+mY=GCD(a,b)
显然
x=BX
y=BY
是原方程的一组解

Code

#include<bits/stdc++.h>
using namespace std;
int exGCD(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int GCD_answer=exGCD(b,a%b,y,x);
	y-=(a/b)*x;
	return GCD_answer;
}
int main(){
	int T,a,b,m,x,y,gcd_ans;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&a,&b,&m);
		gcd_ans=exGCD(a,m,x,y);
		if(b%gcd_ans==0){
			printf("%d\n",(long long)x*b/gcd_ans%m);
		}else{
			puts("Shit!");
		}
	}
}

Question 03 [逆元]

根据 ax%m=1
求 x (a 关于 m 的逆元)
要求 0<x<m
如没有输出“impossible”

Solution

此题为 Question 02 弱化版
ax+my=1
要求 1%GCD(a,m)=0
即 GCD(a,m)=1
即 a,m 互质

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int exGCD(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int GCD_answer=exGCD(b,a%b,y,x);
	y-=(a/b)*x;
	return GCD_answer;
}
signed main(){
	int T,a,m,x,y;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&a,&m);
		if(exGCD(a,m,x,y)==1){
			printf("%d\n",(x%m+m)%m);
		}else{
			puts("impossible");
		}
	}
}