즐거운 삶을 위한 노력

시간 제한1초메모리 제한128 MB

요약
1에서 시작해 최대 50만 개의 수를 차례로 곱해가며 매 단계마다 누적곱이 완전제곱수인지 소인수분해 지수의 홀짝성으로 판별하는 문제입니다.
난이도

보통10점 중 6점

유형
정수론, 수학, 해시맵
정답자
아직 제출이 없습니다

문제

더 나은 삶을 위해 사람들은 공공장소에 특별한 장치를 설치했다. 이 장치는 키보드와 화면으로 입출력을 주고받으며, 내부에 정수 하나를 저장한다. 처음 저장된 정수는 1이다.

장치는 다음 순서로 작동한다.

  1. 사용자가 키보드로 정수 하나를 입력한다.
  2. 장치는 현재 저장된 수에 입력된 수를 곱해 다시 저장한다.
  3. 장치는 저장된 수가 완전제곱수인지 화면에 출력한다.

사람들이 입력하는 수가 순서대로 주어질 때, 각 사용 후 저장된 수가 완전제곱수인지 판별하라.

입력

첫째 줄에 장치를 이용하는 사람의 수 N이 주어진다.

다음 N개의 줄에는 사람들이 입력한 정수 a_i가 이용 순서대로 한 줄에 하나씩 주어진다.

  • 1 <= N <= 500,000
  • 1 <= a_i <= 1,000,000

장치에 저장되는 수는 64비트 정수 범위를 벗어날 수 있다.

출력

각 사용 후 장치에 저장된 수가 완전제곱수이면 DA를, 아니면 NE를 입력 순서대로 한 줄에 하나씩 출력한다.

예제3

  1. 예제 1

    입력
    5
2
2
2
2
2
    예상 출력
    NE
DA
NE
DA
NE

  2. 예제 2

    입력
    7
2
3
6
15
35
21
64
    예상 출력
    NE
NE
DA
NE
NE
DA
DA

  3. 예제 3

    입력
    7
999999
111111
333333
111111
3
27
243
    예상 출력
    NE
DA
NE
NE
DA
NE
DA