For each nonsquare integer \(\beta\), the problem associates a sequence of positive integers derived from the simple continued fraction of \(\sqrt{\beta}\). If that sequence is written as \(h_1,h_2,h_3,\dots\), then the quantity for one fixed \(\beta\) is
$$H(\beta,g)=\sum_{n=1}^{g} h_n \pmod{10^{15}}.$$
The final task is to evaluate this quantity for every nonsquare \(\beta\) between \(2\) and \(1000\), always with \(g=100\), and add the results modulo \(10^{15}\):
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
where the sum runs over all nonsquare integers \(2\le \beta\le 1000\). The C++, Python, and Java implementations all compute the same object by combining continued-fraction coefficients, convergent denominators, and arithmetic blocks coming from odd indices only.
The key observation is that the required sequence is not built from the convergents themselves, but from blocks of semiconvergent denominators determined by the continued fraction of \(\sqrt{\beta}\).
For a nonsquare integer \(\beta\), write
$$\sqrt{\beta}=[a_0;a_1,a_2,a_3,\dots],\qquad a_0=\lfloor\sqrt{\beta}\rfloor.$$
The tail is periodic because \(\sqrt{\beta}\) is a quadratic irrational. The standard recurrence used to generate the coefficients is
$$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt{\beta}\rfloor,$$
$$m_{n+1}=d_n a_n-m_n,\qquad d_{n+1}=\frac{\beta-m_{n+1}^2}{d_n},\qquad a_{n+1}=\left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor.$$
This recurrence is exactly what the implementations maintain while they lazily request more coefficients.
Let \(q_n\) denote the denominators of the convergents of the continued fraction. They satisfy
$$q_{-1}=0,\qquad q_0=1,\qquad q_n=a_n q_{n-1}+q_{n-2}\quad(n\ge 1).$$
Only these denominators are needed for the target sequence. Since the final answer is required modulo \(10^{15}\), the implementations reduce every newly generated denominator modulo \(10^{15}\) immediately. This is safe because the recurrence uses only addition and multiplication, so modular reduction commutes with every later update.
For each odd index \(i=2b+1\), the sequence contributes the block
$$B_i=\left(q_{i-2}+q_{i-1},\ q_{i-2}+2q_{i-1},\ \dots,\ q_{i-2}+a_i q_{i-1}\right).$$
This is an arithmetic progression with base \(q_{i-2}\), common difference \(q_{i-1}\), and length \(a_i\). Concatenating the odd blocks
$$B_1,\ B_3,\ B_5,\ B_7,\dots$$
produces the infinite sequence \(h_1,h_2,h_3,\dots\) required by the problem. Even indices do not contribute, so the implementations skip them entirely.
Suppose the current odd block is \(B_i\), but only its first \(t\) terms are needed, where \(1\le t\le a_i\). Then those \(t\) terms sum to
$$t\,q_{i-2}+q_{i-1}\frac{t(t+1)}{2}.$$
Therefore \(H(\beta,g)\) can be viewed as a prefix sum across consecutive arithmetic blocks: consume whole blocks while their entire length fits inside the first \(g\) terms, and truncate the final block when necessary. The implementations follow this same logic, but they emit the terms one by one so that every intermediate value stays reduced modulo \(10^{15}\).
Once \(H(\beta,100)\) is known for one nonsquare \(\beta\), it is added into the global total. Perfect squares are skipped from the start because their square roots are rational and do not belong to the periodic quadratic-irrational case used here.
So the full computation is simply
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
with the sum taken over all nonsquare integers \(2\le \beta\le 1000\).
For \(\beta=2\), we have
$$\sqrt{2}=[1;\overline{2}],$$
so every tail coefficient equals \(2\). The denominator recurrence gives
$$q_{-1}=0,\quad q_0=1,\quad q_1=2,\quad q_2=5,\quad q_3=12,\quad q_4=29,\quad q_5=70,\quad q_6=169.$$
The odd blocks are therefore
$$B_1=(1,2),\qquad B_3=(7,12),\qquad B_5=(41,70),\qquad B_7=(239,408).$$
Taking the first eight terms gives
$$1,\,2,\,7,\,12,\,41,\,70,\,239,\,408,$$
hence
$$H(2,8)=1+2+7+12+41+70+239+408=780.$$
This matches the checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same pipeline. For each nonsquare \(\beta\), they keep the current quadratic-irrational state \((m,d,a)\), extend the continued-fraction coefficients only when a new denominator is needed, and build the denominator list lazily from the initial values \(q_{-1}=0\) and \(q_0=1\).
Each time the next odd block is requested, the implementation reads the corresponding continued-fraction coefficient to get the block length, uses the previous two convergent denominators as the block's base and step, and emits exactly as many terms as are still needed for the prefix of length \(g\).
Every arithmetic update is reduced modulo \(10^{15}\): while generating denominators, while advancing through a block, and while adding the contribution of one \(\beta\) into the overall total. That keeps the numbers bounded without changing the final residue.
Finally, the outer loop scans \(\beta=2,3,\dots,1000\), skips perfect squares, evaluates \(H(\beta,100)\), and prints the accumulated result as a 15-digit zero-padded decimal string.
For one fixed pair \((\beta,g)\), the implementation emits exactly \(g\) sequence terms. Each emitted term costs \(O(1)\) amortized time once the occasional continued-fraction coefficient and denominator extension are accounted for, so the total running time is \(O(g)\).
The arrays of continued-fraction coefficients and convergent denominators also grow only as far as needed to cover those \(g\) emitted terms. Since every block has length at least \(1\), this requires \(O(g)\) stored values, so the auxiliary memory usage is \(O(g)\).
For the complete problem, the upper bound \(1000\) is fixed. In a generalized form with upper limit \(B\), the total cost would be \(O(Bg)\) time and \(O(g)\) memory.
Zu jeder nichtquadratischen Zahl \(\beta\) gehoert eine Folge positiver ganzer Zahlen, die aus dem einfachen Kettenbruch von \(\sqrt{\beta}\) aufgebaut wird. Schreibt man diese Folge als \(h_1,h_2,h_3,\dots\), dann ist fuer ein festes \(\beta\) die gesuchte Groesse
$$H(\beta,g)=\sum_{n=1}^{g} h_n \pmod{10^{15}}.$$
Im eigentlichen Problem wird dieser Wert fuer alle nichtquadratischen \(\beta\) zwischen \(2\) und \(1000\) mit \(g=100\) berechnet und modulo \(10^{15}\) aufsummiert:
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
wobei die Summe ueber alle nichtquadratischen ganzen Zahlen \(2\le \beta\le 1000\) laeuft. Die Implementierungen in C++, Python und Java verwenden dafuer dieselbe Konstruktion aus Kettenbruchkoeffizienten, Nennern der Konvergenten und arithmetischen Bloecken zu ungeraden Indizes.
Wesentlich ist, dass die Ziel-Folge nicht aus den Konvergenten selbst besteht, sondern aus Bloecken von Zwischenkonvergenten, die durch den Kettenbruch von \(\sqrt{\beta}\) bestimmt werden.
Fuer eine nichtquadratische Zahl \(\beta\) schreiben wir
$$\sqrt{\beta}=[a_0;a_1,a_2,a_3,\dots],\qquad a_0=\lfloor\sqrt{\beta}\rfloor.$$
Da \(\sqrt{\beta}\) eine quadratische Irrationalzahl ist, ist der Schwanz periodisch. Die verwendete Standardrekursion lautet
$$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt{\beta}\rfloor,$$
$$m_{n+1}=d_n a_n-m_n,\qquad d_{n+1}=\frac{\beta-m_{n+1}^2}{d_n},\qquad a_{n+1}=\left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor.$$
Genau diesen Zustand halten die Implementierungen vor, wenn weitere Kettenbruchkoeffizienten benoetigt werden.
Seien \(q_n\) die Nenner der Konvergenten. Dann gilt
$$q_{-1}=0,\qquad q_0=1,\qquad q_n=a_n q_{n-1}+q_{n-2}\quad(n\ge 1).$$
Fuer die gesuchte Folge werden nur diese Nenner gebraucht. Weil am Ende nur der Rest modulo \(10^{15}\) gefragt ist, reduzieren die Implementierungen jeden neu berechneten Nenner sofort modulo \(10^{15}\). Das ist korrekt, weil die Rekursion nur Addition und Multiplikation verwendet und daher mit modularer Reduktion vertraeglich ist.
Zu jedem ungeraden Index \(i=2b+1\) gehoert der Block
$$B_i=\left(q_{i-2}+q_{i-1},\ q_{i-2}+2q_{i-1},\ \dots,\ q_{i-2}+a_i q_{i-1}\right).$$
Das ist eine arithmetische Folge mit Startwert \(q_{i-2}\), Differenz \(q_{i-1}\) und Laenge \(a_i\). Durch Verketten der ungeraden Bloecke
$$B_1,\ B_3,\ B_5,\ B_7,\dots$$
entsteht die unendliche Folge \(h_1,h_2,h_3,\dots\), die im Problem verwendet wird. Gerade Indizes tragen nichts bei und werden deshalb vollstaendig uebersprungen.
Wenn vom aktuellen Block \(B_i\) nur die ersten \(t\) Terme benoetigt werden, wobei \(1\le t\le a_i\), dann ist ihre Summe
$$t\,q_{i-2}+q_{i-1}\frac{t(t+1)}{2}.$$
Damit ist \(H(\beta,g)\) eine Praefixsumme ueber aufeinanderfolgende arithmetische Bloecke: ganze Bloecke werden vollstaendig genommen, bis die Gesamtlänge \(g\) erreicht wuerde, und der letzte Block wird gegebenenfalls abgeschnitten. Die Implementierungen addieren trotzdem Term fuer Term, damit jede Zwischenrechnung direkt modulo \(10^{15}\) bleibt.
Sobald \(H(\beta,100)\) fuer ein nichtquadratisches \(\beta\) berechnet ist, wird dieser Wert zum Gesamtergebnis addiert. Perfekte Quadrate werden von Anfang an ausgelassen, weil ihre Quadratwurzeln rational sind und nicht in den periodischen quadratisch-irrationalen Fall fallen.
Die Endgroesse ist also
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
wobei ueber alle nichtquadratischen ganzen Zahlen \(2\le \beta\le 1000\) summiert wird.
Fuer \(\beta=2\) gilt
$$\sqrt{2}=[1;\overline{2}],$$
also ist jeder Kettenbruchkoeffizient im Schwanz gleich \(2\). Die Nennerrekursion liefert
$$q_{-1}=0,\quad q_0=1,\quad q_1=2,\quad q_2=5,\quad q_3=12,\quad q_4=29,\quad q_5=70,\quad q_6=169.$$
Daraus folgen die ungeraden Bloecke
$$B_1=(1,2),\qquad B_3=(7,12),\qquad B_5=(41,70),\qquad B_7=(239,408).$$
Die ersten acht Folgenterme sind damit
$$1,\,2,\,7,\,12,\,41,\,70,\,239,\,408,$$
und folglich
$$H(2,8)=1+2+7+12+41+70+239+408=780.$$
Genau dieser Wert wird auch in den Implementierungen als Kontrollpunkt verwendet.
Die Implementierungen in C++, Python und Java folgen demselben Ablauf. Fuer jedes nichtquadratische \(\beta\) halten sie den aktuellen quadratisch-irrationalen Zustand \((m,d,a)\), erweitern die Kettenbruchkoeffizienten nur bei Bedarf und bauen die Liste der Nenner ausgehend von \(q_{-1}=0\) und \(q_0=1\) schrittweise auf.
Sobald der naechste ungerade Block benoetigt wird, liest die Implementierung den zugehoerigen Kettenbruchkoeffizienten als Blocklaenge, nimmt die beiden vorherigen Nenner als Startwert und Schrittweite und erzeugt genau so viele Terme, wie fuer das Praefix der Laenge \(g\) noch fehlen.
Jede arithmetische Operation wird modulo \(10^{15}\) reduziert: beim Erzeugen neuer Nenner, beim Durchlaufen eines Blocks und beim Addieren des Beitrags eines einzelnen \(\beta\) zur Gesamtsumme. Dadurch bleiben die Zahlen klein, ohne dass sich der gesuchte Rest aendert.
Die aeussere Schleife durchlaeuft schliesslich \(\beta=2,3,\dots,1000\), ueberspringt perfekte Quadrate, berechnet \(H(\beta,100)\) und gibt das Resultat als 15-stellige, mit Nullen aufgefuellte Dezimalzahl aus.
Fuer ein festes Paar \((\beta,g)\) erzeugt die Implementierung genau \(g\) Folgenterme. Nach Beruecksichtigung der gelegentlichen Erweiterung von Kettenbruchkoeffizienten und Nennern kostet jeder erzeugte Term amortisiert \(O(1)\), also insgesamt \(O(g)\) Zeit.
Auch die Arrays fuer Kettenbruchkoeffizienten und Nenner wachsen nur so weit wie fuer diese \(g\) Terme notwendig. Da jeder Block mindestens einen Term besitzt, werden nur \(O(g)\) Werte gespeichert, also ist der Zusatzspeicher \(O(g)\).
Im vollstaendigen Problem ist die obere Grenze \(1000\) fest. Verallgemeinert man sie zu \(B\), dann ergibt sich insgesamt \(O(Bg)\) Zeit bei \(O(g)\) Speicher.
Her kare olmayan \(\beta\) icin, \(\sqrt{\beta}\) sayisinin basit surekli kesrinden uretilen pozitif bir tam sayi dizisi tanimlanir. Bu dizi \(h_1,h_2,h_3,\dots\) olarak yazilirsa, tek bir \(\beta\) icin istenen buyukluk
$$H(\beta,g)=\sum_{n=1}^{g} h_n \pmod{10^{15}}$$
olur. Asil gorev, \(2\) ile \(1000\) arasindaki tum kare olmayan \(\beta\) degerleri icin \(g=100\) alip bu degerleri modulo \(10^{15}\) toplamak:
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
burada toplam tum kare olmayan \(2\le \beta\le 1000\) tamsayilari uzerindedir. C++, Python ve Java uygulamalari bu hesabi, surekli kesir katsayilarini, yakinsak paydalarini ve sadece tek indekslerden gelen aritmetik bloklari kullanarak yapar.
Ana fikir su: istenen dizi dogrudan yakinsaklardan olusmaz; bunun yerine, \(\sqrt{\beta}\) surekli kesrinden gelen ara yakinsak payda bloklarindan olusur.
Kare olmayan bir \(\beta\) icin
$$\sqrt{\beta}=[a_0;a_1,a_2,a_3,\dots],\qquad a_0=\lfloor\sqrt{\beta}\rfloor$$
yazariz. \(\sqrt{\beta}\) kuadratik irrasyonel oldugu icin kuyruk kisminin periyodik oldugu bilinir. Kullanilan standart yineleme
$$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt{\beta}\rfloor,$$
$$m_{n+1}=d_n a_n-m_n,\qquad d_{n+1}=\frac{\beta-m_{n+1}^2}{d_n},\qquad a_{n+1}=\left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor$$
seklindedir. Uygulamalar yeni katsayi gerektikce tam olarak bu durumu ilerletir.
Yakinsaklarin paydalarini \(q_n\) ile gosterelim. Bunlar
$$q_{-1}=0,\qquad q_0=1,\qquad q_n=a_n q_{n-1}+q_{n-2}\quad(n\ge 1)$$
bagintisini saglar. Hedef dizi sadece bu paydalara baglidir. Sonuc yalnizca \(10^{15}\) modunda istendigi icin uygulamalar her yeni paydayi hemen \(10^{15}\) modunda saklar. Bu dogrudur; cunku yineleme sadece toplama ve carpma kullandigindan, ara adimlarda mod almak nihai kalan sinifini degistirmez.
Her tek indeks \(i=2b+1\) icin diziye su blok eklenir:
$$B_i=\left(q_{i-2}+q_{i-1},\ q_{i-2}+2q_{i-1},\ \dots,\ q_{i-2}+a_i q_{i-1}\right).$$
Bu, baslangici \(q_{i-2}\), artis miktari \(q_{i-1}\) ve uzunlugu \(a_i\) olan bir aritmetik dizidir. Tek indeksli bloklar
$$B_1,\ B_3,\ B_5,\ B_7,\dots$$
ard arda eklenince problemdeki sonsuz \(h_1,h_2,h_3,\dots\) dizisi elde edilir. Cift indeksli bloklar kullanilmaz; bu nedenle uygulama onlarin uzerinden dogrudan atlar.
Eger mevcut blok \(B_i\) icinden yalnizca ilk \(t\) terim gerekiyorsa ve \(1\le t\le a_i\) ise, bu kismin toplami
$$t\,q_{i-2}+q_{i-1}\frac{t(t+1)}{2}$$
olur. Dolayisiyla \(H(\beta,g)\), art arda gelen aritmetik bloklarin bir on toplami olarak gorulebilir: tam sigan bloklar tamamen alinir, son blok ise gerekiyorsa kirpilir. Uygulamalar ayni mantigi terim terim toplama ile uygular; boylece her ara deger \(10^{15}\) modunda tutulur.
Bir kare olmayan \(\beta\) icin \(H(\beta,100)\) hesaplandiktan sonra bu deger genel toplama eklenir. Tam kareler bastan atlanir; cunku bu durumda karekok rasyoneldir ve burada kullanilan periyodik kuadratik irrasyonel yapi ortaya cikmaz.
Son hesap bu nedenle
$$S=\sum H(\beta,100)\pmod{10^{15}}$$
seklindedir; toplam tum kare olmayan \(2\le \beta\le 1000\) tamsayilari uzerindedir.
\(\beta=2\) icin
$$\sqrt{2}=[1;\overline{2}]$$
oldugundan, kuyruktaki tum katsayilar \(2\)'dir. Payda yinelemesi
$$q_{-1}=0,\quad q_0=1,\quad q_1=2,\quad q_2=5,\quad q_3=12,\quad q_4=29,\quad q_5=70,\quad q_6=169$$
degerlerini verir. Buna gore tek indeksli bloklar
$$B_1=(1,2),\qquad B_3=(7,12),\qquad B_5=(41,70),\qquad B_7=(239,408)$$
olur. Ilk sekiz terim
$$1,\,2,\,7,\,12,\,41,\,70,\,239,\,408$$
ve toplam
$$H(2,8)=1+2+7+12+41+70+239+408=780$$
cikar. Bu deger uygulamalardaki kontrol noktasi ile aynidir.
C++, Python ve Java uygulamalari ayni is akisini izler. Her kare olmayan \(\beta\) icin once kuadratik irrasyonel durum \((m,d,a)\) tutulur, sonra yeni bir payda gerektiginde surekli kesir katsayilari ihtiyac kadar uretilir ve \(q_{-1}=0\), \(q_0=1\) baslangicindan itibaren payda listesi tembel bicimde genisletilir.
Bir sonraki tek indeksli blok istendiginde uygulama ilgili surekli kesir katsayisindan blok uzunlugunu alir, onceki iki yakinsak paydasini taban ve artis olarak kullanir ve uzunlugu \(g\) olan oneki tamamlamak icin ne kadar terim gerekiyorsa yalnizca o kadar terim uretir.
Her aritmetik guncelleme \(10^{15}\) modunda yapilir: yeni paydalar uretilirken, blok icinde ilerlerken ve tek bir \(\beta\) katkisi genel toplama eklenirken. Boylece sayilar kontrollu kalir ve son kalan degismez.
Dis dongu son olarak \(\beta=2,3,\dots,1000\) degerlerini tarar, tam kareleri atlar, \(H(\beta,100)\) degerini hesaplar ve sonucu 15 haneli, sola sifir doldurulmus onluk dize olarak yazar.
Sabit bir \((\beta,g)\) cifti icin uygulama tam olarak \(g\) dizi terimi uretir. Arada bir gereken surekli kesir katsayisi ve payda genisletmeleri hesaba katildiginda, terim basina amortize maliyet \(O(1)\) olur; dolayisiyla toplam sure \(O(g)\)'dir.
Surekli kesir katsayilari ve yakinsak paydalari icin tutulan diziler de sadece bu \(g\) terimi kapsayacak kadar buyur. Her blok en az bir terim icerdiigi icin yardimci bellek kullanimi \(O(g)\) seviyesindedir.
Tam problemde ust sinir \(1000\) sabittir. Bu siniri genel olarak \(B\) ile gosterirsek toplam maliyet \(O(Bg)\) zaman ve \(O(g)\) bellek olur.
Para cada entero no cuadrado \(\beta\), el problema define una sucesion de enteros positivos obtenida a partir de la fraccion continua simple de \(\sqrt{\beta}\). Si escribimos esa sucesion como \(h_1,h_2,h_3,\dots\), entonces para un \(\beta\) fijo la cantidad pedida es
$$H(\beta,g)=\sum_{n=1}^{g} h_n \pmod{10^{15}}.$$
La tarea final consiste en calcular este valor para todos los \(\beta\) no cuadrados entre \(2\) y \(1000\), siempre con \(g=100\), y sumar los resultados modulo \(10^{15}\):
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
donde la suma recorre todos los enteros no cuadrados \(2\le \beta\le 1000\). Las implementaciones en C++, Python y Java hacen exactamente esto combinando coeficientes de fracciones continuas, denominadores de convergentes y bloques aritmeticos asociados solo a indices impares.
La idea central es que la sucesion buscada no usa directamente los convergentes, sino bloques de denominadores de semiconvergentes derivados de la fraccion continua de \(\sqrt{\beta}\).
Para un \(\beta\) no cuadrado escribimos
$$\sqrt{\beta}=[a_0;a_1,a_2,a_3,\dots],\qquad a_0=\lfloor\sqrt{\beta}\rfloor.$$
Como \(\sqrt{\beta}\) es irracional cuadratica, la cola es periodica. La recurrencia clasica utilizada para generar los coeficientes es
$$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt{\beta}\rfloor,$$
$$m_{n+1}=d_n a_n-m_n,\qquad d_{n+1}=\frac{\beta-m_{n+1}^2}{d_n},\qquad a_{n+1}=\left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor.$$
Ese es exactamente el estado que mantienen las implementaciones cuando necesitan ampliar la expansion.
Sea \(q_n\) el denominador del \(n\)-esimo convergente. Entonces
$$q_{-1}=0,\qquad q_0=1,\qquad q_n=a_n q_{n-1}+q_{n-2}\quad(n\ge 1).$$
La sucesion objetivo depende solo de estos denominadores. Como la respuesta final se pide modulo \(10^{15}\), las implementaciones reducen cada nuevo denominador en cuanto se calcula. Eso no altera el resultado buscado, porque la recurrencia solo usa suma y multiplicacion.
Para cada indice impar \(i=2b+1\), la sucesion aporta el bloque
$$B_i=\left(q_{i-2}+q_{i-1},\ q_{i-2}+2q_{i-1},\ \dots,\ q_{i-2}+a_i q_{i-1}\right).$$
Se trata de una progresion aritmetica con base \(q_{i-2}\), diferencia \(q_{i-1}\) y longitud \(a_i\). Al concatenar los bloques impares
$$B_1,\ B_3,\ B_5,\ B_7,\dots$$
obtenemos la sucesion infinita \(h_1,h_2,h_3,\dots\) requerida por el problema. Los indices pares no contribuyen, por lo que las implementaciones los omiten.
Si del bloque actual \(B_i\) solo hacen falta los primeros \(t\) terminos, con \(1\le t\le a_i\), entonces su suma es
$$t\,q_{i-2}+q_{i-1}\frac{t(t+1)}{2}.$$
Por tanto, \(H(\beta,g)\) es una suma prefijo a traves de bloques aritmeticos consecutivos: se consumen bloques completos mientras quepan dentro de los primeros \(g\) terminos, y el ultimo bloque se recorta si es necesario. Las implementaciones realizan la suma termino a termino para mantener todos los intermedios reducidos modulo \(10^{15}\).
Una vez calculado \(H(\beta,100)\) para un \(\beta\) no cuadrado, ese valor se agrega al total global. Los cuadrados perfectos se descartan desde el principio, porque sus raices son racionales y no pertenecen al caso periodico de irracionales cuadraticas que se usa aqui.
Asi, la magnitud final es
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
sumando sobre todos los enteros no cuadrados \(2\le \beta\le 1000\).
Cuando \(\beta=2\), se tiene
$$\sqrt{2}=[1;\overline{2}],$$
de modo que todos los coeficientes de la cola valen \(2\). La recurrencia de denominadores produce
$$q_{-1}=0,\quad q_0=1,\quad q_1=2,\quad q_2=5,\quad q_3=12,\quad q_4=29,\quad q_5=70,\quad q_6=169.$$
Por tanto, los bloques impares son
$$B_1=(1,2),\qquad B_3=(7,12),\qquad B_5=(41,70),\qquad B_7=(239,408).$$
Los primeros ocho terminos de la sucesion son
$$1,\,2,\,7,\,12,\,41,\,70,\,239,\,408,$$
y entonces
$$H(2,8)=1+2+7+12+41+70+239+408=780.$$
Ese valor coincide con la comprobacion incluida en las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia de pasos. Para cada \(\beta\) no cuadrado mantienen el estado cuadratico \((m,d,a)\), amplian los coeficientes de la fraccion continua solo cuando hace falta un nuevo denominador y construyen la lista de denominadores de manera perezosa a partir de \(q_{-1}=0\) y \(q_0=1\).
Cada vez que se necesita el siguiente bloque impar, la implementacion lee el coeficiente correspondiente para conocer la longitud del bloque, usa los dos denominadores previos como base y paso, y emite exactamente el numero de terminos que todavia faltan para completar el prefijo de longitud \(g\).
Toda actualizacion aritmetica se reduce modulo \(10^{15}\): al generar nuevos denominadores, al avanzar dentro de un bloque y al sumar la contribucion de un \(\beta\) al total global. Asi se evita el crecimiento descontrolado de los enteros sin alterar el residuo final.
Por ultimo, el bucle exterior recorre \(\beta=2,3,\dots,1000\), omite los cuadrados perfectos, calcula \(H(\beta,100)\) e imprime el resultado acumulado como una cadena decimal de 15 digitos con ceros a la izquierda.
Para un par fijo \((\beta,g)\), la implementacion emite exactamente \(g\) terminos de la sucesion. Cada termino cuesta tiempo amortizado \(O(1)\) una vez contabilizadas las extensiones ocasionales de coeficientes y denominadores, asi que el tiempo total es \(O(g)\).
Los arreglos de coeficientes de fraccion continua y de denominadores tambien solo crecen hasta donde hace falta para cubrir esos \(g\) terminos. Como cada bloque tiene longitud al menos \(1\), el numero de valores almacenados es \(O(g)\), y por tanto la memoria auxiliar tambien es \(O(g)\).
En el problema completo, el limite superior \(1000\) es fijo. En una version general con cota \(B\), el coste total seria \(O(Bg)\) en tiempo y \(O(g)\) en memoria.
对于每个不是完全平方数的整数 \(\beta\)，题目都会从 \(\sqrt{\beta}\) 的简单连分数展开构造出一个正整数序列。若把这个序列记为 \(h_1,h_2,h_3,\dots\)，那么固定 \(\beta\) 时需要计算的量是
$$H(\beta,g)=\sum_{n=1}^{g} h_n \pmod{10^{15}}.$$
最终任务是对所有满足 \(2\le \beta\le 1000\) 的非平方整数取 \(g=100\)，把这些值再做一次模 \(10^{15}\) 的求和：
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
其中求和范围是所有非平方整数 \(2\le \beta\le 1000\)。C++、Python 和 Java 三份实现都采用同一条主线：先生成 \(\sqrt{\beta}\) 的连分数系数，再递推出收敛分母，随后只取奇数位置对应的等差块，最后累加前 \(100\) 项。
本题最重要的结构是：目标序列并不是直接由收敛分数本身组成，而是由连分数展开诱导出的若干个“半收敛分母块”拼接而成。
当 \(\beta\) 不是完全平方数时，可以写成
$$\sqrt{\beta}=[a_0;a_1,a_2,a_3,\dots],\qquad a_0=\lfloor\sqrt{\beta}\rfloor.$$
由于 \(\sqrt{\beta}\) 是二次无理数，它的连分数尾部必然是周期性的。程序使用的标准递推是
$$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt{\beta}\rfloor,$$
$$m_{n+1}=d_n a_n-m_n,\qquad d_{n+1}=\frac{\beta-m_{n+1}^2}{d_n},\qquad a_{n+1}=\left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor.$$
三份实现都是在需要更多连分数系数时，按这个状态递推继续向前推进。
设 \(q_n\) 表示第 \(n\) 个收敛分数的分母，则满足
$$q_{-1}=0,\qquad q_0=1,\qquad q_n=a_n q_{n-1}+q_{n-2}\quad(n\ge 1).$$
题目所需序列只依赖这些分母，不需要分子。由于最终答案只要求模 \(10^{15}\) 的结果，实现会在每一步生成新分母后立刻取模。这是安全的，因为后续递推只包含加法和乘法，模运算可以与这些运算兼容。
对每个奇数下标 \(i=2b+1\)，题目序列贡献一个块
$$B_i=\left(q_{i-2}+q_{i-1},\ q_{i-2}+2q_{i-1},\ \dots,\ q_{i-2}+a_i q_{i-1}\right).$$
这显然是一个等差数列：起点偏移量是 \(q_{i-2}\)，公差是 \(q_{i-1}\)，长度是 \(a_i\)。把所有奇数位置的块按顺序拼接起来，
$$B_1,\ B_3,\ B_5,\ B_7,\dots,$$
就得到题目要求的无限序列 \(h_1,h_2,h_3,\dots\)。偶数下标对应的块完全不参与，所以实现直接跳过它们。
如果当前块 \(B_i\) 只需要前 \(t\) 项，其中 \(1\le t\le a_i\)，那么这 \(t\) 项之和是
$$t\,q_{i-2}+q_{i-1}\frac{t(t+1)}{2}.$$
因此，\(H(\beta,g)\) 可以理解为一串连续等差块的前缀和：只要整个块还落在前 \(g\) 项范围内，就把整块吃掉；一旦最后一个块超过了长度 \(g\)，就只截取它的前一部分。实现层面虽然没有直接套用这个封闭求和公式，而是逐项累加，但它执行的正是同样的数学过程，并且每一步都会取模 \(10^{15}\)。
对某个非平方整数 \(\beta\) 求出 \(H(\beta,100)\) 之后，就把它并入全局总和。完全平方数会在一开始就被跳过，因为此时平方根是有理数，不属于这里使用的周期性二次无理数情形。
所以最终要求的量就是
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
求和范围为所有非平方整数 \(2\le \beta\le 1000\)。
当 \(\beta=2\) 时，
$$\sqrt{2}=[1;\overline{2}],$$
所以尾部所有连分数系数都等于 \(2\)。由分母递推式得到
$$q_{-1}=0,\quad q_0=1,\quad q_1=2,\quad q_2=5,\quad q_3=12,\quad q_4=29,\quad q_5=70,\quad q_6=169.$$
于是奇数下标块分别为
$$B_1=(1,2),\qquad B_3=(7,12),\qquad B_5=(41,70),\qquad B_7=(239,408).$$
前八项因此就是
$$1,\,2,\,7,\,12,\,41,\,70,\,239,\,408,$$
从而
$$H(2,8)=1+2+7+12+41+70+239+408=780.$$
这个值正好与实现中的校验结果一致，因此是一个很好的手工核对样例。
C++、Python 和 Java 三份实现的流程一致。对于每个非平方 \(\beta\)，实现会维护当前的二次无理数状态 \((m,d,a)\)，只有在需要新分母时才继续生成新的连分数系数，并从初始值 \(q_{-1}=0\)、\(q_0=1\) 开始懒惰地扩展分母序列。
每当需要处理下一个奇数块时，实现先读取对应的连分数系数以确定块长，再把前两个收敛分母作为块的基底和步长，然后只输出补足前缀长度 \(g\) 所需的那一部分项数。这样即使最后一个块只取前半段，也能自然处理。
所有算术更新都在模 \(10^{15}\) 下进行：生成新分母时如此，块内逐项推进时如此，把单个 \(\beta\) 的贡献加到总和里时也是如此。这样可以避免中间整数无限增大，同时不会改变最终答案的模值。
最外层驱动程序遍历 \(\beta=2,3,\dots,1000\)，跳过完全平方数，计算 \(H(\beta,100)\)，最后把总结果输出成 15 位、左侧补零的十进制字符串。
对固定的 \((\beta,g)\) 而言，实现恰好输出 \(g\) 个序列项。把偶尔需要扩展的连分数系数和分母也算进去后，每个输出项的均摊代价仍然是 \(O(1)\)，因此总时间复杂度是 \(O(g)\)。
连分数系数数组和分母数组只会增长到足以覆盖这 \(g\) 个输出项为止。由于每个块的长度至少为 \(1\)，所需存储规模也是 \(O(g)\)，辅助空间复杂度同样为 \(O(g)\)。
完整题目的上界 \(1000\) 是固定常数。若把外层上界一般化为 \(B\)，那么总时间复杂度可写为 \(O(Bg)\)，空间复杂度仍为 \(O(g)\)。
Для каждого целого \(\beta\), не являющегося полным квадратом, задача строит последовательность положительных чисел на основе простой цепной дроби для \(\sqrt{\beta}\). Если обозначить эту последовательность через \(h_1,h_2,h_3,\dots\), то для фиксированного \(\beta\) требуется вычислить
$$H(\beta,g)=\sum_{n=1}^{g} h_n \pmod{10^{15}}.$$
Затем этот результат нужно найти для всех неквадратных \(\beta\) от \(2\) до \(1000\) при \(g=100\) и просуммировать по модулю \(10^{15}\):
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
где суммирование ведется по всем неквадратным целым \(2\le \beta\le 1000\). Реализации на C++, Python и Java делают это одинаково: получают коэффициенты цепной дроби, строят знаменатели подходящих дробей и затем склеивают арифметические блоки, соответствующие только нечетным индексам.
Главная идея состоит в том, что целевая последовательность состоит не из самих подходящих дробей, а из блоков знаменателей промежуточных приближений, задаваемых цепной дробью числа \(\sqrt{\beta}\).
Для неквадратного \(\beta\) пишем
$$\sqrt{\beta}=[a_0;a_1,a_2,a_3,\dots],\qquad a_0=\lfloor\sqrt{\beta}\rfloor.$$
Так как \(\sqrt{\beta}\) является квадратичной иррациональностью, хвост этой цепной дроби периодичен. Используется стандартная рекуррентная схема
$$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt{\beta}\rfloor,$$
$$m_{n+1}=d_n a_n-m_n,\qquad d_{n+1}=\frac{\beta-m_{n+1}^2}{d_n},\qquad a_{n+1}=\left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor.$$
Именно это состояние поддерживают реализации, когда им нужен следующий коэффициент цепной дроби.
Пусть \(q_n\) обозначает знаменатель \(n\)-й подходящей дроби. Тогда
$$q_{-1}=0,\qquad q_0=1,\qquad q_n=a_n q_{n-1}+q_{n-2}\quad(n\ge 1).$$
Целевая последовательность зависит только от этих знаменателей. Поскольку нужен только остаток по модулю \(10^{15}\), реализации сразу же сокращают каждый новый знаменатель по этому модулю. Это корректно, так как вся дальнейшая арифметика состоит только из сложения и умножения.
Каждому нечетному индексу \(i=2b+1\) соответствует блок
$$B_i=\left(q_{i-2}+q_{i-1},\ q_{i-2}+2q_{i-1},\ \dots,\ q_{i-2}+a_i q_{i-1}\right).$$
Это арифметическая прогрессия с базой \(q_{i-2}\), шагом \(q_{i-1}\) и длиной \(a_i\). Если последовательно склеить блоки
$$B_1,\ B_3,\ B_5,\ B_7,\dots,$$
то получится бесконечная последовательность \(h_1,h_2,h_3,\dots\), которая и требуется в задаче. Четные индексы не участвуют, поэтому код их полностью пропускает.
Если из текущего блока \(B_i\) нужны только первые \(t\) членов, где \(1\le t\le a_i\), то их сумма равна
$$t\,q_{i-2}+q_{i-1}\frac{t(t+1)}{2}.$$
Следовательно, \(H(\beta,g)\) представляет собой префиксную сумму по последовательным арифметическим блокам: целые блоки берутся полностью, пока помещаются в первые \(g\) членов, а последний блок при необходимости обрезается. В реализациях эта же логика выполняется поэлементно, чтобы каждый промежуточный результат сразу оставался по модулю \(10^{15}\).
После того как для одного неквадратного \(\beta\) вычислено \(H(\beta,100)\), его вклад добавляется к общему итогу. Полные квадраты отбрасываются сразу, потому что их корни рациональны и не относятся к периодическому квадратично-иррациональному случаю, который здесь используется.
Итоговая величина имеет вид
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
где сумма берется по всем неквадратным целым \(2\le \beta\le 1000\).
Для \(\beta=2\) имеем
$$\sqrt{2}=[1;\overline{2}],$$
то есть все коэффициенты хвоста равны \(2\). Рекурсия для знаменателей дает
$$q_{-1}=0,\quad q_0=1,\quad q_1=2,\quad q_2=5,\quad q_3=12,\quad q_4=29,\quad q_5=70,\quad q_6=169.$$
Отсюда получаем нечетные блоки
$$B_1=(1,2),\qquad B_3=(7,12),\qquad B_5=(41,70),\qquad B_7=(239,408).$$
Первые восемь членов последовательности равны
$$1,\,2,\,7,\,12,\,41,\,70,\,239,\,408,$$
поэтому
$$H(2,8)=1+2+7+12+41+70+239+408=780.$$
Этот результат совпадает с контрольным значением, которое используют реализации.
Реализации на C++, Python и Java устроены одинаково. Для каждого неквадратного \(\beta\) они поддерживают текущее состояние квадратичной иррациональности \((m,d,a)\), добавляют новые коэффициенты цепной дроби только по мере необходимости и лениво наращивают список знаменателей, начиная с \(q_{-1}=0\) и \(q_0=1\).
Когда требуется следующий нечетный блок, реализация читает соответствующий коэффициент цепной дроби, чтобы узнать длину блока, берет два предыдущих знаменателя как базу и шаг и выдает ровно столько членов, сколько еще не хватает до префикса длины \(g\).
Каждое арифметическое обновление выполняется по модулю \(10^{15}\): при построении знаменателей, при проходе по блоку и при добавлении вклада одного \(\beta\) в глобальную сумму. Благодаря этому числа остаются ограниченными, а итоговый остаток не меняется.
Во внешнем цикле программа перебирает \(\beta=2,3,\dots,1000\), пропускает полные квадраты, вычисляет \(H(\beta,100)\) и выводит накопленный результат как 15-значную десятичную строку с ведущими нулями.
Для фиксированной пары \((\beta,g)\) реализация порождает ровно \(g\) членов последовательности. С учетом редких расширений цепной дроби и списка знаменателей стоимость одного члена амортизированно равна \(O(1)\), а общее время работы равно \(O(g)\).
Массивы коэффициентов цепной дроби и знаменателей растут только настолько, насколько это нужно для покрытия этих \(g\) членов. Поскольку длина каждого блока не меньше \(1\), объем дополнительной памяти также имеет порядок \(O(g)\).
В исходной задаче верхняя граница \(1000\) фиксирована. Если обозначить внешний предел через \(B\), то итоговая трудоемкость будет \(O(Bg)\) по времени и \(O(g)\) по памяти.
لكل عدد صحيح \(\beta\) ليس مربعا كاملا، تعرّف المسألة متتالية من الاعداد الصحيحة الموجبة مشتقة من الكسر المستمر البسيط لـ \(\sqrt{\beta}\). اذا رمزنا الى هذه المتتالية بـ \(h_1,h_2,h_3,\dots\)، فان الكمية المطلوبة لقيمة ثابتة من \(\beta\) هي
$$H(\beta,g)=\sum_{n=1}^{g} h_n \pmod{10^{15}}.$$
بعد ذلك يجب حساب هذه القيمة لكل \(\beta\) غير مربع بين \(2\) و\(1000\) مع تثبيت \(g=100\)، ثم جمع النتائج بترديد \(10^{15}\):
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
حيث يجري الجمع على جميع الاعداد الصحيحة غير المربعة \(2\le \beta\le 1000\). تعتمد تطبيقات C++ وPython وJava على البنية نفسها: توليد معاملات الكسر المستمر، ثم مقامات التقاربات، ثم تكوين كتل حسابية مرتبطة فقط بالفهارس الفردية.
الفكرة الاساسية هي ان المتتالية المطلوبة لا تتكون من التقاربات نفسها، بل من كتل من مقامات انصاف التقاربات المستخرجة من الكسر المستمر لـ \(\sqrt{\beta}\).
عندما لا يكون \(\beta\) مربعا كاملا نكتب
$$\sqrt{\beta}=[a_0;a_1,a_2,a_3,\dots],\qquad a_0=\lfloor\sqrt{\beta}\rfloor.$$
وبما ان \(\sqrt{\beta}\) عدد غير نسبي تربيعي، فان ذيل هذا الكسر المستمر يكون دوريا. التكرار القياسي المستخدم لتوليد المعاملات هو
$$m_0=0,\qquad d_0=1,\qquad a_0=\lfloor\sqrt{\beta}\rfloor,$$
$$m_{n+1}=d_n a_n-m_n,\qquad d_{n+1}=\frac{\beta-m_{n+1}^2}{d_n},\qquad a_{n+1}=\left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor.$$
وهذه هي بالضبط الحالة التي تحافظ عليها التطبيقات كلما احتاجت الى معاملات اضافية.
لنرمز الى مقام التقارب رقم \(n\) بالرمز \(q_n\). عندئذ تتحقق العلاقة
$$q_{-1}=0,\qquad q_0=1,\qquad q_n=a_n q_{n-1}+q_{n-2}\quad(n\ge 1).$$
المتتالية الهدف تعتمد فقط على هذه المقامات. ولان الجواب النهائي مطلوب بترديد \(10^{15}\)، تقوم التطبيقات باختزال كل مقام جديد مباشرة بهذا الترديد. هذا صحيح لان العلاقات اللاحقة تستخدم الجمع والضرب فقط، وهما منسجمان مع الاختزال المعياري.
لكل فهرس فردي \(i=2b+1\) تضيف المسألة الكتلة
$$B_i=\left(q_{i-2}+q_{i-1},\ q_{i-2}+2q_{i-1},\ \dots,\ q_{i-2}+a_i q_{i-1}\right).$$
هذه متتالية حسابية حدها الاساسي \(q_{i-2}\)، وفرقها \(q_{i-1}\)، وطولها \(a_i\). وعند لصق الكتل الفردية
$$B_1,\ B_3,\ B_5,\ B_7,\dots$$
نحصل على المتتالية اللانهائية \(h_1,h_2,h_3,\dots\) المطلوبة في المسألة. اما الفهارس الزوجية فلا تسهم في البناء، لذلك تتجاوزها التطبيقات تماما.
اذا احتجنا من الكتلة الحالية \(B_i\) اول \(t\) حدود فقط، حيث \(1\le t\le a_i\)، فان مجموع هذه الحدود يساوي
$$t\,q_{i-2}+q_{i-1}\frac{t(t+1)}{2}.$$
لذلك يمكن النظر الى \(H(\beta,g)\) على انه مجموع بادئة عبر كتل حسابية متتالية: نأخذ الكتل الكاملة ما دامت تقع داخل اول \(g\) حدود، ثم نقتطع الجزء اللازم فقط من الكتلة الاخيرة. التنفيذ الفعلي يجمع الحدود واحدا واحدا، لكنه يطبق الفكرة الرياضية نفسها مع اختزال كل خطوة بترديد \(10^{15}\).
بعد حساب \(H(\beta,100)\) لقيمة غير مربعة واحدة من \(\beta\)، تضاف هذه القيمة الى المجموع الكلي. اما المربعات الكاملة فتستبعد منذ البداية، لان جذورها اعداد نسبية ولا تدخل في الحالة الدورية الخاصة بالاعداد غير النسبية التربيعية المستخدمة هنا.
وعليه فان الكمية النهائية هي
$$S=\sum H(\beta,100)\pmod{10^{15}},$$
حيث يمتد الجمع على جميع الاعداد الصحيحة غير المربعة \(2\le \beta\le 1000\).
عندما \(\beta=2\) نحصل على
$$\sqrt{2}=[1;\overline{2}],$$
ولذلك تكون جميع معاملات الذيل مساوية لـ \(2\). تعطي علاقة المقامات
$$q_{-1}=0,\quad q_0=1,\quad q_1=2,\quad q_2=5,\quad q_3=12,\quad q_4=29,\quad q_5=70,\quad q_6=169.$$
ومن ثم تصبح الكتل الفردية
$$B_1=(1,2),\qquad B_3=(7,12),\qquad B_5=(41,70),\qquad B_7=(239,408).$$
وبالتالي فان اول ثمانية حدود هي
$$1,\,2,\,7,\,12,\,41,\,70,\,239,\,408,$$
ومنها
$$H(2,8)=1+2+7+12+41+70+239+408=780.$$
وهذا يطابق قيمة الفحص المستخدمة داخل التطبيقات.
تسير تطبيقات C++ وPython وJava على المسار نفسه. لكل \(\beta\) غير مربع تحافظ على حالة العدد غير النسبي التربيعي \((m,d,a)\)، وتولد معاملات الكسر المستمر فقط عند الحاجة، ثم توسع قائمة المقامات تدريجيا ابتداء من \(q_{-1}=0\) و\(q_0=1\).
وعندما يحين وقت الكتلة الفردية التالية، تقرأ الشفرة معامل الكسر المستمر الموافق لتحديد طول الكتلة، ثم تستخدم المقامين السابقين بوصفهما القاعدة والفرق، وتولد فقط عدد الحدود المطلوب لاكمال البادئة ذات الطول \(g\).
كل تحديث حسابي يختزل بترديد \(10^{15}\): عند توليد مقام جديد، وعند التقدم داخل كتلة، وعند اضافة مساهمة \(\beta\) واحدة الى المجموع الكلي. بهذه الطريقة تبقى القيم الوسيطة محدودة من غير ان يتغير الباقي النهائي.
في النهاية تمر الحلقة الخارجية على \(\beta=2,3,\dots,1000\)، وتتجاهل المربعات الكاملة، وتحسب \(H(\beta,100)\)، ثم تطبع النتيجة على شكل سلسلة عشرية مكونة من 15 خانة مع اصفار بادئة.
بالنسبة الى زوج ثابت \((\beta,g)\)، تنتج التطبيقات بالضبط \(g\) حدود من المتتالية. وبعد احتساب التوسعات المتقطعة لمعاملات الكسر المستمر والمقامات، تكون كلفة كل حد \(O(1)\) في المتوسط، ولذلك يكون الزمن الكلي \(O(g)\).
اما القوائم التي تخزن معاملات الكسر المستمر والمقامات فلا تنمو الا بقدر ما يكفي لتغطية تلك الحدود \(g\). ولان طول كل كتلة لا يقل عن \(1\)، فان الذاكرة الاضافية المطلوبة هي \(O(g)\) ايضا.
في المسألة الكاملة يكون الحد الاعلى \(1000\) ثابتا. ولو رمزنا الى هذا الحد في نسخة عامة بالرمز \(B\)، فسيكون التعقيد الكلي \(O(Bg)\) زمنا و\(O(g)\) ذاكرة.