목록BOJ 1016 (1)

승코딩당당당

[C++] 백준 1016: 제곱 ㄴㄴ 수

문제[C++] 백준 1016: 제곱 ㄴㄴ 수 GOLD 1https://www.acmicpc.net/problem/1016 접근 방법구간 [Min,Max][Min, Max][Min,Max] 안에 있는 수들 중에서 어떤 소수 p에 대해 p^2로 나누어떨어지지 않는 수(= 제곱 ㄴㄴ 수)의 개수를 세는 문제이다. 즉, 구간 안에서 2^2, 3^2, 5^2, ... 이런 제곱수들로 나누어 떨어지는 수는 다 제외하고 남는 숫자의 개수를 세면 된다. 하지만 여기서 중요한 제약은 이와 같기 때문에,단순히 1 ~ Max까지 배열 만들어서 에라토스테네스 같은 걸 돌리거나매 수마다 제곱수 나눠보는 방식으로는 시간/메모리 초과가 난다.그래서 이 문제는 “전체를 다 보는 게 아니라, [Min, Max] 구간만 슬라이딩해서 ..
PS/BOJ 2026. 3. 2. 02:12
이전 Prev 1 Next 다음