BOJ 3964 - 팩토리얼과 거듭제곱

* BOJ 3964 - 팩토리얼과 거듭제곱 (https://www.acmicpc.net/problem/3964)

  [분류 - Mathematics/ GCD/ Sieve of eratosthenes ]

으음.. 생각해야할 부분이 굉장히 많은 문제다. 사실 어떻게 풀어야하겠다는 접근 자체는 다소 간단하다. 하지만 이 과정에서 발생할 수 있는 Overflow를 까다롭게 다뤄야 풀 수 있다.

* 접근 방식

  1. n!이 k^i에 나누어 떨어지기 위해서는 k^i = GCD(n!, k^i)이어야 한다.

  2. 최대 공약수의 후보를 산출하기 위해서 k^i는 lg(k)의 시간이 걸리는 반면 n!은 lg(n!)이 걸린다. k^i가 lg(k)인 이유는 i제곱꼴은 k의 약수의 승수에 i를 곱하면 되기 때문.

따라서 후보를 추출하기 위해 먼저 에라토스테네스의 체를 이용하여 구한다. (소수를 구하는 과정은 테스트 케이스가 100개 뿐이기 때문에 sqrt(k) = 약 10^6이기 때문에 각 테케의 k의 약수를 구해도 상관 없을 것 같다.)

k를 소인수 분해했을 때 결과를 아래처럼 정의해보자.

이제 여기에 k^i과 n! 를 표현해보자.

위에 정의한 내용에 따르면 n!이 k^i로 나누어 떨어지려면 아래 수식이 반드시 만족해야 한다.

위 수식을 정리해보면,

모든 k에 대해 tk를 mk로 나눴을 때, 만족되는 가장 작은 i가 정답이 된다.

나눠주는 이유는 "가능한" k^i를 찾아갈 때, 승수 연산은 곱셈 연산이고, 이를 역으로 계산해야하기 때문이다.

* Overflow

이 문제의 핵심은 위의 접근도 접근이지만, 데이터 형식을 저장하는 타입에 대해 Overflow 검사를 해줘야 한다. 심지어 단순 계산으로는 unsigned long long 범위를 초과하기 때문에 수학적 접근방법으로 처리를 해줘야 한다.

1. i가 가장 클 수 있는 경우를 생각해보자. i가 가장 큰 경우는 n!이 엄청크고, k이 가장 작을 때 발생한다.

n = 10^18 , k = 2

이 때, 2 승수는 몇까지 올라갈 수 있을까 ?

이 과정은 "직접 손으로" 계산해야 한다.

답은 999999999999999976이 나온다. 

이 값은 10^18-24로 long long 에 딱 들어온다. 따라서 답을 제출할 때, 최소값을 찾기 이전의 초기값은 10^18에서 long long 양수의 범위 사이로 놓아주시면 되겠다.

2. 이제 약수를 구해보자.

n!에 있는 소수 pi 승수를 얻어내기 위해선 "얼마나 더 많이 수행"해야 할까?

10^18에서 11의 승수를 얻어내기 위해서는 11^ml 에서 ml의 한계는 어디까지 일까?

아래로 표현할 수 있다.

11^ml <= n!

이제 신나게 코딩을~~~ 하면 안된다.

수식으로 표현은 가능하나 overflow를 생각해야한다..

11 승수가 가능한 최대의 크기 ml는 11^ml <=n!으로 표현은 가능하다.

하지만 여기를 조건문으로 걸어버리면 11^(ml + 1)이 long long 범위를 벗어나지 않는다는 보장이 없다. 하물며 세 자리, 네 자리의 소수라고 생각하면 간단하다.

따라서 여기서 수식이 등장해야한다.

이론적으로 log(pi)(n)을 나타내기 위해선 log(n)/log(pi)를 사용하면 된다. log 함수는 math.h에 정의되어 있다.

- 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
ll min_v(ll a, ll b) { return a < b ? a : b; }
const int LIMIT = 1000001;
struct _d { ll p, c; };

int main() {
	int T;
	ll n, k,i,j, curp, cnt, ans,lgLimit;
	bool chk[LIMIT] = {1,1};
	vector<ll> p;
	vector<_d> factors;
	for (i = 2; i < LIMIT; i++) {
		if (chk[i]) continue;
		p.push_back(i);
		for (j = i * i; j < LIMIT; j += i)
			chk[j] = 1;
	}
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &n, &k);
		factors.clear();
		factors.resize(0);
		for (i = 0; k != 1 && i < p.size(); i++) {
			cnt = 0;
			while (!(k%p[i])) {
				k /= p[i];
				cnt++;
			}
			if(cnt)
				factors.push_back(_d{ p[i], cnt });
		}
		if (k != 1)
			factors.push_back(_d{ k,1 });
		ans = 1e18;
		for (_d& f : factors) {
			cnt = 0;
			curp = f.p;
			lgLimit = log(n) / log(f.p);
			for(i=0;i<lgLimit;i++) {
				cnt += n / curp;
				curp *= f.p;
			}
			ans = min_v(ans, cnt / f.c);
		}
		printf("%lld\n", ans);
	}
	return 0;
}