中国剩余定理
输入格式
第一行包含一个整数n表示建立牛棚的次数。
接下来n行,每行两个整数ai,bi, 表示建立了ai个牛棚,有bi头牛没有去处。
你可以假定不同ai之间互质。
输出格式
输出包含一个正整数,即为阿九至少养奶牛的数目。
数据范围
1≤n≤10,
1≤ai,bi≤1200000
输入样例:
3
3 1
5 1
7 2
输出样例:
16
算法分析
算法的核心是:
一. 构建中间变量$M_i$使得满足条件
条件一: $M_i \% divr_i = rest_i$
条件二: $M_i \% divr_j = 0 , 其中(j \neq i)$
如此便可以使得除以对应的除数得到对应的余数值。
二. 计算变量$M_i$ 的逆元 $M_{rvt}$,其二者相乘mod除数余数为1;以满足如下表达式
ans = $\sum$ $rest_i$$\times$$M_i$$\times$$M_{rvt}$ + k$\times$$\prod$$divr_i$
对变量 ans 分别除以任意 $divr_i$,不难发现符合条件,由此计算得到期望答案。
三. 此处乘法逆元的计算涉及到 拓展欧几里得算法,代码中有简单描述,详细内容需要看官另查。
C++ 代码
include <iostream>
typedef long long ll;
using namespace std;
// 记录样本数;
int n;
// 记录除数 divr 和 余数 rest;
int divr[12], rest[12];
// divr互质,记录其乘积 M divr;
ll M_divr = 1;
/* 函数 exEcd (a , b, x, y)用于计算
a*x + b*y = 1 (mod b)成立的 x y 的值
*/
int exEcd(ll Mi, ll divr, ll &M_rvt, ll &Kdivr) {
// 若整除,则最大公约数计算终止条件出现,准备返回;
if (divr == 0) {
M_rvt = 1;
Kdivr = 0;
return Mi;
}
// 最大公约数。
// 欧几里得算法常用于计算最大公约数,此处顺便存一下,可忽略;
int gcd = 1;
/* 欧几里得算法规律 以gcd表示最大公约数,则有
* gcd(a, b) = gcd(b, a%b) 其中 a>b;
*/
gcd = exEcd(divr, Mi%divr, Kdivr, M_rvt);
/* 由拓展欧几里得的状态转移:
gcd = a*x + b*y;
gcd = b*x + (a%b)*y;
a%b = a - (a/b)*b;
得到如下的递归计算算式;
*/
Kdivr -= Mi / divr * M_rvt;
return gcd;
}
ll CRT(){
ll ans = 0;
// 记录乘法逆元 M_rvt,即 M_rvt * Mi = 1 (mod divr);
// 逆元算式中 divr 的倍数信息 Kdivr;
ll M_rvt, Kdivr;
for (int i = 1; i <= n; i++) {
ll Mi = M_divr / divr[i];
// 计算 Mi 的乘法逆元;
exEcd(Mi, divr[i], M_rvt, Kdivr);
/* 基于以下方程计算:
ans = sum{divr[i]*Mi*M_rvt} + k*M_divr;
Mi*M_rvt + k*divr[i] = 1 (mod divr[i]);
(Mi*M_rvt + k*divr[i])*divr[i] = divr[i] (mod divr[i]);
*/
ans = (ans + rest[i]*Mi% M_divr*M_rvt ) % M_divr;
}
return (ans + M_divr) % M_divr;
}
int main() {
cin >> n;
M_divr = 1;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &divr[i], &rest[i]);
M_divr *= divr[i];
}
printf("%lld\n", CRT());
return 0;
}