Let \(\pi(n)\) denote the Pisano period of the Fibonacci sequence modulo \(n\), meaning the smallest positive period of the pair \((F_m,F_{m+1})\) modulo \(n\). For each positive integer \(p\), define \(M(p)\) as the largest integer \(n\) such that \(\pi(n)=p\), and set \(M(p)=1\) when no such \(n\) exists.
The problem asks for
$$P(n)=\prod_{p=1}^{n} M(p),$$
with the specific target
$$P(10^6)\bmod 1{,}234{,}567{,}891.$$
A brute-force search over moduli and periods would be far too slow. The implementation instead starts from a structural classification of which period lengths can appear as maximal Pisano periods.
The key mathematical reduction used by the implementation is that almost every factor \(M(p)\) is trivial, and the nontrivial factors can be written directly in terms of Fibonacci and Lucas numbers.
The implementation relies on the following classification:
$$M(2)=1,\qquad M(3)=2,$$
and for every odd \(p>3\),
$$M(p)=1.$$
So odd indices contribute nothing except \(p=3\). That already collapses the product to one special odd factor and a family of even factors.
Write the Fibonacci and Lucas sequences as
$$F_0=0,\quad F_1=1,\quad F_k=F_{k-1}+F_{k-2}\quad (k\ge 2),$$
$$L_0=2,\quad L_1=1,\quad L_k=L_{k-1}+L_{k-2}\quad (k\ge 2).$$
For every \(k\ge 2\), the maximal modulus with Pisano period \(2k\) is given by
$$M(2k)= \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
This rule is exactly what the implementation uses. A few small values make the pattern concrete:
$$M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(18)=L_9=76.$$
Once the odd factors are simplified, the product for \(n\ge 3\) becomes
$$P(n)=M(3)\prod_{k=2}^{\lfloor n/2\rfloor} M(2k).$$
Since \(M(3)=2\), this is
$$P(n)=2\prod_{k=2}^{\lfloor n/2\rfloor} \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
That formula removes all period searching. The remaining task is only to generate Fibonacci and Lucas values in order and multiply the correct one at each step.
Recomputing \(F_k\) or \(L_k\) from scratch for every \(k\) would waste time. Instead, because both sequences satisfy the same second-order recurrence, we can advance them together in one forward pass:
$$F_{k}=F_{k-1}+F_{k-2},\qquad L_{k}=L_{k-1}+L_{k-2}.$$
At step \(k\), only the two most recent Fibonacci values and the two most recent Lucas values are needed. After advancing once, the algorithm multiplies the running answer by \(L_k\) when \(k\) is odd and by \(F_k\) when \(k\) is even, always reducing modulo \(1{,}234{,}567{,}891\).
The sample checkpoint used by the implementation is easy to recover from the closed form.
For \(1\le p\le 10\), the nontrivial factors are
$$M(3)=2,\qquad M(4)=F_2=1,\qquad M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(10)=L_5=11.$$
All remaining factors are \(1\). Therefore
$$\begin{aligned} P(10) &=M(1)M(2)\cdots M(10)\\ &=1\cdot 1\cdot 2\cdot 1\cdot 1\cdot 4\cdot 1\cdot 3\cdot 1\cdot 11\\ &=264. \end{aligned}$$
This matches the value produced by the implementation.
The C++, Python, and Java implementations all use the same plan. They first handle the exceptional factor \(M(3)=2\) when \(n\ge 3\). Then they iterate \(k\) from \(1\) to \(\lfloor n/2\rfloor\), maintaining consecutive Fibonacci and Lucas terms modulo the required modulus.
Beginning with the first nontrivial step \(k=2\), each iteration advances both recurrences once. If \(k\) is odd, the current Lucas term is multiplied into the running product; if \(k\) is even, the current Fibonacci term is used instead. Because every multiplication is reduced immediately modulo \(1{,}234{,}567{,}891\), the computation stays bounded and never needs big-integer storage of the full product.
The loop runs for exactly \(\lfloor n/2\rfloor\) iterations. Each iteration performs a constant amount of work: a few modular additions, one parity test, and at most one modular multiplication. Therefore the running time is \(O(n)\), and the memory usage is \(O(1)\).
For \(n=10^6\), this means only about \(500{,}000\) recurrence steps, which is easily practical.
Sei \(\pi(n)\) die Pisano-Periode der Fibonacci-Folge modulo \(n\), also die kleinste positive Periodenlänge des Paares \((F_m,F_{m+1})\) modulo \(n\). Für jedes positive \(p\) sei \(M(p)\) das größte \(n\) mit \(\pi(n)=p\); existiert kein solches \(n\), so setzt man \(M(p)=1\).
Gesucht ist
$$P(n)=\prod_{p=1}^{n} M(p),$$
insbesondere
$$P(10^6)\bmod 1{,}234{,}567{,}891.$$
Eine direkte Suche über Moduli und Perioden wäre viel zu teuer. Die Lösung beginnt deshalb mit einer Strukturklassifikation der Periodenlängen, die als maximale Pisano-Perioden auftreten können.
Die zentrale Vereinfachung lautet: Fast alle Faktoren \(M(p)\) sind gleich \(1\), und die übrigen lassen sich direkt durch Fibonacci- und Lucas-Zahlen ausdrücken.
Die Implementierung benutzt die Klassifikation
$$M(2)=1,\qquad M(3)=2,$$
und für jedes ungerade \(p>3\) gilt
$$M(p)=1.$$
Damit tragen ungerade Indizes nichts bei, außer dem Sonderfall \(p=3\). Das Produkt reduziert sich also auf einen speziellen ungeraden Faktor und eine Familie gerader Faktoren.
Die Fibonacci- und Lucas-Folgen seien definiert durch
$$F_0=0,\quad F_1=1,\quad F_k=F_{k-1}+F_{k-2}\quad (k\ge 2),$$
$$L_0=2,\quad L_1=1,\quad L_k=L_{k-1}+L_{k-2}\quad (k\ge 2).$$
Für jedes \(k\ge 2\) gilt dann
$$M(2k)= \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
Genau diese Fallunterscheidung verwendet der Code. Kleine Beispiele sind
$$M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(18)=L_9=76.$$
Nach dem Wegfall der ungeraden Faktoren erhält man für \(n\ge 3\)
$$P(n)=M(3)\prod_{k=2}^{\lfloor n/2\rfloor} M(2k).$$
Wegen \(M(3)=2\) wird daraus
$$P(n)=2\prod_{k=2}^{\lfloor n/2\rfloor} \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
Damit entfällt jede explizite Periodensuche. Man muss nur noch die Fibonacci- und Lucas-Werte der Reihe nach erzeugen und jeweils den passenden Faktor multiplizieren.
Es wäre unnötig, \(F_k\) oder \(L_k\) für jedes \(k\) neu zu berechnen. Beide Folgen erfüllen dieselbe lineare Rekursion zweiter Ordnung, daher lassen sie sich in einem einzigen Durchlauf gemeinsam fortschreiben:
$$F_k=F_{k-1}+F_{k-2},\qquad L_k=L_{k-1}+L_{k-2}.$$
Im Schritt \(k\) genügen jeweils die beiden zuletzt bekannten Fibonacci- und Lucas-Werte. Nach einem Vorwärtsschritt multipliziert der Algorithmus bei ungeradem \(k\) mit \(L_k\) und bei geradem \(k\) mit \(F_k\), stets modulo \(1{,}234{,}567{,}891\).
Der kleine Kontrollwert der Implementierung folgt sofort aus der geschlossenen Form.
Für \(1\le p\le 10\) sind die nichttrivialen Faktoren
$$M(3)=2,\qquad M(4)=F_2=1,\qquad M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(10)=L_5=11.$$
Alle übrigen Faktoren sind \(1\). Also
$$\begin{aligned} P(10) &=M(1)M(2)\cdots M(10)\\ &=1\cdot 1\cdot 2\cdot 1\cdot 1\cdot 4\cdot 1\cdot 3\cdot 1\cdot 11\\ &=264. \end{aligned}$$
Genau dieser Wert wird von der Implementierung erzeugt.
Die C++-, Python- und Java-Implementierungen verfolgen denselben Ablauf. Zuerst wird der Ausnahmefaktor \(M(3)=2\) berücksichtigt, sobald \(n\ge 3\) ist. Danach läuft eine Schleife über \(k=1,\dots,\lfloor n/2\rfloor\), wobei fortlaufend benachbarte Fibonacci- und Lucas-Werte modulo dem geforderten Modulus gespeichert werden.
Ab dem ersten nichttrivialen Schritt \(k=2\) werden beide Rekursionen pro Iteration genau einmal fortgesetzt. Ist \(k\) ungerade, wird der aktuelle Lucas-Wert in das Produkt aufgenommen; ist \(k\) gerade, der aktuelle Fibonacci-Wert. Durch die sofortige Reduktion modulo \(1{,}234{,}567{,}891\) bleiben alle Zwischenwerte kontrolliert.
Die Schleife hat genau \(\lfloor n/2\rfloor\) Iterationen. Pro Iteration fallen nur konstant viele Operationen an: einige modulare Additionen, ein Paritätstest und höchstens eine modulare Multiplikation. Daher beträgt die Laufzeit \(O(n)\), und der Speicherverbrauch ist \(O(1)\).
Für \(n=10^6\) sind das nur ungefähr \(500{,}000\) Rekursionsschritte und damit problemlos praktikabel.
\(\pi(n)\), Fibonacci dizisinin \(n\) ile bölümünden kalanlar altında oluşan Pisano periyodu olsun; yani \((F_m,F_{m+1})\) çiftinin mod \(n\) altında tekrar etmeye başladığı en küçük pozitif dönem uzunluğu. Her pozitif \(p\) için \(M(p)\), \(\pi(n)=p\) koşulunu sağlayan en büyük \(n\) olarak tanımlanır; böyle bir \(n\) yoksa \(M(p)=1\) alınır.
İstenen büyüklük
$$P(n)=\prod_{p=1}^{n} M(p),$$
ve özel hedef
$$P(10^6)\bmod 1{,}234{,}567{,}891$$
değeridir. Tüm modları tek tek tarayıp Pisano periyotlarını bulmak pratik değildir. Uygulama bunun yerine hangi periyot uzunluklarının en büyük örnek verdiğini söyleyen yapısal sınıflandırmadan başlar.
Uygulamanın kullandığı temel sadeleşme şudur: \(M(p)\) çarpanlarının büyük çoğunluğu zaten \(1\)'dir ve geri kalanlar Fibonacci ile Lucas sayıları cinsinden doğrudan yazılabilir.
Uygulama şu sınıflandırmayı esas alır:
$$M(2)=1,\qquad M(3)=2,$$
ve her tek \(p>3\) için
$$M(p)=1.$$
Böylece tek indeksler içinde yalnızca \(p=3\) gerçek katkı yapar. Geriye bir özel tek terim ve çift periyotlardan gelen bir aile kalır.
Fibonacci ve Lucas dizilerini
$$F_0=0,\quad F_1=1,\quad F_k=F_{k-1}+F_{k-2}\quad (k\ge 2),$$
$$L_0=2,\quad L_1=1,\quad L_k=L_{k-1}+L_{k-2}\quad (k\ge 2)$$
şeklinde tanımlayalım. O zaman her \(k\ge 2\) için
$$M(2k)= \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
Yani \(k\) tekse Lucas, \(k\) çiftse Fibonacci terimi kullanılır. Küçük birkaç örnek bu deseni açıkça gösterir:
$$M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(18)=L_9=76.$$
Tek periyotların büyük kısmı yok olunca, \(n\ge 3\) için
$$P(n)=M(3)\prod_{k=2}^{\lfloor n/2\rfloor} M(2k)$$
elde edilir. \(M(3)=2\) olduğundan
$$P(n)=2\prod_{k=2}^{\lfloor n/2\rfloor} \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
Böylece artık hiçbir \(n\) için Pisano periyodu aramaya gerek kalmaz. Sadece uygun Fibonacci ve Lucas terimlerini sırayla üretip çarpmak yeterlidir.
Her \(k\) için \(F_k\) ve \(L_k\)'yi sıfırdan üretmek gereksizdir. Her iki dizi de aynı ikinci dereceden yinelemeyi sağladığı için tek ileri geçişte birlikte güncellenebilir:
$$F_k=F_{k-1}+F_{k-2},\qquad L_k=L_{k-1}+L_{k-2}.$$
\(k\) adımında yalnızca son iki Fibonacci ve son iki Lucas değeri gerekir. Bir kez ileri gidildikten sonra \(k\) tekse \(L_k\), çiftse \(F_k\) çalışan ürüne çarpılır ve her adımda sonuç \(1{,}234{,}567{,}891\) moduna indirilir.
Uygulamadaki küçük kontrol değeri kapalı formdan doğrudan elde edilir.
\(1\le p\le 10\) için sıfırdan farklı katkı yapan çarpanlar
$$M(3)=2,\qquad M(4)=F_2=1,\qquad M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(10)=L_5=11.$$
Diğer tüm çarpanlar \(1\)'dir. Dolayısıyla
$$\begin{aligned} P(10) &=M(1)M(2)\cdots M(10)\\ &=1\cdot 1\cdot 2\cdot 1\cdot 1\cdot 4\cdot 1\cdot 3\cdot 1\cdot 11\\ &=264. \end{aligned}$$
Bu değer uygulamanın ürettiği sonuçla aynıdır.
C++, Python ve Java uygulamaları aynı planı izler. Önce \(n\ge 3\) ise istisnai çarpan \(M(3)=2\) sonuca eklenir. Daha sonra \(k=1\) ile \(\lfloor n/2\rfloor\) arasında ilerleyen bir döngü içinde, ardışık Fibonacci ve Lucas terimleri gerekli mod altında tutulur.
İlk anlamlı adım olan \(k=2\)'den itibaren her iterasyonda iki yineleme birer kez güncellenir. \(k\) tekse o andaki Lucas terimi, çiftse o andaki Fibonacci terimi çarpıma katılır. Her çarpım hemen \(1{,}234{,}567{,}891\) moduna indirildiği için ara değerler büyümez.
Döngü tam olarak \(\lfloor n/2\rfloor\) kez çalışır. Her adımda sabit sayıda işlem vardır: birkaç modlu toplama, bir parity kontrolü ve en fazla bir modlu çarpma. Bu yüzden zaman karmaşıklığı \(O(n)\), bellek kullanımı \(O(1)\) olur.
\(n=10^6\) için bu yaklaşık \(500{,}000\) yineleme demektir; dolayısıyla yaklaşım fazlasıyla pratiktir.
Sea \(\pi(n)\) el período de Pisano de la sucesión de Fibonacci módulo \(n\), es decir, la menor longitud positiva con la que se repite el par \((F_m,F_{m+1})\) módulo \(n\). Para cada entero positivo \(p\), definimos \(M(p)\) como el mayor \(n\) tal que \(\pi(n)=p\), y fijamos \(M(p)=1\) si no existe ningún \(n\) con esa propiedad.
Debemos calcular
$$P(n)=\prod_{p=1}^{n} M(p),$$
en particular
$$P(10^6)\bmod 1{,}234{,}567{,}891.$$
Buscar directamente todos los módulos y sus períodos sería demasiado costoso. La implementación parte en cambio de una clasificación estructural de qué longitudes de período aparecen como máximos períodos de Pisano.
La simplificación central es que casi todos los factores \(M(p)\) son triviales, y los que no lo son pueden escribirse de forma explícita con números de Fibonacci y de Lucas.
La implementación usa la clasificación
$$M(2)=1,\qquad M(3)=2,$$
y para todo impar \(p>3\),
$$M(p)=1.$$
Así, entre los índices impares solo \(p=3\) aporta algo distinto de \(1\). El producto total queda reducido a un único factor impar especial y a una familia de factores pares.
Definimos las sucesiones de Fibonacci y Lucas por
$$F_0=0,\quad F_1=1,\quad F_k=F_{k-1}+F_{k-2}\quad (k\ge 2),$$
$$L_0=2,\quad L_1=1,\quad L_k=L_{k-1}+L_{k-2}\quad (k\ge 2).$$
Entonces, para todo \(k\ge 2\), se cumple
$$M(2k)= \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
Esa es exactamente la regla que siguen las implementaciones. Algunos valores pequeños ayudan a verla en acción:
$$M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(18)=L_9=76.$$
Después de eliminar los factores impares triviales, para \(n\ge 3\) queda
$$P(n)=M(3)\prod_{k=2}^{\lfloor n/2\rfloor} M(2k).$$
Como \(M(3)=2\), obtenemos
$$P(n)=2\prod_{k=2}^{\lfloor n/2\rfloor} \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
La búsqueda de períodos desaparece por completo. Solo hace falta generar en orden los términos adecuados de Fibonacci y Lucas e ir multiplicándolos.
Sería ineficiente recalcular \(F_k\) o \(L_k\) desde cero para cada \(k\). Como ambas sucesiones satisfacen la misma recurrencia lineal de segundo orden, pueden avanzarse juntas en una sola pasada:
$$F_k=F_{k-1}+F_{k-2},\qquad L_k=L_{k-1}+L_{k-2}.$$
En el paso \(k\) solo se necesitan los dos términos más recientes de cada sucesión. Tras actualizar una vez, el algoritmo multiplica por \(L_k\) si \(k\) es impar y por \(F_k\) si \(k\) es par, reduciendo siempre módulo \(1{,}234{,}567{,}891\).
El pequeño valor de control usado por la implementación sale directamente de la fórmula cerrada.
Para \(1\le p\le 10\), los factores no triviales son
$$M(3)=2,\qquad M(4)=F_2=1,\qquad M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(10)=L_5=11.$$
Todos los demás factores valen \(1\). Por tanto,
$$\begin{aligned} P(10) &=M(1)M(2)\cdots M(10)\\ &=1\cdot 1\cdot 2\cdot 1\cdot 1\cdot 4\cdot 1\cdot 3\cdot 1\cdot 11\\ &=264. \end{aligned}$$
Ese es exactamente el valor producido por la implementación.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero incorporan el factor excepcional \(M(3)=2\) cuando \(n\ge 3\). Después recorren \(k=1,2,\dots,\lfloor n/2\rfloor\), manteniendo términos consecutivos de Fibonacci y Lucas reducidos módulo el valor pedido.
A partir del primer paso no trivial \(k=2\), cada iteración avanza una vez ambas recurrencias. Si \(k\) es impar, se multiplica el término actual de Lucas; si \(k\) es par, el término actual de Fibonacci. Como cada producto se reduce inmediatamente módulo \(1{,}234{,}567{,}891\), no hace falta almacenar el producto exacto completo.
El bucle realiza exactamente \(\lfloor n/2\rfloor\) iteraciones. Cada iteración contiene una cantidad constante de trabajo: unas pocas sumas modulares, una comprobación de paridad y como mucho una multiplicación modular. En consecuencia, el tiempo total es \(O(n)\) y la memoria es \(O(1)\).
Para \(n=10^6\), eso equivale a unas \(500{,}000\) actualizaciones de recurrencias, perfectamente manejables.
设 \(\pi(n)\) 表示 Fibonacci 数列模 \(n\) 的 Pisano 周期，也就是数对 \((F_m,F_{m+1})\) 在模 \(n\) 意义下重新开始重复时的最小正周期。对每个正整数 \(p\)，定义 \(M(p)\) 为满足 \(\pi(n)=p\) 的最大整数 \(n\)；如果不存在这样的 \(n\)，就规定 \(M(p)=1\)。
题目要求计算
$$P(n)=\prod_{p=1}^{n} M(p),$$
特别是
$$P(10^6)\bmod 1{,}234{,}567{,}891.$$
如果直接枚举模数并逐个求 Pisano 周期，代价会非常高。实现采用的思路不是“搜索每个周期”，而是先使用一个结构性结论：哪些周期长度会对应到“最大的模数”，以及这些最大模数到底长什么样。
实现所依赖的核心简化是：绝大多数 \(M(p)\) 实际上都等于 \(1\)，而真正需要乘进去的那些项，可以直接写成 Fibonacci 数和 Lucas 数。
实现使用的分类结论是
$$M(2)=1,\qquad M(3)=2,$$
并且对所有奇数 \(p>3\)，都有
$$M(p)=1.$$
这意味着在所有奇数周期里，只有 \(p=3\) 会给乘积带来非平凡贡献；其余奇数周期全部贡献 \(1\)。因此总乘积立刻缩减为一个特殊的奇数项，加上一串偶数周期项。
先写出 Fibonacci 数列与 Lucas 数列：
$$F_0=0,\quad F_1=1,\quad F_k=F_{k-1}+F_{k-2}\quad (k\ge 2),$$
$$L_0=2,\quad L_1=1,\quad L_k=L_{k-1}+L_{k-2}\quad (k\ge 2).$$
对每个 \(k\ge 2\)，实现采用的规则是
$$M(2k)= \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
也就是说，\(k\) 为奇数时取 Lucas 数 \(L_k\)，\(k\) 为偶数时取 Fibonacci 数 \(F_k\)。这个规则正是程序中的数学核心。几个小例子很能说明问题：
$$M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(18)=L_9=76.$$
一旦接受这个分类，后续工作就不再涉及对 Pisano 周期的搜索，而只剩下顺序生成数列项并做模乘。
由于除了 \(p=3\) 之外的奇数项都等于 \(1\)，当 \(n\ge 3\) 时就有
$$P(n)=M(3)\prod_{k=2}^{\lfloor n/2\rfloor} M(2k).$$
又因为 \(M(3)=2\)，所以可进一步写成
$$P(n)=2\prod_{k=2}^{\lfloor n/2\rfloor} \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
这个公式已经把题目化成了一个非常直接的计算任务：从 \(k=2\) 开始依次往前走，如果 \(k\) 是奇数，就把当前 Lucas 项乘进去；如果 \(k\) 是偶数，就把当前 Fibonacci 项乘进去。
如果对每个 \(k\) 都从头计算 \(F_k\) 和 \(L_k\)，会浪费很多重复工作。幸运的是，两条数列都满足同一个二阶线性递推：
$$F_k=F_{k-1}+F_{k-2},\qquad L_k=L_{k-1}+L_{k-2}.$$
因此实现可以只保留每条数列最近的两个值，然后从小到大同步推进。走到第 \(k\) 步时，先把 Fibonacci 和 Lucas 都前进一步，再根据 \(k\) 的奇偶性决定把哪一个值乘到答案上。每一步都立即对模数 \(1{,}234{,}567{,}891\) 取模，这样中间结果始终保持在受控范围内。
这就是为什么实现只需要常数个状态，却能顺序完成整个乘积。
实现中用到的一个小检查值是 \(P(10)=264\)。这个数可以直接从上面的闭式恢复出来。
在 \(1\le p\le 10\) 中，非平凡项为
$$M(3)=2,\qquad M(4)=F_2=1,\qquad M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(10)=L_5=11.$$
其他所有项都等于 \(1\)。于是
$$\begin{aligned} P(10) &=M(1)M(2)\cdots M(10)\\ &=1\cdot 1\cdot 2\cdot 1\cdot 1\cdot 4\cdot 1\cdot 3\cdot 1\cdot 11\\ &=264. \end{aligned}$$
这个例子既验证了公式，也准确说明了程序实际在乘哪些项。
C++、Python 和 Java 三个实现采用的是同一个算法框架。首先，如果 \(n\ge 3\)，它们会单独把特殊因子 \(M(3)=2\) 乘进答案。然后程序让 \(k\) 从 \(1\) 走到 \(\lfloor n/2\rfloor\)，同时维护 Fibonacci 数列和 Lucas 数列中相邻的几个值，并且始终在给定模数下更新。
从第一个真正有贡献的 \(k=2\) 开始，每次循环都会把两条递推同时前进一步。随后检查 \(k\) 的奇偶性：若 \(k\) 为奇数，就把当前 Lucas 项乘入结果；若 \(k\) 为偶数，就把当前 Fibonacci 项乘入结果。因为每次乘法后都立即取模，所以实现不需要保存完整的大整数乘积，也不需要高精度库来存放最终乘积的真实大小。
循环总共执行 \(\lfloor n/2\rfloor\) 次。每一次迭代只做常数数量的工作：几次模加法，一次奇偶判断，以及至多一次模乘。因此总时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)。
当 \(n=10^6\) 时，这只意味着大约 \(500{,}000\) 次递推更新，完全在可接受范围内。
Пусть \(\pi(n)\) обозначает период Пизано для последовательности Фибоначчи по модулю \(n\), то есть наименьшую положительную длину периода пары \((F_m,F_{m+1})\) по модулю \(n\). Для каждого положительного \(p\) определим \(M(p)\) как наибольшее число \(n\), для которого \(\pi(n)=p\); если такого \(n\) нет, полагаем \(M(p)=1\).
Нужно вычислить
$$P(n)=\prod_{p=1}^{n} M(p),$$
а именно
$$P(10^6)\bmod 1{,}234{,}567{,}891.$$
Прямой перебор модулей и последующий поиск их периодов был бы слишком дорогим. Поэтому реализация опирается на структурное описание того, какие длины периодов вообще дают максимальный модуль.
Главное упрощение состоит в том, что почти все множители \(M(p)\) равны \(1\), а нетривиальные множители можно выписать напрямую через числа Фибоначчи и Лукаса.
Реализация использует следующую классификацию:
$$M(2)=1,\qquad M(3)=2,$$
а для каждого нечётного \(p>3\) выполняется
$$M(p)=1.$$
Значит, среди нечётных индексов только \(p=3\) даёт нетривиальный вклад. Всё произведение сводится к одному особому нечётному множителю и к семейству чётных множителей.
Последовательности Фибоначчи и Лукаса задаются так:
$$F_0=0,\quad F_1=1,\quad F_k=F_{k-1}+F_{k-2}\quad (k\ge 2),$$
$$L_0=2,\quad L_1=1,\quad L_k=L_{k-1}+L_{k-2}\quad (k\ge 2).$$
Для каждого \(k\ge 2\) используется правило
$$M(2k)= \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
Именно это ветвление реализовано в программе. Небольшие примеры:
$$M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(18)=L_9=76.$$
После того как нечётные тривиальные множители отброшены, для \(n\ge 3\) получаем
$$P(n)=M(3)\prod_{k=2}^{\lfloor n/2\rfloor} M(2k).$$
Так как \(M(3)=2\), это превращается в
$$P(n)=2\prod_{k=2}^{\lfloor n/2\rfloor} \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
Тем самым задача больше не требует явного вычисления периодов Пизано. Достаточно последовательно порождать нужные числа Фибоначчи и Лукаса и перемножать подходящие значения.
Было бы неэффективно каждый раз заново строить \(F_k\) или \(L_k\). Обе последовательности удовлетворяют одной и той же линейной рекурсии второго порядка:
$$F_k=F_{k-1}+F_{k-2},\qquad L_k=L_{k-1}+L_{k-2}.$$
Поэтому можно двигаться вперёд одним проходом, храня только два последних значения Фибоначчи и два последних значения Лукаса. На шаге \(k\) алгоритм сначала продвигает обе рекурсии, а затем умножает текущий ответ на \(L_k\), если \(k\) нечётно, и на \(F_k\), если \(k\) чётно. После каждого умножения выполняется взятие по модулю \(1{,}234{,}567{,}891\).
Небольшое контрольное значение, используемое реализацией, легко восстановить из закрытой формулы.
Для \(1\le p\le 10\) нетривиальны только множители
$$M(3)=2,\qquad M(4)=F_2=1,\qquad M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(10)=L_5=11.$$
Все остальные равны \(1\). Следовательно,
$$\begin{aligned} P(10) &=M(1)M(2)\cdots M(10)\\ &=1\cdot 1\cdot 2\cdot 1\cdot 1\cdot 4\cdot 1\cdot 3\cdot 1\cdot 11\\ &=264. \end{aligned}$$
Именно этот результат выдаёт реализация.
Реализации на C++, Python и Java используют один и тот же алгоритм. Сначала отдельно учитывается особый множитель \(M(3)=2\), если \(n\ge 3\). Затем выполняется цикл по \(k=1,2,\dots,\lfloor n/2\rfloor\), в котором поддерживаются соседние значения последовательностей Фибоначчи и Лукаса по заданному модулю.
Начиная с первого нетривиального шага \(k=2\), каждая итерация продвигает обе рекурсии ровно на один шаг. После этого по чётности \(k\) выбирается текущий множитель: при нечётном \(k\) берётся число Лукаса, при чётном \(k\) число Фибоначчи. Немедленное взятие по модулю \(1{,}234{,}567{,}891\) не позволяет промежуточным произведениям разрастаться.
Цикл выполняется ровно \(\lfloor n/2\rfloor\) раз. Внутри каждой итерации выполняется постоянное число операций: несколько сложений по модулю, одна проверка чётности и не более одного умножения по модулю. Поэтому время работы равно \(O(n)\), а дополнительная память равна \(O(1)\).
Для \(n=10^6\) это означает примерно \(500{,}000\) шагов рекурсии, что вполне удобно для практического вычисления.
لتكن \(\pi(n)\) فترة Pisano لمتتالية فيبوناتشي بترديد \(n\)، أي أصغر طول موجب تتكرر بعده الثنائية \((F_m,F_{m+1})\) modulo \(n\). ولكل عدد صحيح موجب \(p\)، نعرّف \(M(p)\) بأنه أكبر عدد \(n\) يحقق \(\pi(n)=p\)، وإذا لم يوجد مثل هذا العدد فنأخذ \(M(p)=1\).
المطلوب حساب
$$P(n)=\prod_{p=1}^{n} M(p),$$
وبالتحديد
$$P(10^6)\bmod 1{,}234{,}567{,}891.$$
البحث المباشر في جميع القيم الممكنة للـ moduli ثم إيجاد فترة Pisano لكل واحدة منها غير عملي. لذلك يبدأ التنفيذ من تصنيف بنيوي يحدد أي أطوال فترات يمكن أن تظهر كأكبر قيم ممكنة.
الفكرة الأساسية التي يعتمد عليها التنفيذ هي أن معظم العوامل \(M(p)\) تساوي \(1\) أصلًا، وأن العوامل غير التافهة يمكن كتابتها مباشرةً بدلالة أعداد فيبوناتشي ولوكاس.
يعتمد التنفيذ على التصنيف التالي:
$$M(2)=1,\qquad M(3)=2,$$
ولكل \(p\) فردي أكبر من \(3\) لدينا
$$M(p)=1.$$
وهذا يعني أن جميع الفترات الفردية لا تسهم في الناتج إلا الحالة الخاصة \(p=3\). لذلك ينهار الجداء الكلي إلى عامل فردي وحيد غير تافه، وإلى عائلة من العوامل الزوجية.
لنكتب متتاليتي فيبوناتشي ولوكاس كما يلي:
$$F_0=0,\quad F_1=1,\quad F_k=F_{k-1}+F_{k-2}\quad (k\ge 2),$$
$$L_0=2,\quad L_1=1,\quad L_k=L_{k-1}+L_{k-2}\quad (k\ge 2).$$
عندئذٍ لكل \(k\ge 2\) يكون
$$M(2k)= \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
أي إذا كان \(k\) فرديًا نأخذ عدد لوكاس \(L_k\)، وإذا كان زوجيًا نأخذ عدد فيبوناتشي \(F_k\). وهذه هي القاعدة نفسها التي يطبقها التنفيذ. ومن الأمثلة الصغيرة:
$$M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(18)=L_9=76.$$
بعد حذف جميع العوامل الفردية التافهة، نحصل عندما يكون \(n\ge 3\) على
$$P(n)=M(3)\prod_{k=2}^{\lfloor n/2\rfloor} M(2k).$$
وبما أن \(M(3)=2\)، فإن ذلك يصبح
$$P(n)=2\prod_{k=2}^{\lfloor n/2\rfloor} \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$$
بهذه الصياغة تختفي الحاجة إلى البحث الصريح عن فترات Pisano. ما يبقى هو توليد حدود فيبوناتشي ولوكاس بالتتابع وضرب الحد المناسب في كل خطوة.
إعادة حساب \(F_k\) أو \(L_k\) من الصفر لكل \(k\) ستكون مضيعةً للوقت. لكن كلتا المتتاليتين تحققان علاقة رجعية خطية من الرتبة الثانية:
$$F_k=F_{k-1}+F_{k-2},\qquad L_k=L_{k-1}+L_{k-2}.$$
ولهذا يكفي أن نحتفظ بآخر قيمتين من فيبوناتشي وآخر قيمتين من لوكاس، ثم نتقدم للأمام مرورًا واحدًا. عند الخطوة \(k\) يحدّث التنفيذ المتتاليتين مرةً واحدة، ثم يضرب في \(L_k\) إذا كان \(k\) فرديًا، أو في \(F_k\) إذا كان \(k\) زوجيًا. وبعد كل عملية ضرب يؤخذ الناتج modulo \(1{,}234{,}567{,}891\)، ولذلك تبقى القيم الوسيطة تحت السيطرة.
توجد قيمة تحقق صغيرة يعتمد عليها التنفيذ، ويمكن استخراجها مباشرةً من الصيغة المغلقة.
للقيم \(1\le p\le 10\)، العوامل غير التافهة هي
$$M(3)=2,\qquad M(4)=F_2=1,\qquad M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(10)=L_5=11.$$
وجميع العوامل الأخرى تساوي \(1\). إذن
$$\begin{aligned} P(10) &=M(1)M(2)\cdots M(10)\\ &=1\cdot 1\cdot 2\cdot 1\cdot 1\cdot 4\cdot 1\cdot 3\cdot 1\cdot 11\\ &=264. \end{aligned}$$
وهذه هي القيمة نفسها التي ينتجها التنفيذ.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. في البداية، إذا كان \(n\ge 3\)، تُضرب القيمة الخاصة \(M(3)=2\) في الجواب. بعد ذلك تتحرك حلقة على \(k=1,2,\dots,\lfloor n/2\rfloor\)، مع الاحتفاظ بحدود متتالية من فيبوناتشي ولوكاس تحت الترديد المطلوب.
ابتداءً من أول خطوة غير تافهة وهي \(k=2\)، تقوم كل دورة بتحديث العلاقتين الرجوعيتين مرةً واحدة. ثم يُختار العامل الحالي بحسب فردية \(k\): إذا كان \(k\) فرديًا يُستخدم حد لوكاس الحالي، وإذا كان زوجيًا يُستخدم حد فيبوناتشي الحالي. وبما أن كل عملية ضرب تُختزل مباشرةً modulo \(1{,}234{,}567{,}891\)، فلا حاجة إلى تخزين الجداء الكامل كعدد ضخم.
تنفذ الحلقة عددًا مقداره \(\lfloor n/2\rfloor\) من الدورات. وفي كل دورة يوجد عدد ثابت من العمليات: بضع عمليات جمع بترديد، واختبار للفردية، وعلى الأكثر عملية ضرب واحدة بترديد. لذلك يكون الزمن الكلي \(O(n)\)، بينما يكون استهلاك الذاكرة \(O(1)\).
عندما \(n=10^6\)، فهذا يعني نحو \(500{,}000\) خطوة تحديث فقط، وهو حجم صغير عمليًا.