[BOJ 24503 // C++] blobfearful

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24503번 문제인 blobfearful이다.
문제는 아래 링크를 확인하자.

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

24503번: blobfearful

이 문제는 각 Aq마다, K에서 "K와 Aq의 최대공약수"를 나눈 수 K'이 x!의 약수인 최소 정수 x를 구하는 문제로 생각할 수 있다.

 

K는 10^15 이하이므로 K의 서로 다른 소인수를 모두 구하는 것은 2부터 sqrt(10^15) (약 31,622,776)까지의 모든 수로 K를 직접 나눠보는 것으로 가능하다.

 

K'이 각 소인수를 각각 몇개를 포함하는지를 이용하여 소인수별로 최소의 x를 구해, 그 중 가장 큰 수를 답으로 출력하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

vector<ll> fac;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll K, KK, Q; cin >> K >> Q; KK = K;
	for (ll p = 2; p < 31622776; p++) {
		if (KK % p == 0) {
			fac.emplace_back(p);
			while (KK % p == 0) {
				KK /= p;
			}
		}
	}
	if (KK > 1) fac.emplace_back(KK);

	while (Q--) {
		ll N; cin >> N;
		ll ans = 1;
		KK = K / gcd(K, N);
		for (ll p : fac) {
			ll cnt = 0;
			while (KK % p == 0) {
				cnt++;
				KK /= p;
			}
			if (cnt <= p) ans = max(ans, p * cnt);
			else {
				ll tmp = p; cnt--;
				while (cnt > 0) {
					tmp += p;
					ll tmpcopy = tmp;
					while (tmpcopy % p == 0) {
						cnt--;
						tmpcopy /= p;
					}
				}
				ans = max(ans, tmp);
			}
		}

		cout << ans << ' ';
	}
}