[Aboi Round 1] I なんです

ID: 13552

远端评测题

1000ms

128MiB

难度: 6

上传者:

标签>

莫队

O2优化

根号分治

题目背景

有一个长度为 $n$ 的序列 $\{a\}$ ， $q$ 次询问，每次给你一个区间 $[l,r]$ ，求该区间内所有长度为奇数的子序列的 $\gcd$ 的平方之积，答案对 $998244353$ 取模。

第一行两个正整数 $n,q$ 。

第二行 $n$ 个正整数 $a_i$ 。

之后 $q$ 行，每行两个正整数 $l,r$ 。

对于每次询问，输出对应的答案。

10 5
1 3 5 2 4 6 8 8 8 10
1 3
5 7
3 6
8 10
7 10

10 5
2 2 2 2 2 2 2 2 2 2
1 2
1 4
1 5
1 6
1 7

对于 $100\%$ 的数据， $1\leq n,q,a_i\leq10^5$ 。

本题采用捆绑测试，你需要通过一个子任务的所有测试点才能得到该子任务的分数。

子任务编号	$n$	$a_i$	特殊性质	分值
$1$	$\le20$	$\le10^5$	/	$10$
$2$	$\le10^3$
$3$	$\le3\times10^4$
$4$	$\le10^5$		$\text{A}$	$5$
$5$		$\le300$	/	$10$
$6$		$\le10^5$	/	$55$

特殊性质 $\text{A}$ ：所有 $a_i$ 均相同。