题解 P1495 【曹冲养猪】

· · 题解

孙子定理的模板题

不算很难，不过你不会中国剩余定理，真的不会做。

因此，本篇题解主要是讲一下中国剩余定理。

中国剩余定理：

大概就是有一个未知数x，以及n个方程，即x除a1余b1，除a2余b2 ... 除ai余bi,问x是多少

注意前提条件ai与aj互质（任意两个模数互质）

设M为a1~an的最小公倍数，则M=a1 a2 ~ an (两两互质)

设ki=M/ai ， 并找到一个常数pi 使得 pi * ki % ai == 1

则答案x= （p1 * k1 * b1 + p2 * k2 * b2 + ... + pn * kn * bn） % M

因为x=x % M 因此x为最小值

最后放代码 

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n,a[11],b[11];
ull sum=1,t[11],ans; 
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i]>>b[i];
        sum*=a[i];
    } 
    for(int i=1; i<=n; i++) t[i]=sum/a[i];
    for(int i=1; i<=n; i++) 
        for(ull j=t[i]; j<=0x7f7f7f7f7f7f; j+=t[i]) 
            if(j%a[i]==1) {ans+=j*b[i]%sum;break;}
    cout<<ans%sum;
    return 0;
}