2313 . 小七的變身魔法
TopCoder
Tags
Description
小七是一位強大的魔法師，她可以變身成其他人的樣子。但是，變身成其他人會需要消耗自己的靈力才可以成功。
今天，她在路上看到了 $N$ 個人在路上，第 $i$ 個人可以用一個數字 $a_i$ 表示，而我們說兩個人相似若且唯若他們的數字不互質。
小七現在的樣貌可以用數字 $S$ 表示，並且如果 $S$ 與 $a_i$ 相似，則她可以花費 $b_i$ 的靈力把自己，也就是 $S$ 變成 $a_i$。
她想知道，對於每個人，如果透過一系列的變身變得跟第 $i$ 個人相似，至少需要花費多少靈力？如果無法變得跟第 $i$ 個人相似，請輸出 -1。
Input Format
第一行輸入一個數字 $N$，表示陣列長度
第二行輸入 $N$ 個數字 $a_1,a_2,\dots,a_N$
第三行輸入 $N$ 個數字 $b_1,b_2,\dots,b_N$
第四行輸入一個數字 $S$
對於所有測試資料：
- $1\le N \le 5 \times 10 ^ 4 $
- $1 \le a_i,S,b_i \le 10 ^ 9 $
Output Format
輸出 $N$ 個整數，分別表示 $S$ 變成與 $a_1,a_2,\dots,a_N$ 不互質分別所需的最小花費
Sample Input 1
7
2 4 10 6 7 14 11
1 2 4 8 16 32 64
3
2 4 10 6 7 14 11
1 2 4 8 16 32 64
3
Sample Output 1
8 8 8 0 40 8 -1
Hints
關於範測中，如果要將 $S$ 變得跟 $a_5$ 相似，則花費最少靈力的方法為：
因為 $\gcd(S,a_4) \ne 1$（$S$ 與 $a_4$ 相似），因此，可以先將 $S$ 變成 $6$，花費 $8$ 的靈力
接下來，因為 $S$ 與 $a_6$ 相似，因此將 $S$ 變成 $14$，花費 $32$ 的靈力。
現在 $S$ 與 $a_5$ 相似，總共花費 $8+32 = 40$ 的靈力。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 1~10 | $a_i,S$ 皆為質數 | 5 |
| 3 | 0~20 | $a_i,S$ 的因數至多只有四個 | 10 |
| 4 | 0, 21~30 | $N \le 1000$ | 15 |
| 5 | 0, 31~40, 63 | $a_i,S \le 10 ^ 6 $ | 45 |
| 6 | 0~64 | 無其他限制 | 25 |