【ICPC模板】扩展中国剩余定理 (扩展CRT)
发布时间
阅读量：
阅读量
该方法与常规方法相似，在实现方式上有所不同，并非仅限于解决特定问题的情景下使用
相较于常规的中国剩余定理，在处理模数之间存在公因数的情况下依然有效。此外还能够处理模数之间互质的情况，在这种情况下，则需要应用扩展欧几里得算法来求解方程组。
整体方法是合并，将多个同余式合并，直到最后只剩下一个，进行求解。
对于两个同余式：
写成等式的形式，并进行联立：
移项得到①式：
当且仅当：
成立时方程有整数解k1与k2，这将作为判断不定方程组是否有解的条件。
在有解的情况下，可以将①式整理成：
其中g = gcd(m1, m2)
这等价于：
令I(a, b)表示a在模b运算下的逆元。
则上式左右同乘m1/g的逆元可以得到：
将上式带回到最初的x = a1 + m1k1中，消去k1可得到：
通过反复运用此公式，并对不定方程组所有方程式进行整合处理后得到一个统一形式的最终方程式，并对这一简化后的模型应用扩展欧几里得算法求解其最优解
要注意在数据较大时long long也存在溢出可能。
全部评论 (0)
还没有任何评论哟~