/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
k=1,2,\dots,N について、A のうち A_k を除いた N-1 個の要素の最小公倍数を 998244353 で割ったあまりを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^7
- 入力はすべて整数
- 1 つの入力に含まれるテストケースについて、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 番目のテストケースに対する出力を意味する。 各テストケースに対しては、以下の通り出力せよ。
A のうち A_k を除いた N-1 個の要素の最小公倍数を 998244353 で割ったあまりが L_k であるとする。 このとき以下の形式で出力せよ。
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
一個目のテストケースについて、以下のようになります。
- A のうち A_1 を除いた N-1 個の要素は 12,25,8,15 であり、これらの最小公倍数は 600 です。
- A のうち A_2 を除いた N-1 個の要素は 9,25,8,15 であり、これらの最小公倍数は 1800 です。
- A のうち A_3 を除いた N-1 個の要素は 9,12,8,15 であり、これらの最小公倍数は 360 です。
- A のうち A_4 を除いた N-1 個の要素は 9,12,25,15 であり、これらの最小公倍数は 900 です。
- A のうち A_5 を除いた N-1 個の要素は 9,12,25,8 であり、これらの最小公倍数は 1800 です。
Score : 475 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N.
For each k=1,2,\dots,N, find the remainder when the least common multiple of the N-1 elements of A excluding A_k is divided by 998244353.
You are given T test cases; solve each of them.
Constraints
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^7
- All input values are integers.
- The sum of N over all test cases in a single input is at most 2 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Here, \mathrm{case}_i denotes the input for the i-th test case. Each test case is given in the following format:
N A_1 A_2 \cdots A_N
Output
Output in the following format:
\mathrm{answer}_1
\mathrm{answer}_2
\vdots
\mathrm{answer}_T
Here, \mathrm{answer}_i denotes the output for the i-th test case. For each test case, output as follows.
Let L_k be the remainder when the least common multiple of the N-1 elements of A excluding A_k is divided by 998244353. Then, output in the following format:
L_1 L_2 \cdots L_N
Sample Input 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
Sample Output 1
600 1800 360 900 1800 447582749 506009091 523568328 588652065 196217355 471970745 921220985 738745385 747032704 756838459 344127037 146466685 159487731 555429485 826726159 884617928 322846201 298477407
For the first test case, the following holds.
- The N-1 elements of A excluding A_1 are 12,25,8,15, and their least common multiple is 600.
- The N-1 elements of A excluding A_2 are 9,25,8,15, and their least common multiple is 1800.
- The N-1 elements of A excluding A_3 are 9,12,8,15, and their least common multiple is 360.
- The N-1 elements of A excluding A_4 are 9,12,25,15, and their least common multiple is 900.
- The N-1 elements of A excluding A_5 are 9,12,25,8, and their least common multiple is 1800.