Link to the problem : https://www.codechef.com/FCF32020/problems/PATHWAY
Link to the code : https://www.codechef.com/viewsolution/38865614
In this code , how can python compute factorials of (N+M) ( N+M is in the order of 10^5 ) so fast? Can anyone explain this ? How did the python interpreter optimize it ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
I googled. It's written in C and it seems that they have a clever algorithm for that too. $$$10^5!$$$ fits in memory nicely and it's not too bad if you have a fast multiplication algorithm too.
I had imagined it would be astronomically large number. But it has just around 5e5 digits.
Thanks a lot for answering.
$$$10^5! \le (10^5)^{10^5} = 10^{5e5}$$$, so it doesn't have that many digits. It is of course very big number, but there are different levels of being a huge number and this is still quite manageable as computations go
Yeah, it was a stupid mistake of mine. I don't know why but thought it will have $$$10^{5e5}$$$ digits. I guess I was not thinking straight back then.
It will have 5e5 + 1 digits so if you have the available memory, python can do it
This website calculates the factorial of 50 digit number in just a few seconds. I wonder how?
Well, this site doesn't calculate factorial of big number, it instead calculates some characteristics of that factorial (number of trailing zeroes, last non-zero digits, first digits). Obviously, one cannot hold such a big number in memory.
hmm. gotcha.