BOJ 백준온라인져지 1016 제곱 ㄴㄴ 수 풀이

min ~ max에 i^2 의 배수가 몇개 있는지를 찾는다.

그리고 있으면 count에 더해준다.

if(duplicatedValue[i] == 1) continue;

이 경우는 n의 m승 이미 계산된거.

else if(duplicatedValue[i] > 1) duplicatedValue[j]--;

이 경우는 i 가 6인경우로 예를 들 수 있다.

i가 6이면 2와 3에서 증가된다.

6의 배수들을 1로 변경해주고,

count -= (max / (i * i) - (min - 1) / (i * i)) * (duplicatedValue[i] - 1);

이 코드에서 6의 배수들이 중복으로 계산됐던걸 빼준다.

	#include <cstdio>
	/**
	* https://www.acmicpc.net/problem/1016
	* BOJ 백준온라인져지 1016 제곱 ㄴㄴ 수 풀이
	*/
	#define MAX 1000005
	using namespace std;
	int main(){
	long long min, max;
	scanf("%lld%lld", &min, &max);
	int count = -1;
	int *duplicatedValue = new int[MAX];
	for(long long i = 2; i * i <= max; i++){
	if(duplicatedValue[i] == 1) continue;
	for(long long j = i * 2; j * j <= max; j += i){
	if(duplicatedValue[i] == 0) duplicatedValue[j]++;
	else if(duplicatedValue[i] > 1) duplicatedValue[j]--;
	}
	count -= (max / (i * i) - (min - 1) / (i * i)) * (duplicatedValue[i] - 1);
	}
	printf("%lld", max - min - count);
	}

view raw BOJ_1016.cpp hosted with ❤ by GitHub