分数: 475 点
问题陈述
给你一个正整数序列 A=(A_1,A_2,\dots,A_N) 长度 N.
对于每个 k=1,2,\dots,N,求最小公倍数时的余数 N-1 的元素 A 不包括 A_k 除以 998244353.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^7
- 所有输入值均为整数。
- 总和 N 单个输入中的所有测试用例最多 2 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里, \mathrm{case}_i 表示输入 i- 第一个测试用例。每个测试用例均按以下格式给出:
N A_1 A_2 \cdots A_N
输出
按以下格式输出:
\mathrm{answer}_1
\mathrm{answer}_2
\vdots
\mathrm{answer}_T
在这里, \mathrm{answer}_i 表示输出 i- 第一个测试用例。 对于每个测试用例,输出如下。
让 L_k 为最小公倍数时的余数 N-1 的元素 A 不包括 A_k 除以 998244353。 然后,按以下格式输出:
L_1 L_2 \cdots L_N
示例输入 1
3 5 9 12 25 8 15 8 592 26 167 912 171 321 327 651 10 9566582 2785103 1924635 359502 6912831 4893928 2820155 5071742 1836019 9037883
示例输出 1
600 1800 360 900 1800 447582749 506009091 523568328 588652065 196217355 471970745 921220985 738745385 747032704 756838459 344127037 146466685 159487731 555429485 826726159 884617928 322846201 298477407
对于第一个测试用例,以下内容成立。
- 的 N-1 的元素 A 不包括 A_1 是 12,25,8,15,它们的最小公倍数是 600.
- 的 N-1 的元素 A 不包括 A_2 是 9,25,8,15,它们的最小公倍数是 1800.
- 的 N-1 的元素 A 不包括 A_3 是 9,12,8,15,它们的最小公倍数是 360.
- 的 N-1 的元素 A 不包括 A_4 是 9,12,25,15,它们的最小公倍数是 900.
- 的 N-1 的元素 A 不包括 A_5 是 9,12,25,8,它们的最小公倍数是 1800.