[BOJ/C++] 1016 제곱 ㄴㄴ 수

에라토스테네스의 체를 응용하여 문제를 해결할 수 있습니다.

우선 문제의 min, max의 최댓값을 보면 1,000,000,000,000로 매우 큰 숫자입니다.

하지만 min <= max <= min + 1,000,000 의 조건을 살펴보면 확인해야 하는 범위는 1,000,000 이라는 것을 알 수 있습니다.

우선 제곱 ㄴㄴ 수의 최댓값은 max-min+1의 값을 가질 수 있습니다. 이후 제곱 ㄴㄴ 수가 아닌 값이 나온다면 해당 값에서 1씩 빼주어 총 제곱 ㄴㄴ 수의 개수를 구할 수 있습니다.

우선 어떤 수 $m$을 $i^2$으로 나눈다는 것은 $m=i^2*q+r$로 나타낼 수 있습니다.

여기서 q는 몫, r은 나머지입니다.

이때 나머지가 0이라면 $m=i^2*q$ 가 됩니다.

나머지가 0이 아니라면 $m$보다 $i^2*q$가 작다는 뜻이고 $q+1$을 해준다면 $i^2*(q+1)$은 이후 가장 작은 제곱수일 것 입니다.

따라서 나머지가 0이 아니라면 몫에 +1 해주면 min보다 큰 가장 작은 제곱수부터 시작할 수 있습니다.

이후 max보다 작거나 같은 값 까지 제곱수를 구하여 max-min+1 값에서 하나씩 빼주면 됩니다.

// boj g1 1016
// 제곱 ㄴㄴ 수

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    long long min, max;
    cin >> min >> max;

    bool isPrime[1000001] = { false };
    long long result = max - min + 1;

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

        while(temp*i*i<=max)
        {
            if(isPrime[temp*i*i - min]==false)
            {
                isPrime[temp * i * i - min] = true;
                result--;
            }

            temp++;
        }

    }

    cout << result;

    return 0;
}