DCEPC604 - Unlock it ! Part 2
Now you all helped Vaibhav solve the puzzle and open the gate last time (although not too much help). But as soon as he opens the gate, there is another puzzle to open the front door. Let’s see whether this time you all are able to help him or not.
- Fac(n) = number of trailing zeroes in n!
- Fact(n) = Fac(n) % 25 + 1
- F(0) = 1
- F(1) = 1
- F(2) = 1
- F(n) = product of all odd primes less than or equal to n (for n <= 10)
- F(n) = 4^fact(n) * f(n/5) * f(n/10) (for n > 10)
For every fraction, a floor value is taken for evaluation.
For eg. F(11)=4^fact(11) * F(floor(11/5)) * F(floor(11/10)) = 4^3 * F(2) * F(1) = 64
Given N, find the maximum value of (a^b) % mod such that a and b satisfies the relation gcd(a,b) = F(N). (Gcd : Greatest common divisor.)
Input
First line gives T, total number of test cases. Next T lines give the number N.
Output
For each test case, print the desired value on a new line.
Constraints
T <= 10
N <= 10^6
mod = 10^9
NOTE: a must be <= 5*F(n) and b must be <=5*F(n), a can be equal to b and mod=10^9
Example
Input: 1 2 Output: 1024
hide comments
Ishan:
2023-03-17 04:53:39
Time limit is strict .It's funny that I needed to do constant optimization in an O(1) solution to pass. |
|
Soma:
2015-03-11 03:06:41
@dce coder: can u tell me where my code fails. i am getiing WA. submission id=13759205;
|
|
Amit RC:
2013-06-29 10:33:15
you can't get AC by blindly following what happened in Unlock part 1...this one is slightly different, but only slightly! |
|
noju:
2012-04-25 13:35:22
getting WA please check my submission 6903877..i am getting AC for unlock part 1 with same approach. |
Added by: | dce coders |
Date: | 2012-04-22 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Resource: | Own Problem |