[BOJ] 4355 - Relatives

문제 : https://www.acmicpc.net/problem/4355

---

[알고리즘풀이]

정수론 시간에 배운 Euler Phi Function(오일러 파이 함수)를 이용해서 답을 도출할 수 있었습니다.

오늘은 간략하게 설명하고, 다음에 오일러 파이 함수는 따로 포스팅을 해보도록 하겠습니다.

양의 정수 N이 다음과 같이 소인수분해가 된다고 한다면, 

N과 서로소인 수의 갯수 = Euler_Phi(N) 은 다음과 같습니다.

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

bool era[100001];

long long euler_phi(int n) {
	// 먼저 n을 소인수분해해야된다.
	vector<int> v, c;
	long long answer = 1;
	for (int i = 2; i <= 100000; i++) {
		if (era[i] == false && n % i == 0) {
			v.push_back(i);
			int count = 0;
			while (n % i == 0) {
				n /= i;
				count++;
			}
			c.push_back(count);
		}
	}
	
	for (int i = 0; i < v.size(); i++) {
		answer *= ((int)(pow(v[i], c[i])) - (int)(pow(v[i], c[i] - 1)));
	}
	if (n == 1)
		return answer;
	else
		return answer * (n - 1);
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 2; i <= 100000; i++) {
		if (era[i] == false) {
			for (int j = 2 * i; j <= 100000; j += i)
				era[j] = true;
		}
	}

	while (1) {
		int n;
		cin >> n;
		if (n == 0)
			return 0;
		cout << euler_phi(n) << '\n';
	}
}

---