| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
So I was trying to solve this problem: Link
I got a TLE, my submission
I'm not sure if the solution is correct but I want to know why am I getting TLE, I think my solution is O(n), buy maybe because the numbers are too big I'm miscalculating something. I've added comments to my code too please let me know why is getting TLE. Thanks!
You have overflow here:
i * i <= minnNote that you are dividing/modding by 64-bit numbers. Since the size is fixed, the operation takes O(1). Generally I think 64-bit is about twice as slow as 32-bit, but it is quite fast in any case. If you were dividing by arbitrarily large numbers, then it's implementation dependent but apparently it can be as fast as O(nlog n), where n is the number of bits in the number. I think the nlog n algorithm has a terrible constant though :P (https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions)