[백준][C++] 11016 제곱 ㄴㄴ 수

11016. 제곱 ㄴㄴ 수

1016번: 제곱 ㄴㄴ 수

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

 

문제는 간단해서 쉬워보이지만, 신경쓸 게 많은 문제였다.

특히 입력값이...

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

min과 max의 차이가 컸다. 1000000을 O(N^2)로 돌리는 건 진짜... 진짜 아니었기 때문에 솔루션을 고안해봤다.

알고리즘 설계

1. 소수의 제곱을 배열에 모은다. 제곱을 구하는 것이기 때문에, 1000000000000)까지만 구해준다. 범위가 크기 때문에 에라토스테네스의 체를 이용한다.

• 소수의 제곱인 이유: 예시로 4, 16, 64 > 2^2, 4^2, 8^2 > 2^2, 2^4, 2^6... 이므로 소수 2의 제곱만 비교하면 파생된 다른 제곱들로 나누어 떨어지는지 알 수 있기 때문이라고 생각했다.

2. min~max까지 소수의 제곱으로 나누어지는 수를 체크한다.

• 이 때 min부터 max까지 모두 체크하지 않고, 1000000 크기의 bool형 배열을 만들어, 에라토스테네스의 체처럼 나누어지지 않는 수를 걸러준다.

코드

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

vector<ll> v;
int check[MAX + 1];
bool answers[MAX + 1];

int main()
{
    int answer = 0;
    ll min, max;
    cin >> min >> max;

    // 에라토스테네스의 체
    // 소수 구하기
    for (ll i = 2; i <= sqrt(max); i++)
    {
        if (!check[i])
        {
            // 소수의 제곱만 넣는다
            v.push_back(i * i);

            for (ll j = (ll)i * i; j < sqrt(max); j += i)
            {
                check[j] = true;
            }
        }
    }

    answer = max - min + 1;

    for (int i = 0; i < v.size(); i++)
    {
        // start와 가장 가깝고 v[i]의 배수인 지점을 구함
        ll start = min + v[i] - (min % v[i]);

        if (start - v[i] >= min)
            start -= v[i];

        // v[i]의 배수를 모두 걸러줌
        for (ll j = start; j <= max; j += v[i])
        {
            if (!answers[j - min])
            {
                answer--;
                answers[j - min] = true;
            }
        }
    }

    cout << answer;
}

처음엔 엄청 어려워 보였지만, 소수의 제곱의 특성만 알면 생각보다 쉬운 문제였다!