[백준] 1016번: 제곱 ㄴㄴ 수 - C/C++

문제링크

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

 

1016_제곱 ㄴㄴ 수 

문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

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

예제 입력 1 복사

1 10

예제 출력 1 복사

7

예제 입력 2 복사

15 15

예제 출력 2 복사

1

예제 입력 3 복사

1 1000

예제 출력 3 복사

608

 

내 제출

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
	long long min, max, ze, j, t;
    long long mod;
    long long count = 0;
    long long* arr;
    
    scanf("%lld %lld", &min, &max);
    arr = (long long*)calloc(max - min + 1, sizeof(long long));
    t = sqrt(max);
    
    for (long long i = 2; i *i<= max; i++) //그냥 int로 i를 선언하면 integeroverflow가 난다.
    {
        ze = i*i;
        mod = (min % ze == 0) ? 0 : 1;
        for (j = (min / ze + mod)  * ze; j <= max; j += ze)
        {
            arr[j - min] = 1;
        }
    }
    
    for (long long int i = 0; i <= max - min; i++)
    {
        if (arr[i] != 1)
        {
           count++;
        }
    }
    
    printf("%d", count);
    return 0;
}

 

단순히 for문을 돌려 하나씩 다 찾아보는 방법도 있지만 이렇게 한다면 당연 시간초과가 난다.

수가 커도 너무 커서 시간초과가 난다요...

해결방법은 아래부터!!----------------------------------------------------------------------------------

우선 1보다 큰 제곱수를 찾아야하기 때문에 i는 2부터 시작한다. 

min과 가장 가까운 제곱수로 나누어 지는 값을 찾고 max보다 같거나 작은 해당 제곱수의 배수들의 배열 값을 1로 변경한다.

이렇게 max보다 작거나 같은 제곱수들로 하고 마지막에 배열에서 0인 값들만 센다.

min <= max <= min + 1,000,000 조건으로 min과 max 사이 값은 최대 1,000,000개이고 여기서 제곱수를 찾아 더 빠른 속도를 낼 수 있다. 

또한 제곱수로 하나하나 나눠보면서 나누어지는 모든 값을 찾지 않아도 되어 속도가 향상된다.

반응형