B_13909

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    long N;
    vector<bool> windows;
    cin >> N;
    for (long i = 0; i <= N; i++)
        windows.push_back(true);

    for (long i = 2; i <= N; i++)
    {
        long multiply = 1;
        while ((i * multiply) <= N)
        {
            windows[i * multiply] = !windows[i * multiply];
            ++multiply;
        }
    }
    int count = 0;
    for (int i = 1; i <= N; i++)
        if (windows[i])
            count++;
    cout << count;
}

저렇게 풀면 메모리가 최소한 525MB가 필요하다.
(메모리 초과로 실패)
그 뒤 여러가지 방법을 생각했을 때 다음과 같은 생각을 하게 되었다.
이진법(보수, 비트연산)
하지만, 아무리 계산을 때려봐도 위와 충족하는 방법을 생각해낼 수 없었다.

문제의 요점은 창문을 열고 닫을 때,
이 행동을 홀수로 행한다면, 창문을 열릴것이고 그렇지 않다면 창문은 닫힐것이다.

여기까지 생각한 뒤 생각이 막혀 찾아보니 '제곱수'라는 것이 있다.

제곱수의 특징은 다음과 같다.
1. 모든 제곱수는 홀수개의 약수를 가진다.
2. 모든 제곱수는 완전수가 아니다.
3. 제곱수는 1부터 시작하는 연속된 홀수의 합과 같다.

여기에서 주목할 특징은 1번째이다.

가령 다음과 같은 상황(N=10)을 보자

(1,2,3,4,5,6,7,8,9,10)이라는 창문이 존재하고 이 창문의 약수를 나열해보면
(1, (1,2), (1,3), (1,2,4), (1,5), (1,2,3,6), (1,7), (1,2,4,8), (1,3,9), (1,2,5,10))
이 된다.
이를 각 약수의 개수로 함축적으로 표현한다면
(1,2,2,3,2,4,2,4,3,4)
이 된다.

원래 약수의 개수는 두 수가 짝을 이루어 곱하는 것이지만, 제곱수를 통해 자기 자신을 곱하는 경우를 따지면 제곱수의 약수의 개수는 홀수가 된다.
따라서, 주어진 범위 내의 제곱수의 개수를 구하면 된다!

 

#include <iostream>

using namespace std;

int main(void)
{
    int N, count = 0;
    cin >> N;
    for (int i = 1; i * i <= N; i++)
        count++;
    cout << count;
}