Ответа на комментарий по задаче так и не получил, поэтому перепост.

Мне кажется, для любых a и t верно утверждение



если



Это связано с тем, что в последовательности предпериод не превосходит степени максимального простого в t, а период после разложения t = t₁t₂ на часть t₁, взаимно простую с a и все остальное будет совпадать по длине с периодом , делителем , делителем

Прошу доказать строго или опровергнуть.

Примитивной программой проверил до t <= 100, n < t*4, работает.

Как использовать этот факт, если это верно? 

Например, расчет быстрым возведением в степень требует либо представления числа n в двоичной системе счисления, либо использования десятичного возведения в степень с плохой константой. При ограничениях a, b ≤ 10⁶, n ≤ 10^10000000 быстрое возведение в степень невозможно.

С уточнениями от freopen