[задачи][числовая последовательность] Задача о последовательности остатков от деления

>Я ищу не ответ, а путь к решению, подсказку

Посмотри методы, связанные с «китайской теоремой об остатках».

http://ru.wikipedia.org/wiki/Конечное_поле

Кнут том 2.

> Конечное поле

Особенно для M=4, да

Есть мысль о том, как задачу свести к теореме Эйлера.

a1 = X * a0 + Y, a2 = X * (X * a0 + Y) + Y, a3 = ..., an = X^n * a0 + (X^(n-1) + ... + 1) * Y

Соответственно, надо бы найти минимальное n, такое что an = a0 (mod M). Переносим a0 влево и делаем чуток преобразований.

(X^n - 1) * a0 + (X^(n-1) + ... + 1) * Y = (X^(n-1) + ... + 1) * ((X - 1) * a0 + Y) = 0 (mod M) — такое уравнение уже решать проще, ибо можно разделить на Z = НОД(M, (X - 1) * a0 + Y), пусть M' = M / Z. Тогда уравнение сводится к X^(n-1) + ... + 1 = 0 (mod M'). Что можно домножить на X - 1 и получить красоту.

X^n - 1 = 0 (mod M'*(X - 1)), где минимальный n можно найти по теореме Эйлера.

Таким образом для решения задачи требуется применить алгоритм Евклида и посчитать функцию Эйлера (что легко делается, если применить разложение на множители).

Хм, тут правда есть некоторая трудность, что теорема Эйлера только для взаимнопростых чисел работает, да и с a0 сравнивать не очень корректно в случае, когда цикл не сразу начинается. В общем, надо бы додумать.

Я бы, честно говоря, забил на эту теорию и взял обыкновенный алгоритм с зайцем и черепахой. http://en.wikipedia.org/wiki/Cycle_detection

О, придумал.

Берем не an = a0 (mod M), но an = ak (mod M). Так же, как и раньше, вычитаем a0 и раскладываем на множители: ((X - 1) * a0 + Y) * (X^(n-1) + ... + 1) = ((X - 1) * a0 + Y) * (X^(k-1) + ... + 1) (mod M); так же, как и раньше, делим на НОД: X^(n-1) + ... + 1 = X^(k-1) + ... + 1 (mod M'); так же, как и раньше, умножаем на X-1: X^n - 1 = X^k - 1 (mod M"), где M" = M' * (X - 1).

Получили уравнение X^n = X^k (mod M"), в котором нужно найти минимальные неравные n и k, далее X^k * (X^(n-k) - 1) = 0 (mod M"). Дальше надо рассматривать разложения на множители X и M". Те множители, которые у них общие, набираются с помощью X^k, а остальные с помощью X^(n-k) - 1. Для первого нужно разложение на простые множители, а для второго теорема Эйлера. Всё.

Итог - оказывается, для этой последовательности можно воспользовать отображением числа последовательности на его номер в ней. До зацикливания все числа уникальны. Всем спасибо за подсказки.