[백준 1016번] 제곱 ㄴㄴ 수 (C++)

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m;
int arr[1000001];

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for(ll i=2; i*i<=m; i++)
    {
        ll tmp = ceil((double)n / (i*i)); //최소 시작 값

        while(tmp * i * i <=m)
        {
            arr[tmp*i*i-n]++;
            tmp++;
        }
    }

    int cnt = 0;
    for(int i=0; i<=m-n; i++) if(!arr[i]) cnt++;
    cout << cnt;
    
    return 0;
}

 

에라스토테네스의 채 방식을 응용하여 풀 수 있는 문제이다.

먼저 입력 값 min과 max가 굉장히 큰 수이나, min~max 범위를 보면 100만으로 int 배열로 값을 저장할 수 있다.

 

따라서 최소 시작 값을 두고, 제곱 수를 곱해가며 시작 값 기준 해당 제곱 수의 배수들을 모두 체크해준다.

반복문을 통해 최소 시작 값을 계속 더해가며, 마찬가지로 배수들을 계속해서 모두 체크해준다.

ex) 시작 값 1
처음 제곱 수 4
1 * 4, 2 * 4, 3 * 4.....

다음 제곱 수 9
1 * 9, 2 * 9, 3 * 9.....

 

다만 시작 값을 주의해야 하는데, 배열 저장할 때 tmp*i*i-n을 통해 저장하므로 tmp*i*i의 값이 n보다 작으면 문제가 생긴다.

따라서 최소 입력값인 min을 활용해 i*i를 나눠주고 나머지를 통해 추가적인 값을 더해주어 최소 시작 값을 선정해준다.

해당 코드에서는 ceil로 바로 올려줬지만, min%(i*i)를 했을 때 값이 존재하면 시작 값을 더해주는 방식이 더 좋은 것 같다.

 

이후에는 시작 범위인 0부터 m-n까지 배열 값을 체크하며, 0인 경우를 카운팅하여 출력해주면 된다.