曹冲养猪

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1302 字

给定若干对表示x≡b_i，a_i两两互质，求

一本通
例

正文

/*
原题：曹冲养猪 (经典中国剩余定理)
题意：给定若干对 (a_i,b_i) 表示 x ≡ b_i (mod a_i)，a_i 两两互质，求最小正整数解 x。
思路：中国剩余定理合并：先算总模 M=∏a_i，再逐项累加 b_i·(M/a_i)·inv(M/a_i, a_i)。
      题目保证 a_i 两两互质，故逆元必存在；合并结果恰为 0 时输出 M（最小正整数）。
复杂度：时间 O(n·log a_i)，空间 O(1)。
易错点：答案可能超过 64 位，需用 __int128 累加；输出要求最小正整数（解为 0 时取 M）。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128;
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1, y1;
    ll g=exgcd(b, a%b, x1, y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
ll inv(ll a, ll m){
    ll x, y;
    exgcd(a, m, x, y);
    return ((x%m)+m)%m;
}
void print_i128(i128 x){
    if(x==0){
        cout<<0;
        return;
    }
    string s;
    while(x>0){
        s+=char('0'+(int)(x%10));
        x/=10;
    }
    reverse(s.begin(), s.end());
    cout<<s;
}
int main(){
    int n;
    cin>>n;
    i128 M=1;
    vector<ll> a(n), b(n);
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        M*=a[i];
    }
    i128 ans=0;
    for(int i=0;i<n;i++){
        i128 Mi=M/a[i];
        ll t=inv((ll)(Mi%a[i]), a[i]);
        i128 term=b[i]%M;
        term=term*(Mi%M)%M;
        term=term*t%M;
        ans=(ans+term)%M;
    }
    if(ans==0){
        ans=M;
    }
    print_i128(ans);
    cout<<"\n";
    return 0;
}

曹冲养猪

正文

一本通·提高篇的其它内容