DCEPC204 - Unlock it !
Vaibhav loves playing with numbers. To enjoy his summer holidays he decides to join the group "number players" of his school. He decides to visit the group hall. At the gate he finds a lock and a paper. The gate can only be unlocked by solving the puzzle written on the paper. Vaibhav is stuck with his puzzle, help him in solving it.
Here is the puzzle description:
Given a sequence F(N)
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) = (2^(n/4)) * F(n/5)* F(n/10) (for n>10)
For every fraction, a ceil value is taken for evaluation.
For eg. F(11)=2^ceil(11/4) * F(ceil(11/5)) * F(ceil(11/10)) = 2^3 * F(3) * F(2) = 24
Given N. Find the max 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 line gives 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
suhash:
2020-07-01 08:31:04
a = f(n), b = 0 satisfy the constraints of the problem. However, this gives WA. Please clarify in the description that b > 0 (cost me several WA). I see now in the comments that someone already mentioned this. |
|
SanchitK:
2014-03-28 21:32:43
please give some more test cases so that i can check if my logic is correct or not |
|
abdou_93:
2013-11-11 16:12:30
@dce coders..
|
|
Gitu:
2013-07-06 13:57:07
An Awesome Trick Question (Y)
|
|
:D:
2012-06-07 11:59:28
Fun "trick" problem. |
|
The Raven:
2012-04-26 06:09:30
b can not be 0 apparently, even though gcd(F[n],0) = F[n] |
|
numerix:
2012-04-05 08:27:27
@problemsetter: Can you give me one n for which my code fails?
|
|
dce coders:
2012-03-31 11:07:21
@Alex : answer will be 625.
|
|
Alex Anderson:
2012-03-25 00:22:59
Supposing mod were 1000, would the answer on input N = 2 be 625 or 24? That is, do you want the maximum value of (a^b), and then that value returned modulo mod, or do you want the maximum value which might be returned modulo mod? |
Added by: | dce coders |
Date: | 2012-02-26 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own Problem |