문제 간략 설명

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n의 개수를 구하는 프로그램을 작성하시오.

풀이 방법

오일러 파이 함수(Euler's totient function)를 이용한다. n을 소인수분해하여 각 소인수 p에 대해 res = res - res/p 공식을 적용한다. 초기값은 n으로 설정하고, 소인수를 찾을 때마다 이 공식을 적용한다.

코드

#include <iostream>
#include <vector>

using namespace std;

long long N;
long long res;
vector<long long> vec;

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	res = N;

	for (long long i = 2; i * i <= N; i++) {
		if (N % i == 0) {
			vec.push_back(i);
			while (N % i == 0) N /= i;
		}
	}

	for (int i = 0; i < vec.size(); i++)
		res -= res / vec[i];

	if (N > 1)
		res -= res / N;

	cout << res << '\\n';

	return 0;
}

Key Points