1562 : 小白的数学题Ⅲ

时间限制:1 Sec 内存限制:256 MiB 提交:2 正确:2

提交 状态 论坛

题目描述

    众所周知，每年一道数学题是 WIT 新生赛的传统，小白无意之间发现了一个函数 f(x) ，现在他只知道函数 f(x) 是一个积性函数，以及对于任意质数 p 和正整数 k ，满足 f(p^k)=p^{k-1}(p+1) 。

    现在小白获得了一个长度为 n 的数组 a ，炮哥现在要问小白 q 个问题，每次询问炮哥会给出两个整数 l 和 r，保证 l \leq r ，然后炮哥想知道 f\left( \prod_{i=l}^{r} a_i \right) 的值是多少，小白看完后觉得这题太简单了，于是想请你来解决这个问题。由于答案可能过大，请将答案对 998244353 取模后输出。

    积性函数的定义：对于正整数 x 的一个算数函数 f(x) ，若 f(1)=1 ，且当 a 和 b 互质时有 f(ab)=f(a)f(b) ，那么这个函数在数论上就被称为积性函数。

输入描述

第一行输入两个整数 n 和 q(1 \leq n,q \leq 3 \times 10^5) ，表示数组的长度和询问的次数。

第二行输入 n 个数 a_1,a_2,a_3...a_n(1 \leq a_i \leq 10^6) ，表示这个数组。

接下来 q 行每行输入两个整数 l_i 和 r_i(1 \leq l_i \leq r_i \leq n) ，表示炮哥询问的区间。

输出描述

输出 q 行，每一行输出一个整数，表示询问的答案，由于答案可能过大，请将答案对 998244353 取模后输出。

样例输入

5 2
4 9 2 1 6
1 3
2 5

样例输出

144
216

提示

由于 \prod_{i=1}^{3} a_i=72 ，f(72)=144 ，所以第一个样例的答案是 144。

由于 \prod_{i=2}^{5} a_i=108 ，f(108)=216 ，所以第二个样例的答案是 216。

来源

WIT第七届新生赛