Define
$$P_{a,b,c}(n)=n^4+a n^3+b n^2+c n.$$
For each positive triple \((a,b,c)\), let \(M(a,b,c)\) be the largest integer that divides \(P_{a,b,c}(n)\) for every integer \(n\). Then
$$S(N)=\sum_{1\le a,b,c\le N} M(a,b,c).$$
The final target is
$$T(K)=\sum_{k=2}^{K} S(F_k),\qquad K=1234567890123,$$
where \(F_k\) denotes the Fibonacci sequence. The implementations return \(T(K)\bmod 10^9\), i.e. the last nine digits.
The crucial fact is that a polynomial is integer-valued on all integers if and only if it has integer coefficients in the binomial basis \(\binom{n}{1},\binom{n}{2},\binom{n}{3},\binom{n}{4},\dots\). So instead of working with powers \(n^j\), we rewrite \(P_{a,b,c}(n)\) in that basis.
The standard identities are
$$n=\binom{n}{1},\qquad n^2=2\binom{n}{2}+\binom{n}{1},$$
$$n^3=6\binom{n}{3}+6\binom{n}{2}+\binom{n}{1},$$
$$n^4=24\binom{n}{4}+36\binom{n}{3}+14\binom{n}{2}+\binom{n}{1}.$$
Substituting these into \(P_{a,b,c}(n)\) gives
$$P_{a,b,c}(n)=24\binom{n}{4}+(36+6a)\binom{n}{3}+(14+6a+2b)\binom{n}{2}+(1+a+b+c)\binom{n}{1}.$$
Each binomial polynomial \(\binom{n}{j}\) is integer-valued for every integer \(n\). Therefore the quotient \(P_{a,b,c}(n)/m\) is integer-valued for all \(n\) exactly when every coefficient in the binomial-basis expansion is divisible by \(m\). The maximal such divisor is the gcd of those coefficients:
$$\boxed{M(a,b,c)=\gcd\bigl(24,\ 36+6a,\ 14+6a+2b,\ 1+a+b+c\bigr).}$$
This explains the statement example immediately:
$$M(4,2,5)=\gcd(24,60,42,12)=6.$$
A tiny consistency check is
$$S(1)=M(1,1,1)=\gcd(24,42,22,4)=2.$$
Only residues modulo \(24\) matter, because \(\gcd(24,x)\) depends only on \(x \pmod{24}\). Write
$$N=24q+r,\qquad 0\le r<24.$$
For each residue \(t\in\{1,\dots,24\}\), the number of integers in \(\{1,\dots,N\}\) with that residue is
$$q+\varepsilon_t(r),\qquad \varepsilon_t(r)=\begin{cases}1,& t\le r,\\0,& t>r.\end{cases}$$
Hence
$$S(N)=\sum_{r_a=1}^{24}\sum_{r_b=1}^{24}\sum_{r_c=1}^{24} M(r_a,r_b,r_c)\bigl(q+\varepsilon_{r_a}\bigr)\bigl(q+\varepsilon_{r_b}\bigr)\bigl(q+\varepsilon_{r_c}\bigr).$$
Expanding the product yields
$$S(N)=C_3 q^3 + C_2(r) q^2 + C_1(r) q + C_0(r),$$
where \(C_3\) is constant and \(C_2,C_1,C_0\) depend only on the remainder \(r\). So \(S(N)\) is a degree-3 quasi-polynomial with period \(24\). The implementations precompute these four coefficient tables once by enumerating all \(24^3\) residue triples.
The built-in checkpoints are
$$S(10)=1972,\qquad S(10000)=2024258331114.$$
Write each Fibonacci number as
$$F_k=24q_k+r_k,\qquad 0\le r_k<24.$$
Because Fibonacci numbers modulo \(24\) have Pisano period \(24\), the residue sequence \(r_k\) is periodic. From \(F_{k+2}=F_{k+1}+F_k\) we obtain
$$r_{k+2}\equiv r_{k+1}+r_k \pmod{24},$$
$$q_{k+2}=q_{k+1}+q_k+\delta_k,\qquad \delta_k=\left\lfloor\frac{r_k+r_{k+1}}{24}\right\rfloor.$$
The carry \(\delta_k\) depends only on the residue pair \((r_k,r_{k+1})\), so it is periodic as well. This converts the huge-index problem into a fixed periodic affine recurrence for the quotients \(q_k\).
Since \(S(F_k)\) is cubic in \(q_k\), it is enough to track all monomials in two consecutive quotient variables \(x=q_k\) and \(y=q_{k+1}\) up to degree \(3\):
$$1,\ x,\ y,\ x^2,\ xy,\ y^2,\ x^3,\ x^2y,\ xy^2,\ y^3,$$
plus one extra coordinate for the running total \(\sum_{j=2}^{k} S(F_j)\). Under the update
$$x'=y,\qquad y'=x+y+\delta_k,$$
every basis monomial becomes a linear combination of the same basis. For example,
$$x'y'=y(x+y+\delta_k),\qquad y'^2=(x+y+\delta_k)^2,\qquad y'^3=(x+y+\delta_k)^3.$$
Therefore one Fibonacci step is represented by an \(11\times 11\) matrix. Multiplying the \(24\) phase matrices of one full residue cycle gives a single block matrix, and binary exponentiation of that block reaches \(K=1234567890123\) in logarithmic time.
The C++, Python, and Java implementations all use the same structure. They first precompute the quasi-polynomial coefficients of \(S(N)\) from the \(24^3\) residue kernel. They then build the \(24\) phase-dependent transition matrices determined by the periodic Fibonacci residues and carries. Finally they exponentiate the one-cycle block matrix, apply the remaining partial cycle, and read the accumulated-sum coordinate modulo \(10^9\).
The residue precomputation is constant-size work, bounded by \(24^4\) elementary updates. The main stage is binary exponentiation of fixed \(11\times 11\) matrices, so the running time is \(O(\log K)\) and the memory usage is \(O(1)\) apart from fixed-size tables and matrices.
Definiere
$$P_{a,b,c}(n)=n^4+a n^3+b n^2+c n.$$
Für jedes positive Tripel \((a,b,c)\) sei \(M(a,b,c)\) der größte ganzzahlige Teiler, der \(P_{a,b,c}(n)\) für alle ganzen \(n\) teilt. Dann gilt
$$S(N)=\sum_{1\le a,b,c\le N} M(a,b,c).$$
Gesucht ist schließlich
$$T(K)=\sum_{k=2}^{K} S(F_k),\qquad K=1234567890123,$$
wobei \(F_k\) die Fibonacci-Zahlen sind. Die Implementierungen geben \(T(K)\bmod 10^9\) aus, also die letzten neun Ziffern.
Der entscheidende Punkt ist: Ein Polynom nimmt auf allen ganzen Zahlen ganzzahlige Werte an, genau dann wenn es in der Binomialbasis \(\binom{n}{1},\binom{n}{2},\binom{n}{3},\binom{n}{4},\dots\) ganzzahlige Koeffizienten besitzt. Deshalb wird \(P_{a,b,c}(n)\) in dieser Basis entwickelt.
Man benutzt die Standardidentitäten
$$n=\binom{n}{1},\qquad n^2=2\binom{n}{2}+\binom{n}{1},$$
$$n^3=6\binom{n}{3}+6\binom{n}{2}+\binom{n}{1},$$
$$n^4=24\binom{n}{4}+36\binom{n}{3}+14\binom{n}{2}+\binom{n}{1}.$$
Daraus folgt
$$P_{a,b,c}(n)=24\binom{n}{4}+(36+6a)\binom{n}{3}+(14+6a+2b)\binom{n}{2}+(1+a+b+c)\binom{n}{1}.$$
Jedes Binomialpolynom \(\binom{n}{j}\) ist für alle ganzen \(n\) ganzwertig. Also ist \(P_{a,b,c}(n)/m\) genau dann für alle \(n\) ganzwertig, wenn alle Koeffizienten der Binomialdarstellung durch \(m\) teilbar sind. Der maximale solche Divisor ist daher
$$\boxed{M(a,b,c)=\gcd\bigl(24,\ 36+6a,\ 14+6a+2b,\ 1+a+b+c\bigr).}$$
Das erklärt unmittelbar das Beispiel aus der Aufgabenstellung:
$$M(4,2,5)=\gcd(24,60,42,12)=6.$$
Ein kleiner Kontrollwert ist
$$S(1)=M(1,1,1)=\gcd(24,42,22,4)=2.$$
Entscheidend sind nur die Restklassen modulo \(24\), denn \(\gcd(24,x)\) hängt nur von \(x \pmod{24}\) ab. Schreibe
$$N=24q+r,\qquad 0\le r<24.$$
Für jede Restklasse \(t\in\{1,\dots,24\}\) ist die Anzahl der Zahlen in \(\{1,\dots,N\}\) mit diesem Rest gleich
$$q+\varepsilon_t(r),\qquad \varepsilon_t(r)=\begin{cases}1,& t\le r,\\0,& t>r.\end{cases}$$
Damit erhält man
$$S(N)=\sum_{r_a=1}^{24}\sum_{r_b=1}^{24}\sum_{r_c=1}^{24} M(r_a,r_b,r_c)\bigl(q+\varepsilon_{r_a}\bigr)\bigl(q+\varepsilon_{r_b}\bigr)\bigl(q+\varepsilon_{r_c}\bigr).$$
Nach dem Ausmultiplizieren ergibt sich
$$S(N)=C_3 q^3 + C_2(r) q^2 + C_1(r) q + C_0(r),$$
wobei \(C_3\) konstant ist und die übrigen Koeffizienten nur vom Rest \(r\) abhängen. Also ist \(S(N)\) ein Quasipolynom dritten Grades mit Periode \(24\). Die Implementierungen berechnen diese vier Koeffiziententabellen einmalig durch Enumeration aller \(24^3\) Restklassen-Tripel.
Die verwendeten Kontrollwerte sind
$$S(10)=1972,\qquad S(10000)=2024258331114.$$
Schreibe jede Fibonacci-Zahl in der Form
$$F_k=24q_k+r_k,\qquad 0\le r_k<24.$$
Da die Fibonacci-Folge modulo \(24\) die Pisano-Periode \(24\) besitzt, ist die Restfolge \(r_k\) periodisch. Aus \(F_{k+2}=F_{k+1}+F_k\) folgt
$$r_{k+2}\equiv r_{k+1}+r_k \pmod{24},$$
$$q_{k+2}=q_{k+1}+q_k+\delta_k,\qquad \delta_k=\left\lfloor\frac{r_k+r_{k+1}}{24}\right\rfloor.$$
Der Übertrag \(\delta_k\) hängt nur vom periodischen Restpaar \((r_k,r_{k+1})\) ab und ist deshalb ebenfalls periodisch. Damit reduziert sich das Problem für riesige Indizes auf eine feste periodische affine Rekursion für die Quotienten \(q_k\).
Weil \(S(F_k)\) kubisch in \(q_k\) ist, genügt es, alle Monome in zwei aufeinanderfolgenden Quotienten \(x=q_k\) und \(y=q_{k+1}\) bis zum Grad \(3\) mitzuführen:
$$1,\ x,\ y,\ x^2,\ xy,\ y^2,\ x^3,\ x^2y,\ xy^2,\ y^3,$$
sowie eine zusätzliche Koordinate für die laufende Summe \(\sum_{j=2}^{k} S(F_j)\). Unter dem Update
$$x'=y,\qquad y'=x+y+\delta_k,$$
wird jedes dieser Monome zu einer linearen Kombination derselben Basis. Beispielsweise gilt
$$x'y'=y(x+y+\delta_k),\qquad y'^2=(x+y+\delta_k)^2,\qquad y'^3=(x+y+\delta_k)^3.$$
Somit entspricht ein Fibonacci-Schritt einer \(11\times 11\)-Matrix. Fasst man die \(24\) Phasen eines vollständigen Restzyklus zusammen, erhält man eine Blockmatrix, die per binärer Exponentiation bis zum Index \(K=1234567890123\) ausgewertet wird.
Die C++-, Python- und Java-Implementierungen folgen demselben Schema. Zuerst werden aus dem Restklassenkern die vier Koeffiziententabellen des Quasipolynoms \(S(N)\) vorab berechnet. Danach werden die \(24\) phasenabhängigen Übergangsmatrizen aus den periodischen Fibonacci-Resten und den zugehörigen Überträgen aufgebaut. Schließlich wird die Blockmatrix für einen vollen Zyklus exponentiert, der verbleibende Teilzyklus angewendet und die Summenkomponente modulo \(10^9\) ausgelesen.
Die Vorberechnung über die Restklassen ist von konstanter Größe und durch höchstens \(24^4\) elementare Aktualisierungen beschränkt. Der Hauptteil ist binäre Exponentiation fester \(11\times 11\)-Matrizen. Deshalb beträgt die Laufzeit \(O(\log K)\) und der Speicherverbrauch \(O(1)\), abgesehen von Tabellen und Matrizen fester Größe.
Şunu tanımlayalım:
$$P_{a,b,c}(n)=n^4+a n^3+b n^2+c n.$$
Her pozitif \((a,b,c)\) üçlüsü için \(M(a,b,c)\), \(P_{a,b,c}(n)\) ifadesini her tamsayı \(n\) için bölen en büyük tamsayı olsun. O zaman
$$S(N)=\sum_{1\le a,b,c\le N} M(a,b,c).$$
Son hedef ise
$$T(K)=\sum_{k=2}^{K} S(F_k),\qquad K=1234567890123,$$
burada \(F_k\) Fibonacci dizisidir. Uygulamalar \(T(K)\bmod 10^9\) değerini, yani son dokuz basamağı döndürür.
Ana fikir şudur: Bir polinom bütün tamsayılarda tamsayı değer alıyorsa ve ancak alıyorsa, \(\binom{n}{1},\binom{n}{2},\binom{n}{3},\binom{n}{4},\dots\) binom tabanında tamsayı katsayılara sahiptir. Bu yüzden \(P_{a,b,c}(n)\) ifadesini kuvvetler yerine bu tabanda yeniden yazarız.
Kullanılan standart özdeşlikler:
$$n=\binom{n}{1},\qquad n^2=2\binom{n}{2}+\binom{n}{1},$$
$$n^3=6\binom{n}{3}+6\binom{n}{2}+\binom{n}{1},$$
$$n^4=24\binom{n}{4}+36\binom{n}{3}+14\binom{n}{2}+\binom{n}{1}.$$
Bunları yerine koyunca
$$P_{a,b,c}(n)=24\binom{n}{4}+(36+6a)\binom{n}{3}+(14+6a+2b)\binom{n}{2}+(1+a+b+c)\binom{n}{1}$$
elde edilir.
Her \(\binom{n}{j}\) polinomu tüm tamsayılarda tamsayı değerlidir. Dolayısıyla \(P_{a,b,c}(n)/m\) ifadesinin her \(n\) için tamsayı değerli olması, binom tabanındaki tüm katsayıların \(m\) ile bölünmesine denktir. En büyük böyle bölen de bu katsayıların EBOB'udur:
$$\boxed{M(a,b,c)=\gcd\bigl(24,\ 36+6a,\ 14+6a+2b,\ 1+a+b+c\bigr).}$$
Böylece soru metnindeki örnek hemen doğrulanır:
$$M(4,2,5)=\gcd(24,60,42,12)=6.$$
Küçük bir kontrol olarak
$$S(1)=M(1,1,1)=\gcd(24,42,22,4)=2$$
bulunur.
Yalnızca \(24\) modundaki kalıntılar önemlidir; çünkü \(\gcd(24,x)\) yalnızca \(x \pmod{24}\) değerine bağlıdır. Şimdi
$$N=24q+r,\qquad 0\le r<24$$
yazalım. \(t\in\{1,\dots,24\}\) kalıntı sınıfındaki sayı adedi
$$q+\varepsilon_t(r),\qquad \varepsilon_t(r)=\begin{cases}1,& t\le r,\\0,& t>r\end{cases}$$
olur. Böylece
$$S(N)=\sum_{r_a=1}^{24}\sum_{r_b=1}^{24}\sum_{r_c=1}^{24} M(r_a,r_b,r_c)\bigl(q+\varepsilon_{r_a}\bigr)\bigl(q+\varepsilon_{r_b}\bigr)\bigl(q+\varepsilon_{r_c}\bigr)$$
elde edilir. Çarpımı açınca
$$S(N)=C_3 q^3 + C_2(r) q^2 + C_1(r) q + C_0(r)$$
şeklinde bir ifade çıkar. Burada \(C_3\) sabittir; diğer katsayılar yalnızca kalan \(r\)'ye bağlıdır. Yani \(S(N)\), periyodu \(24\) olan üçüncü derece bir quasi-polynomial'dir. Uygulamalar bu dört katsayı tablosunu \(24^3\) kalıntı üçlüsünü bir kez tarayarak önceden hesaplar.
Kullanılan kontrol değerleri şunlardır:
$$S(10)=1972,\qquad S(10000)=2024258331114.$$
Her Fibonacci sayısını
$$F_k=24q_k+r_k,\qquad 0\le r_k<24$$
şeklinde yazalım. Fibonacci dizisi mod \(24\) altında \(24\) dönemine sahip olduğundan, \(r_k\) dizisi de periyodiktir. Ayrıca \(F_{k+2}=F_{k+1}+F_k\) eşitliğinden
$$r_{k+2}\equiv r_{k+1}+r_k \pmod{24},$$
$$q_{k+2}=q_{k+1}+q_k+\delta_k,\qquad \delta_k=\left\lfloor\frac{r_k+r_{k+1}}{24}\right\rfloor$$
sonucu çıkar. Taşıma terimi \(\delta_k\) yalnızca periyodik kalıntı çiftine bağlıdır; dolayısıyla o da periyodiktir. Böylece çok büyük indisli problem, \(q_k\) bölümleri üzerinde sabit boyutlu periyodik afin bir özyineli bağıntıya indirgenir.
\(S(F_k)\), \(q_k\) cinsinden kübik olduğu için, ardışık iki bölüm değişkeni \(x=q_k\) ve \(y=q_{k+1}\) için derece \(3\)'e kadar bütün monomları izlemek yeterlidir:
$$1,\ x,\ y,\ x^2,\ xy,\ y^2,\ x^3,\ x^2y,\ xy^2,\ y^3,$$
ve ayrıca bir de \(\sum_{j=2}^{k} S(F_j)\) toplamı için ek koordinat tutulur. Güncelleme
$$x'=y,\qquad y'=x+y+\delta_k$$
altında her monom aynı tabanın lineer kombinasyonu haline gelir. Örneğin
$$x'y'=y(x+y+\delta_k),\qquad y'^2=(x+y+\delta_k)^2,\qquad y'^3=(x+y+\delta_k)^3.$$
Böylece tek Fibonacci adımı bir \(11\times 11\) matrisle temsil edilir. Bir tam kalıntı döngüsünün \(24\) faz matrisi çarpılıp tek blok matrise dönüştürülür; sonra bu blok için ikili üs alma uygulanır.
C++, Python ve Java uygulamaları aynı hattı izler. Önce \(S(N)\) için quasi-polynomial katsayıları, mod \(24\) kalıntı çekirdeğinden önceden hesaplanır. Sonra periyodik Fibonacci kalıntılarından ve taşıma dizisinden gelen \(24\) faz geçiş matrisi kurulur. Son adımda tek çevrimlik blok matris üs alınır, kalan birkaç faz uygulanır ve birikmiş toplam bileşeni mod \(10^9\) okunur.
Kalıntı önhesabı sabit boyutludur; en fazla \(24^4\) temel güncelleme gerekir. Ana maliyet, sabit boyutlu \(11\times 11\) matrisler üzerinde ikili üs almadır. Bu yüzden süre \(O(\log K)\), bellek ise sabit boyutlu tablo ve matrisler dışında \(O(1)\)'dir.
Definimos
$$P_{a,b,c}(n)=n^4+a n^3+b n^2+c n.$$
Para cada triple positivo \((a,b,c)\), sea \(M(a,b,c)\) el mayor entero que divide \(P_{a,b,c}(n)\) para todo entero \(n\). Entonces
$$S(N)=\sum_{1\le a,b,c\le N} M(a,b,c).$$
El objetivo final es
$$T(K)=\sum_{k=2}^{K} S(F_k),\qquad K=1234567890123,$$
donde \(F_k\) son los números de Fibonacci. Las implementaciones devuelven \(T(K)\bmod 10^9\), es decir, las últimas nueve cifras.
El hecho clave es que un polinomio toma valores enteros en todos los enteros si y solo si tiene coeficientes enteros en la base binomial \(\binom{n}{1},\binom{n}{2},\binom{n}{3},\binom{n}{4},\dots\). Por eso reescribimos \(P_{a,b,c}(n)\) en esa base.
Usamos las identidades
$$n=\binom{n}{1},\qquad n^2=2\binom{n}{2}+\binom{n}{1},$$
$$n^3=6\binom{n}{3}+6\binom{n}{2}+\binom{n}{1},$$
$$n^4=24\binom{n}{4}+36\binom{n}{3}+14\binom{n}{2}+\binom{n}{1}.$$
Al sustituir obtenemos
$$P_{a,b,c}(n)=24\binom{n}{4}+(36+6a)\binom{n}{3}+(14+6a+2b)\binom{n}{2}+(1+a+b+c)\binom{n}{1}.$$
Cada polinomio binomial \(\binom{n}{j}\) es enterovalorado para todo entero \(n\). Por tanto, \(P_{a,b,c}(n)/m\) es enterovalorado para todo \(n\) exactamente cuando todos los coeficientes de la expansión binomial son divisibles por \(m\). El máximo tal divisor es
$$\boxed{M(a,b,c)=\gcd\bigl(24,\ 36+6a,\ 14+6a+2b,\ 1+a+b+c\bigr).}$$
Esto explica de inmediato el ejemplo del enunciado:
$$M(4,2,5)=\gcd(24,60,42,12)=6.$$
Un control pequeño es
$$S(1)=M(1,1,1)=\gcd(24,42,22,4)=2.$$
Solo importan los residuos módulo \(24\), porque \(\gcd(24,x)\) depende únicamente de \(x \pmod{24}\). Escribimos
$$N=24q+r,\qquad 0\le r<24.$$
Para cada residuo \(t\in\{1,\dots,24\}\), la cantidad de enteros de \(\{1,\dots,N\}\) con ese residuo es
$$q+\varepsilon_t(r),\qquad \varepsilon_t(r)=\begin{cases}1,& t\le r,\\0,& t>r.\end{cases}$$
Entonces
$$S(N)=\sum_{r_a=1}^{24}\sum_{r_b=1}^{24}\sum_{r_c=1}^{24} M(r_a,r_b,r_c)\bigl(q+\varepsilon_{r_a}\bigr)\bigl(q+\varepsilon_{r_b}\bigr)\bigl(q+\varepsilon_{r_c}\bigr).$$
Al expandir el producto aparece
$$S(N)=C_3 q^3 + C_2(r) q^2 + C_1(r) q + C_0(r).$$
Aquí \(C_3\) es constante y \(C_2,C_1,C_0\) dependen solo del resto \(r\). Por tanto, \(S(N)\) es un cuasipolinomio de grado \(3\) y período \(24\). Las implementaciones precalculan esas cuatro tablas recorriendo una sola vez los \(24^3\) triples residuales.
Los puntos de control usados son
$$S(10)=1972,\qquad S(10000)=2024258331114.$$
Escribimos cada número de Fibonacci como
$$F_k=24q_k+r_k,\qquad 0\le r_k<24.$$
Como la sucesión de Fibonacci módulo \(24\) tiene período de Pisano \(24\), la sucesión \(r_k\) es periódica. A partir de \(F_{k+2}=F_{k+1}+F_k\) obtenemos
$$r_{k+2}\equiv r_{k+1}+r_k \pmod{24},$$
$$q_{k+2}=q_{k+1}+q_k+\delta_k,\qquad \delta_k=\left\lfloor\frac{r_k+r_{k+1}}{24}\right\rfloor.$$
El acarreo \(\delta_k\) depende solo del par residual periódico \((r_k,r_{k+1})\), así que también es periódico. De esta manera, el problema de índice enorme se transforma en una recurrencia afín periódica y de tamaño fijo sobre los cocientes \(q_k\).
Puesto que \(S(F_k)\) es cúbico en \(q_k\), basta seguir todos los monomios de grado a lo sumo \(3\) en dos cocientes consecutivos \(x=q_k\) e \(y=q_{k+1}\):
$$1,\ x,\ y,\ x^2,\ xy,\ y^2,\ x^3,\ x^2y,\ xy^2,\ y^3,$$
más una coordenada adicional para la suma acumulada \(\sum_{j=2}^{k} S(F_j)\). Bajo la actualización
$$x'=y,\qquad y'=x+y+\delta_k,$$
cada monomio pasa a ser combinación lineal de la misma base. Por ejemplo,
$$x'y'=y(x+y+\delta_k),\qquad y'^2=(x+y+\delta_k)^2,\qquad y'^3=(x+y+\delta_k)^3.$$
Así, un paso de Fibonacci queda representado por una matriz \(11\times 11\). Al multiplicar las \(24\) matrices de fase de un ciclo completo se obtiene una matriz de bloque, y sobre ella se aplica exponenciación binaria.
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Primero precalculan los coeficientes del cuasipolinomio \(S(N)\) a partir del núcleo residual módulo \(24\). Después construyen las \(24\) matrices de transición dependientes de la fase, determinadas por los residuos de Fibonacci y por los acarreos asociados. Finalmente elevan a potencia la matriz de un ciclo completo, aplican el resto del ciclo parcial y leen la coordenada de suma acumulada módulo \(10^9\).
La fase de residuos tiene tamaño constante y está acotada por \(24^4\) actualizaciones elementales. La parte principal es la exponenciación binaria de matrices fijas de tamaño \(11\times 11\). Por tanto, el tiempo es \(O(\log K)\) y la memoria es \(O(1)\), aparte de tablas y matrices de tamaño fijo.
定义
$$P_{a,b,c}(n)=n^4+a n^3+b n^2+c n.$$
对每个正整数三元组 \((a,b,c)\)，记 \(M(a,b,c)\) 为能整除 \(P_{a,b,c}(n)\) 对所有整数 \(n\) 的最大整数。再定义
$$S(N)=\sum_{1\le a,b,c\le N} M(a,b,c).$$
最终要求的是
$$T(K)=\sum_{k=2}^{K} S(F_k),\qquad K=1234567890123,$$
其中 \(F_k\) 是 Fibonacci 数。实现返回的是 \(T(K)\bmod 10^9\)，也就是最后九位。
关键事实是：一个多项式对所有整数都取整数值，当且仅当它在二项式基 \(\binom{n}{1},\binom{n}{2},\binom{n}{3},\binom{n}{4},\dots\) 下的系数全为整数。因此我们不直接处理 \(n^j\)，而是先把 \(P_{a,b,c}(n)\) 展开到这组基底上。
标准恒等式为
$$n=\binom{n}{1},\qquad n^2=2\binom{n}{2}+\binom{n}{1},$$
$$n^3=6\binom{n}{3}+6\binom{n}{2}+\binom{n}{1},$$
$$n^4=24\binom{n}{4}+36\binom{n}{3}+14\binom{n}{2}+\binom{n}{1}.$$
代入后得到
$$P_{a,b,c}(n)=24\binom{n}{4}+(36+6a)\binom{n}{3}+(14+6a+2b)\binom{n}{2}+(1+a+b+c)\binom{n}{1}.$$
每个二项式多项式 \(\binom{n}{j}\) 对所有整数 \(n\) 都是整数值的。因此 \(P_{a,b,c}(n)/m\) 对所有 \(n\) 都整数值， 当且仅当上式中的每个二项式基系数都被 \(m\) 整除。于是最大这样的 \(m\) 就是这些系数的 gcd：
$$\boxed{M(a,b,c)=\gcd\bigl(24,\ 36+6a,\ 14+6a+2b,\ 1+a+b+c\bigr).}$$
这立即解释了题目里的例子：
$$M(4,2,5)=\gcd(24,60,42,12)=6.$$
一个很小的校验是
$$S(1)=M(1,1,1)=\gcd(24,42,22,4)=2.$$
这里只需要关心模 \(24\) 的剩余类，因为 \(\gcd(24,x)\) 只依赖于 \(x \pmod{24}\)。写成
$$N=24q+r,\qquad 0\le r<24.$$
对每个剩余类 \(t\in\{1,\dots,24\}\)，集合 \(\{1,\dots,N\}\) 中落在该类的整数个数为
$$q+\varepsilon_t(r),\qquad \varepsilon_t(r)=\begin{cases}1,& t\le r,\\0,& t>r.\end{cases}$$
因此
$$S(N)=\sum_{r_a=1}^{24}\sum_{r_b=1}^{24}\sum_{r_c=1}^{24} M(r_a,r_b,r_c)\bigl(q+\varepsilon_{r_a}\bigr)\bigl(q+\varepsilon_{r_b}\bigr)\bigl(q+\varepsilon_{r_c}\bigr).$$
把乘积展开后得到
$$S(N)=C_3 q^3 + C_2(r) q^2 + C_1(r) q + C_0(r).$$
其中 \(C_3\) 是常数，而 \(C_2,C_1,C_0\) 只依赖于余数 \(r\)。所以 \(S(N)\) 是一个次数为 \(3\)、周期为 \(24\) 的准多项式。实现会先枚举全部 \(24^3\) 个剩余三元组，把这四张系数表一次性预处理出来。
实现中验证的检查点是
$$S(10)=1972,\qquad S(10000)=2024258331114.$$
把每个 Fibonacci 数写成
$$F_k=24q_k+r_k,\qquad 0\le r_k<24.$$
由于 Fibonacci 序列模 \(24\) 的 Pisano 周期是 \(24\)，所以余数序列 \(r_k\) 本身是周期性的。由 \(F_{k+2}=F_{k+1}+F_k\) 可得
$$r_{k+2}\equiv r_{k+1}+r_k \pmod{24},$$
$$q_{k+2}=q_{k+1}+q_k+\delta_k,\qquad \delta_k=\left\lfloor\frac{r_k+r_{k+1}}{24}\right\rfloor.$$
这里的进位 \(\delta_k\) 只由周期性的余数对 \((r_k,r_{k+1})\) 决定，因此也同样周期。这样，大索引问题就被压缩成了一个固定周期的仿射递推。
因为 \(S(F_k)\) 关于 \(q_k\) 是三次的，所以只要跟踪相邻两个商变量 \(x=q_k\)、\(y=q_{k+1}\) 的所有三次以内单项式：
$$1,\ x,\ y,\ x^2,\ xy,\ y^2,\ x^3,\ x^2y,\ xy^2,\ y^3,$$
再加上一个累计和坐标 \(\sum_{j=2}^{k} S(F_j)\) 即可。在更新
$$x'=y,\qquad y'=x+y+\delta_k$$
之下，这些单项式都会变成同一组基底的线性组合。例如
$$x'y'=y(x+y+\delta_k),\qquad y'^2=(x+y+\delta_k)^2,\qquad y'^3=(x+y+\delta_k)^3.$$
因此一个 Fibonacci 步骤可以表示成一个 \(11\times 11\) 矩阵。把完整余数周期的 \(24\) 个阶段矩阵相乘，就得到一个周期块矩阵；再对这个块做快速幂即可。
C++、Python 和 Java 实现都遵循同一条主线。首先从模 \(24\) 的剩余核中预计算出 \(S(N)\) 的四张准多项式系数表；然后根据 Fibonacci 余数和对应进位构造 \(24\) 个相位转移矩阵；最后对一个完整周期的块矩阵做幂运算，补上剩余的几个相位，并读取累计和分量的模 \(10^9\) 结果。
剩余类预处理是常数规模工作，最多只有 \(24^4\) 次基本更新。主阶段是固定维度 \(11\times 11\) 矩阵的二进制快速幂，因此时间复杂度为 \(O(\log K)\)，空间复杂度为 \(O(1)\)；额外空间只来自固定大小的表和矩阵。
Определим
$$P_{a,b,c}(n)=n^4+a n^3+b n^2+c n.$$
Для каждого положительного тройного набора \((a,b,c)\) обозначим через \(M(a,b,c)\) наибольшее целое число, которое делит \(P_{a,b,c}(n)\) при любом целом \(n\). Затем
$$S(N)=\sum_{1\le a,b,c\le N} M(a,b,c).$$
Окончательная цель:
$$T(K)=\sum_{k=2}^{K} S(F_k),\qquad K=1234567890123,$$
где \(F_k\) — числа Фибоначчи. Реализации вычисляют \(T(K)\bmod 10^9\), то есть последние девять цифр.
Ключевой факт: многочлен принимает целые значения на всех целых аргументах тогда и только тогда, когда в биномиальном базисе \(\binom{n}{1},\binom{n}{2},\binom{n}{3},\binom{n}{4},\dots\) его коэффициенты целые. Поэтому нужно переписать \(P_{a,b,c}(n)\) не через степени \(n^j\), а через этот базис.
Используются стандартные тождества
$$n=\binom{n}{1},\qquad n^2=2\binom{n}{2}+\binom{n}{1},$$
$$n^3=6\binom{n}{3}+6\binom{n}{2}+\binom{n}{1},$$
$$n^4=24\binom{n}{4}+36\binom{n}{3}+14\binom{n}{2}+\binom{n}{1}.$$
После подстановки получаем
$$P_{a,b,c}(n)=24\binom{n}{4}+(36+6a)\binom{n}{3}+(14+6a+2b)\binom{n}{2}+(1+a+b+c)\binom{n}{1}.$$
Каждый биномиальный многочлен \(\binom{n}{j}\) целочисленно-значен на всех целых \(n\). Значит, \(P_{a,b,c}(n)/m\) будет целочисленно-значным для всех \(n\) тогда и только тогда, когда все коэффициенты биномиального разложения делятся на \(m\). Максимальный такой делитель равен
$$\boxed{M(a,b,c)=\gcd\bigl(24,\ 36+6a,\ 14+6a+2b,\ 1+a+b+c\bigr).}$$
Это сразу объясняет пример из условия:
$$M(4,2,5)=\gcd(24,60,42,12)=6.$$
Небольшая проверка:
$$S(1)=M(1,1,1)=\gcd(24,42,22,4)=2.$$
Достаточно знать остатки по модулю \(24\), потому что \(\gcd(24,x)\) зависит только от \(x \pmod{24}\). Пишем
$$N=24q+r,\qquad 0\le r<24.$$
Для каждого остатка \(t\in\{1,\dots,24\}\) число элементов множества \(\{1,\dots,N\}\) с этим остатком равно
$$q+\varepsilon_t(r),\qquad \varepsilon_t(r)=\begin{cases}1,& t\le r,\\0,& t>r.\end{cases}$$
Следовательно,
$$S(N)=\sum_{r_a=1}^{24}\sum_{r_b=1}^{24}\sum_{r_c=1}^{24} M(r_a,r_b,r_c)\bigl(q+\varepsilon_{r_a}\bigr)\bigl(q+\varepsilon_{r_b}\bigr)\bigl(q+\varepsilon_{r_c}\bigr).$$
После раскрытия скобок получаем
$$S(N)=C_3 q^3 + C_2(r) q^2 + C_1(r) q + C_0(r).$$
Здесь \(C_3\) — константа, а остальные коэффициенты зависят только от остатка \(r\). Итак, \(S(N)\) — квазиполином степени \(3\) с периодом \(24\). Реализации один раз перебирают все \(24^3\) тройки остатков и предвычисляют эти четыре таблицы коэффициентов.
Используемые контрольные значения:
$$S(10)=1972,\qquad S(10000)=2024258331114.$$
Представим каждое число Фибоначчи в виде
$$F_k=24q_k+r_k,\qquad 0\le r_k<24.$$
Так как последовательность Фибоначчи по модулю \(24\) имеет период Пизано \(24\), последовательность остатков \(r_k\) периодична. Из равенства \(F_{k+2}=F_{k+1}+F_k\) следует
$$r_{k+2}\equiv r_{k+1}+r_k \pmod{24},$$
$$q_{k+2}=q_{k+1}+q_k+\delta_k,\qquad \delta_k=\left\lfloor\frac{r_k+r_{k+1}}{24}\right\rfloor.$$
Перенос \(\delta_k\) зависит только от периодической пары остатков \((r_k,r_{k+1})\), а значит, тоже периодичен. Это превращает задачу с гигантским индексом в фиксированную периодическую аффинную рекурсию для частных \(q_k\).
Поскольку \(S(F_k)\) является кубическим многочленом по \(q_k\), достаточно отслеживать все мономы степени не выше \(3\) от двух соседних частных \(x=q_k\) и \(y=q_{k+1}\):
$$1,\ x,\ y,\ x^2,\ xy,\ y^2,\ x^3,\ x^2y,\ xy^2,\ y^3,$$
а также отдельную координату для накопленной суммы \(\sum_{j=2}^{k} S(F_j)\). При переходе
$$x'=y,\qquad y'=x+y+\delta_k$$
каждый такой моном выражается линейно через тот же базис. Например,
$$x'y'=y(x+y+\delta_k),\qquad y'^2=(x+y+\delta_k)^2,\qquad y'^3=(x+y+\delta_k)^3.$$
Следовательно, один шаг Фибоначчи задаётся матрицей \(11\times 11\). Произведение \(24\) фазовых матриц полного цикла образует одну блочную матрицу, к которой применяется быстрое возведение в степень.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала они предвычисляют коэффициенты квазиполинома \(S(N)\) из ядра остатков по модулю \(24\). Затем строят \(24\) фазозависимые матрицы перехода, определяемые остатками Фибоначчи и соответствующими переносами. После этого возводят в степень блочную матрицу одного полного цикла, применяют оставшуюся часть цикла и считывают координату накопленной суммы по модулю \(10^9\).
Предвычисление по остаткам имеет постоянный размер и ограничено \(24^4\) элементарными обновлениями. Основная часть — бинарное возведение в степень фиксированных матриц размера \(11\times 11\). Поэтому время работы равно \(O(\log K)\), а память — \(O(1)\), если не считать таблицы и матрицы фиксированного размера.
نعرّف
$$P_{a,b,c}(n)=n^4+a n^3+b n^2+c n.$$
ولكل ثلاثية موجبة \((a,b,c)\) نعرّف \(M(a,b,c)\) بأنه أكبر عدد صحيح يقسم \(P_{a,b,c}(n)\) لكل عدد صحيح \(n\). ثم نعرّف
$$S(N)=\sum_{1\le a,b,c\le N} M(a,b,c).$$
والهدف النهائي هو
$$T(K)=\sum_{k=2}^{K} S(F_k),\qquad K=1234567890123,$$
حيث \(F_k\) هي أعداد فيبوناتشي. تعيد التنفيذات القيمة \(T(K)\bmod 10^9\)، أي آخر تسع خانات.
الفكرة الأساسية هي أن كثير الحدود يأخذ قيمًا صحيحة على جميع الأعداد الصحيحة إذا وفقط إذا كانت معاملاته صحيحة في الأساس الثنائي \(\binom{n}{1},\binom{n}{2},\binom{n}{3},\binom{n}{4},\dots\). لذلك نعيد كتابة \(P_{a,b,c}(n)\) في هذا الأساس بدل العمل مباشرة مع القوى \(n^j\).
نستخدم العلاقات القياسية
$$n=\binom{n}{1},\qquad n^2=2\binom{n}{2}+\binom{n}{1},$$
$$n^3=6\binom{n}{3}+6\binom{n}{2}+\binom{n}{1},$$
$$n^4=24\binom{n}{4}+36\binom{n}{3}+14\binom{n}{2}+\binom{n}{1}.$$
وبالتعويض نحصل على
$$P_{a,b,c}(n)=24\binom{n}{4}+(36+6a)\binom{n}{3}+(14+6a+2b)\binom{n}{2}+(1+a+b+c)\binom{n}{1}.$$
كل كثير حدود ثنائي \(\binom{n}{j}\) يعطي قيمة صحيحة لكل عدد صحيح \(n\). لذلك يكون \(P_{a,b,c}(n)/m\) ذا قيم صحيحة لكل \(n\) إذا وفقط إذا كانت جميع معاملات هذا التمثيل قابلة للقسمة على \(m\). ومن ثم فإن أكبر مثل هذا العدد هو القاسم المشترك الأكبر لهذه المعاملات:
$$\boxed{M(a,b,c)=\gcd\bigl(24,\ 36+6a,\ 14+6a+2b,\ 1+a+b+c\bigr).}$$
وهذا يفسر مباشرة المثال الموجود في نص المسألة:
$$M(4,2,5)=\gcd(24,60,42,12)=6.$$
وفحص صغير هو
$$S(1)=M(1,1,1)=\gcd(24,42,22,4)=2.$$
الذي يهم فقط هو البواقي modulo \(24\)، لأن \(\gcd(24,x)\) يعتمد فقط على \(x \pmod{24}\). نكتب
$$N=24q+r,\qquad 0\le r<24.$$
ولكل باقٍ \(t\in\{1,\dots,24\}\)، فإن عدد الأعداد في \(\{1,\dots,N\}\) التي تملك هذا الباقي هو
$$q+\varepsilon_t(r),\qquad \varepsilon_t(r)=\begin{cases}1,& t\le r,\\0,& t>r.\end{cases}$$
ومن ثم
$$S(N)=\sum_{r_a=1}^{24}\sum_{r_b=1}^{24}\sum_{r_c=1}^{24} M(r_a,r_b,r_c)\bigl(q+\varepsilon_{r_a}\bigr)\bigl(q+\varepsilon_{r_b}\bigr)\bigl(q+\varepsilon_{r_c}\bigr).$$
وبعد التوسيع نحصل على
$$S(N)=C_3 q^3 + C_2(r) q^2 + C_1(r) q + C_0(r).$$
حيث إن \(C_3\) ثابت، أما \(C_2,C_1,C_0\) فتعتمد فقط على الباقي \(r\). لذلك فإن \(S(N)\) شبه متعددة حدود من الدرجة الثالثة وفترتها \(24\). تقوم التنفيذات بتهيئة هذه الجداول الأربع مرة واحدة عبر تعداد جميع ثلاثيات البواقي وعددها \(24^3\).
ونقاط التحقق المستخدمة هي
$$S(10)=1972,\qquad S(10000)=2024258331114.$$
نكتب كل عدد فيبوناتشي بالشكل
$$F_k=24q_k+r_k,\qquad 0\le r_k<24.$$
وبما أن متتالية فيبوناتشي modulo \(24\) لها فترة بيسانو مقدارها \(24\)، فإن متتالية البواقي \(r_k\) دورية. ومن \(F_{k+2}=F_{k+1}+F_k\) نستنتج
$$r_{k+2}\equiv r_{k+1}+r_k \pmod{24},$$
$$q_{k+2}=q_{k+1}+q_k+\delta_k,\qquad \delta_k=\left\lfloor\frac{r_k+r_{k+1}}{24}\right\rfloor.$$
وقيمة الحمل \(\delta_k\) تعتمد فقط على زوج البواقي الدوري \((r_k,r_{k+1})\)، ولذلك فهي دورية أيضًا. وهكذا تتحول المسألة ذات الفهرس الضخم إلى علاقة رجعية أفينية دورية وثابتة البعد.
بما أن \(S(F_k)\) تكعيبية في \(q_k\)، فيكفي تتبع جميع الحدود الأحادية حتى الدرجة الثالثة في متغيري خارج القسمة المتتاليين \(x=q_k\) و\(y=q_{k+1}\):
$$1,\ x,\ y,\ x^2,\ xy,\ y^2,\ x^3,\ x^2y,\ xy^2,\ y^3,$$
مع إحداثي إضافي للمجموع التراكمي \(\sum_{j=2}^{k} S(F_j)\). تحت التحديث
$$x'=y,\qquad y'=x+y+\delta_k$$
يتحول كل حد أحادي إلى تركيب خطي من الأساس نفسه. على سبيل المثال،
$$x'y'=y(x+y+\delta_k),\qquad y'^2=(x+y+\delta_k)^2,\qquad y'^3=(x+y+\delta_k)^3.$$
وبالتالي يمكن تمثيل خطوة فيبوناتشي واحدة بمصفوفة \(11\times 11\). ثم تُضرب مصفوفات المراحل الأربع والعشرين لدورة كاملة للحصول على مصفوفة كتلية واحدة، ويُطبَّق عليها الأسّ الثنائي.
تنفيذات C++ وPython وJava تتبع المسار نفسه. أولًا تُهيِّئ معاملات شبه متعددة الحدود الخاصة بـ \(S(N)\) انطلاقًا من نواة البواقي modulo \(24\). بعد ذلك تُبنى مصفوفات الانتقال الأربع والعشرون المعتمدة على الطور، والمحددة بواسطة بواقي فيبوناتشي والحمل الموافق لها. وفي النهاية تُرفع مصفوفة الدورة الكاملة إلى قوة مناسبة، ثم يُطبَّق الجزء المتبقي من الدورة، وتُقرأ مركبة المجموع التراكمي modulo \(10^9\).
مرحلة التهيئة الخاصة بالبواقي ذات حجم ثابت، وحدها الأقصى \(24^4\) تحديثًا أوليًا. أما الجزء الرئيسي فهو الأسّ الثنائي لمصفوفات ثابتة البعد \(11\times 11\). لذلك فإن الزمن \(O(\log K)\)، والذاكرة \(O(1)\) باستثناء الجداول والمصفوفات ذات الحجم الثابت.