백준 9213 자바 - 꽤 좋은 수 (BOJ 9213 JAVA)

문제 : boj9213

 

 

  골드1 치곤 좀 쉬웠으나, 확실히 아이디어를 생각하긴 어려울수도 있을 것 같다.

 

  우선 약수의 합을 구해보자. 소수판정 때 쓰던 에라토스테네스의 체를 쓰던 방식을 응용해서 소수를 구하는 것이 아니라, 약수를 구해 더해주면 각 수의 약수 의 합을 구할 수 있다. (코드 initBadness() 참고)

약수의 합을 구하는 것이므로, 에라토스테네스의 체의 최적화 방식인 sqrt(N) 까지가 아니라, N/2 까지 봐야 한다ㅇ

 

  그럼 이후 [start, stop] 구간에 대해 미리 구해둔 약수의 합을 참고하여 i-arr[i]의 절대값이 badness 이하라면 카운팅하면 된다. 여기서 offline query + mo's algorithm까지 사용한다면 더 효율적으로 가능하겠으나 위의 방식으로 해도 시간제한 근처도 안간다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main extends FastInput {
    int[] arr;

    private void initBadness() {
        arr = new int[1000001];
        Arrays.fill(arr, 1);
        for (int i = 2; i <= 1000000/2; i++) {
            int base = i+i;
            while (base <= 1000000) {
                 arr[base] += i;
                 base += i;
            }
        }
    }

    private void solution() throws Exception {
        StringBuilder sb = new StringBuilder();
        initBadness();
        int tc = 0;
        while (true) {
            int start = nextInt();
            if (start == 0) break;
            int stop = nextInt();
            int badness = nextInt();

            int cnt = 0;
            for (int i = start; i <= stop; i++) {
                if (Math.abs(i-arr[i]) <= badness)
                    cnt++;
            }
            sb.append("Test ").append(++tc).append(':').append(' ').append(cnt).append('\n');
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}