[ 백준 ] 1016번 - 제곱 ㄴㄴ 수 (C++)

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

1016번: 제곱 ㄴㄴ 수

 

 

[ 문제풀이 ]

 

1. 최솟값과 최댓값을 입력받습니다.

 

2. 구해야 하는 수의 범위가 최대 1,000,000이기 때문에 arr [ 1000001 ] 배열을 만들어서 각 숫자의 제곱 ㄴㄴ 수 여부를 판별합니다.

 

3. 범위 내 수의 개수를 ans에 대입합니다.(Max - Min + 1)

 

4. i = 2부터 for문을 돌며 i * i <= Max까지 i를 증가시키면서 그 배수에 Min을 뺀 값 즉, arr [ i * i * j - Min ]을 1로 바꿔주고, ans에 1을 빼줍니다.

 

5. 위의 과정 4에서 시작하는 j값을 얻기 위해 Min / i * i를 통해 나온 몫의 값에 나머지가 없다면 0을 나머지가 있다면 1을 더해줍니다.

 

6. ans를 출력해줍니다.

 

[ 소스코드 ]

#include<iostream>
#define ll long long
 
using namespace std;
 
ll arr[1000001];
ll Min, Max;
int ans;
 
int main()
{
    scanf("%lld %lld", &Min, &Max);
    ans = Max - Min + 1;    //범위 내 모든 수의 개수
 
    for (ll i = 2; i * i <= Max; i++) {
        ll pow = i * i;        //제곱수
        ll cnt = Min / pow;    //범위 내 나누어 떨어지는 수의 최솟값
 
        if (Min % pow) cnt++;    //나누어 떨어지지 않으면 몫 + 1
 
        for (ll j = cnt; j*pow <= Max; j++) {
            if (arr[j * pow - Min] != 1) {
                arr[j * pow - Min] = 1;
                ans--;
            }
        }
    }
 
    printf("%lld", ans);
}