1016 제곱 ㄴㄴ 수 [JAVA]

문제풀이

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

 

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

 

문제가 아주 심플하다.

 

그렇지만

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

범위가 악랄하다.

 

10^12이니 단순히 1번만 돌아도 무조건 timeout이라는 것

min~max의 범위가 10^6 밖에 되지 않는다는 것을 염두에 두고 풀이를 해야 한다.

 

주어진 조건을 조금 변형해보자.

제곱 ㄴㄴ수가 아닌 제곱 ㅇㅇ수를 구해보자.

즉, X가 1보다 큰 제곱수로 나누어지는 X의 갯수를 구해보자.

 

이 말은 아래의 명제들로 풀이할 수 있다

.

• X가 어떠한 제곱 수 Y^2로 나누어 떨어진다.
• X가 어떠한 수 Y로 나누어 떨어진다.
• X가 어떠한 소수의 곱 p*q...r로 나누어 떨어진다.
• X가 어떠한 소수 p로 나누어 떨어진다.

여기서 어떤 수 X가 어떤 수 Y^2로 나누어 떨어지려면 Y^2은 X보다 작아야 한다.

따라서, Y는 root(X)보다 작은 정수여야 한다.

 

이렇게 되면 Y의 범위는 대략 10^6 단위로 줄어들게 된다.

 

여기서, Y는 그 자체가 소수 일 수 있기 때문에 우리가 찾아야 하는 소수의 범위는 2~Y다.

 

에라토스테네스의 체를 이용해서 소수를 쭉 구하면 Nlog(N)의 시간 복잡도로 해결할 수 있다.

따라서, 총 10^9의 시간 복잡도로 소수를 구해낼 수 있다.

 

그 후, 소수들을 모두 제곱하여 Set에 저장한다. (O(N)*O(1))

 

다음으로, 모든 제곱 소수에 대해서 min~max 사이의 몫에 대해 순회하며 해당 제곱 소수로 나누어 떨어지는 수를 별도의 Set에 저장한다. (시간 복잡도는 O(PQ) P:소수의 갯수, Q: 몫의 범위 <= O(N) ) ( 최대 범위까지의 소수의 갯수는 78498개이다. )

 

마지막으로 범위 내 숫자의 갯수 max-min+1 에서 나누어떨어졌던 수들을 빼준다.

 

==> 정답.

 

볼드 해놓은 부분에 대해 조금 더 자세히 설명해보자면

Set<Long> dividedSet = new HashSet<>();

for (Long multiPrime : multiPrimeSet) {
    long a = minValue % multiPrime == 0 ? minValue/multiPrime : minValue/multiPrime +1;
    long b = maxValue / multiPrime;

    for (long i = a; i <= b; i++) {
        dividedSet.add(i*multiPrime);
    }
}

주어진 범위에 대해서 제곱 소수가 나누어 떨어트릴 수 있는 수는 multiPrime * i의 형태이고

해당 수 i는 범위를 만족해야 하기에 a이상 b이하여야 한다.

 

(a의 경우 multiPrime가 주어진 범위에 대해 처음으로 나누어 떨어트릴 수 있는 몫이고

b는 반대로 마지막으로 나누어 떨어트릴 수 있는 몫이다.)

 

따라서, 구한 몫의 범위를 돌며 multiPrime*i를 HashSet에 저장해나간다면 loop가 종료된 후 min~max 사이의 제곱 소수로 나누어 떨어지는 모든 수를 Set에 저장할 수 있게 된다.

 

 

 

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long minValue = sc.nextLong();
        long maxValue = sc.nextLong();
        long ans = maxValue-minValue+1;

        int primeRange = (int)Math.sqrt(maxValue);

        boolean[] isNotPrime = new boolean[primeRange+1];
        isNotPrime[0]=isNotPrime[1]=true;

        for (int i = 2; i <= Math.sqrt(primeRange); i++) {
            if(isNotPrime[i])
                continue;
            for (int j = i*i; j <= primeRange; j+=i) {
                isNotPrime[j]=true;
            }
        }

        Set<Long> multiPrimeSet = new HashSet<>();

        for (int i = 2; i <= primeRange; i++) {
            if(!isNotPrime[i])
                multiPrimeSet.add((long)i*i);
        }

        Set<Long> dividedSet = new HashSet<>();

        for (Long multiPrime : multiPrimeSet) {
            long a = minValue % multiPrime == 0 ? minValue/multiPrime : minValue/multiPrime +1;
            long b = maxValue / multiPrime;

            for (long i = a; i <= b; i++) {
                dividedSet.add(i*multiPrime);
            }
        }

        ans -= dividedSet.size();

        System.out.println(ans);
    }
}