#P7999. [2021年山东省队集训]欧拉函数

    ID: 8012 传统题 2000ms 512MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-欧拉函数普通线段树位集求并试除法分解质因数线性筛最小质因子预处理逆元线性递推全子集枚举

[2021年山东省队集训]欧拉函数

题目描述

记 1,2,...,n1, 2, . . . , n 中与 nn 互质的数的个数为 φ(n)\varphi (n)。

给定正整数序列 a1,a2,...,ana_1, a_2, . . . , a_n, 请依次执行 qq 个操作,操作有以下三种类型:

  1. 0 i x: 修改 aia_i 的值为 xx;
  2. 1 l r: 查询 φ(al+a(l+1)+⋯+ar)\varphi(a_l + a_{(l + 1)} + \cdots + a_r) 的值,对 109+710^9 + 7 取模后输出;
  3. 2 l r: 查询 $\varphi(a_l \times a_{(l + 1)} \times \cdots \times a_r)$ 的值,对 109+710^9 + 7 取模后输出;

输入格式

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

第二行 nn 个正整数 a1,a2,...,ana_1, a_2, . . . , a_n。

接下来 qq 行,每行三个整数 0 i x, 1 l r 或 2 l r。 保证 1≤i≤n1 ≤ i ≤ n, x∈N∗x ∈ N^* , 1≤l≤r≤n1 ≤ l ≤ r ≤ n。

输出格式

对于每次形如 1 l r 或 2 l r 的操作,输出一行表示答案。

样例 #1

样例输入 #1

5 10
1 3 5 7 9
1 2 4
0 3 3
1 1 4
2 1 4
0 3 4
2 1 3
0 4 5
1 3 5
1 1 5
2 1 5

样例输出 #1

8
6
36
4
6
10
144

提示

样例解释

初始序列为 1,3,5,7,91, 3, 5, 7, 9,依次进行的 1010 个操作如下:

  1. 查询 φ(3+5+7)=φ(15)=8φ(3 + 5 + 7) = φ(15) = 8,输出 88;
  2. 修改 a3a_3 的值为 33,此时的序列为 1,3,3,7,91, 3, 3, 7, 9;
  3. 查询 φ(1+3+3+7)=φ(14)=6φ(1 + 3 + 3 + 7) = φ(14) = 6,输出 66;
  4. 查询 φ(1×3×3×7)=φ(63)=36φ(1 × 3 × 3 × 7) = φ(63) = 36,输出 3636;
  5. 修改 a3a_3 的值为 4,此时的序列为 1,3,4,7,91, 3, 4, 7, 9;
  6. 查询 φ(1×3×4)=φ(12)=4φ(1 × 3 × 4) = φ(12) = 4,输出 44;
  7. 修改 a4a_4 的值为 55,此时的序列为 1,3,4,5,91, 3, 4, 5, 9;
  8. 查询 φ(4+5+9)=φ(18)=6φ(4 + 5 + 9) = φ(18) = 6,输出 66;
  9. 查询 φ(1+3+4+5+9)=φ(22)=10φ(1 + 3 + 4 + 5 + 9) = φ(22) = 10,输出 1010;
  10. 查询 φ(1×3×4×5×9)=φ(540)=144φ(1 \times 3 × 4 × 5 × 9) = φ(540) = 144,输出 144144。

数据范围

每个测试点的数据规模及特点如下表:

测试点编号 nn ai,xa_i,x qq 包含的操作类型
11 ≤5\leq 5 ≤10\leq 10 1
22
33 2
44
55 0,1,2
66 ≤500\leq 500 ≤1000\leq 1000 ≤1000\leq 1000
77
88 ≤5000\leq 5000 ≤10000\leq 10000 0,1
99 ≤5000\leq 5000
1010 ≤1000\leq 1000 0,1,2
1111 ≤3000\leq 3000
1212 ≤5000\leq 5000
1313 ≤50000\leq 50000 ≤40000\leq 40000 ≤50000\leq 50000 0,1
1414 ≤75000\leq 75000
1515 ≤100000\leq 100000
1616
1717 ≤25000\leq 25000 0,1,2
1818 ≤50000\leq 50000
1919 ≤100000\leq 100000
2020

表中“包含的操作类型”表示对应测试点中每个操作的第一个数的可能值,例如,包含的操作类型为“0,1”表示该测试点不会出现形如 2 l r 的操作。

对于全部测试点,n≤50000,q≤100000n ≤ 50000, q ≤ 100000,操作 00 的个数不超过 2000020000,所有的 aia_i、操作 00 中的 i,xi, x 及操作 1,21, 2 中的 l,rl, r 均在给定的限制下内均匀随机生成。