seuOJ305 - Mental Out

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：2000 ms
• 空间限制：256 MiB
• 题目标签：秋季, 校赛, 2020

题目描述

Misaki的能力是「心理掌控」。

她能了解每一个Sister对Mikoto的好感度$a$。

她的手提袋里有一把遥控器，能将一个Sister的好感度由$a$变为$f(a)$。

在调查Sister情报的时候，Misaki遇到了$n$个Sister。这$n$个Sister的标号从$1$到$n$，第$i$个Sister对Mikoto的好感度为$a_i$。

于是Misaki想要：

• 对某段区间$[l,r]$内的Sister使用遥控器攻击；

• 算出某段区间$[l,r]$内的Sister对Mikoto好感度的乘积。

这对于Level 5的Misaki来说自然不是问题，但你能做到吗？

形式化描述如下：

对于正整数$i\geq 2$，定义$f(i)$为除了本身以外$i$的最大因子，如$f(12)=6$，$f(2)=1$。特别地，定义$f(0)=0,f(1)=1$。

给定一个数列$a$，你需要完成$m$个操作，每个操作为以下$2$种之一：

操作$1$：将所有满足$l\leq i \leq r$的$a_i$改为$f(a_i)$；

操作$2$：求所有满足$l\leq i \leq r$的$a_i$的积对$10^9+7$取模后的结果。

输入格式

输入的第一行为$1$个整数$n(1\leq n\leq 2\times10^5)$，表示数列的长度。

接下来一行包含$n$个正整数，第$i$个数字表示数列$a$第$i$项的初值$a_i(1\leq a_i\leq 2\times10^7)$。

接下来一行包含$1$个整数$m(1\leq m\leq 2\times10^5)$，表示操作个数

接下来$m$行，每行包含$3$个整数$op,l,r(op\in\{1,2\}, 1\leq l \leq r \leq n)$，分别表示操作类型和区间范围，具体描述如下：

• $op=1$时，输入格式为$1\ l\ r$，表示将所有满足$l\leq i \leq r$的$a_i$改为$f(a_i)$
• $op=2$时，输入格式为$2\ l\ r$，表示求所有满足$l\leq i \leq r$的$a_i$的积对$10^9+7$取模后的结果。

输出格式

对于每个操作$2$，输出一行包含一个整数，表示这个询问的答案。

样例

样例输入

5
1 2 3 4 5
3
2 1 5
1 1 5
2 1 5

样例输出

120
2

样例解释

在操作$1\ 1\ 5$之后，数组$a=[1\ 1\ 1\ 2\ 1]$。