P12524 [Aboi Round 1] I なんです
题目背景
题目描述
有一个长度为 $n$ 的序列 $\{a\}$，$q$ 次询问，每次给你一个区间 $[l,r]$，求该区间内所有长度为奇数的子序列的 $\gcd$ 的平方之积，答案对 $998244353$ 取模。
输入格式
第一行两个正整数 $n,q$。
第二行 $n$ 个正整数 $a_i$。
之后 $q$ 行，每行两个正整数 $l,r$。
输出格式
对于每次询问，输出对应的答案。
说明/提示
对于 $100\%$ 的数据，$1\leq n,q,a_i\leq10^5$。
本题采用捆绑测试，你需要通过一个子任务的所有测试点才能得到该子任务的分数。
| 子任务编号 | $n$ | $q$ | $a_i$ | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $\le20$ | $\le20$ | $\le10^5$ | / | $10$ |
| $2$ | $\le10^3$ | $\le10^3$ | $\le10^5$ | / | $10$ |
| $3$ | $\le3\times10^4$ | $\le3\times10^4$ | $\le10^5$ | / | $10$ |
| $4$ | $\le10^5$ | $\le10^5$ | $\le10^5$ | $\text{A}$ | $5$ |
| $5$ | $\le10^5$ | $\le10^5$ | $\le300$ | / | $10$ |
| $6$ | $\le10^5$ | $\le10^5$ | $\le10^5$ | / | $55$ |
特殊性质 $\text{A}$：所有 $a_i$ 均相同。