Consecutive Remainders

3.9

7 votes
Basic Programming, Approved, Medium-Hard
Problem

Alice and Bob playing with numbers today!

Alice says three numbers p, a, b. p, as you may guess, is prime.

Bob, on his turn, want to find integer \(0 \leqslant x < p\) such that \((x + b) ^ a \equiv x^a \mod p\). But finding just one such number is boring, so Bob wants to find few such numbers.

If there are less than 10 such x, print all of them. Else print 10 different x, satisfying equation above.

Input Format:
Input contains t testcases. Each testcase given in separate line.
t
\(p_1\; a_1\; b_1\)
\(p_2\; a_2\; b_2\)
\(\dots\)
\(p_t\; a_t\; b_t\)

Output Format:
For each testcase, output number of integers you have found. Then output found integers.

Constraints:
\(1 \leqslant t \leqslant 10,000\).
\(2 \leqslant p \leqslant 1,000,000,009\), p is prime.
\(0 \leqslant a \leqslant 1,000,000,000\).
\(0 \leqslant b \leqslant p - 1\).

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

In first testcase, we have \(p = 11, a = 5, b = 3\). We need to find all x-s such that \((x+3)^5 \equiv x^5 \mod 11\). This equation has 4 solutions -- \(1, 7, 9, 10\). For example, \((1+3)^5 = 4^5 = 1024 \equiv 1 = 1^3 \mod 11\).
In second testcase \(p = 13, a = 5, b = 4\), and we have no solutions.
In third, we have just one solution.

Editor Image

?