TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

85.0% (17/20)

Submission's AC Ratio

52.2% (48/92)

Tags

Description

《孟子•滕文公下•第六章》提到:

一齊人傅之,眾楚人咻之,雖日撻而求齊也,不可得矣

但是其實「一傅眾咻」的原本典故是出自《戰國策》的:馮諼在建立三窟之後,準備要繼續幫助孟嘗君!這件事於《史記·列傳·孟嘗君列傳》中也有記載,是「一傅眾咻」的第一個記載:為了繼續幫助孟嘗君選賢與能,馮諼出了一道會用到傅立葉轉換的題目,而來應徵食客的人全部都被嚇的「咻」一聲跑走了。在古籍中,也有記載那時候的題目,請你來解一解(題目皆已經從古文翻譯為現代的中文和記號):

給定兩個長度為$N$($N \leq 10^ 5$)的序列$\langle a_i \rangle$和$\langle b_i \rangle$,我們定義
$$c_i = \sum_{1 \leq j, k \leq N, \gcd(j, k) = i} a_jb_k$$
請算出$c_i$從$1$到$N$依序為多少!

Input Format

$N$
$a_1\; a_2 \;a_3\; \dots\; a_N$
$b_1\; b_2 \;b_3\; \dots\; b_N$

對於佔分$20 $分的測試資料,保證$N \leq 1000$、且對於另外佔$30$分的資料,有$N \leq 8000$。且對於所有的測試資料,皆滿足$1 \leq N \leq 10^ 5$,$-10^ 3 \leq a_i, b_j \leq 10^ 3$。

Output Format

請輸出$N$個數字,第$i$個數字代表$c_i$。

Sample Input

第一筆測試資料:
1
9
7
第一筆測試資料:
2
5 5
6 2
第三筆測試資料:
4
1 2 3 4
5 6 7 8

Sample Output

第一筆測試資料的答案:
63
第二筆測試資料的答案:
70 10
第三筆測試資料的答案:
155 52 21 32

Hints

對於第一筆測試資料,因為$\gcd(1, 1) = 1$,所以唯一一項$c_1 = a_1b_1 = 63$。
對於第二筆測試資料,$\gcd$為$1$的有:$(1, 2), (1, 1), (2, 1)$,所以$a_1b_2 + a_1b_1 + a_2b_1 = 10 + 30 + 30 = 70$,$\gcd$為$2$的有$(2, 2)$,所以$a_2b_2 = 10$。

Problem Source

by Seanliu

Subtasks

No. Testdata Range Constraints Score
1 0~10 $N \leq 1000$ 20
2 0~15 $N \leq 8000$ 30
3 0~25 $N \leq 100000$ 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2 3
1 1000 65536 262144 1 2 3
2 1000 65536 262144 1 2 3
3 1000 65536 262144 1 2 3
4 1000 65536 262144 1 2 3
5 1000 65536 262144 1 2 3
6 1000 65536 262144 1 2 3
7 1000 65536 262144 1 2 3
8 1000 65536 262144 1 2 3
9 1000 65536 262144 1 2 3
10 1000 65536 262144 1 2 3
11 1000 65536 262144 2 3
12 1000 65536 262144 2 3
13 1000 65536 262144 2 3
14 1000 65536 262144 2 3
15 1000 65536 262144 2 3
16 1000 65536 262144 3
17 1000 65536 262144 3
18 1000 65536 262144 3
19 1000 65536 262144 3
20 1000 65536 262144 3
21 1000 65536 262144 3
22 1000 65536 262144 3
23 1000 65536 262144 3
24 1000 65536 262144 3
25 1000 65536 262144 3