#P4802. 欧拉函数

    ID: 3919 传统题 1000ms 256MiB 尝试: 2039 已通过: 390 难度: 6 上传者: 标签>难度分类提高+/省选-数论欧拉函数Miller–RabinPollard–Rho快速幂快速乘防溢出枚举与搜索快慢指针CF2100ByFancyCoder

欧拉函数

题目描述

给定正整数 nn,求它的欧拉函数值 φ(n)\varphi(n)。φ(n)\varphi(n) 表示 11 到 nn 中与 nn 互质的整数个数。

输入格式

从标准输入读入一行一个正整数 nn,满足 1≤n≤10181\le n\le 10^{18}。

输出格式

向标准输出写入一行一个正整数 φ(n)\varphi(n)。

样例

8
4