洛谷 P3868 [TJOI2009]猜数字

思路

中国剩余定理 + 快速乘

题目要求找到最小的(nin N)，满足对于(forall iin [1,k])，有(b_i | (n-a_i))

我们试着来转化一下这个式子

(b_i|(n-a_i))，也就是说((n-a_i))在模(b_i)意义下同余(0)，即(n - a_iequiv 0( ext{mod} b_i))，进一步转化，就能得到(nequiv a_i( ext{mod} b_i))，转化到多个式子就是

[egin{equation} left{ egin{array}{lr} n equiv a_1 ( ext{mod} b_1)\ n equiv a_2 ( ext{mod} b_2)\……\ n equiv a_k ( ext{mod} b_k) end{array} ight. end{equation}]

这个式子是不是很眼熟？没错，就是中国剩余定理的式子，因为题目中已经保证了(b_i)两两互素，所以我们就可以直接套中国剩余定理的板子了

设(N=prod_{i=1}^nb_i)，(Mi=N/b_i)，(x_i)是线性同余方程(M_ix_i≡1( ext{mod} b_i))的一个解(即(Mi)的逆元)，最后的解即为(ans=sumlimits_{i=1}^ka_iM_ix_i)

那么这样就完了嘛？

~~此题终结~~其实不然

这样交上去之后，会发现只有九十分，最后一个点(WA)了，因为这题要用快速乘，于是写上快速乘

那么这样就完了嘛？

~~此题终结~~其实也不然

又交上去之后，发现还是九十分，不过这次错的点是第二个了。

这是为什么呢？

看题目条件：(∣a_i∣≤10^9)

什么意思呢？意思就是(a_i)可能是负的！（出题人真是用心良苦

处理的方法就是：快速乘传参时取模

那么这样就完了嘛？

~~兴冲冲的~~交上去，终于满分了，没错，这次真完了

代码

/*
Author:loceaner
中国剩余定理板子题 
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
	char c = getchar(); int x = 0, f = 1;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return x * f;
}

int n, N = 1, b[A], a[A], ans;

inline int mul(int n, int m, int mod) {
	int res = 0;
	while (m) {
		if (m & 1) res = (res + n) % mod;
		n = (n + n) % mod, m >>= 1;
	}
	return res;
}

inline void exgcd(int a, int b, int &x, int &y) {
	if (!b) x = 1, y = 0;
	else exgcd(b, a % b, y, x), y -= a / b * x;
}

signed main() {
	n = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= n; i++) b[i] = read(), N *= b[i];
	for (int i = 1; i <= n; i++) {
		int x, y, Mi = N / b[i];
		exgcd(Mi, b[i], x, y);
		ans = (ans + mul(mul(Mi, x % N + N, N), a[i] % N + N, N) % N + N) % N; 
	}
	cout << ans % N << '
';
	return 0;
}