LCM 卷积（LCM Convolution）

问题描述

给定两个长度为 $N$ 的整数序列 $a_1, a_2, \dots, a_N$ 和 $b_1, b_2, \dots, b_N$，
计算序列 $c_1, c_2, \dots, c_N$，其中：

$$c_k = \sum_{\substack{1 \le i, j \le N \\ \mathrm{lcm}(i, j) = k}} a_i \cdot b_j \bmod 998244353.$$

注意：下标从 1 开始；$\mathrm{lcm}(i,j)$ 表示 $i$ 与 $j$ 的最小公倍数。

约束条件

• $1 \leq N \leq 10^6$
• $0 \leq a_i, b_i < 998244353$

输入格式

$N$
$a_1\ a_2\ \cdots\ a_N$
$b_1\ b_2\ \cdots\ b_N$

输出格式

$c_1\ c_2\ \cdots\ c_N$

6
1 2 3 4 5 6
6 5 4 3 2 1

6 27 34 65 42 125