백준 문제 1016번 제곱 ㄴㄴ 수 문제풀이 c++

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

1016번: 제곱 ㄴㄴ 수

 

문제해석

 

수의 범위가 굉장히 큰 것에 비해 max와 min의 차이는 최대 100만까지 나지 않는 점을 주목해야한다.

따라서 사실상 최대 100만 정도 배열이면 이 문제를 푸는데 지장이 없다.

 

min부터 max까지 순서대로 배열에 저장하고 이에 대해 에라토스테네스의 체는 아니지만 그와 같은 방식으로 걸러주면된다.

 

예를 들어 min=50 max=60 이 입력으로 주어지면

 1<a^2<=max 인 a에 대해서 그림과 같이 연산을 하면 남는것이 51 53 55 57 58 59로 6개가 되고 답이 6이 된다.

 

이 방법으로 아래코드를 작성했다.

 

코드

#define MAX 1000002
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string.h>
typedef long long int ll;
using namespace std;
void setting();
ll a[MAX];
ll n,m;
int main(){
	cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=0; i<m-n+1; i++)
    {
        a[i]=i+n;
    }
    setting();
    ll ans=0;
    for(ll i=0; i<m-n+1; i++)
    {
        if(a[i]!=0)
        {
            ans++;
        }
    }
    cout<<ans;
}
void setting(){
    for(ll i=2; i*i<=m; i++)
    {
        ll x=(n/(i*i))*i*i;
        if(x==n)
        {
            for(ll j=0; ; j=j+i*i)
            {
                if(x-n+j>m-n)
                {
                    break;
                }
                a[x-n+j]=0;
            }
        }
        else
        {
            x=x+i*i;
            for(ll j=0; ; j=j+i*i)
            {
                if(x-n+j>m-n)
                {
                    break;
                }
                a[x-n+j]=0;
            }
        }
    }
}