经验谈

代码模板

线性同余方程

//* 求A在M下的逆元x, 即x * A = 1 (% M)

A = Mod_pos( A, M);

if( Gcd( A, M) != 1){
    printf("impossible\n");
    return;
}
auto ret = Bezout( A, M);
auto inverse = get< 0>( ret);
printf("%lld\n", Mod_pos( inverse, M));

模意义下的乘法逆元

对于任意数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与5同余, 这是怎么来的呢?

模意义下的除法

其实上面的(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的逆元

重定向ID

{}