Ещё одна задача у нас была с того же контеста, называется Fibonacci Period, дано число r, числа фибоначчи вычисляются по модулю r. Требуется найти период последовательности. r до 10^9.

Подскажите как можно решить эти задачи. По второй получилось только зависимость от разложения числа на простые, но это ничего не дает, так как для простых ответы тоже не известно как получить.