test/phi.test.cpp

View this file on GitHub
Last update: 2024-03-03 06:51:22+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D

Depends on

Euler's Phi-function (C++/math/euler_phi.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D"
#include <iostream>
#include "C++/math/euler_phi.hpp"
int main() {
    long n;
    std::cin >> n;
    std::cout << euler_phi(n) << '\n';
}

#line 1 "test/phi.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D"
#include <iostream>
#line 2 "C++/math/euler_phi.hpp"
template <class T> inline T euler_phi(T n) {
	T res = n;
	for(T i = 2; i * i <= n; ++i) {
	    if(n % i == 0) {
			res -= res / i;
			while(n % i == 0) {
				n /= i;
			}
		}
	}
	if(n > 1) {
		res -= res / n;
	}
	return res;
}

/**
 * @brief Euler's Phi-function
 */
#line 4 "test/phi.test.cpp"
int main() {
    long n;
    std::cin >> n;
    std::cout << euler_phi(n) << '\n';
}