BOJ 13010 - h(n)

* BOJ 13010 - h(n)

[분류 - 정수론, 이분 탐색]

  탐색 범위 실수로 왜맞틀을 계속한 문제..ㅜ

[풀이]

  문제를 읽으면 소인수분해를 하고 싶어지지 않으십니까. 그래서 먼저 소인수분해 해줍니다.

  

  여기서 n=h(x)=x^d(x)를 만족하는 x 중 가장 작은 x를 찾는 것이 문제인데요, d(x)는 x의 약수의 개수이기에 하나의 수입니다. 따라서 소수 Pt를 인수로 몇 개로 갖는지를 나타내는 Ck로 묶어낼 수 있어야 합니다. 따라서 d(x)의 후보 집합을 A로 나타내면 아래와 같습니다.

  이 집합은 최대공약수로 쉽게 구할 수 있습니다. 

  따라서 답을 구할 때 소인수 분해하고 승수에 대한 최대 공약수를 구한 뒤, 모든 가능한 d(x)에 대해 x를 역으로 구한 뒤 이 x의 약수의 개수가 d(x)와 같은 값 중 가장 작은 x를 구하면 됩니다. 뭐 여기까지 문제였다면 껌이겠죠,

  문제는 n 자체가 너무 큰 수라는 겁니다. 범위를 줄여봅시다. 로 줄이는 것은 잘 알려져 있고, 대체로 최적이나 이 문제에서는 10^9이므로 적합하지 않습니다. 한 차례 더 로 줄여봅시다.

  1. 소수 Pt (<=)인 n의 소인수를 찾아서 분해한다.

  2. 1.에서 걸러지고 남은 수가 1이 아니라면 여기서 소인수가 나올 수 있는 경우는 세 가지밖에 나오지 않는다.

    2-1. 소수 Pt (>) 자체이다.

    2-2. 소수 Pt 의 제곱꼴이다.

    2-3. 보다 크고 보다 작은 서로 다른 소수 Pt, Pl의 곱셈으로 표현된다.

  여기서 2-1.과 2-3.는 d(x)의 후보가 될 수 없습니다. 각각 소수가 단 하나뿐이고 Ct=1인데, 소수 자체가 이미 약수가 2개이므로 d(x) 후보군 집합은 A={1}밖에 없고 이를 만족할 x가 존재할 수가 없습니다.

  이제 2-2.만 보면 되는데, 소수 Pt의 제곱꼴이므로 이분 탐색으로 1.에서 걸러지고 남은 수가 제곱꼴인지 확인하면 됩니다. 이 때 그 수 Pt^2=(남은 n)에서 Pt가 소수인지 아닌지는 판단할 필욘 없어요. 만약 이 수가 소수가 아니었다면 이미 1.에서 걸러졌을테니까요.

#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
using ll = long long;
const ll INF = 1e18 + 9, L = 1e6;
ll _pow(ll a, ll n) {
	if (n <= 1) return n ? a : 1;
	ll h = _pow(a, n >> 1);
	return h * h * (n % 2 ? a : 1);
}
ll gcd(ll p, ll q) { return !q ? p : gcd(q, p % q); }
int main() {
	ll n, l, r, mid, i, j, cnt, cur, g = -1, ans = INF, valid = 1;
	vector<pair<ll, ll>> pf;
	bool c[L + 1] = {};
	scanf("%lld", &n);
	l = 1, r = L;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (mid * mid * mid >= n) r = mid - 1;
		else l = mid + 1;
	}
	for (i = 2; i <= l; i++) if (!c[i]) {
		if (n % i == 0) {
			cnt = 0;
			while (n % i == 0) {
				n /= i;
				cnt++;
			}
			pf.push_back({ i, cnt });
			g = g == -1 ? cnt : gcd(g, cnt);
		}
		for (j = i * i; j <= l; j += i) c[j] = 1;
	}
	if (n > 1) {
		l = 1, r = 1e9;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (mid * mid >= n) r = mid - 1;
			else l = mid + 1;
		}
		if (l * l == n) {
			pf.push_back({ l, 2 });
			g = g == -1 ? 2 : gcd(g, 2);
		}
		else valid = 0;
	}
	if (valid) {
		for (i = g; i >= 1; i--) if (g % i == 0) {
			cur = cnt = 1;
			for (auto pp : pf) {
				cur *= _pow(pp.first, pp.second / i);
				cnt *= (pp.second / i + 1);
			}
			if (i == cnt) {
				ans = cur;
                break;
            }
		}
	}
	
	printf("%lld", ans == INF ? -1 : ans);
	return 0;
}