1438 . 方塊酥
TopCoder
Tags
Description
小方塊當上 IOIC 總召後，決定拿出他珍藏的方塊酥請大家吃。
對於一個正整數 $n$，「一個尺寸為 $n$ 的方塊酥」為一個邊長為 $n$ 的正方體，且其可以被切成若干個尺寸為 $d$ 的方塊酥若且唯若 $n$ 是 $d$ 的倍數。
小方塊發現自己的家裡有 $q$ 盒方塊酥，其中對於 $1\leq i\leq q$，第 $i$ 盒方塊酥中恰有所有「尺寸為 $a_i$ 的因數」的方塊酥各一個（也就是那些可以由「尺寸為 $a_i$ 的方塊酥」切出來的尺寸），並記第 $i$ 盒中的方塊酥數量為 $c_i$。
例如若 $a_1 = 6$，則第 $1$ 盒中共有 $c_1 = 4$ 個方塊酥，尺寸分別為 $1, 2, 3, 6$。
小方塊決定拆封前 $k$ 盒方塊酥，並從這 $\sum_{i=1}^ k c_i$ 個方塊酥中挑出其中若干個（至少一個）來請客，若有剩下的則自己吃，故總共有 $2^ {\sum_{i=1}^ k c_i} - 1$ 種請客方案。因為小方塊為人方正，為了公平起見，他在請客前會將所挑選的方塊酥都切成一樣的尺寸 $d$，並讓 $d$ 儘量大好讓大家吃得過癮（即 $d$ 為所有「挑選的方塊酥的尺寸」的最大公因數）。此時的滿足度就會是 $d^ 3$，即每塊方塊酥的體積。
對於每一個 $1\leq k\leq q$，小方塊想要知道「拆封前 $k$ 盒方塊酥」的前提下，所有請客方案的滿足度總和 $ans_k$。但總召還在忙著籌備營隊，所以他把任務交給了你，請幫他計算 $ans_k \mod 998244353$。
Input Format
第一行恰有一個整數 $T$，表示測試資料的總筆數。
對於每個測試資料，輸入共有兩行：第一行有一個正整數 $q$，表示操作次數；第二行有 $q$ 個正整數 $a_1, a_2, \cdots, a_q$
- $1\leq q\leq 5\times 10^ 5$
- $1\leq a_i\leq 2\times 10^ 6$
- $T$ 個 $q$ 的總和 $\sum q \leq 5\times 10^ 5$
Output Format
對於每筆測試資料，請輸出 $q$ 行。其中第 $k$ 行恰有一個非負整數「$ans_k\mod 998244353$」。
Sample Input 1
4 3 1 2 3 10 2 3 7 5 7 7 2 5 5 3 5 1024 2048 2 4 8 6 30 30 30 30 30 30
Sample Output 1
1 14 64 10 48 438 754 2206 6646 18948 68348 265452 1051936 433411071 505413611 545259499 897581035 989855718 38000 237384 17847368 313707268 614293307 672953108
Sample Input 2
1 10 377892 294472 883711 1877693 335590 1591474 1834375 1399638 313329 184792
Sample Output 2
429480889 56915356 529357707 340414769 744955307 220381009 890110533 10385507 847028477 56067770
Hints
Sample Input 1 的第一筆測資中
- $k=1$ 時只有一個尺寸為 $1$ 的方塊酥，故只有 $2^ 1 - 1 = 1$ 種請客方案，滿足度為 $1^ 3 = 1$。
- 當 $k = 2$，前兩盒共有 $3$ 個方塊酥，尺寸分別為 $1, 1, 2$，並有 $2^ 3 - 1 = 7$ 種請客方案。其中只有「只選擇尺寸為 $2$ 的方塊酥」這個方案的滿足度為 $2^ 3 = 8$，其他 $6$ 種方案的滿足度皆為 $1$，故 $ans_2 = 8\times 1 + 1 \times 6 = 14$。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例輸入。 | 0 |
| 2 | 2~4 | $a_1 = \cdots = a_q \leq 500$（但 $T$ 筆測資的 $a_1$ 不一定相同） | 9 |
| 3 | 5~7 | $a_k$ 皆為 $2$ 的冪次（包含 $1$）。 | 8 |
| 4 | 8~10 | $a_k$ 皆為質數。 | 7 |
| 5 | 0~17 | 無特別限制。 | 76 |