2176 . 一傅眾咻
TopCoder
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
1
9
7
第一筆測試資料：
2
5 5
6 2
第三筆測試資料：
4
1 2 3 4
5 6 7 8
Sample Output 1
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 |