Привет CodeForces!
Возможно ли находить минимальное простой делитель для чисел n <= 10 ^ 12, а количество запросов до 10 ^ 5?
Заранее большое спасибо
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.12.2024 15:39:31 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Try: Pollard's rho
check the number by each prime number less than 10^4 till it get it smallest prime factor which are around 1200 so it can be done. if prime number less than 10^4 is not factor so it is clear that n have all prime factor greater than 10^4 therefore n can have maximum two no. of factor than there are only three possibility that either
1- Number is itself is prime number so it can be check using Miller Rabin algorithm in O(k(logn)^3)
2- Number is square of prime number so again it can be check
3- Number is product of two distinct prime number. Using Pollard Rho Algorithm we can find the factor of number and smallest number will be smallest prime factor of number in O(n^1/4)
It will be done in O(10^3) Hope it Help!! Sorry for bad English !!
I could never use that Miller Rabin, I always get WA by that.
Is there any good and reliable c++ code for the algorithm?
NOTE : I don't even know the algorithm and don't wanna know it too :). Just need a code.
Also the third part happens when first and second are rejected, You don't have to check it by weird algorithms...
Here is my code Miller Rabin. I didn't get WA till now but now also if you get the WA from this code please ping me so that i can correct my code
In the question we need to apply third part because we need to find smallest prime factor.
I tested your code on some problem and it was OK...
Thank you ;)
Store the primes less than 10^6 and factorise by iterating over primes less than sqrt(N). Complexity will be around sqrt(N)/logN.