#P5245. [Fjwc2018]欧拉函数

    ID: 4287 传统题 5000ms 512MiB 尝试: 133 已通过: 53 难度: 7 上传者: 标签>难度分类提高数论欧拉函数数据结构普通线段树位运算位集求并试除法分解质因数线性筛最小质因子预处理逆元线性递推CF2200作者未知

[Fjwc2018]欧拉函数

[Fjwc2018] 欧拉函数

题目描述

对正整数 xx,定义欧拉函数 φ(x)\varphi(x) 为不超过 xx 且与 xx 互质的正整数个数。例如 φ(1)=1\varphi(1)=1,φ(8)=4\varphi(8)=4。

给定正整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n,依次执行 qq 个操作:

  • 0 i x:将 aia_i 改为 xx。
  • 1 l r:查询 φ(al+al+1+⋯+ar)\varphi(a_l+a_{l+1}+\cdots+a_r) 对 109+710^9+7 取模的结果。
  • 2 l r:查询 φ(alal+1⋯ar)\varphi(a_l a_{l+1}\cdots a_r) 对 109+710^9+7 取模的结果。

输入格式

从标准输入读入。

第一行两个正整数 n,qn,q,表示序列长度和操作数。

第二行 nn 个正整数,表示初始序列。

接下来 qq 行,每行三个整数,表示一种操作。

输出格式

向标准输出对每次操作 1 或操作 2 写出一行,表示所求的值对 109+710^9+7 取模的结果。

样例

样例输入

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

样例输出

8
6
36
4
6
10
144

样例解释

操作 变化或查询
1 φ(3+5+7)=φ(15)=8\varphi(3+5+7)=\varphi(15)=8
2 序列变为 1,3,3,7,91,3,3,7,9
3 φ(1+3+3+7)=φ(14)=6\varphi(1+3+3+7)=\varphi(14)=6
4 φ(1×3×3×7)=φ(63)=36\varphi(1\times3\times3\times7)=\varphi(63)=36
5 序列变为 1,3,4,7,91,3,4,7,9
6 φ(1×3×4)=φ(12)=4\varphi(1\times3\times4)=\varphi(12)=4
7 序列变为 1,3,4,5,91,3,4,5,9
8 φ(4+5+9)=φ(18)=6\varphi(4+5+9)=\varphi(18)=6
9 φ(1+3+4+5+9)=φ(22)=10\varphi(1+3+4+5+9)=\varphi(22)=10
10 $\varphi(1\times3\times4\times5\times9)=\varphi(540)=144$

数据范围

n≤50000n\le50000,q≤100000q\le100000,1≤ai,x≤400001\le a_i,x\le40000。操作 0 的个数不超过 2000020000。

保证 1≤i≤n1\le i\le n,1≤l≤r≤n1\le l\le r\le n。所有初始 aia_i、修改操作中的 i,xi,x 以及查询中的 l,rl,r 均在给定限制内均匀随机生成。

来源

作者未知,本站付费获得。