백준 19577번 C++ 풀이

문제

https://www.acmicpc.net/problem/19577

시간 제한	메모리 제한	solved.ac 티어
1초 (추가 시간 없음)	1024MB	플래티넘 5

---

풀이

 밀린 문제 정리하기, 그중에서도 오일러 피함수 두번째 문제이다.

 

 이번 문제는 대놓고 나 오일러 피함수요 하고 있다. 다만 형태가 좀 특별한데, x * phi(x) = n을 만족하는 x를 찾는 문제이다. n은 입력으로 주어진다. 우리는 이 식만으로 힌트를 얻을 수 있다. 우선, 오일러 피함수의 결과값은 무조건 자연수이다. 오일러 피함수의 정의가 phi(n) = (n 이하의 n과 서로소인 정수의 개수)이기 때문에, 무조건 자연수이다. x와 n, 그리고 phi(x)는 모두 자연수이기 때문에 phi(x) = n/x라는 식을 유도할 수 있고, n/x는 자연수여야만 한다. 오일러 피함수의 값이기 때문이다. 즉, x의 후보는 n의 인수임을 알 수 있다.

 

 n의 인수를 모두 찾은 후, 제일 작은 인수부터 값을 비교해가면서, 등식을 만족한다면 값을 출력하면 될 것이다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;
using ul = uint64_t;

int n;

ul euler_phi(int n) {
	ul res = n;

	for (int i = 2; i * i <= n; i++) {
		if (n % i) continue;

		res /= i;
		res *= (i - 1);
		while (n % i == 0) n /= i;
	}
	if (n != 1) {
		res /= n;
		res *= (n - 1);
	}

	return res;
}

void sol() {
	int tmp;
	vector<int> factor;

	for (int i = 1; i * i <= n; i++) {
		if (n % i) continue;
		factor.push_back(i);
		if (i != n / i) factor.push_back(n / i);
	}
	sort(ALL(factor));

	for (int& x : factor) {
		if (euler_phi(x) == n / x) {
			cout << x;
			return;
		}
	}
	cout << -1;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n;
	sol();
}