9031: [yosupo] Convolution - Lcm Convolution
[Creator : ]
Description
Given integer sequences $a_1, ..., a_{N}$ and $b_1, ..., b_{N}$.
Calculate an integer sequence $c_1, ..., c_{N}$ as follows:
$c_k = \sum_{\mathrm{lcm}(i,j)=k} a_ib_j \bmod 998244353$
Calculate an integer sequence $c_1, ..., c_{N}$ as follows:
$c_k = \sum_{\mathrm{lcm}(i,j)=k} a_ib_j \bmod 998244353$
Input
$N$
$a_1$ ... $a_{N}$
$b_1$ ... $b_{N}$
$a_1$ ... $a_{N}$
$b_1$ ... $b_{N}$
Output
$c_1$ ... $c_{N}$
Constraints
$1 \leq N \leq 10^6$
$0 \leq a_i, b_i < 998244353$
$0 \leq a_i, b_i < 998244353$
Sample 1 Input
6
1 2 3 4 5 6
6 5 4 3 2 1
Sample 1 Output
6 27 34 65 42 125