이번 문제는 1을 제외한 제곱수로 나누어 떨어지는 수를 구하는 것입니다. 에라토스테네스 체의 확장판이라고 생각하시면 될 것 같네요.
그리고 숫자의 범위는 작지만 숫자 자체가 꽤 커서 소수를 꽤 많이 구해야 합니다. 어떤 수 \(n\)이 소수인지는 \(O(\sqrt{n})\)의 복잡도로 판단할 수 있어서, 숫자가 \(10^{12}\) 오더이긴 하지만 제곱수이기 때문에 실제 구해야할 소수는 \(10^6\) 오더입니다. 계산량으로 보면 제한시간의 절반 이하로 가능합니다. 그런데 정답비율은 18%로 아주 낮습니다.
문제는 아래의 링크에 있습니다.
https://www.acmicpc.net/problem/1016
1016번: 제곱 ㄴㄴ 수
첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
주어진 범위가 (min, max)로 주어지기 때문에 에라토스테네스의 체를 구성하려면 offset 개념을 두어야 합니다. 당연히 min이 offset 수치가 되겠죠. 전 소수 \(p\)를 구한 후에 \(p^2\)으로 min 값을 나눈 나머지로 offset을 썼습니다. 2에 대해서는 미리 처리를 하면, 소수 검사를 할 때 홀수만을 사용할 수 있습니다.
아래는 제가 작성한 소스입니다. 소스는 참고용으로만 봐주세요.
//----------------------------------------------------------
// baekjoon #1016 - Square Free Number
// - by Aubrey Choi
// - created at 2019-06-14
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>
static char check[1000001];
void mark(long long p, long long r, int n)
{
for(long long i = (p - r)%p; i < n; i += p) check[i] = 1;
}
int main()
{
long long min, max, r;
int k, n, c = 0;
scanf("%lld%lld", &min, &max);
k = (int)sqrt(max);
r = min % 4;
n = (int)(max - min + 1);
mark(4, r, n);
for(long long p = 3; p <= k; p += 2)
{
r = min % (p*p);
mark(p*p, r, n);
}
for(int i = 0; i < n; i++) if(check[i] == 0) c++;
printf("%d\n", c);
}
반응형
'Programming > BOJ' 카테고리의 다른 글
[C/C++] 백준 #1018 체스판 다시 칠하기 (0) | 2019.12.24 |
---|---|
#1017 소수쌍(네트워크 플로우) (0) | 2019.12.24 |
[C/C++] 백준 #1015 수열 정렬 (0) | 2019.12.23 |
[C/C++] 백준 #1012 유기농 배추 (0) | 2019.12.22 |
[C/C++] 백준 #1011 Fly me to the Alpha Centauri (0) | 2019.12.22 |
댓글