메모리: 117840 KB, 시간: 1448 ms
수학, 정수론, 소수 판정, 에라토스테네스의 체
더 나은 삶을 위해 사람들은 특이한 장치 하나를 공공장소에 놓기로 결정했다. 이 장치는 키보드와 화면을 통해 입출력을 주고받으며, 내부에 정수 하나를 저장한다. 초기에 저장되어있는 정수는 1이다.
이 장치는 아래와 같은 과정으로 작동한다.
- 사용자는 키보드를 통해 정수 하나를 입력한다.
- 이 장치는 원래의 수에 입력된 수를 곱해 저장한다.
- 그러고 나면 결과가 완전제곱수인지를 화면에 출력한다. 만약 완전제곱수가 맞을 경우 사용자는 기쁘게 춤을 추고 뛰며 다른 사람들에게 걸리지 않도록 조심스럽게 장치로부터 다른 곳으로 간다.
사람들이 입력하는 수가 순서대로 주어졌을 때, 누가 기쁘게 되는지를 알아내시오.
첫 번째 줄에는 이 장치를 이용하는 사람의 수 N(1 ≤ N ≤ 500 000)이 들어온다.
다음 N개의 줄에는 사람들이 입력한 정수 ai(1 ≤ ai ≤ 1 000 000)가 사용하는 순서대로 한 줄에 하나씩 들어온다.
장치에 저장되는 수의 범위가 64비트 int형의 범위를 벗어날 수도 있음에 유의하라.
장치에 저장된 수가 완전제곱수이면 "DA"를, 그렇지 않다면 "NE"를 각각의 사용자가 얻는 순서대로 출력하시오.