[BOJ 14941 // C++] 호기심

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

 

이번에 볼 문제는 백준 14941번 문제인 호기심이다.
문제는 아래 링크를 확인하자.

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

14941번: 호기심

문제에서 주어진 식은 범위 내에서 홀수번째로 등장하는 소수는 3을 곱해 더하고 짝수번째로 등장하는 소수는 -1을 곱해 더하는 형태로 생각할 수 있다.

 

이러한 계산은 적절한 구간합 전처리를 통해 빠르게 계산해낼 수 있다.

 

또한 A와 B의 범위가 L = 10만이므로, O(L)의 전처리로 이전 소수와 다음 소수가 무엇인지 O(1)로 접근할 수 있는 배열을 만들 수 있다. (즉, 이분탐색을 구현할 필요가 없다.)

 

위 둘을 이용해 문제를 간단히 해결하자.

 

주어진 구간 내에 소수가 존재하지 않거나 하나만 존재해 짝수번째 소수가 존재하지 않는 경우 등의 예외처리에 주의하자.

 

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

#include <iostream>
using namespace std;

int sieve[101001];
bool isoddprime[101001];
int nextprime[101001], prevprime[101001];
int oddpsum[101001], evenpsum[101001];

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

	sieve[1] = 1;
	for (int i = 2; i * i < 101001; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 101001; j += i) sieve[j] = 1;
	}

	int parity = 0;
	for (int i = 1; i < 101001; i++) {
		if (!sieve[i]) {
			parity ^= 1;
			if (parity) oddpsum[i] = oddpsum[i - 1] + i, evenpsum[i] = evenpsum[i - 1], isoddprime[i] = 1;
			else oddpsum[i] = oddpsum[i - 1], evenpsum[i] = evenpsum[i - 1] + i;
		}
		else oddpsum[i] = oddpsum[i - 1], evenpsum[i] = evenpsum[i - 1];
	}

	int tmp = 0;
	for (int i = 1; i < 101001; i++) {
		prevprime[i] = tmp;
		if (!sieve[i]) tmp = i;
	}
	tmp = 101111;
	for (int i = 101000; i > 0; i--) {
		nextprime[i] = tmp;
		if (!sieve[i]) tmp = i;
	}

	int Q; cin >> Q;
	while (Q--) {
		int L, R; cin >> L >> R;
		if (sieve[L]) L = nextprime[L];
		if (sieve[R]) R = prevprime[R];

		int oddL, oddR, evenL, evenR;
		if (isoddprime[L]) oddL = L, evenL = nextprime[L];
		else oddL = nextprime[L], evenL = L;
		if (isoddprime[R]) oddR = R, evenR = prevprime[R];
		else oddR = prevprime[R], evenR = R;

		if (isoddprime[L]) {
			int ans = 0;
			if (oddL <= oddR) ans += 3 * (oddpsum[oddR] - oddpsum[oddL] + oddL);
			if (evenL <= evenR) ans -= evenpsum[evenR] - evenpsum[evenL] + evenL;
			cout << ans << '\n';
		}
		else {
			int ans = 0;
			if (evenL <= evenR) ans += 3 * (evenpsum[evenR] - evenpsum[evenL] + evenL);
			if (oddL <= oddR) ans -= oddpsum[oddR] - oddpsum[oddL] + oddL;
			cout << ans << '\n';
		}
	}
}