[ABC250] D - 250-like Number (AtCoder Beginner Contest 250 with Java)

문제 : abc250_d

  최대 10^18 까지 표현이 가능해야 한다. 이 때 p<q인 소수 p와 q에 대해 p x q^3이 10^18까지 나와야 한다. p가 가장 작은 소수인 2라고 한다면, q는 결국 10^6정도까지의 소수는 구해놔야 계산이 가능하다. 정확히 어디까지 구해야 하는지는 다음과 같다.(이하 코드에서는 대회 중에 푼거라 시간이 없어서 별도로 계산 안하고 대강 10^6으로 잡고 짰다.)

 

 

  따라서 10^6 이하의 모든 소수를 우선 '에라토스테네스의 체'를 사용해 구해준다(코드의 initPn() 참고). 이 대 sqrt(10^6)까지만 보면 되는 이유는 이 글을 참고하자.

 

  그 후 p<q인 모든 소수 쌍에 대해 직접 p x q^3을 계산해서 N보다 작은 값을 카운팅하면 된다.

다만 p와 q가 커짐에 따라 long의 최대값인 2^63-1을 넘어서는 경우가 생길 수 있다. 따라서 이걸 적절한 시간내에 알 수 있어야 한다. 우선 BigInteger로 해봤으나 시간초과가 났다. 그래서 생각한 방법은 우선 p와 q가 무슨 값이던지, 그 중 3개를 곱한 값 까지는 10^18을 넘지 않는다(10^6 이하의 소수이므로). 따라서 p x q^2 까지만 우선 구해본 후, p x q^2의 자리수와 q의 자리수를 더한게 19를 넘는다면 long 범위를 넘어가므로 처리되지 않도록 했다(long의 범위는 9,223,372,036,854,775,807 까지의 19자리 수이다.).  그러니 숫자 크기 제한이 없는 파이썬을 사용합시다.

 

코드 : github

...
ArrayList<Integer> pn = new ArrayList<>();
 
private void initPn() {
    boolean[] isPn = new boolean[1000000+1];
    int sqrtN = (int)Math.sqrt(1000000);
    for (int i = 3; i <= sqrtN; i+=2) {
        if (isPn[i]) continue;
        int base = i+i;
        while (base <= 1000000) {
            isPn[base] = true;
            base+=i;
        }
    }
    pn.add(2);
    for (int i = 3; i <= 1000000; i+=2) {
        if (!isPn[i]) pn.add(i);
    }
}

private int getDigitCnt(int n) { return getDigitCnt((long)n); }
private int getDigitCnt(long n) {
    int cnt = 0;
    while (n != 0) {
        n/=10;
        cnt++;
    }
    return cnt;
}

private void solution() throws Exception {
    initPn();
    long n = nextLong();
    int cnt = 0;
    for (int i = 0; i < pn.size(); i++) {
        for (int j = i+1; j < pn.size(); j++) {
            int a = pn.get(i);
            int b = pn.get(j);
            if (a > n || b > n) break;
            long calc = 1l*a*b*b;
            if (calc > n) break;
            if (getDigitCnt(calc) + getDigitCnt(b) > 19) break;
            calc *= b;
            if (calc > n || calc < 0) break;

            cnt++;
        }
    }
    System.out.println(cnt);
}
...