Быстро — никак. Нужно использовать перебор с отсечением. Подсказка: какие делители φ(n) могут указывать на факторизацию n?

P.S. Мог бы скинуть исходник, но у меня настолько жуткий говнокод, что Вам лучше его не видеть.

Вот буквально неделю назад решал эту задачу.

Сначала факторизировал число K. Потом, перебрав все его делители, нашёл все такие простые P, что P-1 делит K.

Таким образом получил все простые числа, на которые может делиться N, а так же соответствующие им обязательные степени для нашего K (то-есть факторизация К). Отсортировал эти простые по убыванию и запустил перебор.

На каждом шаге для текущего простого было два варианта:

1)Если текущая степень этого простого для нашего текущего N меньше чем должна быть, то домножить до необходимой степени, и пустить перебор дальше.

2)Если текущая степень равна обязательной, то разветвляем наш перебор: не домножая на это простое P, и домножив на P ( соответственно текущее K домножится на P-1).

Если доходим до конца и текущее К становится равным искомому, то мы получили то, что искали.

Плюс ко всему, всегда проверялась корректность, и то, что текущее N меньше уже полученного... В общем некоторые ветви перебора отсекались.

Решение прошло, но за 1.1 сек. То-есть очень медленно, по сравнению с лучшими решениями, поэтому мне тоже хотелось бы услышать другие идеи решения этой задачи=)

Объяснять я конечно не мастер, да и решение объёмное, но вот так в общем...)

It is the same problem I have.

It is the same problem I have.

попробуй бинпоиском искать среди отсортированных (по парам в векторе пар, дабы фиксировался номер функции) значений функции эйлера и так искать