Skip to content

제곱ㄴㄴ수.md

Latest commit

 

History

History
91 lines (65 loc) · 2.54 KB

제곱ㄴㄴ수.md

File metadata and controls

91 lines (65 loc) · 2.54 KB
DONE_DATE 2025/01/30

제곱 ㄴㄴ 수

난이도

  • 골드 1

문제

https://www.acmicpc.net/problem/1016

알고리즘 분류

  • 수학
  • 정수론
  • 소수 판정
  • 에라토스테네스의 체

회고

  • 제곱수로 나누어 떨어지지 않는 수를 구하는 문제

  • 에라토스테네스의 체를 응용하여 풀 수 있다. => 제곱수의 배수를 체크하는 배열을 만들기

  • min의 크기가 1조 이기 때문에 단순히 배열을 사용할 수 없다.

  • 하지만 max 가 min + 1,000,000 이하이기 때문에 범위를 좁혀서 배열을 사용할 수 있다.

  • 제곱수의 배수를 체크하는 배열을 만들어서 풀었다.

  • ll start = ((min_val - 1) / square + 1) * square;

  • start는 min_val 이상이면서 square의 배수인 최소값이다.

  • 예를 들어) square = 4, min_val = 12면

  • start = ((12 - 1) / 4 + 1) * 4

  • start = (11 / 4 + 1) * 4

  • start = (2 + 1) * 4

  • start = 3 * 4

  • start = 12

  • 이런식이다. 그러므로 12는 4의 배수 중 제일 12에 까까운 수이다.

  • -1 을 해주는 이유는 -1을 해주면 min_val이 square의 배수인 경우에도 start가 min_val이 되기 때문이다.

  • -1이 없다면 이미 딱 나누어 떨어지는 수가 있더라도 그 다음 배수로 넘어가 버린다.

  • 이렇게 => ( 12 / 4 + 1) * 4 = (3 + 1) * 4 = 16

  • start 부터 max_val까지 square씩 증가하면서 제곱수의 배수를 체크한다.

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

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

    ll min_val, max_val;
    cin >> min_val >> max_val;
    ll rangeSize = max_val - min_val + 1;

    // 제곱수 배수 여부를 체크할 배열(각 인덱스는 해당 범위의 한 숫자에 대응)
    vector<bool> isSquareMultiple(rangeSize, false);

    // 2 이상 sqrt(max_val) 이하의 모든 i에 대해 i^2의 배수를 체크
    for (ll i = 2; i * i <= max_val; i++) {
        ll square = i * i;

        // min_val 이상이면서 square로 나누어떨어지는 최소 시작값
        ll start = ((min_val - 1) / square + 1) * square;

        // start부터 max_val 이하까지 square씩 증가
        for (ll j = start; j <= max_val; j += square) {
            isSquareMultiple[j - min_val] = true;
        }
    }

    // 제곱수의 배수가 아닌(아직 false인) 인덱스 개수
    ll result = 0;
    for (ll i = 0; i < rangeSize; i++) {
        if (!isSquareMultiple[i]) {
            result++;
        }
    }

    cout << result << "\n";
    return 0;
}