中国剩余定理
设一个数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 条评论