Boj 1016 c++ 제곱 ㄴㄴ수

제곱 ㄴㄴ수

정말 까다로운 문제였다. 

정말 11번 정도 시도하고서야 맞췄다

이것도 역시 문제는 간단했다. 두 수 m과 n이 주어지면 m이상 n이하의 제곱 ㄴㄴ수, 즉  SFN(square free number)의 개수를 구하는 것이였다.  

 

예를 들어 1과 10을 입력하면 1이상 10 이하의 SFN의 개수, 8을 출력하는 것이다.

 

우선 코드를 구현하기 전, 가장 중요한 아이디어는 어떤 수가 SFN이 되려면, 그 수는 소수의 제곱수의 배수가 되면 안된다는 것이다. 우선 문제의 태그는 에라스토테네스의 체, 수학, 정수론이였기에 정수의 특성을 최대한으로 이용하려 했다.

 

코드를 구상하는 중 가장 큰 문제는 엄청난 수의 범위(무려 10^12)와 시간제한이였다. 10^12까지 올라가는 범위 속에서 시간 안에 답을 출력하려면 최적화된 알고리즘이 필요했다. 그래서 고안한 것이 sqrt()범위 내의 소수 판정과 이를 통한 SFN구하기 이다.

 

우선 m과 n이 입력되면 2~sqrt(n)의 범위 내의 소수를 모두 구하여 저장한다. 이를 모두 구하여 따로 배열에 저장하는 것은 매우 비효율적일 뿐더러 다시 그 값을 찾아가는 것 또한 어렵기 때문에 에라스토테네스의 체와 벡터의 인덱스를 적극 활용해야 한다. 

 

우선 sqrt(n)의 값을 int형의 변수 Max로 저장하여 소수점을 버린다. 그 후, Max+1의 크기를 가진 소수 판정 벡터(prime(Max+1))를 선언한 후, 초기값을 모두 1로 저장해둔다. 그 후, prime[i]에 대하여(2<=i<=Max) j=2 부터 j x j<=max까지  j의 배수는 모두 0으로 바꾸어 버린다. 

초반 부분 코드

이때, sqrt(Max)의 범위의 j를 이용하여 j의 배수를 지워나가는 방식으로 소수들만 남겨놓는다. 이때, prime[i]=1, 즉 i가 소수인 경우만 동작을 수행함으로써 불필요한 반복을 줄일 수 있다. 또한 이러한 방식으로 배수를 이용하여 소수를 판정하는 방식은 자주 쓰이므로 기억해놓으면 좋다.

 

이렇게 prime[i]=1인 인덱스 i로 범위 내의 소수를 구하였다.

이후 코드에서는 이 소수들의 제곱수로 나누어지는 숫자들의 개수를 세면 된다.

 

후반 코드

정답을 구하기 위한 벡터는 ans이며, 모두 1로 초기화되어있다.

 

이때, 소수의 제곱수, 즉 square의 배수인 인덱스의 값들을 모두 0으로 바꾸어주어야 한다. 

문제의 수 범위를 고려하여 long long을 사용하여야 하는 부분 또한 주의하여야 한다. 잘못하다간 오버플로우가 발생할 수도 있다. 우리가 구해야 하는 범위는 m과 n의 사이의 수 이므로 m이상의 square의 배수 중 최소값(시작값)을 올림값 계산 방식

(m+square-1)/square x square를 이용하여 구해낸다.

그 이후 부터는 square의 배수들을 제거하는 반복작업들 뿐이다. 

 

이 모든 작업이 끝난 후, 값이 1로 저장된 인덱스의 개수를 세어 답을 출력하면 된다.

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

using namespace std;



int main(){

    long long m, n;

    cin>>m>>n;

    int Max=sqrt(n);
    vector<int> prime(Max+1, 1);
    prime[0]=prime[1]=0;
    vector<int> ans(n - m + 1, 1);



    for(int i=2; i*i<=Max; i++){
        if(prime[i]==1)
        {
            for(int j=i*i; j<=Max; j+=i)
                prime[j]=0;
        }
    }

    for(int i=2; i<=Max; i++){
        if(prime[i]==0) continue;
        long long square=i;
        square*=square;
        long long start=(m+square-1)/square*square;

        for(long long j=start; j<=n; j+=square)
            ans[j-m]=0;
    }


    int cnt=0;
    for(int i=0; i<n-m+1; i++){
        if(ans[i]==1)
            cnt++;
    }
    cout<<cnt;




}

최대한 효율적으로 코드를 짜려 노력해야 한다. 특히 배수판정, 소수 판정 부분.