中国剩余定理 [洛谷日报第66期]浅析中国剩余定理

先验知识

1.如果a% b = d，c% b = e，那么(a+c)%b=(d+e)%b(这里不证明正确性)

2.如果a% b = 1，那么(d * a)%b=d%b(这里不证明正确性)

我们先来看一个问题(改编自曹冲养猪):

烤青鸟的故事

标题描述:

包勉是个贪婪的孩子。这一天，他买了一堆青鸟来吃。当然，他妈妈不想让他吃太多的食物(因为这会让他变胖)。为了避免妈妈的唠叨，他决定不告诉妈妈绿鸟的数量，而是用下面的公式来描述绿鸟的数量x

因为他妈妈数学不好，所以来找你帮忙。请找出至少买了多少只烤青鸟面包

I/o格式

输入格式:

第一行包含整数n (n

首先，我们把这个问题简化成下图

例子有:

33 15 17 2 意义下有且只有1个在模的意义上，每个crt方程组只有一个解

为什么？因为每个解的差都是A的乘积，所以不管序列中哪个数是模，加数都是0

2.论暴力的扩张

先说点别的

从上面的暴力可以看出，这个样本crt解的本质是从5和7的公倍数中找出一个数n_1除以3加1，从3和5的公倍数中找出一个数n_2除以5加1，从3和5的公倍数中找出一个数n_3除以7加2。

那我们能说这样可以获得更多的答案吗？

答案是肯定的。

规则

这是一眼就能看穿的问题

因此，上面的exgcd可以在这里使用

每两个按顺序合并

一次获得一个当前解决方案

合并很简单，

我们首先使用exgcd来寻找解决方案

然后，利用这个解，构造一个新的方程并进行计算

如何构建新的解决方案？

目前，我们有两个方程，一个是前面方程的组合，我们称之为方程1

另一个是我们在这一步要合并的方程，叫做方程2

我们可以用exgcd在这里找到x

现在的关键是如何合并A和A _ I。

我们知道，x+lcm (a，a_i)仍然满足上述方程

我们可以得到一个新的等式

代码:

别忘了会后写NOI2018屠龙侠~

特别感谢洛谷曹冲养猪和挖坑解决方案的作者，他们给了我很多想法

如果你出锅了，请私下联系我(我可能看不到评论)，非常感谢

本文发表在《洛谷日报》上，作者:ztz11

原地址:https://www . lo gu . org/blog/ztz 11/钱-Xi-中-国-生-玉-定-立-宗-CRT-道-excr