#P5435. 基于值域预处理的快速 GCD

基于值域预处理的快速 GCD

题目背景

模板题,无背景。

题目描述

给定 nn 个正整数 a1,a2,,ana_1,a_2,\dots,a_n,再给定 nn 个正整数 b1,b2,,bnb_1,b_2,\dots,b_n,你需要对每对 (i,j)(i,j) 求出 aia_ibjb_j 的最大公因数。

不难发现你的输出应有 n2n^2 个正整数。为了减少输出对程序的运行效率的影响,你只需要输出 nn 行,每行一个整数 AiA_i

其中对于 i[1,n]i\in[1,n]Ai=j=1nijgcd(ai,bj)A_i=\sum_{j=1}^{n}i^j\gcd(a_i,b_j)。由于答案可能过大,你只需要输出模 998,244,353998,244,353 后的结果即可。

输入格式

第一行一个正整数 nn

第二行 nn 个正整数,表示 a1,a2,,ana_1,a_2,\dots,a_n

第三行 nn 个正整数,表示 b1,b2,,bnb_1,b_2,\dots,b_n

输出格式

nn 行,第 ii 行应输出一个非负整数 AiA_i。意义见题目描述。

5
200 300 300 300 23333
666 666 666 666 123456

16
564
3636
14328
3905

提示

对于 20%20\% 的数据,1n5001\leqslant n\leqslant 500

对于 100%100\% 的数据,$1\leqslant n\leqslant 5000;1\leqslant a_i,b_i\leqslant 10^6$。

请注意常数因子对程序运行效率的影响