8376: 【模板题】 基于值域预处理的快速 GCD
[Creator : ]
Description
给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$，再给定 $n$ 个正整数$b_1,b_2,\dots,b_n$，你需要对每对 $(i,j)$ 求出 $a_i$ 与 $b_j$ 的最大公因数。
不难发现你的输出应有 $n^2$ 个正整数。为了减少输出对程序的运行效率的影响，你只需要输出 $n$ 行，每行一个整数 $A_i$。
其中对于 $i\in[1,n]$，$A_i=\sum_{j=1}^{n}i^j\gcd(a_i,b_j)$。由于答案可能过大，你只需要输出模 $998,244,353$ 后的结果即可。
不难发现你的输出应有 $n^2$ 个正整数。为了减少输出对程序的运行效率的影响，你只需要输出 $n$ 行，每行一个整数 $A_i$。
其中对于 $i\in[1,n]$，$A_i=\sum_{j=1}^{n}i^j\gcd(a_i,b_j)$。由于答案可能过大，你只需要输出模 $998,244,353$ 后的结果即可。
Input
第一行一个正整数 $n$。
第二行 $n$ 个正整数，表示 $a_1,a_2,\dots,a_n$。
第三行 $n$ 个正整数，表示 $b_1,b_2,\dots,b_n$。
第二行 $n$ 个正整数，表示 $a_1,a_2,\dots,a_n$。
第三行 $n$ 个正整数，表示 $b_1,b_2,\dots,b_n$。
Output
共 $n$ 行，第 $i$ 行应输出一个非负整数 $A_i$。意义见题目描述。
Constraints
对于 $100\%$ 的数据，$1\leqslant n\leqslant 5000;1\leqslant a_i,b_i\leqslant 10^6$。
请注意常数因子对程序运行效率的影响
请注意常数因子对程序运行效率的影响
Sample 1 Input
5
200 300 300 300 23333
666 666 666 666 123456
Sample 1 Output
16
564
3636
14328
3905