BOJ 1016 : 제곱 ㄴㄴ 수

알고리즘 문제 전체 링크

 

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

 

 

에라토스테네스의 체와 같은 방법으로 구할 수 있다.

 

소수의 배수를 모두 지우고 남은 수가 소수가 되는 것처럼

제곱수의 배수를 모두 지우면 제곱 ㄴㄴ 수가 남게 된다.

---

1,000,000,000,000의 수에 대해 모든 제곱 ㄴㄴ 수를 구할 수 없으므로,

MIN ~ MAX (최대 1,000,000 차이)까지만 구하면 된다.

따라서 100만개의 수 중 제곱 ㄴㄴ수를 구분하기 위해 배열을 100만개 잡는다.

check[number] = 0 인 경우가 제곱 ㄴㄴ수이다.

이때, MIN번 째 수가 제곱 ㄴㄴ 수 인지 여부는 check 배열의 0번째 index를 본다.

int check[1000100]; /* 0 = 제곱 ㄴㄴ 수 */

 

소수를 지우는 방법을 응용하여 제곱수를 모두 지우면 남은 수가 제곱 ㄴㄴ 수가 된다.

i = 2의 제곱수부터 i * i 가 MAX가 될 때 까지 지우면 된다.

typedef long long int ll;

int main(void)
{
	int ans;

	scanf("%lld %lld", &MIN, &MAX);

	for (ll i = 2; i * i <= MAX; i++)
	{
		ll st = i * i - MIN % (i * i); /* MIN ~ MAX 사이에서 가장 먼저 지우는 수 */
		
		if (st == i * i) st = 0; /* MIN이 제곱수라면 check[MIN] = check[0] = 1로 표시 */

		for (ll k = st; k <= MAX - MIN; k += i * i) check[k] = 1;
	}
    
 	...  
}

 

check[0]이 MIN번 째 수의 제곱 ㄴㄴ 수 여부이므로, start를 i * i 에서 MIN % (i * i)만큼 뺀다.

만약 MIN이 제곱수라면 check[0] = 1로 표시되어야 하므로, st = 0으로 맞춘다.

i * i 가 MAX가 될 때 까지 for k에서 제곱수의 배수를 계속 지워나가면 된다.

 

마지막으로 check가 0인 배열을 세면 제곱 ㄴㄴ 수의 개수가 된다.

ans = 0;
for (int i = 0; i <= MAX - MIN;i++) ans += !check[i];

 

최종 코드는 아래와 같다.

수가 매우 크기 때문에 long long int로 type을 재정의하였다.

#include <stdio.h>

typedef long long int ll;

ll MIN, MAX;
int check[1000100];

int main(void)
{
	int ans;

	scanf("%lld %lld", &MIN, &MAX);

	for (ll i = 2; i * i <= MAX; i++)
	{
		ll st = i * i - MIN % (i * i); /* MIN ~ MAX 사이에서 가장 먼저 지우는 수 */
		
		if (st == i * i) st = 0; /* MIN이 제곱수라면 check[MIN] = check[0] = 1로 표시 */

		for (ll k = st; k <= MAX - MIN; k += i * i) check[k] = 1;
	}

	ans = 0;
	for (int i = 0; i <= MAX - MIN;i++) ans += !check[i];

	printf("%d\n", ans);

	return 0;
}