could any one post code for the followong question.
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 22:35:56 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
This question is pretty simple if you have Pollard Rho algorithm in your library. It's a straight copy and paste.
Here you go :
http://ideone.com/3dnYAv
Note: I think there is some way ( which I don't know ) to solve this question without this algorithm.
Blog Post
First remove all prime factors that are less than 10^6. Let x be the resulting number. Now check if x is prime or not using miller-rabin. If it is prime then we already have the prime factorization. If x is not prime we know that the remaining prime factors are greater than 10^6, therefore it must have exactly two prime factors (since having 3 or more would yield a number greater than 10^18). Now we need to know whether those prime factors are equal or not, we can simply check if x is a square or not, we can do this be testing if x == pow(int(sqrt(x) + .5), 2). With these you should be able to get the number of divisors.
Correct me if I'm wrong, but isn't miller rabin unreliable especially for programming contests?
Depends on the implementation, you can guarantee that the algorithm will work up to certain value. Here is an example that will work for numbers up to 3*10^18:
http://pastebin.com/6XEFRPaZ
Is it garanteed that x == pow(int(sqrt(x) + .5), 2) works for every case (precision loss)?? I remember doing something similar and getting wrong answer, so I just iterated from sqrt(x)-5 till sqrt(x)+5 to avoid that, though probably sqrt(x) and sqrt(x)+1 are enough.
here is a recent blog post by himanshujaju.