백준1016_제곱 ㄴㄴ수

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

 

 

문제 정의

min 과 max 가 주어졌을 때, 제곱수로 나누어지지 않는 정수의 개수를 찾아야 한다.

 

예제 입력 1에서 min=1 , max=10 이 주어졌을 떄, 1보다 큰 제곱수(4,9)로 나누어지지 않는 정수의 개수는 1,2,3,5,6,7,10 으로 7개이다.

 

 

위 그림과 같이 2부터 제곱수가 max값을 넘기 전까지 제곱수로 나누어지는 수들을 하나씩 제거해주면 된다.

 

 

배열 초기화

입력받은 min, max 값에 따라 범위를 설정해주고 배열을 초기화한다.

long long range = max - min + 1;
std::vector<bool> is_power(range, false);

 

 

제곱수로 나누어지는 수 순차적으로 탐색

i^2 형태의 제곱수를 순회하며 해당 제곱수로 나눌 수 있는 숫자들을 범위 내에서 표시한다.

제곱수로 나누어지면 true로, 나누어지지 않으면 처음 초기화한 false 그대로 남는다.

for (long long i = 2; i * i <= max; i++) {
  long long p = i * i;
  long long sIdx = min / p;

  if (min % p != 0) sIdx++;
  for (long long j = sIdx; p * j <= max; j++) {
    is_power[(int)((j * p) - min)] = true;
  }
}

 

 

결과 계산

탐색 이후, false로 남아있는 값의 개수를 세면 문제의 답을 구할 수 있다.

long count = 0;
for (int i = 0; i < range; i++) {
  if (!is_power[i]) count++;
}
std::cout << count << '\n';

 

 

시간 복잡도

 

전체 코드

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

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

  long long min, max;
  std::cin >> min >> max;
  long long range = max - min + 1;

  std::vector<bool> is_power(range, false);

  for (long long i = 2; i * i <= max; i++) {
    long long p = i * i;
    long long sIdx = min / p;

    if (min % p != 0) sIdx++;
    for (long long j = sIdx; p * j <= max; j++) {
      is_power[(int)((j * p) - min)] = true;
    }
  }

  long count = 0;
  for (int i = 0; i < range; i++) {
    if (!is_power[i]) count++;
  }
  std::cout << count << '\n';
  return 0;
}