2377 . 小祥的生日禮物
TopCoder
Tags
Description
初華在小祥生日時送給小祥一個生日禮物。
小祥打開來發現裡面是一個長度為 $n$ 的非負整數陣列 $a$，小祥想要用陣列 $a$ 生成出另外一個陣列 $b$。
一開始 $b$ 是一個空陣列，並且 $1\sim n$ 都未標記。每次操作小祥會選一個未標記的整數 $i$（$1\le i\le n$），並且維護一個初始值為 $0$ 的整數 $s$，小祥會把所有在 $1\sim n$ 中為 $i$ 的倍數且未被標記的整數 $j$ 做標記，並且把 $s$ 加上 $a_j$，等到這次操作的標記都做完後，小祥會把 $s$ 加進陣列 $b$ 的後面。小祥會一直做操作直到 $1\sim n$ 都被標記了。
舉例來說，$n=5,a=[3,7,6,5,2]$，假設小祥第一次操作選的 $i=2$，那 $2,4$ 會被做上標記，並且 $s=a_2+a_4=12$，小祥會把 $12$ 加進陣列 $b$ 後面；第二次操作選的 $i=5$，$5$ 會被做上標記，並且 $s=a_5=2$，$2$ 會被加進 $b$ 後面；第三次操作選的 $i=1$，在 $1$ 的倍數中未標記的數字有 $1,3$，$1,3$ 會被做上標記且 $s=a_1+a_3=9$，$9$ 會被加進 $b$ 後面。因為 $1\sim 5$ 都被標記了，所以小祥會停止操作，並且得到一個長度為 $3$ 的陣列 $b$，$b=[12,2,9]$。
小祥很好奇她能生成出最大字典序的陣列 $b$ 是什麼，請你幫幫她！
Input Format
第一行有一個正整數 $n$。
第二行有 $n$ 個非負整數 $a_1\sim a_n$。
對於所有測試資料：
- $1\le n\le 10^ 5$
- $0\le a_i\le 10^ 4$（$1\le i\le n$）
Output Format
第一行輸出 $k$ 代表最大字典序陣列 $b$ 的長度。
第二行輸出 $k$ 個整數 $b_1\sim b_k$。
Sample Input 1
8
Sample Output 1
8
Sample Input 2
0 114
Sample Output 2
114 0
Sample Input 3
9999 0 1
Sample Output 3
10000
Hints
有兩個陣列 $A$ 與 $B$，$A$ 的字典序大於 $B$ 代表：$B$ 的長度小於 $A$ 且 $B$ 為 $A$ 的前綴，或是存在一個位置 $i$（$1\le i\le\min(|A|,|B|)$），使得 $A_j=B_j$（$1\le j<i$），且 $A_i\ \textgreater\ B_i$。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0, 3~6 | $a_i>0$（$1\le i\le n$） | 18 |
| 3 | 7~9 | $a_i=0$（$1\le i\le n$） | 18 |
| 4 | 0~1, 10~14 | 恰好有一個 $i$（$1\le i\le n$），使得 $a_i>0$ | 27 |
| 5 | 0~24 | 無其他限制 | 37 |