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

Online Judge

Задачи

Авторы

Соревнования

О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки

Архив задач
Отправить на проверку
Состояние проверки
Руководство

Регистрация
Исправить данные
Рейтинг авторов

Текущее соревнование
Расписание
Прошедшие соревнования
Правила

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

Can someone explain this problem to me?

Послано Stefan Ciobaca 22 мар 2002 03:41

I can have my program solve it in sqrt(n) but this is not good enough.
Please tell me how to optimize. 10x in advance

Re: Can someone explain this problem to me?

Послано MadPsyentist/Sam 22 мар 2002 18:04

As I guess, your O(sqrt(n)) time is from finding ap+bq=1 , right?
If so , you can use extended Euclidean algorithm (one which find GCD)
to solve this equation.

Re: Can someone explain this problem to me?

Послано Dragon 19 окт 2002 15:20

Right! I got AC! (the GCD of p and q is 1!!!!!!!)