17603번 - Factorization 스페셜 저지다국어

Integer factorization serves an important role in many cryptography systems. It is about finding two positive integers p and q for a given positive composite number n such that n = pq and 1 < p ≤ q < n. However, it is a well-known NP-intermediate candidate. We still don’t have any algorithm to solve it in polynomial time.

Taylor, a number theorist, created another factorization problem as follows.

Given a prime number p and two integers a₀, a₁ ∈ {0, 1, . . . p − 1}. Find two integers b₀, b₁ ∈ {0, 1, . . . p − 1} such that a₀ ≡ b₀ · b₁ (mod p) and a₁ ≡ b₀ + b₁ (mod p).

“This factoring is way much cooler, in the sense that it can be computed efficiently,” said Taylor. Now, he invites you to enjoy this new variant of factorization.

The first line contains an integer 1 ≤ T ≤ 100 indicating the number of test cases. For each test case, there is a line containing three non-negative integers p, a0, a1 separated by a single blank.

For each test case, output a line containing b₀ and b₁ in ascending order separated by a single blank if b₀ and b₁ satisfy the equations. If there are multiple solutions, you may output any of them. If there is no solution, output −1.

• 1 ≤ T ≤ 100
• 1 < p < 2³¹ and p is a prime number.
• a₀, a₁ ∈ {0, 1, . . . , p − 1}.