单点时限: 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)$。
输出一行，表示答案。
1 8
4
2 2 4
4
3 2 4 1
4
6 1 1 1 1 1 1
1
6 666666 717171 666666 226 666666 999999
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$ 个质因子。
上面两个定理的证明略去，有兴趣可以自行搜索。