SPOJ.com - Problem FUNMODSEQ

FUNMODSEQ - Funny Modular Sequence

no tags

Lets define a funny modular sequence as a sequence such that:

a₁ x a₂ = 1 (mod p)
a₂ x a₃ = 1 (mod p)
...
a_n-1 x a_n = 1 (mod p)

Also, a₁, a₂, a₃ ... a_n must be less than p and greater than or equal to 0. Given one element, a₁, find the sum of the entire funny modular sequence of length n. If, for any a_i, where i>=1, there exists no a_i+1 such that a_ix a_i+1 = 1 (mod p), output -1.

Note: p is not necessarily prime.

Input

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

Output

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

Constraints

1<=T<=10⁵
1<=a₁<=10⁵
1<=n<=10⁹
a₁ < p <=10⁹

Sample

Input:
2
2 3 2
3 7 2

Output:
4
8

Explanation

In the first test case, the funny modular sequence will be 2, 2, which has a sum of 4.

In the second test case, it will be 3, 5, which has a sum of 8.

Submit solution!

hide comments

< Previous 1 2 Next >

	nadstratosfer: 2019-03-20 04:46:33 Testcases are uncompromising, which is a shame as I've had a blast exploring the patterns here and building and optimizing a solution based on my findings, on and off for 2 days, only to find out it has to TLE. Finally had to turn to wikipedia and after 15mins a played out NT trick did the job. And the fun was over. Disappointed.
	:D: 2016-09-13 00:44:40 It must be added that a{i+1} in the condition for -1 can be out of the sequence.
	TKD: 2016-06-27 13:58:17 sequence in increasing order?? can sequence be 535353 for p=7 Last edit: 2016-06-27 13:58:46
	Min_25: 2016-06-25 13:10:06 [ Note ] Some input file does not end with '\n'. Last edit: 2016-06-25 13:39:48
	krunner: 2016-06-25 02:25:38 @Piyush: could you please check submission 17172921 ? Shouldn't time limit be increased for Java programs ? I can see one Python submission in 1.84 sec whereas limit on this page is 1 sec Thank you for looking Re: The time 1.84 sec tells you the total time it took to run all test files whereas the TL mentioned on the description is for one test file. The TL for Java looks tight but I think a decent code can pass. There are a lot of optimizations you can make in your code. Best of Luck! Last edit: 2016-06-25 09:29:36
	geeta: 2016-06-22 22:08:06 should the sequence be in increasing order?? plz give a test case for which output is -1!! Re: If it helps=> 5706 24466 28146 Last edit: 2016-06-23 06:22:17
	pvsmpraveen: 2016-06-17 17:10:35 Nice Question :) !! 1WA for Overlook AC :)
	wisfaq: 2016-06-17 13:30:20 If you ask me to calculate something mod p it is very deceptive to use p's that aren't prime. Re: Although, the problem statement doesn't give any reason to believe that p is prime, I will add a note. Last edit: 2016-06-17 14:17:40
	lt: 2016-06-17 12:09:02 Awesome problem! Ac in one go. :) Re: Congrats! Glad you liked it :) Last edit: 2016-06-17 12:17:31
	akshayvenkat: 2016-06-17 07:26:57 @Piyush i think the sample input given in the problem must be 2 2 3 2 3 7 2 Re: Thanks! Updated! Last edit: 2016-06-17 07:28:30

Submit solution!

Added by:	Piyush Kumar
Date:	2016-06-16
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 GOSU JS-MONKEY
Resource:	Hackerearth Monthly Contest