| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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 ?
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.