[Gold / 11689] GCD（n， k） ＝ 1

문제 링크

---

🔷 분류

수학, 정수론, 오일러 피 함수

✒️ 문제 설명

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

⬅️ 입력

첫째 줄에 자연수 n (1 ≤ n ≤ 10¹²)이 주어진다.

➡️ 출력

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

💻 코드 (C++)

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	long n;
	cin >> n;
	long ans = n;
	
	for(long i = 2; i <= sqrt(n); i++) {
		if(n % i == 0) { // 소인수면
			ans -= ans / i; // 답 줄이기
			while(n % i == 0) n /= i; // 소인수 지우기
		}
	}
	
	if(n > 1) ans -= ans / n;
	cout << ans;	
}