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;

}