백준 1016: 제곱 ㄴㄴ수 (C++)

문제 링크: www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

풀이 방법

[min, max] 구간의 최대 원소 개수는 1000001이므로 bool arr[1000001]을 선언하고 여기에 min~max구간의 수가 제곱ㄴㄴ수인지 아닌지 저장해줬다.

arr[0]: min이 제곱ㄴㄴ수인지, arr[1]: min + 1이 제곱ㄴㄴ수인지 ...

일단 모두 제곱ㄴㄴ수라고 가정하고 시작한다. (memset을 통해 모두 true로 초기화한다.)

그다음 2부터 (루트 max)까지 값을 제곱한 제곱수로 [min, max] 구간의 수를 순회하며 나누어본다. 이때 나누어 떨어지면 제곱ㄴㄴ수가 아니므로 arr배열에 표시한다. 루트 max까지만 확인하는 이유는 그보다 더 큰 수의 제곱은 max보다 더 커지기 때문이다.

반복문 내에서는 [min, max]구간의 모든 수가 아니라 나누어 떨어지는 수에 대해서만 체크하므로 시간 복잡도가 크지 않다.

 

소스 코드

#include <cstdio>
#include <cmath>
#include <cstring>

long long min, max;

// arr[0]: min이 제곱ㄴㄴ수인지, arr[1]: min + 1이 제곱ㄴㄴ수인지 ...
bool arr[1000001];

int main() {
    scanf("%lld %lld", &min, &max);
    memset(arr, true, sizeof(arr));

    for (long long i = 2; i <= sqrt(max); i++) {
        long long x = min / (i * i);
        if (min % (i * i) != 0)    x++;

        while (x * (i * i) <= max) {
            arr[x * (i * i) - min] = false;
            x++;
        }
    }

    int ans = 0;
    for (int i = 0; i <= max - min; i++) {
        if (arr[i]) ans++;
    }

    printf("%d", ans);
}