#P2920. 第2题-Tk的素区间

    ID: 2554 Tried: 28 Accepted: 5 Difficulty: 5 所属公司 : 阿里 时间 :2025年4月28日-阿里国际(算法岗)
      算法标签>前缀和质数筛

第2题-Tk的素区间

题目内容

TkTk 有一个长度为 nn 的数组 aaTkTk 定义 g(x)=i=1nx+1j=ii+x1ajg(x) = \sum_{i=1}^{n-x+1} \sum_{j=i}^{i+x-1} a_j,即所有区间长度为 xx 的区间和,TkTk 会向你询问 mm 次,每一次给你个区间 [l,r][l, r],你需要求出区间内所有素数 yy 对应 g(y)g(y) 的和,由于所求值可能比较大,你只需要告诉他答案对 998244353998244353 的取模结果即可。

输入描述