Обсуждение @ 1204. Идемпотенты @ Timus Online Judge

Timus Online Judge

Online Judge	Задачи	Авторы	Соревнования
О системе Часто задаваемые вопросы Новости сайта Форум Ссылки	Архив задач Отправить на проверку Состояние проверки Руководство	Регистрация Исправить данные Рейтинг авторов	Текущее соревнование Расписание Прошедшие соревнования Правила

вернуться в форум

Обсуждение задачи 1204. Идемпотенты

Blue cat Yes,I know all this.My algorithm is O(sqrt(n)),but I got Time Limited exceeded.The program uses only 1.5 sec at my computer when K=1000 and the dataset is random.It will cost also O(sqrt(n)) to get p [3] // Задача 1204. Идемпотенты 19 мар 2002 15:46

I have answers to all your questions :) Use precalc. array of all primes <= sqrt(10^9), I think ur program'll be much faster [2] // Задача 1204. Идемпотенты 19 мар 2002 15:57

>

Blue cat You think I'm so fool.Of course,I know such trick.Maybe the timelimit is too strict.I'll try more [1] // Задача 1204. Идемпотенты 19 мар 2002 15:59

> >

Leonid Volkov This problem has a solution fastre than O(sqrt(N)) // Задача 1204. Идемпотенты 20 мар 2002 11:41

It has a pure analitical solution with almost no cycles needed :-)
The test are specially made so to do not allow all the possible O(sqrt
(N)) solutions pass!