TopCoder

Caido
Waimai

User's AC Ratio

88.5% (23/26)

Submission's AC Ratio

55.6% (55/99)

Tags

Description

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

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

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

給定兩個長度為NN105)的序列aibi,我們定義
ci=1j,kN,gcd(j,k)=iajbk
請算出ci1N依序為多少!

Input Format

N
a1a2a3aN
b1b2b3bN

對於佔分20分的測試資料,保證N1000、且對於另外佔30分的資料,有N8000。且對於所有的測試資料,皆滿足1N105103ai,bj103

Output Format

請輸出N個數字,第i個數字代表ci

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,所以唯一一項c1=a1b1=63
對於第二筆測試資料,gcd1的有:(1,2),(1,1),(2,1),所以a1b2+a1b1+a2b1=10+30+30=70gcd2的有(2,2),所以a2b2=10

Problem Source

by Seanliu

Subtasks

No. Testdata Range Constraints Score
1 0~10 N1000 20
2 0~15 N8000 30
3 0~25 N100000 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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