[Fjwc2018] 欧拉函数
题目描述
对正整数 x,定义欧拉函数 φ(x) 为不超过 x 且与 x 互质的正整数个数。例如 φ(1)=1,φ(8)=4。
给定正整数序列 a1,a2,…,an,依次执行 q 个操作:
0 i x:将 ai 改为 x。
1 l r:查询 φ(al+al+1+⋯+ar) 对 109+7 取模的结果。
2 l r:查询 φ(alal+1⋯ar) 对 109+7 取模的结果。
输入格式
从标准输入读入。
第一行两个正整数 n,q,表示序列长度和操作数。
第二行 n 个正整数,表示初始序列。
接下来 q 行,每行三个整数,表示一种操作。
输出格式
向标准输出对每次操作 1 或操作 2 写出一行,表示所求的值对 109+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 |
| 2 |
序列变为 1,3,3,7,9 |
| 3 |
φ(1+3+3+7)=φ(14)=6 |
| 4 |
φ(1×3×3×7)=φ(63)=36 |
| 5 |
序列变为 1,3,4,7,9 |
| 6 |
φ(1×3×4)=φ(12)=4 |
| 7 |
序列变为 1,3,4,5,9 |
| 8 |
φ(4+5+9)=φ(18)=6 |
| 9 |
φ(1+3+4+5+9)=φ(22)=10 |
| 10 |
$\varphi(1\times3\times4\times5\times9)=\varphi(540)=144$ |
数据范围
n≤50000,q≤100000,1≤ai,x≤40000。操作 0 的个数不超过 20000。
保证 1≤i≤n,1≤l≤r≤n。所有初始 ai、修改操作中的 i,x 以及查询中的 l,r 均在给定限制内均匀随机生成。
来源
作者未知,本站付费获得。