← 返回题目列表

AtCoder · abc445_e

E. 许多 LCM

中文机器翻译题面 查看原题

分数: 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.