ACM模版

描述

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler’s totient function、φ函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。

Input
输入一个数N。(2 <= N <= 10^9)

Output
输出Phi(n)。

Input示例
8

Output示例
4

题解

因为2 <= N <= 10^9，所以需要用到公式直接单独求解。

代码

#include <iostream>
#include <cmath>

using namespace std;

long long euler(long long x)
{
    long long i, res = x;
    for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
    {
        if (!(x % i))
        {
            res = res / i * (i - 1);
            while (!(x % i))
            {
                x /= i;     // 保证i一定是素数
            }
        }
    }
    if (x > 1)
    {
        res = res / x * (x - 1);
    }
    return res;
}

int main(int argc, const char * argv[])
{
    long long N;
    while (cin >> N)
    {
        cout << euler(N) << '\n';
    }
    return 0;
}

参考

欧拉函数PHI