二元一次方程的整数解、逆元及有理数求模

前言

C++算法与数据结构
打开打包代码的方法兼述单元测试

一，f(a,b)求ax+by=1的任意解，a>0,b >0，且a、b互质。

暴力做法，辗转相减法：

如果a>b，则(a-b)和b互质，且都大于0。a<b，类似。
a,a == b，a,b互质说明是a和b，都是1。故返回(0,1)。
b,a>b则 令(a-b)x+by=1的解为(x1,y1) ,即ax1+b(y1-x1)=1成立，即解为(x1,y1-x1)。
c,b<a则 令ax+(b-a)y=1的解为(x1,y1),即a(x1-y1)+by1=1成立，即解为(x1-y1,y1)。
时间复杂度：O(n) b为1，要运行a次。可能有人想，1做作特殊处理，那2,3呢？

辗转相除法

如果a >= b， a/b和b都大于0，且互质。
a, b =1，返回(0,1)。
b,a=1，返回(1,0)。
c,如果a >= b。a除b等于c，余d。令dx+by=1解为(x1,y1)，则(bc+d)x+by的解为：(x1,y1-cx1)，下面用数学归纳法来证明：
c=1是，就是辗转相减法。
假设c成立，则根据辗转相减法，(bc+c)x+by=1的解(x1,y1-cx1-x1)，得证。
d,如果a < b。ax+dy=1的解为(x1,y1)。
解为：(x1-y1*c,y1)。
时间复杂度：O(logmax(a,b)) ，当min(a,b)为1的时，结束。故max(a,b)每次至少除以2。

已知任意解，如何求最小自然数解

d = a,b的最小公倍数。
y = ax1%d
如果y < 0则 y +=d。
y/a就是最小自然数解。

求ax+by=gcd(a,b)的解

g = gcd(a,b)如果g为0，说明a,b为0，任意整数都是解，如：(0,0)。
如果g不为0，则$⟺$ a/gx+b/gy=1。

求ax+by=c

如果g $\ne$ gcd(g,c) 则无解。
令 a/gx+b/gy=1 是(x1,y1)，则解是(c/gx1,c/gx2)。

乘法逆元

乘法逆元的定义可以直观地理解为a的倒数，即与a相乘等于1的数。在模运算中，如果a和b互质（即最大公约数为1），那么存在一个整数x，使得a×x≡1(mod b)

有理数求模

如果p是质数，可以通过逆元求，我有模板。非质数，也可以，太麻烦，我没模板。可以直接求bx+py=a(式子一）的任意解。
如果式子一无解，说明a不是gcd(b,p)的倍数，则bx=a%p一定无解。
如果式子一有任意解(x1,y1），则a = bx1+py1,则 (a/b)p=(x1+py1/b)%p= x1%p。即 x1%p是解。待证点一：b对模p，存在逆元d。
求b存在逆元：
即bx%p=1有解，即bx+py=1即bp互质。本题的p是固定，且是质数。且0 < b < p，故互质。
本质：用二元一次方程求逆元。之所以看起来不一样，是因为我的旧模板是费马小定理，新方式是扩展欧几里得（二元一次方程）。
总结：除数b为0，无意义。其它情况b和p互质，故一定有逆元。

封装类

解ax+by=gcd(a,b) a,b无需互质，可以全部或部分为负数。

class Caxby1 {
public:
	Caxby1(int a, int b) :G(m_iG) {
		m_iSignA = (a < 0)?-1:1;
		m_iSignB = (b < 0)?-1:1;
		m_a = abs(a);
		m_b = abs(b);
		m_iG = gcd(m_a, m_b);
	}
	tuple<int, int> Any() {//ax+by=gcd(a,b)的任意解
		if (0 == m_iG) { return { 0,0 }; }
		auto [x,y]= Any(m_a / m_iG, m_b / m_iG);
		return { m_iSignA * x,m_iSignB * y };
	}
	const int& G;
private:
	static pair<int, int> Any(long long a, long long b) {//求ax+by=1的整数解，a>0,b>0,a,b互质,a,b int32范围
		if (1 == a) { return { 1,0 }; }
		if (1 == b) { return { 0,1 }; }
		//如果a,b相等且互质，则两者一定都是1。
		if (a > b) {
			auto c = a / b, d = a % b;
			if (0 == d) { d = b; c--; }
			auto [x1, y1] = Any(d, b);
			return { x1, y1 - c * x1 };
		}
		auto [x2, y2] = Any(b, a);
		return { y2,x2 };
	}

private:
	int m_a, m_b, m_iG, m_iSignA, m_iSignB;
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。