先驗(yàn)知識(shí)

1.如果a% b = d，c% b = e，那么(a+c)%b=(d+e)%b(這里不證明正確性)

2.如果a% b = 1，那么(d * a)%b=d%b(這里不證明正確性)

我們先來(lái)看一個(gè)問題(改編自曹沖養(yǎng)豬):

烤青鳥的故事

標(biāo)題描述:

包勉是個(gè)貪婪的孩子。這一天，他買了一堆青鳥來(lái)吃。當(dāng)然，他媽媽不想讓他吃太多的食物(因?yàn)檫@會(huì)讓他變胖)。為了避免媽媽的嘮叨，他決定不告訴媽媽綠鳥的數(shù)量，而是用下面的公式來(lái)描述綠鳥的數(shù)量x

因?yàn)樗麐寢寯?shù)學(xué)不好，所以來(lái)找你幫忙。請(qǐng)找出至少買了多少只烤青鳥面包

I/o格式

輸入格式:

第一行包含整數(shù)n (n

首先，我們把這個(gè)問題簡(jiǎn)化成下圖

例子有:

33 15 17 2 意義下有且只有1個(gè)在模的意義上，每個(gè)crt方程組只有一個(gè)解

為什么？因?yàn)槊總€(gè)解的差都是A的乘積，所以不管序列中哪個(gè)數(shù)是模，加數(shù)都是0

2.論暴力的擴(kuò)張

先說點(diǎn)別的

從上面的暴力可以看出，這個(gè)樣本crt解的本質(zhì)是從5和7的公倍數(shù)中找出一個(gè)數(shù)n_1除以3加1，從3和5的公倍數(shù)中找出一個(gè)數(shù)n_2除以5加1，從3和5的公倍數(shù)中找出一個(gè)數(shù)n_3除以7加2。

那我們能說這樣可以獲得更多的答案嗎？

答案是肯定的。

規(guī)則

這是一眼就能看穿的問題

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

每?jī)蓚€(gè)按順序合并

一次獲得一個(gè)當(dāng)前解決方案

合并很簡(jiǎn)單，

我們首先使用exgcd來(lái)尋找解決方案

然后，利用這個(gè)解，構(gòu)造一個(gè)新的方程并進(jìn)行計(jì)算

如何構(gòu)建新的解決方案？

目前，我們有兩個(gè)方程，一個(gè)是前面方程的組合，我們稱之為方程1

另一個(gè)是我們?cè)谶@一步要合并的方程，叫做方程2

我們可以用exgcd在這里找到x

現(xiàn)在的關(guān)鍵是如何合并A和A _ I。

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

我們可以得到一個(gè)新的等式

代碼:

別忘了會(huì)后寫NOI2018屠龍俠~

特別感謝洛谷曹沖養(yǎng)豬和挖坑解決方案的作者，他們給了我很多想法

如果你出鍋了，請(qǐng)私下聯(lián)系我(我可能看不到評(píng)論)，非常感謝

本文發(fā)表在《洛谷日?qǐng)?bào)》上，作者:ztz11

原地址:https://www . lo gu . org/blog/ztz 11/錢-Xi-中-國(guó)-生-玉-定-立-宗-CRT-道-excr