SPOJ.com - Problem FCTRHELL

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.

Submit solution!

hide comments

< Previous 1 2 Next >

	nadstratosfer: 2020-07-02 15:47:28 What a torture. Wrote more code just to find the nasty cases than to actually solve them, but due to huge search space still some analysis was needed to know where to look. And the automated debugger ran for a week just to find one case my "careless" solution failed on! But the ranking for this problem is legends-only and being listed there was worth all the frustration. Thanks. Almudena, if you ever read this, daddy dedicated this success to you for your second birthday tomorrow =) =(Francky)=> If I remember well, it's the second time you honored one of 'my' ranking with your presence associated with a personal dedication. Let me say, I'm very proud of that. And Almudena, if you ever read this, you can be very proud of the accomplishments of your daddy. Last edit: 2020-07-02 21:27:03
	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(Nlog(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

Submit solution!

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