题目 30018

最大公约数卷积

查看题解 ↗GitHub ↗如何评测
题号
30018
时间限制
10000 ms
内存限制
1024 MB
标签
数学
来源
Library Checker (yosupo06) - gcd_convolution

【题目描述】

给定整数序列 a1,...,aNa_1, ..., a_{N} 和 b1,...,bNb_1, ..., b_{N}。按如下方式计算整数序列 c1,...,cNc_1, ..., c_{N}:

ck=∑gcd⁡(i,j)=kaibj mod 998244353c_k = \sum_{\gcd(i,j)=k} a_ib_j \bmod 998244353

【输入】

文本
$N$
$a_1$ ... $a_{N}$
$b_1$ ... $b_{N}$

【输出】

文本
$c_1$ ... $c_{N}$

【输入样例】

文本
6
1 2 3 4 5 6
6 5 4 3 2 1

【输出样例】

文本
284 90 39 12 10 6

【数据范围】

  • 1≤N≤10000001 \leq N \leq 1000000
  • 0≤ai,bi<9982443530 \leq a_i, b_i < 998244353

【来源】

Library Checker(yosupo06) gcd_convolution

数据下载

题目 30018 的公开数据

正在读取文件列表…

常用命令

题目 30018 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。