2019年2月

Description

题目链接:BZOJ 2120

墨墨购买了一套 $n​$ 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令:

  • Q l r:询问从第 $l$ 支画笔到第 $r$ 支画笔中共有几种不同颜色的画笔。
  • R p c :把第 $p$ 支画笔替换为颜色 $c$。

数据范围:$1\le n,m\le 5\times 10^4$,$1\le c\le 10^6​$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 594D

今天的数学课上,老师告诉 Vovochka 正整数的欧拉函数 $\varphi(n)$ 是计算小于等于 $n$ 且与 $n$ 互质的正整数的函数,$1$ 和任意正整数互质所以 $\varphi(1)=1$。

现在老师给了 Vovochka 一个数列 $a_1,a_2,\dots,a_n$,要求回答 $q$ 个询问 $l_i,r_i$,计算 $\varphi\left(\prod_{i=l}^r a_i\right)$ 的值,答案对 $10^9 + 7$ 取模。这个问题对二年级学生来说太难了,所以你决定帮助 Vovochka。

数据范围:$1 \le n,q \le 2 \times 10 ^ 5$,$1 \le a_i \le 10 ^ 6$。

- 阅读剩余部分 -