Time Limit: 3000ms Memory Limit: 65536kb Description Now, you are given three positive A, B, C, your task is to compute the first B digits and the last C digits of the factorial of A. For example A=5, B=2, C=1. Then A! =120, so you should output 12 0 separated by one blank. Input The first line, an integer T, representing T test cases below. (T<=200). Each test case contains three integers: A (1<=A<=10^8), B (1<=B<=50) and C (1<=C<=100). Notice: No illegal case is permitted. For example, the condition A=4, B=10, C=10 is not permitted in the input data. Output For each case, output the first B digits and the last C digits of the factorial of A separated by one blank. Sample Input 2 5 2 1 8 2 2 Sample Output 12 0 40 20
I've no idea about calculating the first B digits of the factorial. Please help.Thank you. If you want to submit your code , here is the link. http://acm.ustc.edu.cn/ustcoj/problem.php?id=1265 Anybody interested？
Some interesting fact about last digits: if A>=405 answer will be all zeroes.
And for the first digits there should be sublinear algo.
sublinear algo? Any detail information, if you can give me a link to some pages that introduce the algo, that would be lovely. Thank you sincerely.^_^
Have you tried this method?
Stirling's approximation is one of my failed choices. T^T,however N is not large enough for Stirling's approximation.
Did you used your own floating point arithmetics or some standard like double?
If last, there will be lack of precision since even C++ long double holds out around 20 decimal digits.
Previously, I used double... OK, I'll try.
H-m-m, I don't believe that Stirling's approximation is accurate enough to get 100 decimal digits.
What about such combination of stupid ideas:
1) Calculate only 2*B or 1.5*B eldest digits and forget all smaller, hoping that rounding error will not be very large
2) Pre-calc and store results for different A, with step, for example, 10^5, or even 10^4. (How large is source file size limit?)
?
Less than 20MB. One problem, I need to be really careful about how large B is. How about b is not too big and also not too small. However ,worth a try.Thank you.
About the first B digits, the problem has something same to this problems in hackerrank. The solution is to calculate the first k digits of x, we calculate log10(round(x/10^k)). => Editoral of it. The function can be calculate easily if we can calculate log(n!) in O(1) or O(log(n)). About calculate log(n!) you can see here.
It's likely to be what I'm looking for. I'm coding now, to see if it works out. And thanks.
Maybe I run into a wrong direction.Still can not solve the problem.Since even if I can calculate log(n!)in a short time,I can't get enough precisions to guarantee that I am able to get first 400 digits of n!.Maybe, I just didn't understand this method.Any help?
You can calculate first digits using prime numbers wiki. There is about 5761455 prime numbers less than 10^8. Use Sieve of Eratosthenes to construct them in one second. Don't forget to use long arithmetics. I think first 500 digits is enough to keep to calculate correctly first 400 digits. To make your solution faster on the testing server you can precompute intermediate multiplication results for n = k, k * 2, k * 3 .... for some fixed K, e.g. k = 100000.
There is about 6500 different powers for prime numbers. so you can build segment tree with partial results of p[1] * p[2] * p[3] ... . then answer one query for 6500 * log (NumOfPrimes) * BigNumDigits
Got it!
Would you please tell the final way with which you were successful ?
Can I just show you the code？I will soon give the link.
Link. I don't not whether this link works, if not, tell me.
Thanks, but unfortunately the link seems to direct me to chinese language(website) which I don't know and even there is some account creation stuff. If you can share it some where else.
I just find it's the easiest way to share my code.... Link
The constraints on B is (1<=B<=50). Why theme title says about 400 first digits?
Sorry, it should be 50, my mistake. What do you mean by "using prime numbers"? --Counting how many times a prime number appears in N! for every prime,and use long arithmetics to multiple them up,and everytime just save first 100 digits(as you point out, B <= 50,100 is enough)? And thank you.
I think the last 100 digits can compute by make a list ,because while N>1000,all the last digits is 0. And the first B digits ,may I use the first B digits to compute?Such as,A=8,B=2,C=1,1*2*3*4=24,then use the first B digis to factory,24*5=120->12,12*6=72->72,72*7=504->50,50*8=400->40 I have not try ,I not sure it is an enable method!!! I hope more acmer provide more and better method.
Seems to be very harsh roundation, so we loose precision. For ex. A=8, B=1:
1*2*3=6, 6*4=2(4), 2*5=1(0), 1*6=6, 6*7=4(2), 4*8=3(2). So we have contradiction between your and my examples — 8! must be starting with 40 and 3.
Using HolyInq`s idea, you can use BigInteger to compute the factorial of A, always taking the remainder by 10**C. It will reach zero in not so much iterations, and you can break if it happens.
Getting the first digits is the toughest part, and I am still not sure of how is the best way to achieve that. I found a lot of ideas on this page and I suggest you take a look on the 100 digits challenge, maybe it helps you: http://www.luschny.de/math/factorial/approx/SimpleCases.html
I am sorry I do not have a very good idea to solve the second part yet...
Anyway，thanks。 I will take a look and learn something.