Facing a lot of difficulty in solving this problem from a long time. Problem Link-SAS002. Naive approach O(sqrt(n)) clearly times out. How to solve this problem in given time limit and what is the intended time complexity of the algorithm? Thought about finding number of divisors in O(n^(1/3)) and using that, after some research.Is that correct approach?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 165 |
| 2 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.11.2024 11:03:05 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Yes, it seems to be the correct approach. This blog describes how to count number of divisors of a a number in O(N1 / 3) and this gives a proof that product of all divisors of N is Nd / 2 where d is the number of divisors of N.
Nice problem! Thanks for sharing.