RNG

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

요약

y와 a, b, c, n이 주어질 때 a x^2 + b x + c ≡ y (mod 2^n)을 만족하는 x를 [0, 2^n)에서 모두 구하고, 해가 정확히 하나일 때만 그 값을 출력한다.

난이도: 어려움10점 중 8점
유형: 정수론, 수학, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

현수는 해적과 원숭이가 등장하는 새 어드벤처 게임을 만들고 있다. 이 게임은 여러 무작위 요소를 위해 난수 생성기(RNG, Random Number Generator)를 사용한다.

직전 난수를 $x$ 라 할 때, RNG는 다음 난수 $y$ 를 아래 식으로 만든다.

$y = ax^2 + bx + c \pmod{2^n}$

여기서 $a$ , $b$ , $c$ , $n$ 은 정수이다.

게임을 디버깅하던 현수는 디버그 콘솔에서 현재 난수 하나( $y$ )를 확인했다. 이제 바로 직전에 생성되었던 난수 $x$ 를 거꾸로 알아내려 한다.

현재 난수 $y$ 와 상수 $a$ , $b$ , $c$ , $n$ 이 주어질 때, 위 식을 만족하는 직전 난수 $x$ ( $0 \le x < 2^n$ )를 구하라. 조건을 만족하는 $x$ 가 정확히 하나면 그 값을 출력하고, 존재하지 않거나 둘 이상이면 No unique solution을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다.

각 테스트 케이스는 한 줄로 이루어지며, 다섯 정수 $y$ , $a$ , $b$ , $c$ , $n$ 이 공백으로 구분되어 주어진다. ( $0 \le y, a, b, c < 2^n$ , $1 \le n \le 31$ )

출력

각 테스트 케이스마다 조건을 만족하는 직전 난수 $x$ 를 한 줄에 하나씩 출력한다.

조건을 만족하는 $x$ 가 유일하지 않으면(존재하지 않거나 둘 이상이면) No unique solution을 출력한다.

예제1

예제 1

입력

4
26 2 1 5 5
10 1 0 0 4
1 1 1 1 4
3 14 15 92 7

예상 출력

3
No unique solution
No unique solution
55