线性同余方程

介绍

形如 $ax\equiv c\ (mod\ b)$ 的方程被称为线性同余方程

前置知识

定理1： $ax \equiv c \ (mod \ b)$ 有解的充要条件为 $gcd(a,b)|c$

根据定理1，可根据拓展欧几里得算法求出 $ax+by=gcd(a,b)$ 的一组特解 $x_0,y_0$ 。然后对原方程进行变形得到下式。即找到方程的一个解

$$a\frac{c}{gcd(a,b)}x_0+b\frac{c}{gcd(a,b)}y_0 = c$$

由上式可推出方程通解

$$(1)\ x=x_0*\frac{c}{gcd(a,b)}+\frac{b}{gcd(a,b)}t ，y=\frac{c-a*x}{b}\\ (2)\ y=y_0*\frac{c}{gcd(a,b)}-\frac{a}{gcd(a,b)}t ，x=\frac{c-b*y}{a}$$

，t 为任意整数

注意,上面两个通解公式只能选择其中一个,另一个需要在原方程中推出。即选了公式(1) y只能通过方程推导，不能使用公式(2)求解

求解步骤

1. 转化成一般式： $ax+by=c$
2. 求最大公约数：$d=gcd(a,b)$，如果 $c\ mod\ d \not = 0$,则方程无解
3. 将原方程转为：$a\frac{c}{d}x+b\frac{c}{d}y = \frac{c}{d}d$
4. 利用欧几里得(GCD)及拓展欧几里得(ExGCD)求解： $ax+by=d$，得到特解 $x_0 , y_0$
5. 根据定理2，可以得出线性同余方程 x 的最小整数解 $x=(x*\frac
   {c}{d}\ mod\ t+t)mod\ t$ ，其中 $t=\frac{b}{gcd(a,b)}$

代码实现

#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 ans=ExGcd(b,a%b,x,y);	//先计算底层x y
	int temp=y;
	y=x-(a/b)*y;
	x=temp;
	return ans;
}
int main()
{
	int a,b,c,x,y;
	cin>>a>>b>>c;
	int gcd=ExGcd(a,b,x,y);
	int t=b/gcd;
	x=((x*c/gcd)%t+t)%t;
	cout<<x<<endl;
	return 0;
}