POWTOW - Power Tower City
You are living in a city build entirely of power towers such as 3^3^3 and 10^10^10^10. To enter a building you must type the last 9 digits of the number represented by the tower, written in decimal form, on a keypad next to the main entrance. You are not sharp enough at mental maths, but you can write a handy program to bring along in your pocket.
A power tower is defined as repeated exponentiation. We write this using Knuth's up-arrow notation as: e↑↑a = e^e^...^e (a terms). Remember that ^ (exponentiation) is right associative. For example: 2↑↑4 = 2^2^2^2 = 2^(2^(2^2)) = 2^2^4 = 2^16 = 65536, and 3↑↑1 = 3. The value of a tower of height 0 is 1.
Input
The first line contains integer C in [0..1000], the number of test cases.
Then follows C lines, each with integers e,a in [0..2147483647]. (non-negative 32-bit integers).
Output
For each testcase output e↑↑a, or if the output has more than 9 digits, output "..." and then the last 9 digits.
Example
Input: 3 0 0 2 5 993306745 75707320 Output: 1 ...719156736 ...884765625
hide comments
cubyte:
2022-08-10 16:05:23
This problem is fixed now.
|
|
Thomas Dybdahl Ahle:
2015-12-30 20:04:36
@Tarun There are multiple ways to solve it, but I don't think I spoil anything if I say it'll help to know a bit of modular arithmetic, and maybe Euler's theorem. Last edit: 2016-09-16 11:17:41 |
|
Tarun Dutt:
2015-06-04 16:34:47
Any prerequisites to solve this problem? |
|
aksam:
2015-01-01 10:05:03
@Thomas Dybdahl Ahle why my solution gives NZEC in 4th test case |
|
[Lakshman]:
2014-12-31 16:32:33
@Thomas Dybdahl Ahle can you please check my last submission I am getting WA. Thanks
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2014-08-25 05:51:41
There are many crazy corner case in this problem, and it's fun to discover them all :-D Very nice problem :-) |
|
Francky:
2014-05-03 01:33:14
@psetter : I've made intense check and I'm unable to get NZEC (at home) with my Python code, could you give me a reason for NZEC here ; I tried several input methods...
|
|
Alessandro Amici:
2014-03-30 10:06:20
Ok, I did all sort of dumb mistakes, but now I can't see which corner cases I'm still missing in ID 11354832 :/ Any hint? |
|
Thomas Dybdahl Ahle:
2012-05-02 13:06:16
pulkit: You have errors in some towers of 0, and large towers of 2.
|
|
Thomas Dybdahl Ahle:
2012-04-14 04:25:59
I have disqualified the solutions by hqztrue and zzy since they were identical to the solution submitted by DHH. |
Added by: | Thomas Dybdahl Ahle |
Date: | 2011-11-21 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |