백준 1016 : 제곱 ㄴㄴ수

문제 링크

소수를 이용해서 풀었다.

min과 max의 범위가 최대 10^12이므로, 제곱이 되기 위한 수는 10^6까지만 봐줘도 된다. 10^6 까지 소수인 수들은 에라토스테네스의 체를 이용해서 구할 수 있다.

그 다음 이 문제의 특징은 min과 max의 차이가 최대 백만이라는 것이다. 따라서 모든 소수에 대해서 min~max중 소수^2 으로 나누어 떨어지는 것들에 표시를 해놓고 마지막에 표시가 되어있지 않은 것들의 개수를 세었다. 이것을 크기 max-min+1짜리 배열을 선언하고 시작위치를 계산해준 후, 소수^2씩 더해줌으로써 구현하였다. 이 배열에서 인덱스 0은 min에, 인덱스 max-min은 max에 대응된다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21*1e8;
const int MAX = 1e6;
const int mod = 20150523;

vector<bool> isprime;

ll a,b;

int main()
{
   ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	isprime = vector<bool>(MAX+1,true);
	
   cin>>a>>b;
	isprime[0] = isprime[1] = false;
	
	vector<ll> p;
	for(int i = 2;i<=1e3;i++)
	{
		if(isprime[i])
		{
			for(int j = i*i;j <= 1e6;j+=i)
			{
				isprime[j] = false;
			}
		}
	}
	
	for(int i = 2;i<=MAX;i++)
	{
		if(isprime[i]) p.push_back(i);
	}
	
	vector<bool> is(b-a+1,false);

   for(auto elem : p)
   {
       if(1LL * elem * elem > b) break;
       
       elem *= elem;

       ll s;
       if(a < elem) s = elem - a;
       else if(a % elem == 0) s = 0;
       else s = (a/elem)*elem + elem - a;

       for(;s<b-a+1;s+=elem)
       {
           is[s] = true;
       }

   }

   int ans = 0;
   for(auto elem : is)
   {
       if(!elem) ans++;
   }
	
   cout<<ans;
   return 0;
}
​