[BOJ 26763 // C++] Liczby silne

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

 

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

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

26763번: Liczby silne

n!이 들어간 합의 구성은 n-1 이하의 자연수의 팩토리얼들의 합으로 구성된 수보다 항상 큼을 관찰하자.

또한, 16!의 값이 10^13보다 큼 또한 관찰하자.

 

이를 이용하면 범위 내에 존재하는 모든 조건을 만족하는 수를 배열에 저장해두고(2^16개), prefix sum 배열을 만들어 준 뒤 이진탐색을 통해 적절한 인덱스를 찾아 문제를 해결할 수 있게 된다.

 

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

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

ll cur = 1; ll nxt = 2;
vector<ll> vec;
vector<ll> psum;

int Q;

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

	vec.emplace_back(0);
	while (cur < 10000000000001) {
		int vecsize = vec.size();
		for (int i = 0; i < vecsize; i++) vec.emplace_back(vec[i] + cur);
		cur *= nxt++;
	}

	psum.emplace_back(0);
	int vecsize = vec.size();
	for (int i = 1; i < vecsize; i++) psum.emplace_back(psum.back() + vec[i]);

	cin >> Q;
	while (Q--) {
		ll qL, qR; cin >> qL >> qR;
		qL--;
		int L1 = 0, R1 = vec.size() - 1, L2 = 0, R2 = vec.size() - 1;
		while (L1 < R1) {
			int mid = (L1 + R1) / 2 + 1;
			if (vec[mid] <= qL) L1 = mid;
			else R1 = mid - 1;
		}
		while (L2 < R2) {
			int mid = (L2 + R2) / 2 + 1;
			if (vec[mid] <= qR) L2 = mid;
			else R2 = mid - 1;
		}

		cout << psum[L2] - psum[L1] << '\n';
	}
}