Дается число N. Требуется найти наименьшее число меньшей N с наибольшим количеством делителей.N <= 10^16.1 и само число являются делителем.
Дается число N. Требуется найти наименьшее число меньшей N с наибольшим количеством делителей.N <= 10^16.1 и само число являются делителем.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
N <= ?
Речь идет о простых делителях или не только? Какие ограничения на N?
Если о простых, то учитываются ли одинаковые делители как один или несколько? Если как один, берем произведение 2 * 3 * 5 * 7 * ..., если как несколько, то ответ — ближайшая снизу степень двойки
В противном случае. Если число N факторизуется как N = ax1 * bx2 * ... * zxn, то число его делителей равно (x1 + 1)(x2 + 1)..(xn + 1)
Дальше все зависит от ограничений, можно, например, сделать предподсчет, можно, что-то еще.
дальше понятно, что нам не имеет смысла пропускать простые, т.е. наш ответ имеет вид 2^x1 * 3^x2 * 5^x3..., дальше понятно, что x1 >= x2, x2 >= x3, ..., xn — 1 >= xn. Еще понятно, что нам хватает первых 20 простых(примерно) и что никакое простое не надо брать в степени больше чем 50(примерно). Поэтому пишем перебор. Ну там может отсек каких-нибудь добавить.
Вы из карКТЛа?
Нет
1) Цикл до корня из N, находим все делители (в 2 сек должно уложиться)
2) Среди найденных делителей выделяем простые числа
3) Для каждого найденного делителя считаем количество делителей (либо в лоб, либо используя простые числа из пункта (2) и формулу из коммента ниже)
Это боян с тимуса: http://acm.timus.ru/problem.aspx?space=1&num=1748, решается перебором с отсечениями. Текущий ответ храним как список (сколько двоек, сколько троек, сколько пятерок и т.д.), причем значения в этом списке всегда неубывают. На очередном этапе перебора добавляем к имеющемуся набору простых делителей еще один — либо такой же как последний, либо следующий.