`算法知识` 裴蜀定理Bezout

@Mark_1

裴蜀方程 @Mark_0

Defintion of Bezout-Equation

Solution (解): a pair $(x_0,y_0)$ satisfying the equation;

--

Solvable (有解): there has at-least one solution;
. Actually, this case must correspond to Infinite-Many solutions;
Unsolvable (无解): there is no solution;

性质

For any $x,y\in Z$, it is obvious that the result $ax+by$ is always a Multiple of $GCD(a,b)$;
. Therefore, for the equation $ax+by=K$, if $K\%GCD(a,b)\ne 0$, then this equation is Unsolvable;

@Delimiter

If the equation is Solvable, then there are Infinite solutions which share a General-Solution;
. For the equation $ax+by=c$, if $(x_0,y_0)$ is a Solution, then the General-Solution is $(x_0+k\ast A,y_0-k\ast B)\forall k\in Z$ where $A=\frac{b}{GCD(a,b)}$, $B=\frac{a}{GCD(a,b)}$; (notice, it is a Minus in $y_0-k\ast B$, not $+$)
. Once you get one-solution, you can derive the general-solution;
. Cuz $\neg (a=b=0)$, then $\neg (A=B=0)$, there must always has Infinite-Solutions; (the General-Solution maybe $(x_0,y-k\ast B)B\ne 0$, that is, $b=0$, all solutions share a same $x_0$)

算法

Solve the equation $ax+by=c$;

gcd = GCD( a, b);
if( c % gcd != 0){
	return "No-Solution";
}
(x0, y0) = ExGCD( a, b);
//>< (x0,y0) is a solution for $ax + by = gcd$;
A = b / gcd;
B = a / gcd;
return {x0 + k * A, y0 - k * B};
1
2
3
4
5
6
7
8
9

裴蜀定理

Bezout-Theorem: For a Special Bezout-Equation $ax+by=GCD(a,b)$, this equation must be Solvable;
. We have already discussed the General-Case Bezout-Equation (of course, including this special-case), refer to Bezout-Equation;

拓展GCD

ExGCD Algorithm is used to get the one-solution of the Special-Bezout-Equation which described by Bezout-Theorem;
. That is, ExGCD can get one-solution $(x_0,y_0)$ that satisfying the Bezout-Equation $ax+by=GCD(a,b)$;

例题

AcWing-877. 扩展欧几里得算法

线性同余方程

LCE: Linear-Congruence-Equation $ax\equiv b(\%M)$ where $M\in Z^{+},a,b\in Z$;

--

Solution (解/一般解): $x_0\in Z$ satisfying the LCE;
Normal-Solution (正态解): $x_0\in [0,M)$ satisfying the LCE;

--

Solvable (有解): there has at-least one Solution;
. Actually, it is equivalent to (there has at-least one Normal-Solution) or (there has Infinite-Many solutions);
Unsolvable (无解): there has no solution;

性质

定理

@Delimiter

除法
$a\equiv b(\%M)$, if $c|a,c|b,c|M$, then $a_0\equiv b_1(\%M_0)$ where $a_0=\frac{a}{c},b_0=\frac{b}{c},M_0=\frac{M}{c}$;
. @Unfinished( $2\equiv 6(\%4)$ but not $1\equiv 3(\%4)$);

@Delimiter

乘法
@Unfinished (a=b(M)% -> (ax=bx(M), but not ax=bx(Mx)

答案

有解无解的充要条件
Solvable $⟺$ $GCD(a,M)|b$;
Unsolvable $⟺$ $\neg (GCD(a,M)|b)$;

@Delimiter

一般解与正态解的关系
Let $S$ be the set of all Solutions, $NS$ is that of all Normal-Solutions;
. Solvable: $S\ne \varnothing$ $⟺$ $NS\ne \varnothing$;
. Unsolvable: $S=\varnothing$ $⟺$ $NS=\varnothing$;
. Inclusion: $(S\ne \varnothing )$ $\to$ $NS⫋S$;

@Delimiter

一般解
If the LCE is Solvable, let $x_0$ be a Solution, then the General-Solution are $x_0+k\ast A,\forall k\in Z$ where $A=\frac{M}{GCD(a,M)}$;
. Cuz $A\ne 0$, Solvable always implies Infinite-Many solutions;

正态解
If the LCE is Solvable, let the General-Solution are $x_0+k\ast A,\forall k\in Z$ where $A=\frac{M}{GCD(a,M)}$,
. Then, there are $GCD(a,M)$ Normal-Solutions;
. Let $x_1=(x_0\%A+A)\%A$ (i.e., $x_1$ is the Minimal-Nonnegative-Solution, and $x_1\in [0,A)$), all these Normal-Solutions are $x_1+k\ast A,\forall k\in [0,GCD(a,M))$;

算法

逆元法

Proof

1

LCE法

证明

1

$ax\equiv b(\%M)$

Divide $GCD(a,M)$ in the LCE, $a_{0}x\equiv b_0(\%M_0)$ (notice, $x$ in here is the same as that in the above equation);

Cuz $(a_0,M_0)$ are Coprime, $a_0$ must exist Multiplicative-Inverse (let it be $a_1$), then Multiple $a_1$, we get $x{a}_0{a}_1\equiv b_0{a}_1(\%M_0)$ $\to$ $x\equiv b_0{a}_1(\%M_1)$; (this $x$, is the same as the above equation)

Once we got one-solution, we will get all-solutions;

例题

@Delimiter

AcWing-222. 青蛙的约会
Method
$x+km\equiv y+kn(\%L)\to k(m-n)\equiv y-x(\%L)$

@Delimiter

AcWing-878. 线性同余方程

AcWing-203. 同余方程

乘法逆元

定义

Under the modulo-$M\ge 1$, $a$ has a Multiplicative-Inverse $b$ means $b$ is the Solution of the Congruence-Equation $ax\equiv 1(\%M)$;

性质

等价条件
$a$ has a Multiplicative-Inverse, if and only if $(a,M)$ are Co-Prime;

@Delimiter

正态解唯一性
If $a$ has a Multiplicative-Inverse, then it must has one Normal-Solution (i.e., all solutions corresponding to a same Normal-Solution);

@Delimiter

互逆性
The Multiplicative-Inverse of $a$ is $b$ if and only if $a$ is also the Multiplicative-Inverse of $b$;

算法模板

欧拉定理法

线性同余方程法

//{ MultiplicativeInverse_EXGCD-Declaration
template< class _Type> _Type MultiplicativeInverse_EXGCD( long long, _Type);
//} MultiplicativeInverse_EXGCD-Declaration

//{ MultiplicativeInverse_ExGCD-Implementation
template< class _Type> _Type MultiplicativeInverse_EXGCD( long long _a, _Type _mod){
//< + $O(\ln(_mod))$;
    @Pseudocode: assert( `_a, _mod` are Coprime);
    _Type ret = GCD_extended< _Type>( (_Type)(_a % _mod), _mod).first % _mod;
    if( ret < 0){ ret += _mod;}
    return ret;
}
//} MultiplicativeInverse_EXGCD-Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13

费马小定理

//{ MultiplicativeInverse_FermatLittleTheorem-Declaration
template< class _Type> _Type MultiplicativeInverse_FermatLittleTheorem( long long, _Type);
//} MultiplicativeInverse_FermatLittleTheorem-Declaration

//{ MultiplicativeInverse_FermatLittleTheorem-Implementation
template< class _Type> _Type MultiplicativeInverse_FermatLittleTheorem( long long _a, _Type _primeModulo){
//<
// @Brief
// . @Return would be a Solution of the Congruence-Equation `a * ? == 1 (% primeModulo)`, and @Return would in the range [0, primeModulo);
// @Warning
// . Make sure `primeModulo` is a Prime-Number;
// . Mark sure `a` is not a Multiple of `primeModulo`;
    ASSERT_( _a % _primeModulo != 0);
	_Type ret = Binary_Exponentiation< _Type>( _a, _primeModulo - 2, _primeModulo);
    if( ret < 0){ ret += _primeModulo;}
    return ret;
}
//} MultiplicativeInverse_FermatLittleTheorem-Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

例题

Redirect-ID 4

---

@Delimiter(旧解释)

# 模意义下的乘法逆元
对于任意数A, 如果存在一个x, 满足: A * x = 1 (% M);
则称: 在模M意义下, A是x的乘法逆元, x是A的乘法逆元;

比如: 2 * 3 = 1 (% 5), 所以(2,3)互为各自的乘法逆元
但是: 0 * x = 1 (% 5), 不存在满足x, 所以, 0没有乘法逆元;

---

乘法逆元的作用是: 对于任意x, 则x / A操作, 等价于: x * B
比如, (3 / 2) = (3 * 3) = 4 (% 5)

---

由定义式: A * x = 1 (% M);
化简为恒等式: A * x + k * M = 1, 其符合(裴蜀二元方程)
方程有解的前提是: GCD(A,M) | 1; 即(A, M)互质

假如(A,M)不互质, 是不存在x 这样的解的

---

##`` 模意义下的除法

一直的疑问是: 为什么要这样定义呢?
比如: 在%5意义下, 3 / 2 他的值是1.5; 由于3 / 2 = 3 * 3 = 4, 所以: 1.5与4同余, 这是怎么来的呢?

其实上面的(3 / 2 = 1.5, 1.5与4同余(在%5下)), 这种分析, 是正确的;
因为, 模意义下的(四则运算), 依然生效; 比如(15 / 3 = 5)在%5下, 等于0

但问题是, 模意义下, 都是在整数域, 不适用于小数;

因此, 在取模意义下, 如果要参与除法运算(A / B), 必须满足: 可以整除; 这样, 其结果必然在整数域

但是, 如果 ~(B | A), 其(A / B)虽然是个小数, 但其除法行为 仍然可能有效;
因为, 在取模M意义下, 任何数A 都等价于 (A + k * M);
虽然(A / B)是小数, 但如果你可以找到一个 (A + k * M) / B 是可以整除的, 那么, 就可以把(A / B) 定义为: (A + k * M) / B

---

根据: 取模元素, (A/B) 等价于(A%M / B%M); 所以, 下面的(A,B)都是%M后的

对于(A/B) 不管是否可以整除, 找到(A + k0 * M) 因为他和A等价, 使得其可以整除B (即是B的倍数)
… 即 (A + k0 * M) = 0 (% B), 即 (A + k0 * M + k1 * B = 0), (k0 * M + k1 * B = -A)
因为(k0, k1)未知, 这是(裴蜀二元方程), 其有解的前提是: GCD(M, B) | -A

只有当(B, M)互质时, 方程才有解;

当求出(k0 * M + k1 * B = -A)的解后, 则此时: (A + k0 * M) 是 B 的倍数, 且(A + k0 * M) / B = -k1

即, 我们以(-k1) 作为 (A/B)在模M下的结果;

由于k0是个通解, 即满足B的倍数的(A + k0 * M)有很多, 那么, 他们 / B后的结果(- k1)也有很多; 他们在%M下, 是否一致呢?
… -(k1) = -(k1 + k * (M/G)), 因为G = GCD(B,M)互质 = 1, 所以: -k1 = -(k1 + k * M) = -k1 (在%M下)

举个例子:
在%5下, (A = 3, B = 2), (A/B)虽然是个小数, 但他定义为: (A1/B) 且A1与A同余
这样A1 有: (8, 18, 28, 38, …), 可以发现, 他们/B后, 都等于4 (% 5)

此时(A / B) = -k1; 而(A * R = -k1 * B * R = -k1) , R为B的逆元;
可以发现, (A / B = A * R)

---

感觉有点绕糊涂了…
总之, 在模M意义下, (A / B)操作, 定义为: (A * R), 其中R为B的逆元;

对于(A/B), B=2, M=4;
可以发现, (B,M)不互质, 即B不存在逆元; 因此此时(A / B)是未定义的;
因为, 比如(1 / B = 1 / 2), (1 + k*M)都不会是B的倍数;
… 但是, 有个例外, 如果A为0, 此时, 虽然B没有逆元, 但是(A / B)是可以计算的其实, 等于0

而如果B = 3, 此时(B,M)互质, 这就很中规中矩, B的逆元是3;
任何的(A / B) 都等于 (A * 3)

---

在%M意义下:

如果(B, M)互质, 则B存在逆元R; 对于所有的(A / B)操作, 都等价于: (A * R)
… 因为此时, A可以表示为A1 = (A + k * M) 且其为B的倍数; A1不唯一;
… 可以证明: 所有的(A1 / B) 在%M下, 都等于(A1 * R) = A * R

否则, (B, M)不互质, 虽然B不存在逆元; 但不一定说明, 除法一定不可行;
对于所有的(A / B) 且A!=0, 这确实是未定义的; 即(A / B)的结果 是未定义的
但是, 如果A是0, 则(A / B = 0 / B = 0) 这是可以的;

因此, (逆元) 和 (除法), 并不是完全的对应;
但只有这一个例外, 只要A != 0, 都是可以使用逆元的;

##`` 算法

#``##`` 线性同余方程
给定A, M, 求线性同余方程: x * A = 1 (% M)的解;

用处理线性同余方程的方式来求解,
1, 令A1 = A % M, 求线性方程: x * A1 = 1 (% M)的解
… 这样数据范围就变小了
… 转换为等式, x * A1 + y * M = 1, 其中(x, y)为变量
2, 如果Gcd(A1, M)为1, 则有解; 使用裴蜀定理, 可以求出(x0, y0)
3, (x0 + k * (M/G)) = (x0 + k * M) 就是x的通解, 即A的逆元

---

#``##`` 欧拉定理
如果(P, M)互质, 则: $P^{\varphi (M)}=1(\%M)$

因此, 如果(A, M)互质, 求A的逆元R, 即满足: A * R = 1 (% M)
使用欧拉定义, 满足(A, M)互质, 则: $A^{\varphi (M)}=A\ast A^{\varphi (M)-1}=1(\%M)$
因此: R = $A^{\varphi (M)-1}$

可以使用(快速幂)来求解;

特别当, 如果M为质数, 则(费马小定理): 此时A的逆元R = $A^{M-2}$

---

##`` 性质

---

#``##`` 逆元与互质
在%M下, A存在逆元B, 则, (B, M)也互质;

证明: A*B = 1 (% M)
如果(B, M)不互质, 存在公约数g; 则(A * B) + k * M = 1
k * g = 1; 因为g > 1, 等式不成立;

因此, A的逆元是B; 则B也有逆元, 逆元为A

#``##`` 逆元的四则运算
令F为二元运算, 若A存在逆元R; B存在逆元R1, C存在逆元R2

若F为(加, 减):
若(B F C = A (% M)), 则, (R1 F R2 = R (% M)) 这是假的
… 比如: 在M=7, (2的逆元4; 3的逆元为5; 5的逆元为3;), 虽然(2 + 3 = 5; 但是, (4 + 5) != 3)

若F为(乘法):
若(B * C = A) , 则: (R1 * R2 = R); 这是真的
证明: A * R = 1, A * R * (B * R1) * (C * R1) = (B * R1) * (C * R1)
… A * R * 1 * 1 = B * C * R1 * R2; … A * R = A * R1 * R2
… 根据: 取模除法, 因为(A, M)互质, 可以约去; 即: R = R1 * R2;

---

# 裴蜀定理

##`` 证明
对于任意的满足(G | C)的C, 该方程式 一定有解(即存在满足的(x,y)整数)

转换: 只要证明, 方程式 (x * A + y * B = G)是有解的, 则两端同乘整数, 方程右侧就可以变成C

而裴蜀定理就是说: 存在(x,y) 使得 (x * A + y * B = G)

他的证明, 需要用到GCD算法; 因为这里的G, 就是GCD;

令A>=B, GCD算法是, 求若干项的GCD: (A,B) -> (B%A, B) -> … -> (G, 0)
每一项, 我们令第一参数是P1, 第二参数P2; (在GCD里, 每一项都有: P1 >= P2)

根据GCD算法有: 第一项的GCD = 第二项的GCD = … = 最后一项的P1

将每一项, 都看作是一个 (上述的方程式), 即x * P1 + y * P2 = G

第一项是: x * A + y * B = G
第二项是: x * B + y * (A%B) = G
…
最后一项是: x * G + y * 0 = G

当然, 要满足方程式, 每一项的(x, y)是不同的;
答案要求的是: 第一项的(x, y);

此时用到(数学归纳法); (如果可以求出最后一项的解) (如果根据后一项的解, 得到前一项的解), 则就可以得到(第一项的解)

1, 最后一项的解: 此时, 令(x = 1, y = 任意), 这就是满足最后一项方程的解)

2, 假如当前项是: xc * P1 + yc * P2 = G; 当前项的下一项是: xp * P2 + yp * (P1%P2) = G;
且, 下一项的解(xp, yp)是已知的; (xc, yc中c为当前cur; xp, yp中p为pre)
即, 根据已知项(即下一项), 来推导当前项;
由于当前项的未知量是(xc, yc), 即当前项的形式: ? * P1 + ? * P2 = G;
于是, 我们将已知项 也转换为: ? * P1 + ? * P2 = G 的形式;

xp * P2 + yp * (P1 - (P1/P2) * P2) = G;
… 要注意, 取模%有3种 整除也有3种, 两者是对应的; 如果你%用的是(正负取模), 则/整除必须使用(向0取整); … 当然, C++默认的%和/号, 是对应的;

yp * P1 + ( xp - (P1/P2) * yp) * P2 = G;
… 这里以前会有这样的疑问: 此时化简成的: ? * P1 + ? * P2的形式里, ?里面有P1和P2怎么办?
… 比如上面, 可以发现, 里面有(P1/P2)这个式子
… 这是没问题的, 一切以(目的)出发; 我们的目的就是要化简为: ? * P1 + ? * P2的形式
… 比如对于: P1 * P2 * P1 + P2 * P1 * P2, 他化简为: (P1P2) * P1 + (P2P1) * P2, 就可以了
… 不用关注, ?里面是什么; 只要满足: ? * P1 + ? * P2的(形式), 就可以;

得到: xc = yp; yc = ( xp - (P1/P2) * yp);

因此, 满足(归纳法);

---

##`` 参数范围
由于裴蜀定理不是(同余式), 不涉及(取模操作); 那么, 参数(x,y) 会爆出LL吗?
Ll_ xc = yp;
Ll_ yc = xp - yp * ( _a / _b);
分析这个yc, 还真是挺困难的, 只能说一般不会爆LL;

下面有一些尝试;

---

##`` 通解
比如最终答案求出了一个解(x0, y0), 即: x0 * A + y0 * B = G … G为(A,B)的GCD
对于这个二元方程式, 他其实是有无限个解的;

如果是一元方程: x * A = G, 如果得到一个解x0, 那么, 只会有这一个解(就是G/A) ;

但是, 对于二元方程: x * A + y * B = G, 如果得到了一个解(x0, y0)
那么最简单的, (x0 + B) * A + (y0 - A) * B = G; 这个式子化简后, 也会得到: x0 * A + y0 * B = G;

即, 我们得到了(x0, y0) 与 (x0 + B, y0 - A), 两个解;
进一步, (x0 + k * B, y0 - k * A)全是解; 但这不是通解, 下面会讲到

即在 x0 * A + y0 * B = G; 这一组解的基础上, 我们需要得到通解(x1, y1), 使得同样: x1 * A + y1 * B = G

即满足: x1 * A + y1 * B = x0 * A + y0 * B,
化简得到: (x1 - x0) * A = (y0 - y1) * B

由于(x1, y1)未知, 我们记作: x2 = (x1 - x0), y2 = (y0 - y1)

则满足: x2 * A = y2 * B 二元方程, 求(x2, y2)通解
目测来看, 满足的解有: (0, 0) (B, A) (-B, -A) (2B, -2A) …

关键是如何找(通解);
我们令C = x2 * A = y2 * B,
注意C不是常数, 对于不同的(x2, y2)解, 其值也不同;
但是对于一个确定的C, 如果其有解, 则一定是唯一的; C确定了, x2 = C / A 也就确定了
换句话说, 任何一个解, 都对应一个唯一的C; 那么我们从C入手, 合法的C的个数, 就是解的个数

对于x2 * A = y2 * B 二元方程, 等价于是: C要满足: A | C, B | C, 且(x2,y2)为整数
满足此要求的C, 是一个(A,B)的公倍数集合 参见: 公倍数定义

因为公倍数集合为: k * LCM, 其中LCM为(A,B)的最小公倍数;

令G为(A,B)的GCD, 则: x2 = k * LCM / A = k * B / G, y2 = k * A / G

则, 通解 x1 = x2 + x0 = x0 + k * (B/G), 通解 y1 = y0 - y2 = y0 - k * (A/G)
k的取值是任意整数, 但要注意, 两式中的k, 是相同的!!!

此时, x1 * A + y1 * B = (x0 + k * (B/G)) * A + (y0 - k * (A/G)) * B 方程, 会发现, 他是等价于: x0 * A + y0 * B = G 原方程的

---

该性质, 适用于任何的 (裴蜀二元方程);
即对任意的(裴蜀二元方程), x0 * A + y0 * B = G
则(x0 + k * (B/G), y0 - k * (A/G))是通解;

即以下代码, 也是正确的:

using Item_ = tuple< Ll_, Ll_, Ll_>; //< x, y, gcd
function<Item_(Ll_,Ll_)> dfs = [&]( Ll_ _a, Ll_ _b) -> Item_{
    if( _b == 0){
        return { 1, 0, _a};
    }
    Item_ pre = dfs( _b, _a % _b);
    auto xp = get< 0>( pre);
    auto yp = get< 1>( pre);
    auto gcd = get< 2>( pre);
    Ll_ xc = yp;
    Ll_ yc = xp - yp * ( _a / _b);
    //{
	    int k = random();
	    xc += k * ( _b / gcd);
	    yc -= k * ( _a / gcd);
    //}
    return { xc, yc, gcd};
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

代码中的注释域, 是与一般裴蜀代码不同的地方;
但一定要注意, 虽然k是任意的, 但是: (对(x,y)的操作, 是同一个k值, 而且必须是一个加 一个减)

应该这样讲, 有一组解(x0, y0), 其中(x0 = xc % (_b/gcd));
还有一组解(x1, y1), 其中(y1 = yc % (_a/gcd));
但是(xc % (_b/gcd), yc % (_a/gcd)), 这个解, 不一定是通解里面的

因此, xc %= ( _b / gcd); yc %= ( _a / gcd); 这是错误的!!! 两者的k, 是不同的

假如你要执行 xc %= ( _b / gcd); 他有一个k, 那么, yc也必须是这个k
而xc %= ( _b / gcd)这个执行, 所对应的k, 是可以求出来的; 参见: 取模还原
得到了这个k后, 再执行: yc -= k * ( _a / gcd);
… 即, 只能有一个执行(%取模)操作, 不可以两个都执行;

将上面的注释域, 写成以下, 也是正确的:

auto init = xc;
xc %= ( _b / gcd);
auto k = ( xc - init) / ( _b / gcd);
yc -= ( k * ( _a / gcd));
1
2
3
4

或

auto init = yc;
yc %= ( _a / gcd);
auto k = ( yc - init) / ( _a / gcd);
xc -= ( k * ( _b / gcd));
1
2
3
4

但一般裴蜀算法, 不需要这样写; 一般不会爆LL
因为, 即使你让其中一个进行了取模%操作, 另一个, 还是得执行( -= k * (…))的操作; 还是可能爆LL

---

#``##`` 通解的结果无关性

我们上面讨论的是:
对于一组解: (x0 * A + y0 * B = G)
可以得到他的通解: $(x0+k\ast (B/G),y0-k\ast (A/G))$

这个过程, 其实与(右侧的G)是完全无关的

比如对于最初的 (x0 * A + y0 * B = G)
我们两侧同乘于D, 即: (D * x0 * A + D * y0 * B = G * D)

我们令(x1 = D * x0, y1 = D * y0), 即得到: x1 * A + y1 * B = G*D
该方程的通解, 依然是: $(x1+k\ast (B/G),y1-k\ast (A/G))$

他是与(右侧的值), 无关的;
即通解中: (x1 + k * (B/G)) 中的G, 不是等于右侧, 而是代表: (A, B)的GCD

---

# 线性同余方程

给定(A,B,M), 找到满足: x * A = B (% M) 下的一个解; 若无解, 输出no; 若有解, 保证x是在int范围内

进行(同余转换: 即将同余式, 变为恒等式): x * A + k * M = B;
根据: 同余转换, k = (B - x * A) / M; 但是因为x是未知的, 所以k也是未知的

即, 两个变量: (x, k), 可以发现, 他就是(裴蜀二元方程),
那么可以求出: x1 * A + k1 * M = GCD(A, M), 其中(x1,k1)为该方程的一个解(即裴蜀定理求出的)

根据(裴蜀定理), 对于(x * A + k * M), 任意的(x, k), 其结果, 一定是GCD(A, M)的倍数;

因此, 如果 ~( GCD(A,M) | B), 则方程无解;

令K = B / GCD(A,M), 则: x2 * A + k2 * M = B, 其中(x2 = x1 * K, k2 = k1 * K)
但这里要注意, 我们裴蜀定理得到的(x1, k1), 可能已经是LL范围了, 如果再* K, 可能就溢出了;

根据(裴蜀的通解形式):
单个解: x1 * A + k1 * M = G, (G为(A,M)的GCD)
通解: (x1 + k * (M/G)) * A + (k1 - k * (A/G)) * M = G,

我们可以执行: x1 %= (M / G); 让他处在int范围;
… 但注意, 此时不可以让: k1 %= (A/G); 这是错的; 否则(x1, k1)对应的k就不同了; 上面有讲过, 此时k1有一个复杂的公式可以求出;
… 而且, 进行: x1 %= (M/G);后, 可能k1就溢出LL了!
… 但是, 在线性同余方程里, 我们只求的是(x)第一个变量, 不涉及(第二个变量)! 所以, 不用管(k1)

单个解: x1 * A + k1 * M = G, (G为(A,M)的GCD)
令: x2 = x1 % (M/G); k2暂不关注是多少 但知道他是存在的
得到另一组解: x2 * A + k2 * M = G

两侧同乘K(K = B / G), K * x2 * A + K * k2 * M = B

令x3 = (K * x2), k3 = K * k2 (k3不关注他是多少, 但知道他是存在的)
即: x3 * A + k3 * M = B;

可以发现, 这就是题目要求的, 线性同余方程(x * A + k * M = B)的形式;

但是, k3 = (K * x2); x2是int范围, 进行*K后, 得到的x3 也能又是LL范围了;

因此: 对于( x3 * A + k3 * M = B), 此时x3是LL范围
根据: 无关性, 他的通解是: (x3 + k * (M/G), k3 - k * (A/G)), 其中G为(A,M)的GCD

即, x3 %= (M/G)后, 就变成int范围了;

##`` 取模
对于给定的线性方程: x * A = B (% M)
由于他是在(取模意义)下, 所以, 我们一开始, 就可以将他化简为: A1 = A % M, B1 = B % M
求线性方程: x * A1 = B1 (% M) 的解;

这样, 数据范围就小了