Решение задач

Экстремальные виды спорта
Экстремальные виды спорта: Решение задачТоварищи! Давайте делится своими идеями решения задач на последних срмах. Я думаю, что немногие могут решить все три задачи 1-го дивизиона. А зачем ждать, пока на топкодере напишут problem set & analyses к последнему контесту? К тому же, всегда в чужих решениях можно открыть для себя что-то новое :)
28 комментариев
avatar
Гм... Пожалуй я и начну :)

SRM 400, 250div1
Злые ограничения до 10^18... ;)
Но все просто: можно проверить, не является ли наше число N квадратом какого-то простого числа. Если является, то ответ (sqrt(N),2). Если нет - то тогда искомое число является как минимум корнем кубическим от N. Теперь решение очевидно: ищем простые числа до 10^6, а потом проверяем - является ли степень этого простого числа ответом.
avatar
Другой вариант: допустим число N = некоторому простому числу p в степени i, перебираем это i (от 2 до того числа, в которое нужно возвести 2, чтобы получилось >= N), извлекаем корень i-той степени из N (используем либо функцию pow, либо бинарный поиск) и проверяем, является ли получившееся число простым.
avatar
Илья, а теперь вопрос: почему почти половина решений упала на systest'е?

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.