[1016] 제곱 ㄴㄴ 수 (C++)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll min, max; cin >> min >> max;
    int cnt = 0;

    vector<bool> powcheck(max - min + 1, true);

    for (ll i = 2; i * i <= max; i++) {
        ll square = i * i;
        ll s = ((min + square - 1) / square) * square;
        for (ll j = s; j <= max; j += square)
            powcheck[j - min] = false;
    }

    for (int i = 0; i < max - min + 1; i++) {
        if (powcheck[i]) cnt++;
    }

    cout << cnt;

    return 0;
}

 

만약 max = 20 일 때 sqrt(20)을 기준으로 1*20 2*10 4*5 sqrt(20) 5*4 10*2 20*1 대칭을 이룬다.

따라서 제곱수를 판별 할 때 i의 범위를 i * i <= max로 놓는다.

 

1. 큰 수의 계산을 위해 long long을 사용한다

2. 시작 지점인 s를 설정한다

=> 만약 min이 4인 경우, i = 2일때 square = 4이고 min보다 큰 4의 배수 중 가장 작은 수를 구하려면

min + square의 square로 나누면 2가 되어버리므로 -1을 해준 후 square로 나눈다

나눈 후 몫과 square를 곱해주면 4의 배수 중 가장 작은 수가 나오게 된다

따라서 s = ((min + square - 1) / square) * square 라는 식을 세워야 한다

3. 시작 지점인 s를 설정했다면, j를 s부터 시작하여 square만큼 더하며 for문을 반복한다

=> 이때 j += square는 i의 2승, i의 3승, ... 을 의미한다

 

 

for문의 시간복잡도가 초과되어 시간 초과가 났던 문제