test/AOJ/NTL_1_D-Eulers-Phi-Function.test.cpp

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D"

#include <iostream>

#include "../../Math/Number-Theory/totient-func.hpp"

int main() {
    int n;
    std::cin >> n;
    std::cout << totient(n) << std::endl;

    return 0;
}

#line 1 "test/AOJ/NTL_1_D-Eulers-Phi-Function.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D"

#include <iostream>

#line 2 "Math/Number-Theory/totient-func.hpp"

/**
 * @brief totient() (オイラーのトーシェント関数)
 */
template <class Integer>
constexpr Integer totient(Integer n) {
    Integer ret = n;
    for (Integer i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ret -= ret / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n != 1) ret -= ret / n;
    return ret;
}
#line 6 "test/AOJ/NTL_1_D-Eulers-Phi-Function.test.cpp"

int main() {
    int n;
    std::cin >> n;
    std::cout << totient(n) << std::endl;

    return 0;
}