[백준 14941] 호기심 - JAVA

문제 개요

남규는 호기심이 많다.
호기심이 많은 남규는 $a$와 $b$ 사이의 소수들의 합과 차를 이용한 특수한 함수 F를 만들었다. 남규는 이 특수한 함수의 결과값을 알고 싶다.

함수 $F(a,b)$는 $a$와 $b$ 사이의 소수를 순서대로 다음과 같은 규칙에 따라 계산하고, 그 값을 반환한다.

$3×A_1 - A_2 + 3×A_3 - A_4 + 3×A_5 - A_6 ..... A_n (a ≤ A_1 < … < A_n ≤ b , A_i$는 소수이다.)

질문이 $F(3, 7)$ 이라면 $3$과 $7$ 사이에는 $3, 5, 7$ 총 $3$개의 소수가 있고, 규칙에 따라 계산한 결과는

$3×3 - 5 + 3×7 = 25$ 이다.

입력

첫 줄에는 질문의 개수 $n$이 주어진다.
다음 줄 부터 차례대로 함수의 입력 $a, b$가 주어진다.
$(1 ≤ a ≤ b ≤ 10^5)$ 또한 남규는 호기심이 많기 때문에 매우 많은 질문을 한다.
따라서 질문의 수 $n$은 최대 $10^5$ 개이다.

출력

남규가 물어본 질문 $a, b$에 대한 답변 $F(a, b)$을 각 줄에 하나씩 순서대로 출력한다.

접근 방법

이 문제에서 가장 먼저 해야할 일은 소수를 판별하는 것입니다.
질문 수가 최대 $10^5$개이기 때문에 소수 판별 및 연산을 미리 저장해야 합니다.
또한 최적화를 하기 위해서는 $F(a, b)$를 구하기 위한 누적합을 미리 저장해두어야 합니다.

각 소수는 하나의 연산 공식을 따르지만
$a$와 $b$값에 따른 소수 순서에 따라 두 가지 방식으로 더해지게 됩니다.

특정 소수가 $P$라고 가정했을 때
$a$와 $b$의 범위에 따라 각 소수들은 $-P$ 또는 $3 * P$ 연산을 하게 되는데

시작 소수가 짝수 인덱스인지 홀수 인덱스인지에 따라
even과 odd 배열의 누적합을 활용하도록 구현했습니다.

$F(a, b)$는 이분 탐색으로
$a$이상 $b$이하의 숫자 중 가장 작은 소수를 시작 소수로
$a$이상 $b$이하의 숫자 중 가장 큰 소수를 종료 소수로 선정했습니다.

시작 소수를 구할 때는 특정 범위 내 가장 작은 값을 구하는 lower bound
종료 소수를 구할 때는 범위 내 가장 큰 값을 구하는 upper bound를 사용했습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static StringTokenizer st;
    static final int MAX = 100000;
    static ArrayList<Integer> primes = new ArrayList<>();
    static long[] even;
    static long[] odd;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        init();

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(f(a, b)).append("\n");
        }

        System.out.println(sb);
    }

    private static void init() {
        boolean[] isNotPrime = new boolean[MAX + 1];
        isNotPrime[0] = isNotPrime[1] = true;

        for (int i = 2; i <= MAX; i++) {
            if (!isNotPrime[i]) {
                primes.add(i);

                if ((long)i * i <= MAX) {
                    for (int j = i * i; j <= MAX; j += i) {
                        isNotPrime[j] = true;
                    }
                }
            }
        }

        even = new long[primes.size()];
        odd = new long[primes.size()];
        long e = 0;
        long o = 0;
        for (int i = 0; i < primes.size(); i++) {
            int n = primes.get(i);

            if (i % 2 == 0) {
                even[i] = e += 3L * n;
                odd[i] = o -= n;
            }
            else {
                even[i] = e -= n;
                odd[i] = o += 3L * n;
            }
        }
    }

    static long f(int a, int b) {
        int si = -1;
        int ei = -1;

        int s = 0;
        int e = primes.size() - 1;

        while (s <= e) {
            int m = (s + e) / 2;
            int cp = primes.get(m);

            if (cp >= a) {
                si = m;
                e = m - 1;
            } else {
                s = m + 1;
            }
        }

        s = 0;
        e = primes.size() - 1;

        while (s <= e) {
            int m = (s + e) / 2;
            int cp = primes.get(m);

            if (cp <= b) {
                ei = m;
                s = m + 1;
            } else {
                e = m - 1;
            }
        }

        if (si == -1 || ei == -1 || si > ei) return 0;

        if (si % 2 == 0) {
            return even[ei] - (si > 0 ? even[si - 1] : 0);
        } else {
            return odd[ei] - (si > 0 ? odd[si - 1] : 0);
        }
    }
}