洛谷 P3868 【猜数字】

题库：洛谷
题号：3868
题目：猜数字
link：https://www.luogu.com.cn/problem/P3868

思路：

由题意得$n$ $-$ $a[i]$ 整除 $b[i]$。

可以转化为$n$ $-$ $a[i]$ $=$ $b[i]$ $*$ $k$。

于是可得$n$ $-$ $a[i]$ $≡$ $0$ $(mod$ $b[i])$。

即$n$ $≡$ $a[i]$ $(mod$ $b[i])$。

因为题目中说$b[i]$两两互质，显而易见这是个裸的中国剩余定理。

这个题数据有点大，会爆$long$ $long$，所以将代码中的乘法改成这个就行了。

ll mul(ll a, ll b, ll m) {return (a * b - (ll)((long double)a * b / m) * m + m) % m;}

$code：$

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define ll long long
 4 using namespace std;
 5 ll n, ans, sum, M[110], x, y, t[110], m[110], a[110];
 6 ll mul(ll a, ll b, ll m) {return (a * b - (ll)((long double)a * b / m) * m + m) % m;}
 7 void exgcd(ll a, ll b, ll &x, ll &y)
 8 {
 9     if(!b) x = 1, y = 0;
10     else exgcd(b, a % b, y, x), y -= x * (a / b);
11     return;
12 }
13 int main()
14 {
15     scanf("%lld", &n);
16     sum = 1;
17     for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
18     for(int i = 1; i <= n; ++i) scanf("%lld", &m[i]), sum *= m[i];
19     for(int i = 1; i <= n; ++i) M[i] = sum / m[i];
20     for(int i = 1; i <= n; ++i) exgcd(M[i], m[i], x, y), t[i] = (x % m[i] + m[i]) % m[i];
21     for(int i = 1; i <= n; ++i) ans += mul(mul(a[i], t[i], sum), M[i], sum);
22     printf("%lld", (ans % sum + sum) % sum);
23     return 0;
24 }