[C/C++] 백준 19577번 - 수학은 재밌어

✏️ 문제 링크

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

19577번: 수학은 재밌어

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

오일러 피 함수 문제에서 xφ(x) = n을 만족해야 한다는 조건이 추가되었습니다.

φ(x)의 값은 무조건 정수이기 때문에 x는 n의 약수여야 합니다. 사실 어찌보면 당연할 수도 있습니다.

여기서 얻을 수 있는 힌트는, n의 약수에 대해서만 φ(x)을 구해서 xφ(x)=n인지만 확인하면 됩니다.

정리를 해보자면 주어진 n에 대해서 n의 약수를 모두 구한 뒤, 각 약수들에 대한 xφ(x)을 n과 비교하기

 

총 함수는 두 개를 만들 수 있습니다. 먼저 소인수분해를 해주는 함수와 φ(x)를 구하는 함수입니다.

소인수분해 함수는 sqrt(n)까지만 반복문을 돌려서 나머지가 0이라면 벡터v에 i와 n/i를 넣어줍니다.

벡터 v에 n의 약수들을 모조리 다 집어넣는 셈이며, 반복문이 끝난 뒤에는 n도 넣어줘야 합니다.

 

 φ(x)를 구하는 함수는 간단합니다. 말 그대로 오일러 피 함수 자체를 구현하면 되기 때문에 이 문제를 풀기 전

GCD(n,k)=1등의 문제를 푸셨다면 쉽게 구현하실 수 있을 것입니다.

자료형에 주의하시고 sqrt를 사용하기 위해서 <cmath>헤더파일을 불러와야 한다는 점!

 

✏️ 문제 코드

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

vector<long long>v;
void findPrime(long long n);
long long eulerPhi(long long n);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long n;
	cin >> n;
	if (n == 1) {
		cout << 1;
		return 0;
	}
	else {
		findPrime(n);
		for (int i = 0; i < v.size(); i++) {
			if (v[i] * eulerPhi(v[i]) == n) {
				cout << v[i];
				return 0;
			}
		}
	}
	cout << -1;
}
void findPrime(long long n) {
	for (long i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) {
			v.push_back(i);
			v.push_back(n / i);
		}
	}
	v.push_back(n);
}

long long eulerPhi(long long n)
{
	long long res = n;
	for (long long i = 2; i * i <= n; i++) {
		if (n % i == 0)
			res = res / i * (i - 1);
		while (n % i == 0)
			n /= i;
	}
	if (n > 1)
		res = res / n * (n - 1);
	return res;
}