当前没有测试数据。

题目描述

（猜数字）现有两组数字，每组 $k$ 个。

第一组中的数字分别用 $a_1,a_2,\cdots ,a_k$ 表示，第二组中的数字分别用 $b_1,b_2,\cdots ,b_k$ 表示。

其中第二组中的数字是两两互素的。求最小的 $n\in \mathbb{N}$，满足对于 $\forall i\in [1,k]$，有 $b_i | (n-a_i)$。

输入格式

第一行一个整数 $k$。

第二行 $k$ 个整数，表示：$a_1,a_2,\cdots ,a_k$。

第三行 $k$ 个整数，表示：$b_1,b_2,\cdots ,b_k$。

输出格式

输出一行一个整数，为所求的答案 $n$。

提示

对于 $100\%$ 的数据：

$1\le k \le 10$，$|a_i|\le 10^9$，$1\le b_i\le 6\times 10^3$，$\prod_{i=1}^k b_i\le 10^{18}$。

每个测试点时限 $1$ 秒。

试补全程序。

提示：使用中国剩余定理完成此题。

#include <cstdio>
#define int long long
#define MAXN 100000
using namespace std;
int a[MAXN + 10], m[MAXN + 10], n;
int exgcd(int a, int b, int &x, int &y) {
	if(!b) {
		x = 1, y = 0;
		return a;
	}
	else {
		int ret, temp;
		ret = exgcd(b, a % b, x, y);
		temp = x, x = y, y = temp - a / b * y;
		return ret;
	}
}
int mul(int a, int b, int M) {
	int ans = 0;
	while(b) {
		if(b & 1) ans = (ans + a) % M;
		a = (a + a) % M, b >>= 1;
	}
	return ans;
}
int CRT(int n) {
	int M = 1, x, y, ans = 0;
	for(int p = 1; p <= n; p++)
		M *= m[p];
	for(int p = 1; p <= n; p++) {
		x = y = 0;
		exgcd(M / m[p], m[p], x, y);
		int M_ = M / m[p]; x = ((x % M + M) + M) % M;
		ans = (ans + mul(mul(M_, a[p], M), x, M) + M) % M;
	}
	return (ans + M) % M;
}
signed main() {
	scanf("%lld", &n);
	for(int p = 1; p <= n; p++)
		scanf("%lld", &a[p]);
	for(int p = 1; p <= n; p++)
		scanf("%lld", &m[p]), a[p] = ((a[p] % m[p] + m[p]) + m[p]) % m[p];
	printf("%lld", CRT(n));
    return 0;
}

① 处应填

• A.
• B.
• C.
• D.

② 处应填

• A.
• B.
• C.
• D.

③ 处应填

• A.
• B.
• C.
• D.

④ 处应填

• A.
• B.
• C.
• D.

⑤ 处应填

• A.
• B.
• C.
• D.

输出格式

只有一行，为五个连续写出的大写字符，表示每个空你的选项。