3280. 简单送分题

单点时限: 3.0 sec

内存限制: 256 MB

本题任务是计算

$$\varphi (a_1 a_2 \cdots a_n) \bmod 1~000~000~007$$

输入格式

第一行一个正整数 $n$ $(1 \leq n \leq 10^5)$。

接下来的一行是用空格隔开的 $n$ 个正整数,$a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^6)$。

输出格式

输出一行,表示答案。

样例

Input
1
8
Output
4
Input
2
2 4
Output
4
Input
3
2 4 1
Output
4
Input
6
1 1 1 1 1 1
Output
1
Input
6
666666 717171 666666 226 666666 999999
Output
521721323

提示

以下内容引自维基百科

在数论中,对正整数 $n$,欧拉函数 $\varphi (n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。例如:$\varphi (8)=4$,因为 $1,3,5,7$ 均和 $8$ 互质。

特例:$\varphi (1)=1$,小于等于 $1$ 的正整数中唯一和 $1$ 互质的数就是 $1$ 本身。

若 $n$ 是质数 $p$ 的 $k$ 次幂,$\varphi (n)=\varphi (p^{k})=p^{k}-p^{{k-1}}=(p-1)p^{k-1}$,因为除了 $p$ 的倍数外,其他数都跟 $n$ 互质。

欧拉函数是积性函数,即是说若 $m,n$ 互质,$\varphi (mn)=\varphi (m)\varphi (n)$。

欧拉函数的值可以用下面的公式表示:

$$\displaystyle \varphi(x) = x(1- \frac{1}{p_1})(1 - \frac{1}{p_2})(1 - \frac{1}{p_3}) \cdots (1 - \frac{1}{p_n})$$

其中 $p_1, p_2, \ldots, p_n$ 是 $x$ 的 $n$ 个质因子。

上面两个定理的证明略去,有兴趣可以自行搜索。

14 人解决,20 人已尝试。

19 份提交通过,共有 123 份提交。

5.8 EMB 奖励。

创建: 3 年,7 月前.

修改: 3 年,4 月前.

最后提交: 1 月,3 周前.

来源: 2017 ACM 「一场」测验赛

题目标签