Fredo and Maths
Practice
3.9 (15 votes)
Approved
Euler's totient function
Math
Medium
Prime factorization
Sieve
Problem
44% Success 6254 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Given three numbers x,k and m, you need to find the value of \(x^{x^{x^{.^{.^{.^x}}}}}\)%m where number of x's in the expression are k. That is, if x=5,k=3 and m=3, then you need to compute \(5^{5^5}\)%3.

Constraints:
\(1 \le T \le 10^5\)
\(1 \le m \le 10^7\)
\(1 \le k \le 10^{18}\)
\(m < x \le 10^8\) x is always a prime number

Format of the input file:
First line : T i.e number of testcases.
For each testcase :
First line : Three space separated integers x , k and m.

Format of the output file:
Print the answer for each test case in a separate line

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
95 votes
Tags:
ApprovedData StructuresEuler's totient functionFenwick TreeMathMediumNumber TheorySegment Trees
Points:30
Tags:
Totient FunctionGraphNumber theoryData StructuresAlgorithmsNumber TheoryMath