제곱 ㄴㄴ 수 1016

문제

접근 방법

처음에는 제곱ㄴㄴ수가 뭔 이야기인가 했다.
제곱수란 4, 9, 16같이 n^2을 의미한다.
나누어떨어진단 건 n^2*m 같은 형식을 말한다. (4, 8, 16, 24...)
에라토스테네스의 체가 생각났다.
에라토스테네스의 체는 배수를 제거해나가며 소수를 찾아내는 방식이다. 이 문제는 역으로 배수를 찾아내 가는 방식으로 접근해야 한다고 생각했다.

코드

#include <iostream>
#include <set>
typedef unsigned long long ull;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    set<ull> s; // 중복을 제거하는 set
    ull min, max;
    cin >> min >> max;
    for (ull i = 2; i * i <= max; ++i)
    {
        ull j = (min / (i * i)); // 제곱수로 나누었을 때 값이 가장 가까운 제곱수의 m
        if (min % (i * i))       // 나머지가 있다면 n^2*m보다 크다는 것이므로 +1
            ++j;
        for (j *= (i * i); j <= max; j += i * i) // 제곱수만큼 커짐 (제곱수에 나누어떨어지므로)
        {
            s.insert(j);
        }
    }
    ull ret = max - min + 1 - s.size(); // 범위 내 수의 개수에서 제곱수로 나누어지는 수의 개수만큼 빼기
    cout << ret;
    return 0;
}

풀이

가장 가까운 제곱수에 간 다음 (시간 절약을 위해) 제곱수만큼 더해주면서 제곱수에 나누어떨어지는 값을 모으면 된다.
전체 값에서 제곱수에 나누어떨어지는 값들의 개수를 빼주면 제곱 ㄴㄴ 수의 개수가 구해진다.

첫 접근 땐 int 범위를 쓴 것과 가장 가까운 제곱수에 도달하는 방법에서 틀렸었다.
방법을 보고 나서야 "왜 나는 생각 못했지"라는 생각이 든다.
연습을 많이 해야겠다.