#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; }