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

Обсуждение задачи 1673. Допуск к экзамену

question (+)
Послано vav[14] 13 фев 2009 21:35
Is it true that k=f(n), where f(n) is Euler function?

Edited by author 13.02.2009 22:03
Re: question(+)
Послано Vedernikoff Sergey (HSE: EconomicsForever!) 13 фев 2009 21:56
Yes =)
2 ADMINS: don't delete this hint. Really, it's easy to think it out - harder is to write
Re: question(+)
Послано die_young 29 июн 2018 19:59
If anyone got stuck with this.

here is the well-known formula for computing phi function:

phi(n) = product of [ p^{a - 1} * (p - 1) ], where factorized n = product [ p^a ].

The problem has a pretty fast brute force solution. Once you find a number K such that (K + 1) is prime and K divides phi(n) try to construct n with this prime (multiply by (K + 1) once and continue while phi(n) / (K + 1)^b is a multiple of (K + 1)).