3280. 简单送分题

单点时限: 3.0 sec

内存限制: 256 MB

本题任务是计算

输入格式

第一行一个正整数

接下来的一行是用空格隔开的 个正整数,

输出格式

输出一行,表示答案。

样例

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

提示

以下内容引自维基百科

在数论中,对正整数 ,欧拉函数 是小于或等于 的正整数中与 互质的数的数目。例如:,因为 均和 互质。

特例:,小于等于 的正整数中唯一和 互质的数就是 本身。

是质数 次幂,,因为除了 的倍数外,其他数都跟 互质。

欧拉函数是积性函数,即是说若 互质,

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

其中 个质因子。

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

13 人解决,19 人已尝试。

18 份提交通过,共有 56 份提交。

5.6 EMB 奖励。

创建: 2 年,5 月前.

修改: 2 年,2 月前.

最后提交: 10 月前.

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

题目标签