P5435 Fast GCD Based on Value-Range Preprocessing

Given $n$ positive integers $a_1,a_2,\dots,a_n$, and another $n$ positive integers $b_1,b_2,\dots,b_n$, you need to compute the greatest common divisor of $a_i$ and $b_j$ for every pair $(i,j)$. It is not hard to see that the output should contain $n^2$ positive integers. To reduce the impact of output on the program’s running efficiency, you only need to output $n$ lines, with one integer $A_i$ per line. For $i\in[1,n]$, $A_i=\sum_{j=1}^{n}i^j\gcd(a_i,b_j)$. Since the answer may be too large, you only need to output the result modulo $998,244,353$.

The first line contains one positive integer $n$. The second line contains $n$ positive integers, representing $a_1,a_2,\dots,a_n$. The third line contains $n$ positive integers, representing $b_1,b_2,\dots,b_n$.

Output $n$ lines. The $i$-th line should contain one non-negative integer $A_i$. Its meaning is described in the statement.

For $20\%$ of the testdata, $1\leqslant n\leqslant 500$. For $100\%$ of the testdata, $1\leqslant n\leqslant 5000;1\leqslant a_i,b_i\leqslant 10^6$. **Please pay attention to the impact of constant factors on the program’s running efficiency.** Translated by ChatGPT 5