P5694 - 怎样跑得更快

题目

P5694怎样跑得更快

限制 : 时间限制 : - MS 空间限制 : 262144 KB

评测说明 : 1s,256MB

大力水手问禅师：“大师，我觉得我光有力气是不够的。比如我吃菠菜可以让力气更大，但是却没有提升跑步的速度。请问怎样才能跑得更快？我试过吃白菜，没有效果。”

禅师浅笑，答：“方法很简单，不过若想我教你，你先看看这道UOJ Round的C题。”

令 $p = 998244353$（$7 \times 17 \times 2^{23} + 1$，一个质数）。

给你整数 $n, c, d$。现在有整数 $x_1, \dots, x_n$ 和 $b_1, \dots, b_n$ 满足 $0 \leq x_1, \dots, x_n, b_1, \dots, b_n < p$，且对于 $1 \leq i \leq n$ 满足：

\[ \begin{equation} \sum_{j = 1}^{n} \gcd(i, j)^c \cdot \mathrm{lcm}(i, j)^d \cdot x_j \equiv b_i \pmod{p} \end{equation} \]

其中 $v \equiv u \pmod{p}$ 表示 $v$ 和 $u$ 除以 $p$ 的余数相等。$\gcd(i, j)$ 表示 $i$ 和 $j$ 的最大公约数，$\mathrm{lcm}(i, j)$ 表示 $i$ 和 $j$ 的最小公倍数。

有 $q$ 个询问，每次给出 $b_1, \dots, b_n$，请你解出 $x_1, \dots, x_n$ 的值。

第一行四个整数 $n, c, d, q$。保证 $n, q \geq 1$。

接下来 $q$ 行，每行 $n$ 个整数依次表示 $b_1, \dots, b_n$。保证 $0 \leq b_1, \dots, b_n < p$。

共 $q$ 行，每行对给出的 $b_1, \dots, b_n$，输出对应的 $x_1, \dots, x_n$。如果有多组解输出任意一组即可。如果无解那么这一行只用输出一个整数 $-1$。

3 1 0 2
1 0 0
1 2 3

499122179 998244352 499122176
998244352 1 1

$nq \leq 3\times 10^5$ ， $0\leq c,d\leq 10^9$ 。

测试点编号	$n$	$q$	其他
1	$\leq 3$	$=1$	$c, d \leq 1000$
2	$\leq 100$	$=1$	$c = d$
3		$\leq 10$	保证有唯一解
4		$\leq 10$	保证有唯一解
5		$\leq 1000$	$c = 1, d = 0$
6			保证有唯一解
7
8
9	$\leq 1000$	$=1$	保证有唯一解
10
11
12		$\leq 10$	$c = d$
13			保证有唯一解
14			保证有唯一解
15	$\leq 10^5$	$\leq 3$	$c = 1, d = 0$
16			$c = 1, d = 0$
17			$c = d$
18			无
19
20

还没听完题，大力水手就嘶吼着：“太难了我不会我不会！”，飞快地跑掉了。

禅师看着大力水手消失的背影，叹了口气说：“你们这些人啊，每天就想做些大水题，一碰到难题，跑得不知道比谁都快。”

后来大力水手把UOJ Round的C题题面贴在了汽车的后挡风玻璃上，人类从此掌握了光速旅行的正确方式。