511. Fermat's Last Theorem
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
Given a positive integer
n and a positive prime number
p, find
x,
y and
z such that
xn+
yn=z
n modulo
p and
x,
y and
z are nonzero modulo
p or report that there's no such triple.
Input
The first line of the input file contains the number
t of testcases to solve, 1 ≤
t ≤ 1000. Each of the next
t lines contains two integers
n and
p, 3 ≤
n ≤ 10
6, 2 ≤
p ≤ 10
6.
Output
For each input testcase, output one line:
- when there exists a solution, output three integers x, y and z, 1 ≤ x, y, z ≤ p-1. If there are multiple solutions, output any.
- when there's no solution, output one integer -1.
Example(s)
sample input | sample output |
2
5 41
3 5
| -1
1 2 4
|