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 0x<p such that (x+b)axamodp. 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
p1a1b1
p2a2b2

ptatbt

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

Constraints:
1t10,000.
2p1,000,000,009, p is prime.
0a1,000,000,000.
0bp1.

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)5x5mod11. This equation has 4 solutions -- 1,7,9,10. For example, (1+3)5=45=10241=13mod11.
In second testcase p=13,a=5,b=4, and we have no solutions.
In third, we have just one solution.

Editor Image

?