FCTRHELL - Factor y Hell

no tags 

Factorial(N) in base B : The number of trailing zeros.

Factorial(19) in base 9×10^0=9 can be written 725735500635080000, ending with 4 zeros.
Factorial(43) in base 2×10^1=20 can be written 59HHHFECFCCEGH5G7I7A3A8G88F8CD8G000000000, ending with 9 zeros.
What about working with serious constraints and tricky cases ?
Factorial(N) will be a huge one, the base will be dummy too and have the special form : B×10^E.

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are three integers : N, B, E.

Output

For each test case, print the number of zeros at the end of Factorial(N) written in base B×10^E.

Example

Input:
3
19 9 0
43 2 1
10000 100 10

Output:
4
9
208

Constraints

1 <= T < 2000
1 <= N < 10^1000
1 <= B < 10^9
0 <= E < 10^9

Informations

Don't worry about the 'special' base 1 (B=1 and E=0), it is absent from input.
About distribution : random input (N : log-uniform, B : uniform, E : uniform) in their range. Some tricky cases are added.
It is recommended to solve FACTBASE first, and find a way to solve FCTRL much faster than common solutions.
Time limit is ×13.6 my best Python3 time, or ×1.33 my "basic" one.


hide comments
Min_25: 2014-04-20 12:53:43

Nice problem. :)
--ans(Francky)--> Thanks for your appreciation.

Last edit: 2014-04-21 21:33:39
Apoorv Jindal: 2013-12-19 15:45:07

I am getting TLE. Cant see how I can optimize it further! Please suggest something.
--ans(francky)--> It is recommended to solve FCTRL in a way much faster than common solutions. And it's not enough...
Edit(apoorv) --> Thank you! I'll look into it.

Last edit: 2013-12-19 19:31:33
abdou_93: 2013-05-27 19:58:24

time limit exceeded ... time limit exceeded...:( not easy to solve this problem

Michael Kharitonov: 2013-03-15 12:54:07

Thank god O(N^2) per test is enought. I know how to solve it in O(N*log(N)^2), that would be real hell
--ans--> Yes, this problem is not so hard compared to DTPOLY2. ;-) Again, congratulations, you've found many corners to attack this problem and joined them successfully. Your method is more generalist, mine is more specialized on the 5-attack.

Last edit: 2013-03-15 15:18:41
[Rampage] Blue.Mary: 2013-02-28 16:56:57

It's a boring constant optimization problem when using PIKE.
--ans(Francky)--> I took only pleasure in the opti part, I found it too easy by nature. There's many good things to be found. I'm under half a second in python... But I can understand your sentiment. Oh, and in fact, find the tricky cases were source of more fun than solving it, it's true.

Last edit: 2013-02-28 17:08:22
Ehor Nechiporenko: 2013-02-06 12:30:25

Thanks a lot Franky)) Increasing cell size in long arithmetics was enough, but that's not all possible ways of optimizing.
Thanks a lot. Your tasks are allways a good play for my brains;-)))
--ans--> Well done. Thanks for your appreciation. ;-)

Last edit: 2013-02-06 12:55:34
(Tjandra Satria Gunawan)(曾毅昆): 2013-02-05 18:08:43

TLE.. It's not easy to do with C/C++! I should learn PIKE to solve this one!
--ans--> You correctly solve all tests cases but you need a good ×3 speedup ; I see at least three places where to gain ×5. Good luck, you're not so far. The 'easier' part for you could be to try around 0.05s in C for FCTRL, and avoid some useless computations. Good luck.
EDIT(Tjandra): Thanks for the info :-)

Last edit: 2013-02-05 20:46:37
Ehor Nechiporenko: 2013-02-05 15:06:01

Great probmlem, Franky)) And now it's time for the optimizing trip to resolve this one.
--ans--> Yet a good job, you passed all test cases. If you're interested, you need something like a ×10 speedup. There's many possible corners to solve this problem. Good luck.

Last edit: 2013-02-05 20:21:03
:D: 2013-02-04 13:57:04

I don't understand how is E uniform in it's range. Wouldn't that make pretty much all generated cases trivial? I'm probably missing something, but isn't the result always 0 for E > 1000?
(ans Gerbicz) that is not true.
--ans(Francky)--> I confirm that no cases are trivial, I hope I set constraints the best as possible. I've worked to set nice tricky cases, and let solutions not so hard in 'any' language. In C (or Pascal, ...) you'll only need a basic home made bignum class with division_by_one_word as the 'hardest' part. Have fun ;-)

Ok, I missed a major part of this problem logic. The question did not happen :)

Last edit: 2013-02-04 22:08:06
(Tjandra Satria Gunawan)(曾毅昆): 2013-02-03 21:57:49

great problem! but I'm weak to deal with big integer.. (B and E is no problem but N) and I'm weak to work with python too (because it's slow).. Hard as hell! :-O
--ans--> It's not so hard to solve, 'hell' is here just because in French factorial sounds 'factor y hell', that's all. But find tricky cases was the best part for me. If N was 'small' there were no interest at all. Thanks for your comment.
Edit : and in C, it's not so difficult to implement an efficient one-word-division, so it's very accessible too.
Good luck to everybody.

Last edit: 2013-02-03 22:12:19

Added by:Francky
Date:2013-02-03
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem