[백준] 1016 제곱 ㄴㄴ수

1016번: 제곱 ㄴㄴ 수

문제 확인

 

수학을 사용해서 푸는 문제입니다.

 

풀이

 

bool 배열은 char와 마찬가지로 1byte를 사용하기 때문에 메모리 사용량이 적은 bitset 객체를 사용합니다.

조건에 따라 모든 수의 비트를 만들순 없기 때문에 min ~ max 간격의 최댓값인 1000001개의 비트를 만듭니다. min ~ max 사이에 있는 수에 각각 비트를 할당하고 각 수는 index - a 위치에 저장됩니다. 초기값은 false, 0입니다.

 

제곱수 4, 9, 16, 25 ... 의 배수 중에서 min과 max 사이에 있는 값들을 빼주어 제곱 ㄴㄴ 수들을 구할 수 있습니다. min과 max 사이에 있는 수를 탐색하며 제곱수의 배수가 되는 경우를 1로 만들고 처음으로 1이 되면 count를 1 증가시켜 수를 셉니다.

제곱수부터 배수를 모두 탐색하게 되면 시간 초과가 발생하므로 탐색할 제곱수의 배수를 min에서 가장 가까운 upper bound 수부터 탐색을 합니다.

예를 들어 min = 10 인 경우 4의 배수를 처리해 주기 위해서는 12부터 탐색을 진행합니다.

이 upper bound 수를 구하러면 n의 배수를 처리 해주는 경우 min을 가장 가까운 n의 배수로 만들어 주면 됩니다. 

n의 배수로 만들기 위해서는 min을 n으로 나누고 다시 n을 곱해주는 소수점 삭제 방법을 사용하면 됩니다. 이때 min 자신이 n의 배수면 그대로 두어야 하기 대문에 범위 수정을 위해 식을 (min + n - 1) / n * n을 사용합니다.

가장 배수가 많은 4를 먼저 전처리 해준 후 9, 25, ... 의 배수들을 max를 넘지 않는 선에서 처리를 해 줍니다.

 

코드

#include <cstdio>
#include <bitset>
using namespace std;
int main() {
    long long a, b, i, j, t;
    bitset<1000001> ary;
    scanf("%lld%lld", &a, &b);
    int count = 0;
    for (i = (a + 3) / 4 * 4; i <= b; i += 4) {
        ary[i - a] = 1;
        count++;
    }
    for (i = 3, t; (t = i * i) <= b; i += 2) {
        for (j = (t + a - 1) / t * t; j <= b; j += t) {
            if (!ary[j - a]) {
                ary[j - a] = 1;
                count++;
            }
        }
    }
    printf("%d", b - a + 1 - count);
}