DCEPC200 - The Prime Minister
DCE Coders mentors got fed up by making problems, they are deciding upon the toughest problem for contest. Everybody started to tease Ankur sir that he can’t make a single tough problem for juniors. He got very angry, now you only handle Ankur sir’s anger (Beware: All the tough number theory problems given to you as assignments are like 2+2=4 for Ankur sir). Here is the problem given by him (Say thanks to Jyoti ma’am that she softens the problem slightly.. ;)). You are given an integer n. There will be 2 different numbers K1 and K2, such that K1*K2 = n.
Both of which satisfies the equation (Totient(K!) mod K) !=0.
You are also given value of a function, F(n) = Sum of squares of factor of n. (example F(20) = 546)
Now you have to calculate the value of x and y which satisfies the equation K1x + K2y = m. Where m is given. Since there are many roots you have to find a single pair (x,y) which satisfies the equation having minimum absolute value of (x +y). If no pair is possible output -1. Else output (abs(x+y)^m)%mod
Input
First line contains T(1<=T<=10000) number of test cases. Each test case consist of single line containing 3 integers n, F(n) and m.
Output
Output T lines , each line contains a single integer ((x+y)^m)%mod.
Constraints
T<=10000
N<=10^8
F(n)<=10^18
M<=100
mod=10000000000283
Example
Input: 1 6 50 3 Output: 0
hide comments
Naivedya Bansal:
2015-10-24 11:57:53
Correct logic..but numerous bugs in implementation, caused me many WAs. :/ |
|
Ashish Lavania:
2013-05-02 09:40:23
@dce coders: what's the use of the middle input?
|
|
Mitch Schwartz:
2012-10-08 17:04:29
Important note: The expected output is actually (abs(x+y)^m)%mod. It was in the previous comments but somehow got deleted.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-10-08 17:04:29
@dce coders: Thanks :-D |
|
dce coders:
2012-10-08 17:04:29
Solutions have been rejudged due to faulty test data. Some AC solutions got WA now and vice versa. Sorry for the mess :) |
|
Mitch Schwartz:
2012-10-08 17:04:29
@xilinx: x and y are integers. |
|
[Rampage] Blue.Mary:
2012-10-08 17:04:29
Are x and y integers, or real numbers? |
Added by: | dce coders |
Date: | 2012-02-27 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C C++ 4.3.2 CPP JAVA |
Resource: | Own Problem |