中国剩余定理

设一个数x,再给定k组数a,n,满足k个方程x \equiv a_{i}(mod n_{i}),且a之间两两互质,求x的最小可能值,x是正整数。

在问题中,n是模数,a是余数,算法流程:
1.计算所有模数的积n
2.对于第i组方程:计算 m_i = \frac{n}{n_i}m_i在模n_i意义下的逆元m_i^{-1},令c_i = m_im_i^{-1},不取模。
3.x = \sum a_ic_i(modn)

曹冲称象
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int A[11], B[11];

void extgcd(ll a, ll b, ll &x, ll &y) {
    if (b==0) {
        x = 1, y = 0;
        return;
    }
    extgcd(b, a%b, y, x);
    y -= a/b*x;
    return;
}

int main() {
    int n;
    ll ans = 0;
    cin >> n;
    ll tmp = 1;
    for (int i=1; i<=n; i++) {
        cin >> A[i] >> B[i];
        tmp *= A[i];
    }
    for (int i=1; i<=n; i++) {
        ll x, y;
        extgcd(tmp/A[i], A[i], x, y);
        ans += (ll)B[i] * (tmp/A[i]) * x;
    }
    cout << (ans%tmp + tmp) % tmp;
    return 0;
}

0 条评论

发表评论

邮箱地址不会被公开。