P3868 [TJOI2009] 猜数字 解题报告
vanueber
·
·
个人记录
题目描述
现有两组数字，每组 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。
样例 #1
样例输入 #1
3
1 2 3
2 3 5
样例输出 #1
23
提示
对于 100\% 的数据：
每个测试点时限 $1$ 秒。
注意：对于 ```C/C++```语言，对 $64$ 位整型数应声明为 ```long long```。
若使用 ```scanf```，```printf```函数（以及 ```fscanf```，```fprintf```等），应采用 ```%lld```标识符。
## 题目分析
$$ b_i \mid (n - a_1) \\ \Leftrightarrow b_i \times k = n - a_i(k \in \mathbb Z) \\ \Leftrightarrow n = b_i \times k + a_i \\ \Leftrightarrow n \equiv a_i \pmod {b_i} $$
裸的 CRT。
## 代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define int __int128
using namespace std;
inline int read()
{
int w = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
w = (w << 1) + (w << 3) + (ch ^ 48);
ch = getchar();
}
return w * f;
}
inline void write(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int maxk = 15;
int k, a[maxk], b[maxk];
int M = 1;
int c[maxk], inv[maxk];
int ans = 0;
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int d, x1 = 0, y1 = 0;
d = exgcd(b, a % b, x1, y1);
x = y1, y = x1 - a / b * y1;
return d;
}
void crt()
{
for (int i = 1; i <= k; i++)
{
c[i] = M / b[i];
}
for (int i = 1; i <= k; i++)
{
int x = 0, y = 0;
exgcd(c[i], b[i], x, y);
inv[i] = (x % b[i] + b[i]) % b[i];
}
for (int i = 1; i <= k; i++)
{
ans += (a[i] * c[i] * inv[i]) % M;
ans %= M;
}
}
signed main()
{
#ifndef ONLINE_JUDGE
#define LOCAL
//freopen("in.txt","r",stdin);
#endif
k = read();
for (int i = 1; i <= k; i++)
{
a[i] = read();
}
for (int i = 1; i <= k; i++)
{
b[i] = read();
M *= b[i];
}
crt();
write(ans);
puts("");
#ifdef LOCAL
fprintf(stderr, "%f\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
```