Nice-P Sequence
Practice
3.9 (99 votes)
Mathematics
Medium
Open
Approved
Problem
40% Success 848 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

A Nice-P sequence is defined as a sequence such that a1 x a2=1 (mod p), a2 x a3=1 (mod p) ..., an-1 x an = 1 (mod p). In addition, a1, a 2, a 3, ... an must be less than p and greater than or equal to 0. Given one element, a1, find the sum of the entire Nice-P sequence of length n. If, for any ai, where i>=1, there exists no ai+1 such that ai x ai+1 = 1 (mod p), output -1.

NOTE: p IS NOT NECESSARILY A PRIME

Input:

The first line contains T, the number of test cases.
T lines follow, each containing a1, p, and n.

Output:

For each test case, output one line, the required sum.

Constraints:

1<=T<=105
1<=a1<=105
1<=n<=109
a1 < p <=109

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
70 votes
Tags:
ReadyMathematicsMedium
Points:30
2 votes
Tags:
MathematicsMediumOpenApproved