CF594D REQ

今天在数学课上，老师告诉 Vovochka，正整数 $φ(n)$ 的欧拉函数是一个算术函数，用于统计小于等于 $n$ 且与 $n$ 互质的正整数的数量。数字 $1$ 与所有正整数互质，且 $φ(1)=1$。 现在老师给了 Vovochka 一个长度为 $n$ 的正整数数组 $a_1, a_2, ..., a_n$，并布置了一个处理 $q$ 个询问 $l_i$ $r_i$ 的任务——对于每个询问，计算并输出区间 $[l_i, r_i]$ 上所有数连乘所得结果的欧拉函数值，即 $φ(a_{l_i} · a_{l_i+1} · ... · a_{r_i})$，并对 $10^9+7$ 取模。由于这对二年级学生来说太难了，你决定帮助 Vovochka 完成这个任务。

第一行输入一个整数 $n$（$1 \leq n \leq 200000$），表示 Vovochka 得到的数组的长度。 第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$（$1\leq a_i \leq 10^6$）。 第三行输入一个整数 $q$（$1 \leq q \leq 200000$），表示询问的数量。 接下来 $q$ 行，每行两个整数，表示一次询问的区间边界 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）。

输出 $q$ 行，每行一个整数，分别表示每次询问所得区间乘积的欧拉函数值，对 $10^9+7$ 取模后的结果。

对于第二组样例，欧拉函数的计算方式如下： - $φ(13·52·6)=φ(4056)=1248$ - $φ(52·6·10·1)=φ(3120)=768$ - $φ(24·63·13·52·6·10·1)=φ(61326720)=12939264$ - $φ(63·13·52)=φ(42588)=11232$ - $φ(13·52·6·10)=φ(40560)=9984$ - $φ(63·13·52·6·10)=φ(2555280)=539136$ 由 ChatGPT 5 翻译