| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
I am getting TLE on last test case of this problem Link to the problem, i used Big mod Link to Big mod implmentation for multiplication while calculating power as we need last ten digits so we have to modulo it by 1e10 which will overflow in C++.
Any type of help is appreciated. Thanks in advance.
Auto comment: topic has been updated by Not-Afraid (previous revision, new revision, compare).
BigMod implementation adds another factor of $$$log (MOD)$$$, making the time complexity $$$O(n log n log MOD)$$$.To remove the $$$log (MOD)$$$ factor, You can compute the remainder modulo $$$2^{10}$$$ and $$$5^{10}$$$, and then find the remainder modulo $$$10^{10}$$$ using chinese remainder theorem.
can we do it without CRT ??
Thanks! I solved it using CRT. Solution
I found an implementation for Big mod in Discussion form of this question Ideone Link but couldn't understand what is it doing exactly, if you can help?