| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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.