홀수와 짝수의 대결
시간 제한1초메모리 제한512 MB
각 n에 대해 1부터 n까지의 정수 중 소인수 분해했을 때 소인수가 짝수 개(중복 포함)인 수의 개수를 세고, 그 개수가 나머지 이상이면 O를, 아니면 E를 출력한다.
문제
1 이상 n 이하의 자연수 중 짝수가 더 많을까, 홀수가 더 많을까?
입력
첫째 줄에는 테스트케이스의 개수 T(0 이상 1,000,000 이하)가 주어진다. 각각의 테스트케이스는 한 줄로 이루어져 있으며, 그 줄에 1 이상 109 이하의 자연수 n이 주어진다.
출력
각 테스트케이스마다 한 줄씩, 짝수가 홀수보다 많으면 적지 않으면 O, 아니면 E를 출력한다.
네, 참으로 올바르시겠어요...
힌트
문제가 너무 쉽기 때문에 그나마 구데기스럽게 만들기 위해 예제를 숨겼다.
출처
Contest > 구데기컵 > 진짜 최종 구데기컵 2 🆚번
- 문제를 만든 사람: jh05013
채점
- 예제는 채점하지 않는다.
진짜 노트
일반적인 정의와 달리 이 문제에서는 홀수와 짝수를 다음과 같이 정의한다.
1 이상의 자연수 k는 소수의 곱으로 표현할 수 있고, 그 표현 방법은 소수의 순서를 바꾸는 경우를 제외하면 유일하다. 이때 사용된 소수의 개수가 2의 배수가 아니면 k는 짝수, 아니면 k는 홀수이다. (k = 1일 때는 소수 0개의 곱이고, 0은 2의 배수이다.) 같은 소수가 여러 번 사용되었을 경우, 사용될 때마다 하나씩 세어야 한다.