[백준 / BOJ] C++ 1016 제곱 ㄴㄴ 수

1016번: 제곱 ㄴㄴ 수

 

문제

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

1016번: 제곱 ㄴㄴ 수

 

 

풀이

min 이상 max 이하의 제곱 ㄴㄴ 수의 개수를 구하는 문제다. 제곱 ㄴㄴ 수란 어느 제곱수로 나누어 떨어지지 않는 수를 말한다.

 

이 문제의 핵심은 에라토스테네스의 체의 변형이다.

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

위와 같은 범위 때문에 애를 먹었다. 아래 범위 조건 때문에 0 ≤ max - min ≤ 1,000,000 이므로 배열의 크기는 1,000,000 + 1의 크기로 충분함을 알 수 있다. (런타임 에러를 10번 내고서야 이걸 한참 뒤에 깨닫고 겨우 풀었다.)

 

그리고 2의 제곱부터 4, 8, 12,... 하나하나 없애는 건 10e12라는 범위를 절대 커버할 수 없음이 명백해 보였다. 그래서 최소한의 경우, 필요한 경우만 순회하자 했다.

 

n * i * i 가 max 이하인 동안 n을 제거해주면 된다. 이 n은 min을 i * i 로 나눈 몫부터 차례대로 순회하면 최소한으로 확인할 수 있다.

(min을 i*i로 나누어 떨어지지 않으면 n에 1을 더해준다. - 범위가 벗어나기 때문)

 

따라서 n * i * i 가 min 이상 max 이하일 때, sieve[n * i * i - min] 값을 0으로 바꾸었다.

 

그리고 sieve 배열에서 값이 1인 개수를 세주었다. (sieve 배열의 0~max-min index의 모든 원소의 합)

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  long long min, max;
  cin >> min >> max;
  vector<long long> sieve(1000001, 1);
  for (long long i = 2; i * i <= max; i++) {
    long long n = min / (i * i);
    if (min % (i * i))
      n++;
    while (n * i * i <= max) {
      sieve[n * i * i - min] = 0;
      n++;
    }
  }
  cout << accumulate(sieve.begin(), sieve.begin() + max - min + 1, 0) << '\n';
  return 0;
}