[백준 1016] 제곱ㄴㄴ수

• 안녕하세요. BlockDMask 입니다.

• 오늘자 문제 "제곱 ㄴㄴㄴㄴㄴㄴㄴㄴ 수 " 풀어보겠습니다.
  이 문제 생각하는데 너무 오래걸렸어..

0. 제목

• 백준 1016 제곱ㄴㄴ수

• BOJ 1016 제곱ㄴㄴ수

1. 문제설명

어떤 수가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ 수라고 합니다.

제곱수는 정수의 제곱.

min과 max의 범위가 주어지면 min, max를 포함한 사이에 제곱 ㄴㄴ 수가 몇 개 있는지 출력하는 문제.

min의 조건은.

1 <= min <= 1,000,000,000,000 사이의 자연수입니다.

max의 조건은.

max >= min 이고,

max <= min + 1,000,000 입니다.

2. 풀이과정

[대략적으로]

첫번째, 범위 내의 제곱근의 최대값(max의 제곱근)을 구합니다.

그것보다 작은 제곱근 들을 저장해놓습니다.

두번째, 저장한 제곱근 들의 배수중 최소값(min)보다 크거나 같은 배수를 구합니다.

그 배수들의 갯수를 count 합니다.

이때 중복이 발생하지 않도록 bool 배열을 통해 예외 처리 해줍니다.

[자세히]

우선. max와 min 사이 숫자의 갯수는 최대 1,000,000개 입니다.

bool 타입으로 result[1000001] 의 배열을 선언합니다.

그다음 제곱 들을 저장할 수의 배열을 선언합니다.

long long 타입으로 num[1000002]

<cmath> 헤더의 sqrt 함수를 통해서 min과 max 사이의 가장큰 제곱근(sq_max)을 구해줍니다.

구한 제곱근 보다 작고 2보다 큰 숫자들의 

제곱을 num 배열에 넣고 그것의 개수를 셉니다(cntNum)

제곱들의 갯수만큼 for문을 돌립니다.

for문 내부에서

min과 max사이에 제곱(num[i])으로 나누어 떨어지는 가장 작은 수를 div_min에 넣고

div_min + num[i] 의 갯수를 구해줍니다.

중복 체크는 result 배열을 이용합니다.

중복 되지 않은 true의 개수를 count 변수로 구합니다.

마지막 출력은 max-min + 1 갯수에서 result 배열에서의 true의 개수를 빼줍니다.

3. 코드

#include<iostream>
#include<cmath>
 
using namespace std;
 
bool result[1000001] = {false};  //max - min 사이의 최대 갯수
long long num[1000001] = {0};    //제곱들 저장
 
int main(void){
    long long min;
    long long max;
 
    cin >> min >> max;
 
    long long sq_max = (long long)sqrt(max);    //범위 내 제곱값이 될 수 있는 가장 큰수
    long long cntNum =0;                        //제곱들의 개수
    for(long long i=2; i<=sq_max; i++) {        //제곱들 저장
        num[i] = i*i;
        cntNum++;
    }
 
    int count =0; // max와  min 사이에 제곱의 수로 나누어 떨어지는 수.
 
    for(int i=2; i<cntNum+2; i++){
 
        long long div_min = min;                 //div_min을 범위의 최소값 min으로 둔 후 
        if(div_min % num[i] != 0){               //div_min이 제곱수로 나누어 지지 않으면 
            div_min = (min/num[i] + 1) * num[i]; //최소값을 제곱근으로 나눈 몫에 +1 후 다시 곱해서 범위 안의 값으로 바꾼다.
        }
 
        
        for(long long tmp = div_min; tmp <=max; tmp += num[i]){ //num[i]로 나누어지는 div_min을 count 한다.
            if(!result[tmp-min]){
                result[tmp-min] = true;
                count++;
            }
        }
 
    }
    cout << max-min-count+1 ;
 
    return 0;
}

4. 인증

문제출처 - https://www.acmicpc.net/problem/1016

감사합니다 도움이 되셨다면 하트 한번 부탁드립니다.