标签 欧拉函数 下的文章

「Luogu 5106」dkw 的 lcm

题目链接：Luogu 5106

善良的 dkw 决定直接告诉你题面：

$$ \prod_{i_1 = 1} ^ n \prod_{i_2 = 1} ^ n \cdots\prod_{i_k = 1} ^ n \varphi(\operatorname{lcm}(i_1, i_2, \cdots, i_k)) $$

请你求上述式子，答案对 $10 ^ 9 + 7$ 取模。

其中 $\operatorname{lcm}(i_1, i_2, \cdots, i_k)$ 表示这 $k$ 个数的最小公倍数。特别地，一个数的 $\operatorname{lcm}$ 是自身。

数据范围：$1\le n,k\le 10^6$。

「Codeforces 594D」REQ

题目链接：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$。

「算法笔记」欧拉函数