目录

题目-曹冲养猪(中国剩余定理)

在这里插入图片描述

问题分析

假设养的猪的数量是 t t t, 那么有 t ≡ b i ( m o d    a i ) t \equiv b_i(\mod a_i) t≡bi​(modai​), 求 t t t的最小值, 并且 a a a之间互质

得到的方程是中国剩余定理的形式
{ x ≡ r 1 (   m o d   m 1 ) x ≡ r 2 (   m o d   m 2 ) x ≡ r 3 (   m o d   m 3 ) ⋮ x ≡ r n (   m o d   m n ) \left\{\begin{array}{l} x \equiv r_{1}\left(\bmod m_{1}\right) \\ x \equiv r_{2}\left(\bmod m_{2}\right) \\ x \equiv r_{3}\left(\bmod m_{3}\right) \\ \vdots \\ x \equiv r_{n}\left(\bmod m_{n}\right) \end{array}\right. ⎩ ⎨ ⎧​x≡r1​(modm1​)x≡r2​(modm2​)x≡r3​(modm3​)⋮x≡rn​(modmn​)​
直接套用公式即可

t t t是 M i − 1 M_i ^ {-1} Mi−1​
t ⋅ M i ≡ 1 ( m o d    m i ) t \cdot M_i \equiv 1(\mod m_i) t⋅Mi​≡1(modmi​)
求下面方程的解
t ⋅ M i + y ⋅ m i = 1 t \cdot M_i + y \cdot m_i = 1 t⋅Mi​+y⋅mi​=1

算法步骤

  • 计算 M = m 1 ⋅ m 2 ⋅ m 3 . . . ⋅ m k M = m_1 \cdot m_2 \cdot m_3 ... \cdot m_k M=m1​⋅m2​⋅m3​...⋅mk​
  • 计算 M i = M m i M_i = \frac{M}{m_i} Mi​=mi​M​, 再计算 M i − 1 M_i ^ {-1} Mi−1​
  • 累加答案

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef __int128 i128;
const int N = 15;

int n;
LL a[N], b[N];

LL exgcd(LL a, LL b, LL &x, LL &y) {
   
    if (!b) {
   
        x = 1, y = 0;
        return a;
    }

    LL _x, _y;
    LL d = exgcd(b, a % b, _x, _y);
    x = _y, y = _x - (a / b) * _y;
    return d;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    LL M = 1;
    for (int i = 0; i < n; ++i) {
   
        cin >> a[i] >> b[i];
        M = M * a[i];
    }

    LL ans = 0;
    for (int i = 0; i < n; ++i) {
   
        LL Mi = M / a[i];
        LL t, y;
        exgcd(Mi, a[i], t, y);
        // 这一步要么用龟速乘算法, 要么转为(i128)
        ans = (ans + (i128) b[i] * Mi * t) % M;
    }

    ans = (ans % M + M) % M;

    cout << ans << '\n';

    return 0;
}