P1495 【模闆】中國剩餘定理(CRT)/曹沖養豬+中國剩餘定理講解

​​傳送門​​ 借此題複習一下中國剩餘定理。

題意：

此題可簡化成求同餘方程的解(

)：

…

直接求出

的值不太現實，于是将問題轉化為求以下

的解：

…

而

就是答案，當然，對于每一個

，我們還需要制定額外的限制條件，以保證

可以作為答案：

對于

，我們需要讓它能夠整除

到

中除

之外的所有數，即：

必須要是

的倍數并且

。

首先設prod為

，對于

，我們來羅列一下它的限制條件：

也就是說，我們要在除了

之外的所有模數的乘積（即

）倍數中，找到一個模

等于

的數，但在這裡我們不選擇枚舉的方式，而是通過找到

模

下的逆元，再乘上模數

，進而得到

。

那麼，為什麼采取這種方式去得到

？

首先看一下逆元的定義：

設d為a模b下的逆元，則：

，即：

,

此外，要引入一條定理：

若

，則

于是，求出逆元

後，

，而

。

在這題上就是：用

得到一個

的倍數且模

為1的數，再乘上相應的模數

即可得到一個滿足上述限制條件表達式的值。

于是最後的答案就是：

，而最小的答案為

最終答案的表達式為：

，其中

為

模

下的逆元。

這題的ac代碼：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100010],b[100010];
void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    ll temp = x;
    x = y;
    y = temp - (a / b) * y;
}

int main()
{
    int n;
    cin>>n;
    ll sum = 1;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i]>>b[i];
        sum*=a[i];
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ll x=0,y=0;
        exgcd(sum/a[i],a[i],x,y);
        ans += sum*b[i]*(x > 0?x:x+a[i]);
        
    }
    cout<<ans%sum<<endl;

}