题解：P8178 「EZEC-11」Sequence

不难发现：

$$
f_i = A_if_0 + B_i
$$

其中 $A_i = \prod_{j = 1}^i a_j, B_i = \sum_{j=1}^i b_j \times \prod_{k=j+1}^i a_k$。是关于 $i$ 的常数。

那么条件就变成了：

$$
\left\{
\begin{matrix}
A_1f_0 + B_1 \equiv 0 \pmod {p_1} \\
A_2f_0 + B_2 \equiv 0 \pmod {p_2} \\
\vdots \\
A_if_0 + B_i \equiv 0 \pmod {p_i} \\
\vdots \\
A_nf_0 + B_n \equiv 0 \pmod {p_n} \\
\end{matrix}
\right.
$$

当 $A_i = 0$ 时，如果 $B_i \not \equiv 0 \pmod {p_i}$ 则无解，否则如果 $B_i \equiv 0 \pmod {p_i}$ 则无需考虑这个方程。

当 $A_i \ne 0$ 时，将方程变形：

$$
f_0 \equiv \dfrac{-B_i}{A_i} \pmod {p_i}
$$

因为 $p_i$ 是质数，方程右边是能用费马小定理算的。所以我们可以求出 $f_0$ 在模 $p_i$ 意义下的值。

若存在 $f_0$ 在同一个模数下的值不同，则无解。否则对于两个不同的模数，一定可以通过中国剩余定理的方式得到解。

```cpp
int n, a[N], b[N], p[N], A[N], B[N];

int fpm(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1, a = a * a % p;
	}
	return res;
}

bool solve() {
	cin >> n;
	
	for (int i = 1; i <= n; ++ i ) cin >> a[i];
	for (int i = 1; i <= n; ++ i ) cin >> b[i];
	for (int i = 1; i <= n; ++ i ) cin >> p[i];
	
	map<int, int> mp;
	for (int i = 1; i <= n; ++ i ) {
		A[0] = 1;
		for (int j = 1; j <= n; ++ j ) {
			A[j] = A[j - 1] * a[j] % p[i];
			B[j] = (a[j] * B[j - 1] % p[i] + b[j]) % p[i];
		}
		
		if (A[i] == 0) {
			if (B[i]) return false;
		}
		else {
			int y = (p[i] - B[i]) * fpm(A[i], p[i] - 2, p[i]) % p[i];
			if (mp.count(p[i]) && mp[p[i]] != y) return false;
			mp[p[i]] = y;
		}
	}
	
	return true;
}
```

正在渲染内容...