For every non-square integer \(2 \le n \le 100000\), the task is to find the reduced fraction \(\frac{p}{q}\) with \(1 \le q \le 10^{12}\) that minimizes the error \( \left| \sqrt{n} - \frac{p}{q} \right| \), and then sum all winning denominators \(q\).
Because \(\sqrt{n}\) is irrational whenever \(n\) is not a square, there is no tie: exactly one reduced fraction is closest for each such \(n\). The difficulty is the denominator limit \(10^{12}\). A direct search over all denominators is impossible, so the solution uses the continued fraction of \(\sqrt{n}\) and turns the choice into an exact integer comparison between two final candidates.
The whole argument rests on one classical fact: once a denominator bound is imposed, the best rational approximation to an irrational number must come from the continued-fraction ladder, namely from a convergent or from an intermediate fraction between two consecutive convergents. For \(\sqrt{n}\), the code never leaves exact integer arithmetic while it walks that ladder.
Let \(a_0 = \lfloor \sqrt{n} \rfloor\). For a non-square \(n\), the continued fraction of \(\sqrt{n}\) is periodic after the first term, and the standard quadratic-irrational state can be written as
$$x_k = \frac{\sqrt{n} + m_k}{d_k}, \qquad a_k = \lfloor x_k \rfloor.$$
The next state is obtained entirely with integers:
$$m_{k+1} = d_k a_k - m_k,$$
$$d_{k+1} = \frac{n - m_{k+1}^2}{d_k},$$
$$a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$$
This recurrence is exactly what the implementations maintain. It generates the partial quotients of \(\sqrt{n}\) without ever approximating \(\sqrt{n}\) numerically.
If
$$\sqrt{n} = [a_0; a_1, a_2, a_3, \dots],$$
then the convergents satisfy
$$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},$$
with initial values \(p_{-2}=0\), \(p_{-1}=1\), \(q_{-2}=1\), \(q_{-1}=0\). These convergents are the principal best approximations.
Between two consecutive convergents there are also semiconvergents, sometimes called intermediate fractions:
$$\frac{p_t}{q_t} = \frac{t p_{k-1} + p_{k-2}}{t q_{k-1} + q_{k-2}}, \qquad 1 \le t < a_k.$$
When a denominator cap \(D\) is present, the optimum fraction under \(q \le D\) must be either the last convergent whose denominator still fits, or one of these semiconvergents for the next continued-fraction digit. Nothing else can beat them.
Let \(k\) be the first index for which \(q_k > D\). Then \(q_{k-1} \le D\), so the previous convergent is admissible, while the next full convergent is already too large.
Every admissible semiconvergent on that last edge has denominator
$$q_t = t q_{k-1} + q_{k-2}.$$
The largest allowed choice is therefore
$$t = \left\lfloor \frac{D - q_{k-2}}{q_{k-1}} \right\rfloor,$$
which gives the boundary semiconvergent \(q_t \le D < q_{t+1}\). Because \(q_k = a_k q_{k-1} + q_{k-2} > D\), this \(t\) automatically satisfies \(0 \le t < a_k\).
Among semiconvergents on the same edge, larger \(t\) means a larger denominator and also a smaller error. In other words, once the bound has cut the edge, only the boundary semiconvergent needs to be compared with the last admissible convergent.
The key identity is
$$\sqrt{n} = \frac{p_{k-2} + x_k p_{k-1}}{q_{k-2} + x_k q_{k-1}}, \qquad x_k = \frac{\sqrt{n} + m_k}{d_k}.$$
From this one obtains the exact errors
$$\left| \sqrt{n} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_{k-1}(x_k q_{k-1} + q_{k-2})},$$
and for the semiconvergent with parameter \(t\),
$$\left| \sqrt{n} - \frac{p_t}{q_t} \right| = \frac{x_k - t}{(t q_{k-1} + q_{k-2})(x_k q_{k-1} + q_{k-2})}.$$
So the semiconvergent is better exactly when
$$q_{k-1} x_k < 2 t q_{k-1} + q_{k-2}.$$
Substituting \(x_k = \frac{\sqrt{n} + m_k}{d_k}\) turns that into
$$q_{k-1} \sqrt{n} < R,$$
where
$$R = d_k (2 t q_{k-1} + q_{k-2}) - q_{k-1} m_k.$$
This is the integer test used by the implementations. If \(R \le 0\), the semiconvergent cannot win. If \(R > q_{k-1}(a_0+1)\), then it definitely wins because \(\sqrt{n} < a_0 + 1\). Otherwise both sides are positive, so the comparison becomes the exact square test
$$R^2 > n q_{k-1}^2.$$
No floating-point approximation is needed at any stage.
The continued fraction is
$$\sqrt{13} = [3; 1,1,1,1,6,\dots].$$
The convergents begin
$$\frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}, \frac{119}{33}, \dots$$
Suppose first that \(D=20\). The last admissible convergent is \(\frac{18}{5}\), because the next denominator \(33\) is too large. At this cutoff stage the quadratic-irrational state is \(m_k=3\), \(d_k=1\), and \(q_{k-1}=5\), \(q_{k-2}=3\). The boundary parameter is
$$t = \left\lfloor \frac{20-3}{5} \right\rfloor = 3,$$
so the boundary semiconvergent has denominator \(q_t = 3 \cdot 5 + 3 = 18\), namely \(\frac{65}{18}\). The comparison value is
$$R = 1 \cdot (2 \cdot 3 \cdot 5 + 3) - 5 \cdot 3 = 18.$$
Since \(5 \sqrt{13} \approx 18.0278\), we have \(R < 5\sqrt{13}\), so \(\frac{65}{18}\) is worse than \(\frac{18}{5}\). The winning denominator is therefore \(5\).
Now change the bound to \(D=30\). Then
$$t = \left\lfloor \frac{30-3}{5} \right\rfloor = 5,$$
so the boundary semiconvergent is \(\frac{101}{28}\). This time
$$R = 1 \cdot (2 \cdot 5 \cdot 5 + 3) - 5 \cdot 3 = 38,$$
and \(38 > 5\sqrt{13}\), so \(\frac{101}{28}\) beats \(\frac{18}{5}\). The winning denominator becomes \(28\). This is exactly the behavior checked by the implementations.
The C++, Python, and Java implementations all follow the same mathematical pipeline: skip perfect squares, generate the continued fraction of each \(\sqrt{n}\) with the integer recurrence above, stop at the first convergent whose denominator exceeds \(10^{12}\), and then decide between the previous convergent and the single boundary semiconvergent.
For each non-square \(n\), the implementation starts from \(a_0=\lfloor \sqrt{n} \rfloor\) and updates the quadratic-irrational state \((m_k,d_k,a_k)\) together with the convergent numerators and denominators. The recurrence for \((p_k,q_k)\) is synchronized with the recurrence for \((m_k,d_k,a_k)\), so when the denominator first crosses the bound, all data needed for the final comparison is already available.
Once the first oversized convergent appears, the implementation sets the provisional answer to the previous denominator \(q_{k-1}\). If the denominator bound still leaves room beyond \(q_{k-1}\), it computes the boundary value \(t = \left\lfloor \frac{D-q_{k-2}}{q_{k-1}} \right\rfloor\) and forms the corresponding semiconvergent denominator \(t q_{k-1} + q_{k-2}\).
The final decision is made with the exact criterion above. The C++ and Java implementations use wider integer arithmetic for intermediate values, while Python relies on arbitrary-precision integers automatically. The C++ implementation also performs small exact validations against brute force before launching the full computation, which confirms the continued-fraction logic on tiny cases.
After the winning denominator for one \(n\) is known, it is added to the running total. The C++ implementation distributes different \(n\)-values across several worker threads; the Python and Java implementations execute the same logic serially. The mathematical decision rule is identical in all three languages.
For one fixed \(n\), the loop continues until a convergent denominator exceeds \(D\). Since every partial quotient satisfies \(a_k \ge 1\), the denominators obey \(q_k \ge q_{k-1} + q_{k-2}\), so they grow at least as fast as Fibonacci numbers. Therefore the number of continued-fraction steps is \(O(\log D)\).
Each step performs only a constant amount of integer arithmetic, so over all non-squares \(n \le N\) the total work is \(O(N \log D)\), with \(N=100000\) and \(D=10^{12}\) in this problem. Memory usage is \(O(1)\) per worker aside from the running total. The practical speed comes from replacing a hopeless scan over \(10^{12}\) denominators by a very short continued-fraction walk for each \(n\).
Für jede nichtquadratische Zahl \(2 \le n \le 100000\) soll der vollständig gekürzte Bruch \(\frac{p}{q}\) mit \(1 \le q \le 10^{12}\) gefunden werden, der den Fehler \( \left| \sqrt{n} - \frac{p}{q} \right| \) minimiert. Anschließend werden alle so entstehenden Nenner \(q\) aufsummiert.
Weil \(\sqrt{n}\) für Nichtquadrate irrational ist, gibt es keinen Gleichstand: Zu jedem solchen \(n\) existiert genau ein bester gekürzter Bruch. Die Schwierigkeit steckt allein in der Schranke \(10^{12}\) für den Nenner. Deshalb durchsuchen die Lösungen nicht alle Nenner, sondern benutzen die Kettenbruchentwicklung von \(\sqrt{n}\) und reduzieren die Entscheidung am Ende auf einen exakten Ganzzahlvergleich zwischen zwei Kandidaten.
Der gesamte Beweis beruht auf einer klassischen Eigenschaft von Kettenbrüchen: Unter einer Nennerbeschränkung kann die beste rationale Approximation einer irrationalen Zahl nur ein Konvergente oder ein Zwischenbruch zwischen zwei aufeinanderfolgenden Konvergenten sein. Für \(\sqrt{n}\) lässt sich dieser Weg vollständig mit ganzzahliger Arithmetik verfolgen.
Setze \(a_0 = \lfloor \sqrt{n} \rfloor\). Für ein Nichtquadrat ist der Kettenbruch von \(\sqrt{n}\) nach dem ersten Glied periodisch, und der übliche Zustand eines quadratischen Irrationals lautet
$$x_k = \frac{\sqrt{n} + m_k}{d_k}, \qquad a_k = \lfloor x_k \rfloor.$$
Der nächste Zustand ergibt sich rein ganzzahlig durch
$$m_{k+1} = d_k a_k - m_k,$$
$$d_{k+1} = \frac{n - m_{k+1}^2}{d_k},$$
$$a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$$
Genau diese Rekursion halten die Implementierungen aufrecht. Sie erzeugt die Kettenbruchkoeffizienten von \(\sqrt{n}\), ohne \(\sqrt{n}\) jemals numerisch zu approximieren.
Gilt
$$\sqrt{n} = [a_0; a_1, a_2, a_3, \dots],$$
dann erfüllen die Konvergenten
$$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},$$
mit Startwerten \(p_{-2}=0\), \(p_{-1}=1\), \(q_{-2}=1\), \(q_{-1}=0\). Diese Konvergenten sind die hauptsächlichen besten Approximationen.
Zwischen zwei aufeinanderfolgenden Konvergenten liegen außerdem Semikonvergenten beziehungsweise Zwischenbrüche:
$$\frac{p_t}{q_t} = \frac{t p_{k-1} + p_{k-2}}{t q_{k-1} + q_{k-2}}, \qquad 1 \le t < a_k.$$
Unter einer Schranke \(q \le D\) kann das Optimum also nur der letzte noch zulässige Konvergente oder einer dieser Zwischenbrüche zum nächsten Kettenbruchglied sein. Andere rationale Zahlen kommen nicht mehr in Frage.
Sei \(k\) der erste Index mit \(q_k > D\). Dann ist \(q_{k-1} \le D\), also ist der vorige Konvergente zulässig, während der nächste volle Konvergente schon zu groß ist.
Jeder zulässige Zwischenbruch auf dieser letzten Kante besitzt einen Nenner der Form
$$q_t = t q_{k-1} + q_{k-2}.$$
Die größte noch erlaubte Wahl ist daher
$$t = \left\lfloor \frac{D - q_{k-2}}{q_{k-1}} \right\rfloor,$$
und liefert den Rand-Semikonvergenten mit \(q_t \le D < q_{t+1}\). Weil zugleich \(q_k = a_k q_{k-1} + q_{k-2} > D\) gilt, folgt automatisch \(0 \le t < a_k\).
Unter den Zwischenbrüchen derselben Kante bedeutet größeres \(t\) sowohl größeren Nenner als auch kleineren Fehler. Sobald also die Schranke diese Kante abschneidet, muss nur noch der Rand-Semikonvergente mit dem letzten zulässigen Konvergenten verglichen werden.
Die Schlüsselformel lautet
$$\sqrt{n} = \frac{p_{k-2} + x_k p_{k-1}}{q_{k-2} + x_k q_{k-1}}, \qquad x_k = \frac{\sqrt{n} + m_k}{d_k}.$$
Daraus folgen die exakten Fehlerdarstellungen
$$\left| \sqrt{n} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_{k-1}(x_k q_{k-1} + q_{k-2})},$$
und für den Zwischenbruch mit Parameter \(t\)
$$\left| \sqrt{n} - \frac{p_t}{q_t} \right| = \frac{x_k - t}{(t q_{k-1} + q_{k-2})(x_k q_{k-1} + q_{k-2})}.$$
Der Zwischenbruch ist also genau dann besser, wenn
$$q_{k-1} x_k < 2 t q_{k-1} + q_{k-2}.$$
Mit \(x_k = \frac{\sqrt{n} + m_k}{d_k}\) wird daraus
$$q_{k-1} \sqrt{n} < R,$$
wobei
$$R = d_k (2 t q_{k-1} + q_{k-2}) - q_{k-1} m_k.$$
Genau diesen Ganzzahltest verwenden die Implementierungen. Gilt \(R \le 0\), dann kann der Zwischenbruch nicht gewinnen. Gilt \(R > q_{k-1}(a_0+1)\), dann gewinnt er sicher, weil \(\sqrt{n} < a_0+1\). Im verbleibenden Fall sind beide Seiten positiv, und der Vergleich wird zu
$$R^2 > n q_{k-1}^2.$$
Damit bleibt der gesamte Algorithmus frei von Rundungsfehlern.
Der Kettenbruch lautet
$$\sqrt{13} = [3; 1,1,1,1,6,\dots].$$
Die ersten Konvergenten sind
$$\frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}, \frac{119}{33}, \dots$$
Nehmen wir zunächst \(D=20\). Der letzte zulässige Konvergente ist \(\frac{18}{5}\), denn der nächste Nenner \(33\) überschreitet die Schranke. Am Abschneidepunkt ist der Zustand \(m_k=3\), \(d_k=1\), außerdem \(q_{k-1}=5\) und \(q_{k-2}=3\). Daraus folgt
$$t = \left\lfloor \frac{20-3}{5} \right\rfloor = 3,$$
also hat der Rand-Zwischenbruch den Nenner \(q_t = 3 \cdot 5 + 3 = 18\), konkret \(\frac{65}{18}\). Der Vergleichswert ist
$$R = 1 \cdot (2 \cdot 3 \cdot 5 + 3) - 5 \cdot 3 = 18.$$
Weil \(5 \sqrt{13} \approx 18{,}0278\) gilt, haben wir \(R < 5\sqrt{13}\). Also ist \(\frac{65}{18}\) schlechter als \(\frac{18}{5}\), und der gesuchte Nenner ist \(5\).
Ändern wir nun die Schranke auf \(D=30\). Dann erhält man
$$t = \left\lfloor \frac{30-3}{5} \right\rfloor = 5,$$
also den Rand-Zwischenbruch \(\frac{101}{28}\). Jetzt ist
$$R = 1 \cdot (2 \cdot 5 \cdot 5 + 3) - 5 \cdot 3 = 38,$$
und \(38 > 5\sqrt{13}\). Daher schlägt \(\frac{101}{28}\) den Konvergenten \(\frac{18}{5}\), und der beste Nenner wird \(28\). Genau dieses Verhalten wird in den Implementierungen auch getestet.
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Struktur: perfekte Quadrate werden sofort übersprungen, für jedes übrige \(n\) wird die Kettenbruchentwicklung von \(\sqrt{n}\) mit der obigen Ganzzahlrekursion erzeugt, beim ersten Nenner über \(10^{12}\) wird angehalten, und dann wird zwischen dem letzten zulässigen Konvergenten und genau einem Rand-Semikonvergenten entschieden.
Für jedes Nichtquadrat startet die Implementierung mit \(a_0=\lfloor \sqrt{n} \rfloor\) und aktualisiert gleichzeitig den Zustand \((m_k,d_k,a_k)\) sowie die Zähler und Nenner der Konvergenten. Dadurch ist beim ersten Überschreiten der Schranke sofort die komplette Information für die Endentscheidung vorhanden.
Sobald der erste zu große Konvergente erscheint, wird der vorige Nenner \(q_{k-1}\) als vorläufige Antwort gesetzt. Falls zwischen \(q_{k-1}\) und der Schranke noch Platz liegt, berechnet die Implementierung den Randwert \(t = \left\lfloor \frac{D-q_{k-2}}{q_{k-1}} \right\rfloor\) und damit den Nenner des Rand-Semikonvergenten \(t q_{k-1} + q_{k-2}\).
Die endgültige Wahl erfolgt dann durch den exakten Test oben. Die C++- und Java-Implementierungen benutzen dafür breitere Ganzzahlarithmetik für Zwischenwerte, während Python ohnehin mit beliebig großen ganzen Zahlen arbeitet. Die C++-Version prüft die Logik zusätzlich auf kleinen Eingaben gegen eine brute-force-Suche.
Ist der beste Nenner für ein bestimmtes \(n\) gefunden, wird er zum Gesamtergebnis addiert. Die C++-Implementierung verteilt verschiedene Werte von \(n\) auf mehrere Threads; die Python- und Java-Implementierungen führen denselben mathematischen Ablauf seriell aus. Die Entscheidungsregel bleibt in allen drei Sprachen identisch.
Für festes \(n\) läuft die Schleife nur so lange, bis ein Konvergenten-Nenner die Grenze \(D\) überschreitet. Da jeder Kettenbruchkoeffizient \(a_k \ge 1\) ist, gilt \(q_k \ge q_{k-1} + q_{k-2}\), also wachsen die Nenner mindestens so schnell wie Fibonacci-Zahlen. Deshalb werden nur \(O(\log D)\) Kettenbruchschritte benötigt.
Jeder Schritt enthält nur konstant viele Ganzzahloperationen. Über alle Nichtquadrate \(n \le N\) ergibt sich daher insgesamt \(O(N \log D)\) Arbeit, hier mit \(N=100000\) und \(D=10^{12}\). Der Speicherbedarf beträgt \(O(1)\) pro Worker zusätzlich zur laufenden Summe. Praktisch ist das Verfahren schnell, weil es eine völlig unbrauchbare Suche über \(10^{12}\) Nenner durch sehr kurze Kettenbruchläufe ersetzt.
Her \(2 \le n \le 100000\) kare olmayan tam sayısı için, \(1 \le q \le 10^{12}\) koşulu altında \( \left| \sqrt{n} - \frac{p}{q} \right| \) hatasını en küçük yapan sadeleştirilmiş \(\frac{p}{q}\) kesri bulunur ve sonra bu kazanan paydalar \(q\) toplanır.
\(n\) kare değilse \(\sqrt{n}\) irrasyoneldir; dolayısıyla eşitlik durumu oluşmaz ve en yakın sade kesir tektir. Zorluk, \(10^{12}\) gibi çok büyük bir payda üst sınırından gelir. Çözümler bu yüzden bütün paydaları denemez; onun yerine \(\sqrt{n}\)'nin sürekli kesrini izler ve son kararı iki aday arasında tam sayı aritmetiğiyle verir.
Tüm yöntem şu klasik gözleme dayanır: bir irrasyonel sayıya, payda sınırı altında en iyi rasyonel yaklaşım ancak sürekli kesrin yakınsaklarından ya da iki ardışık yakınsak arasındaki ara kesirlerden biri olabilir. \(\sqrt{n}\) için bu yapı bütünüyle tam sayılarla takip edilebilir.
\(a_0 = \lfloor \sqrt{n} \rfloor\) olsun. \(n\) kare değilse \(\sqrt{n}\)'nin sürekli kesri ilk terimden sonra periyodiktir ve standart ikinci dereceden irrasyonel durumu
$$x_k = \frac{\sqrt{n} + m_k}{d_k}, \qquad a_k = \lfloor x_k \rfloor$$
şeklinde yazılır. Bir sonraki durum yalnızca tam sayılarla elde edilir:
$$m_{k+1} = d_k a_k - m_k,$$
$$d_{k+1} = \frac{n - m_{k+1}^2}{d_k},$$
$$a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$$
Uygulamalar tam olarak bu özyinelemeyi yürütür. Böylece \(\sqrt{n}\)'nin sürekli kesir katsayıları, \(\sqrt{n}\)'yi kayan noktalı olarak yaklaşık hesaplamadan üretilir.
Eğer
$$\sqrt{n} = [a_0; a_1, a_2, a_3, \dots]$$
ise yakınsaklar
$$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2}$$
bağıntısını sağlar; başlangıç değerleri \(p_{-2}=0\), \(p_{-1}=1\), \(q_{-2}=1\), \(q_{-1}=0\)'dır. Bunlar temel en iyi yaklaşımlardır.
İki ardışık yakınsak arasında yarı-yakınsak ya da ara kesir denen adaylar da vardır:
$$\frac{p_t}{q_t} = \frac{t p_{k-1} + p_{k-2}}{t q_{k-1} + q_{k-2}}, \qquad 1 \le t < a_k.$$
Dolayısıyla \(q \le D\) kısıtı altında optimum kesir ya paydası hâlâ sınır içinde kalan son yakınsaktır ya da bir sonraki sürekli kesir basamağındaki bu ara kesirlerden biridir. Bunun dışındaki rasyonellerin kazanma şansı yoktur.
\(q_k > D\) olan ilk indise \(k\) diyelim. O zaman \(q_{k-1} \le D\) olduğundan önceki yakınsak geçerlidir; ama bir sonraki tam yakınsak artık çok büyüktür.
Bu son kenar üzerindeki her uygun ara kesrin paydası
$$q_t = t q_{k-1} + q_{k-2}$$
biçimindedir. En büyük izinli seçim bu yüzden
$$t = \left\lfloor \frac{D - q_{k-2}}{q_{k-1}} \right\rfloor$$
olur ve \(q_t \le D < q_{t+1}\) eşitsizliğini veren sınır ara kesri üretir. Aynı zamanda \(q_k = a_k q_{k-1} + q_{k-2} > D\) olduğu için otomatik olarak \(0 \le t < a_k\) sağlanır.
Aynı kenar üzerindeki ara kesirlerde \(t\) büyüdükçe hem payda hem de yaklaşım kalitesi artar. Bu nedenle sınır kesildikten sonra bütün ara kesirleri tek tek denemek gerekmez; yalnızca en büyük izinli olanı, yani sınır ara kesrini, son uygun yakınsakla karşılaştırmak yeterlidir.
Temel özdeşlik şudur:
$$\sqrt{n} = \frac{p_{k-2} + x_k p_{k-1}}{q_{k-2} + x_k q_{k-1}}, \qquad x_k = \frac{\sqrt{n} + m_k}{d_k}.$$
Buradan son uygun yakınsağın hatası
$$\left| \sqrt{n} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_{k-1}(x_k q_{k-1} + q_{k-2})}$$
ve parametresi \(t\) olan ara kesrin hatası
$$\left| \sqrt{n} - \frac{p_t}{q_t} \right| = \frac{x_k - t}{(t q_{k-1} + q_{k-2})(x_k q_{k-1} + q_{k-2})}$$
şeklinde çıkar. O hâlde ara kesir tam olarak şu koşul altında daha iyidir:
$$q_{k-1} x_k < 2 t q_{k-1} + q_{k-2}.$$
\(x_k = \frac{\sqrt{n} + m_k}{d_k}\) yazınca bu
$$q_{k-1} \sqrt{n} < R$$
eşitsizliğine dönüşür; burada
$$R = d_k (2 t q_{k-1} + q_{k-2}) - q_{k-1} m_k.$$
Uygulamaların kullandığı tam sayı testi budur. \(R \le 0\) ise ara kesir kazanamaz. \(R > q_{k-1}(a_0+1)\) ise \(\sqrt{n} < a_0+1\) olduğundan ara kesrin daha iyi olduğu hemen anlaşılır. Geriye kalan durumda iki taraf da pozitiftir ve karşılaştırma
$$R^2 > n q_{k-1}^2$$
biçiminde kare alınarak tam olarak yapılır. Böylece yuvarlama hatası hiç oluşmaz.
Sürekli kesir
$$\sqrt{13} = [3; 1,1,1,1,6,\dots]$$
olur. İlk yakınsaklar
$$\frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}, \frac{119}{33}, \dots$$
şeklindedir. Önce \(D=20\) alalım. Son uygun yakınsak \(\frac{18}{5}\)'tir; çünkü bir sonraki payda \(33\) sınırı aşar. Bu kesme noktasında durum \(m_k=3\), \(d_k=1\), ayrıca \(q_{k-1}=5\), \(q_{k-2}=3\)'tür. Bu yüzden
$$t = \left\lfloor \frac{20-3}{5} \right\rfloor = 3$$
ve sınır ara kesrinin paydası \(q_t = 3 \cdot 5 + 3 = 18\) olur; kesrin kendisi \(\frac{65}{18}\)'dir. Karşılaştırma değeri
$$R = 1 \cdot (2 \cdot 3 \cdot 5 + 3) - 5 \cdot 3 = 18$$
çıkar. \(5\sqrt{13} \approx 18.0278\) olduğundan \(R < 5\sqrt{13}\) ve \(\frac{65}{18}\), \(\frac{18}{5}\)'ten daha kötüdür. Dolayısıyla kazanan payda \(5\) olur.
Şimdi sınırı \(D=30\) yapalım. Bu kez
$$t = \left\lfloor \frac{30-3}{5} \right\rfloor = 5$$
ve sınır ara kesri \(\frac{101}{28}\) elde edilir. Artık
$$R = 1 \cdot (2 \cdot 5 \cdot 5 + 3) - 5 \cdot 3 = 38$$
olur ve \(38 > 5\sqrt{13}\). Böylece \(\frac{101}{28}\), \(\frac{18}{5}\)'ten daha iyidir; en iyi payda da \(28\) olur. Kodların doğruladığı küçük örnek tam olarak budur.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler: mükemmel kareleri hemen atlar, kalan her \(n\) için \(\sqrt{n}\)'nin sürekli kesrini yukarıdaki tam sayı özyinelemesiyle üretir, paydası \(10^{12}\)'yi ilk aşan yakınsakta durur ve ardından önceki yakınsak ile tek bir sınır ara kesri arasında seçim yapar.
Her kare olmayan \(n\) için süreç \(a_0=\lfloor \sqrt{n} \rfloor\) ile başlar. Ardından \((m_k,d_k,a_k)\) durumu ile yakınsakların pay ve paydaları birlikte güncellenir. Böylece payda ilk kez sınırı aştığında, son karar için gereken bütün sayılar zaten elde edilmiş olur.
İlk büyük yakınsak görüldüğünde geçici cevap olarak \(q_{k-1}\) alınır. Eğer \(q_{k-1}\) ile sınır arasında hâlâ boşluk varsa, uygulama \(t = \left\lfloor \frac{D-q_{k-2}}{q_{k-1}} \right\rfloor\) değerini hesaplar ve buna karşılık gelen sınır ara kesri paydasını \(t q_{k-1} + q_{k-2}\) oluşturur.
Son seçim yukarıdaki tam sayı eşitsizliğiyle yapılır. Derlenmiş sürümler ara değerlerde taşmayı önlemek için daha geniş tamsayı türleri kullanır; Python ise bunu doğal olarak keyfi büyüklükte tamsayılarla yapar. C++ sürümü ayrıca tam çözümden önce küçük girdilerde brute-force karşılaştırmalarıyla kendini doğrular.
Bir \(n\) için kazanan payda belirlendikten sonra toplam sonuca eklenir. C++ uygulaması farklı \(n\) değerlerini birden çok iş parçacığına dağıtır; Python ve Java uygulamaları aynı mantığı tek iş parçacığında yürütür. Üç dilde de matematiksel karar kuralı aynıdır.
Sabit bir \(n\) için döngü yalnızca bir yakınsak paydası \(D\)'yi aşana kadar sürer. Her kısmi bölüm \(a_k \ge 1\) olduğundan paydalar \(q_k \ge q_{k-1} + q_{k-2}\) bağıntısını sağlar; yani en az Fibonacci kadar hızlı büyürler. Bu yüzden gereken sürekli kesir adımı sayısı \(O(\log D)\) olur.
Her adımda yalnızca sabit sayıda tam sayı işlemi vardır. Böylece \(n \le N\) olan tüm kare olmayan sayılar üzerinde toplam iş yükü \(O(N \log D)\) olur; burada \(N=100000\) ve \(D=10^{12}\)'dir. Bellek kullanımı, çalışan başına koşan toplam dışında \(O(1)\)'dir. Yöntem pratikte hızlıdır; çünkü \(10^{12}\) farklı paydayı taramak yerine her \(n\) için çok kısa bir sürekli kesir yürüyüşü yapar.
Para cada entero no cuadrado \(2 \le n \le 100000\), hay que encontrar la fracción reducida \(\frac{p}{q}\) con \(1 \le q \le 10^{12}\) que minimiza el error \( \left| \sqrt{n} - \frac{p}{q} \right| \), y después sumar todos los denominadores ganadores \(q\).
Como \(\sqrt{n}\) es irracional cuando \(n\) no es un cuadrado perfecto, no hay empates: para cada \(n\) existe una única fracción reducida más cercana. La dificultad real está en la cota \(10^{12}\) sobre el denominador. Por eso las soluciones no prueban todos los valores de \(q\), sino que recorren la fracción continua de \(\sqrt{n}\) y convierten la decisión final en una comparación exacta entre dos candidatos.
Todo el método descansa sobre un hecho clásico: bajo una restricción de denominador, la mejor aproximación racional de un irracional debe aparecer entre los convergentes de su fracción continua o entre las fracciones intermedias situadas entre dos convergentes consecutivos. Para \(\sqrt{n}\), ese recorrido puede hacerse enteramente con aritmética exacta.
Sea \(a_0 = \lfloor \sqrt{n} \rfloor\). Si \(n\) no es cuadrado, la fracción continua de \(\sqrt{n}\) es periódica después del primer término, y el estado cuadrático estándar se escribe como
$$x_k = \frac{\sqrt{n} + m_k}{d_k}, \qquad a_k = \lfloor x_k \rfloor.$$
El siguiente estado se obtiene solo con enteros:
$$m_{k+1} = d_k a_k - m_k,$$
$$d_{k+1} = \frac{n - m_{k+1}^2}{d_k},$$
$$a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$$
Esa es exactamente la recurrencia que mantienen las implementaciones. De ese modo generan los cocientes parciales de \(\sqrt{n}\) sin aproximar nunca \(\sqrt{n}\) mediante coma flotante.
Si
$$\sqrt{n} = [a_0; a_1, a_2, a_3, \dots],$$
entonces los convergentes cumplen
$$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},$$
con valores iniciales \(p_{-2}=0\), \(p_{-1}=1\), \(q_{-2}=1\), \(q_{-1}=0\). Estos convergentes son las aproximaciones principales.
Entre dos convergentes consecutivos también aparecen semiconvergentes o fracciones intermedias:
$$\frac{p_t}{q_t} = \frac{t p_{k-1} + p_{k-2}}{t q_{k-1} + q_{k-2}}, \qquad 1 \le t < a_k.$$
Con una cota \(q \le D\), la fracción óptima solo puede ser el último convergente cuyo denominador aún cabe en la cota, o una de estas fracciones intermedias asociadas al siguiente dígito de la fracción continua. No hace falta considerar nada más.
Sea \(k\) el primer índice tal que \(q_k > D\). Entonces \(q_{k-1} \le D\), así que el convergente anterior sí es admisible, mientras que el siguiente convergente completo ya es demasiado grande.
Toda fracción intermedia admisible en ese último tramo tiene denominador
$$q_t = t q_{k-1} + q_{k-2}.$$
La elección máxima permitida es por tanto
$$t = \left\lfloor \frac{D - q_{k-2}}{q_{k-1}} \right\rfloor,$$
que produce el semiconvergente de frontera con \(q_t \le D < q_{t+1}\). Como además \(q_k = a_k q_{k-1} + q_{k-2} > D\), automáticamente se cumple \(0 \le t < a_k\).
Entre los semiconvergentes del mismo tramo, un valor mayor de \(t\) significa un denominador mayor y también un error menor. Por eso, una vez cortado el tramo por la cota \(D\), basta comparar el último convergente admisible con el semiconvergente de frontera.
La identidad central es
$$\sqrt{n} = \frac{p_{k-2} + x_k p_{k-1}}{q_{k-2} + x_k q_{k-1}}, \qquad x_k = \frac{\sqrt{n} + m_k}{d_k}.$$
De aquí se obtienen los errores exactos
$$\left| \sqrt{n} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_{k-1}(x_k q_{k-1} + q_{k-2})},$$
y para el semiconvergente con parámetro \(t\),
$$\left| \sqrt{n} - \frac{p_t}{q_t} \right| = \frac{x_k - t}{(t q_{k-1} + q_{k-2})(x_k q_{k-1} + q_{k-2})}.$$
Por tanto, el semiconvergente es mejor exactamente cuando
$$q_{k-1} x_k < 2 t q_{k-1} + q_{k-2}.$$
Sustituyendo \(x_k = \frac{\sqrt{n} + m_k}{d_k}\), esto se convierte en
$$q_{k-1} \sqrt{n} < R,$$
donde
$$R = d_k (2 t q_{k-1} + q_{k-2}) - q_{k-1} m_k.$$
Ese es el criterio entero usado por las implementaciones. Si \(R \le 0\), el semiconvergente no puede ganar. Si \(R > q_{k-1}(a_0+1)\), gana automáticamente porque \(\sqrt{n} < a_0+1\). En el caso restante ambos lados son positivos y la comparación exacta pasa a ser
$$R^2 > n q_{k-1}^2.$$
Así se evita cualquier inestabilidad numérica.
La fracción continua es
$$\sqrt{13} = [3; 1,1,1,1,6,\dots].$$
Los primeros convergentes son
$$\frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}, \frac{119}{33}, \dots$$
Tomemos primero \(D=20\). El último convergente admisible es \(\frac{18}{5}\), porque el siguiente denominador \(33\) ya supera la cota. En ese punto de corte el estado vale \(m_k=3\), \(d_k=1\), y además \(q_{k-1}=5\), \(q_{k-2}=3\). Entonces
$$t = \left\lfloor \frac{20-3}{5} \right\rfloor = 3,$$
de modo que el semiconvergente de frontera tiene denominador \(q_t = 3 \cdot 5 + 3 = 18\), es decir, \(\frac{65}{18}\). El valor de comparación es
$$R = 1 \cdot (2 \cdot 3 \cdot 5 + 3) - 5 \cdot 3 = 18.$$
Como \(5\sqrt{13} \approx 18.0278\), se tiene \(R < 5\sqrt{13}\), así que \(\frac{65}{18}\) es peor que \(\frac{18}{5}\). El denominador ganador es entonces \(5\).
Si cambiamos la cota a \(D=30\), obtenemos
$$t = \left\lfloor \frac{30-3}{5} \right\rfloor = 5,$$
y el semiconvergente de frontera pasa a ser \(\frac{101}{28}\). Ahora
$$R = 1 \cdot (2 \cdot 5 \cdot 5 + 3) - 5 \cdot 3 = 38,$$
y \(38 > 5\sqrt{13}\). Por tanto \(\frac{101}{28}\) supera a \(\frac{18}{5}\), y el mejor denominador se convierte en \(28\). Ese es exactamente el comportamiento comprobado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia matemática: descartan de inmediato los cuadrados perfectos, generan la fracción continua de cada \(\sqrt{n}\) con la recurrencia entera anterior, se detienen en el primer convergente cuyo denominador supera \(10^{12}\) y luego eligen entre el convergente anterior y un único semiconvergente de frontera.
Para cada \(n\) no cuadrado, la implementación comienza con \(a_0=\lfloor \sqrt{n} \rfloor\) y va actualizando a la vez el estado \((m_k,d_k,a_k)\) y los numeradores y denominadores de los convergentes. Así, cuando el denominador cruza la cota por primera vez, toda la información necesaria para la decisión final ya está preparada.
Cuando aparece el primer convergente demasiado grande, el denominador provisional pasa a ser \(q_{k-1}\). Si la cota \(D\) deja espacio más allá de ese valor, la implementación calcula \(t = \left\lfloor \frac{D-q_{k-2}}{q_{k-1}} \right\rfloor\) y forma el denominador del semiconvergente de frontera \(t q_{k-1} + q_{k-2}\).
La decisión definitiva usa el criterio exacto descrito arriba. Las versiones compiladas recurren a enteros más amplios para valores intermedios, mientras que Python se beneficia de enteros de precisión arbitraria. La versión en C++ además incluye verificaciones exactas en casos pequeños contra una búsqueda por fuerza bruta antes de ejecutar el cálculo completo.
Una vez determinado el mejor denominador para un valor de \(n\), ese denominador se añade al total. La implementación en C++ reparte distintos valores de \(n\) entre varios hilos de trabajo; las implementaciones en Python y Java ejecutan la misma lógica en serie. La regla matemática de decisión es la misma en los tres lenguajes.
Para un \(n\) fijo, el bucle avanza hasta que un denominador de convergente supera \(D\). Como todos los cocientes parciales satisfacen \(a_k \ge 1\), los denominadores obedecen \(q_k \ge q_{k-1} + q_{k-2}\), así que crecen al menos tan rápido como la sucesión de Fibonacci. Por ello, el número de pasos de fracción continua es \(O(\log D)\).
Cada paso requiere solo una cantidad constante de operaciones enteras. Sumando sobre todos los no cuadrados \(n \le N\), el trabajo total es \(O(N \log D)\), con \(N=100000\) y \(D=10^{12}\) en este problema. La memoria es \(O(1)\) por trabajador, aparte del total acumulado. En la práctica el método es rápido porque sustituye una búsqueda imposible sobre \(10^{12}\) denominadores por un recorrido muy corto de fracción continua para cada \(n\).
对每个满足 \(2 \le n \le 100000\) 的非平方整数，都要在 \(1 \le q \le 10^{12}\) 的限制下，找到使误差 \( \left| \sqrt{n} - \frac{p}{q} \right| \) 最小的既约分数 \(\frac{p}{q}\)，然后把所有最优分母 \(q\) 相加。
只要 \(n\) 不是完全平方数，\(\sqrt{n}\) 就是无理数，因此不会出现并列最优的情况；每个这样的 \(n\) 都只有一个最近的既约有理数。真正的难点在于分母上界 \(10^{12}\) 极大，不可能逐个枚举分母。实现采用的是 \(\sqrt{n}\) 的连分数结构，并把最后的判断压缩为两个候选之间的精确整数比较。
整个解法建立在一个经典结论上：对无理数施加分母上界之后，最优有理逼近一定来自它的连分数收敛分数，或者来自两个相邻收敛分数之间的中间分数。对于 \(\sqrt{n}\)，这一条链可以完全用整数运算走完。
设 \(a_0 = \lfloor \sqrt{n} \rfloor\)。当 \(n\) 不是平方数时，\(\sqrt{n}\) 的连分数在首项之后是周期性的，而标准的二次无理数状态可以写成
$$x_k = \frac{\sqrt{n} + m_k}{d_k}, \qquad a_k = \lfloor x_k \rfloor.$$
下一步状态完全由整数递推给出：
$$m_{k+1} = d_k a_k - m_k,$$
$$d_{k+1} = \frac{n - m_{k+1}^2}{d_k},$$
$$a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$$
实现维护的正是这组递推。这样就能在不使用浮点近似的前提下，逐步生成 \(\sqrt{n}\) 的连分数部分商。
如果
$$\sqrt{n} = [a_0; a_1, a_2, a_3, \dots],$$
那么收敛分数满足
$$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},$$
初值为 \(p_{-2}=0\)、\(p_{-1}=1\)、\(q_{-2}=1\)、\(q_{-1}=0\)。这些收敛分数给出了主导性的最佳逼近。
在两个相邻收敛分数之间，还存在半收敛分数，也常被称为中间分数：
$$\frac{p_t}{q_t} = \frac{t p_{k-1} + p_{k-2}}{t q_{k-1} + q_{k-2}}, \qquad 1 \le t < a_k.$$
因此，在约束 \(q \le D\) 下，最优分数只可能是最后一个仍未超界的收敛分数，或者是下一段上的某个半收敛分数。除此之外的有理数都不需要再检查。
令 \(k\) 为第一个满足 \(q_k > D\) 的下标。那么 \(q_{k-1} \le D\)，前一个收敛分数仍然可用，而下一个完整收敛分数已经超出限制。
这一最后区间上所有可行的半收敛分数，其分母都写成
$$q_t = t q_{k-1} + q_{k-2}.$$
因此，最大的允许参数是
$$t = \left\lfloor \frac{D - q_{k-2}}{q_{k-1}} \right\rfloor,$$
它给出边界半收敛分数，并满足 \(q_t \le D < q_{t+1}\)。同时，由于 \(q_k = a_k q_{k-1} + q_{k-2} > D\)，这个 \(t\) 自动满足 \(0 \le t < a_k\)。
同一段上的半收敛分数中，\(t\) 越大，分母越大，逼近误差也越小。所以一旦分母上界把这条边切断，就不必枚举所有半收敛分数，只需把最后一个可行的边界半收敛分数与上一个收敛分数比较即可。
关键恒等式是
$$\sqrt{n} = \frac{p_{k-2} + x_k p_{k-1}}{q_{k-2} + x_k q_{k-1}}, \qquad x_k = \frac{\sqrt{n} + m_k}{d_k}.$$
由此可得，上一个可行收敛分数的误差为
$$\left| \sqrt{n} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_{k-1}(x_k q_{k-1} + q_{k-2})},$$
而参数为 \(t\) 的半收敛分数误差为
$$\left| \sqrt{n} - \frac{p_t}{q_t} \right| = \frac{x_k - t}{(t q_{k-1} + q_{k-2})(x_k q_{k-1} + q_{k-2})}.$$
因此，半收敛分数更优，当且仅当
$$q_{k-1} x_k < 2 t q_{k-1} + q_{k-2}.$$
把 \(x_k = \frac{\sqrt{n} + m_k}{d_k}\) 代回去，就变成
$$q_{k-1} \sqrt{n} < R,$$
其中
$$R = d_k (2 t q_{k-1} + q_{k-2}) - q_{k-1} m_k.$$
这就是实现使用的整数判据。若 \(R \le 0\)，则半收敛分数不可能获胜。若 \(R > q_{k-1}(a_0+1)\)，则它一定更好，因为 \(\sqrt{n} < a_0+1\)。在剩余情形下，两边都为正，于是只需比较
$$R^2 > n q_{k-1}^2.$$
整个过程始终保持精确整数运算，不会出现浮点误判。
它的连分数是
$$\sqrt{13} = [3; 1,1,1,1,6,\dots].$$
前几个收敛分数为
$$\frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}, \frac{119}{33}, \dots$$
先取 \(D=20\)。最后一个没有超界的收敛分数是 \(\frac{18}{5}\)，因为下一个分母 \(33\) 已经太大。在这一截断点，状态是 \(m_k=3\)、\(d_k=1\)，并且 \(q_{k-1}=5\)、\(q_{k-2}=3\)。于是
$$t = \left\lfloor \frac{20-3}{5} \right\rfloor = 3,$$
边界半收敛分数的分母为 \(q_t = 3 \cdot 5 + 3 = 18\)，对应分数 \(\frac{65}{18}\)。比较量为
$$R = 1 \cdot (2 \cdot 3 \cdot 5 + 3) - 5 \cdot 3 = 18.$$
由于 \(5\sqrt{13} \approx 18.0278\)，所以 \(R < 5\sqrt{13}\)，说明 \(\frac{65}{18}\) 还不如 \(\frac{18}{5}\)。因此最优分母是 \(5\)。
如果把上界改成 \(D=30\)，则
$$t = \left\lfloor \frac{30-3}{5} \right\rfloor = 5,$$
边界半收敛分数变成 \(\frac{101}{28}\)。这时
$$R = 1 \cdot (2 \cdot 5 \cdot 5 + 3) - 5 \cdot 3 = 38,$$
而 \(38 > 5\sqrt{13}\)，于是 \(\frac{101}{28}\) 比 \(\frac{18}{5}\) 更接近 \(\sqrt{13}\)，最优分母也就变成 \(28\)。实现中的小规模校验正是验证这一行为。
C++、Python 和 Java 实现遵循同一条数学流程：先跳过完全平方数，再用上面的整数递推生成每个 \(\sqrt{n}\) 的连分数，在第一个分母超过 \(10^{12}\) 的收敛分数处停下，然后在前一个收敛分数和唯一一个边界半收敛分数之间作出选择。
对每个非平方 \(n\)，实现从 \(a_0=\lfloor \sqrt{n} \rfloor\) 出发，同时更新 \((m_k,d_k,a_k)\) 状态以及收敛分数的分子分母。这样一来，当分母第一次越过上界时，最终判定需要的全部信息都已经就位。
一旦出现第一个超界收敛分数，程序先把前一个分母 \(q_{k-1}\) 作为暂定答案。如果 \(q_{k-1}\) 与上界 \(D\) 之间还有空间，就计算 \(t = \left\lfloor \frac{D-q_{k-2}}{q_{k-1}} \right\rfloor\)，并构造对应的边界半收敛分母 \(t q_{k-1} + q_{k-2}\)。
最后的胜负由上面的精确整数判据决定。编译型实现为中间值准备了更宽的整数类型；Python 则天然使用任意精度整数。C++ 实现还会在正式求和前，用一些很小的输入与暴力搜索结果逐项比对，确认连分数逻辑无误。
当某个 \(n\) 的最优分母确定后，就把它加入总和。C++ 实现把不同的 \(n\) 分配给多个工作线程；Python 和 Java 实现按相同的数学规则串行执行。三种语言的核心判定完全一致。
对固定的 \(n\)，循环只进行到某个收敛分母首次超过 \(D\) 为止。由于所有部分商都满足 \(a_k \ge 1\)，所以分母满足 \(q_k \ge q_{k-1} + q_{k-2}\)，至少按 Fibonacci 速度增长。因此连分数步骤数是 \(O(\log D)\)。
每一步只包含常数次整数运算，所以对所有 \(n \le N\) 的非平方数，总工作量为 \(O(N \log D)\)，这里 \(N=100000\)、\(D=10^{12}\)。除累计总和外，每个工作单元只需要 \(O(1)\) 额外空间。实际运行很快，因为它把不可能的 \(10^{12}\) 次分母扫描，替换成了每个 \(n\) 上极短的连分数推进。
Для каждого целого не-квадрата \(2 \le n \le 100000\) нужно найти несократимую дробь \(\frac{p}{q}\) с условием \(1 \le q \le 10^{12}\), минимизирующую ошибку \( \left| \sqrt{n} - \frac{p}{q} \right| \), а затем просуммировать все победившие знаменатели \(q\).
Поскольку \(\sqrt{n}\) иррационально для любого не-квадрата, ничьих не бывает: для каждого такого \(n\) существует единственная ближайшая несократимая дробь. Трудность создаёт огромная граница \(10^{12}\) на знаменатель. Поэтому решения не перебирают все возможные \(q\), а используют цепную дробь для \(\sqrt{n}\) и сводят последний выбор к точному сравнению двух кандидатов.
Всё решение опирается на классический факт: при ограничении на знаменатель лучшая рациональная аппроксимация иррационального числа обязательно лежит на лестнице цепной дроби, то есть является либо подходящей дробью, либо промежуточной дробью между двумя соседними подходящими. Для \(\sqrt{n}\) эту конструкцию можно пройти целиком в точной целочисленной арифметике.
Пусть \(a_0 = \lfloor \sqrt{n} \rfloor\). Для не-квадрата цепная дробь числа \(\sqrt{n}\) периодична после первого члена, а стандартное состояние квадратической иррациональности записывается так:
$$x_k = \frac{\sqrt{n} + m_k}{d_k}, \qquad a_k = \lfloor x_k \rfloor.$$
Следующее состояние вычисляется только через целые числа:
$$m_{k+1} = d_k a_k - m_k,$$
$$d_{k+1} = \frac{n - m_{k+1}^2}{d_k},$$
$$a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$$
Именно эту рекурсию поддерживают реализации. Она порождает частные коэффициенты цепной дроби для \(\sqrt{n}\), не прибегая к плавающей арифметике.
Если
$$\sqrt{n} = [a_0; a_1, a_2, a_3, \dots],$$
то подходящие дроби удовлетворяют рекуррентным формулам
$$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},$$
при начальных значениях \(p_{-2}=0\), \(p_{-1}=1\), \(q_{-2}=1\), \(q_{-1}=0\). Это основные лучшие приближения.
Между двумя соседними подходящими дробями существуют также полуподходящие, или промежуточные, дроби:
$$\frac{p_t}{q_t} = \frac{t p_{k-1} + p_{k-2}}{t q_{k-1} + q_{k-2}}, \qquad 1 \le t < a_k.$$
Поэтому при ограничении \(q \le D\) оптимальная дробь может быть только либо последней подходящей дробью, чей знаменатель ещё помещается в границу, либо одной из этих промежуточных дробей на следующем шаге. Другие рациональные числа рассматривать не нужно.
Пусть \(k\) — первый индекс, для которого \(q_k > D\). Тогда \(q_{k-1} \le D\), значит предыдущая подходящая дробь допустима, а следующая полная подходящая дробь уже слишком велика.
Любая допустимая промежуточная дробь на этом последнем участке имеет знаменатель
$$q_t = t q_{k-1} + q_{k-2}.$$
Следовательно, максимальный допустимый параметр равен
$$t = \left\lfloor \frac{D - q_{k-2}}{q_{k-1}} \right\rfloor,$$
и даёт граничную полуподходящую дробь с \(q_t \le D < q_{t+1}\). Так как одновременно \(q_k = a_k q_{k-1} + q_{k-2} > D\), автоматически получается \(0 \le t < a_k\).
На одном и том же участке больший \(t\) означает и больший знаменатель, и меньшую ошибку. Поэтому после отсечения границей \(D\) достаточно сравнить только последнюю допустимую подходящую дробь с единственной граничной промежуточной дробью.
Ключевое тождество имеет вид
$$\sqrt{n} = \frac{p_{k-2} + x_k p_{k-1}}{q_{k-2} + x_k q_{k-1}}, \qquad x_k = \frac{\sqrt{n} + m_k}{d_k}.$$
Отсюда следуют точные формулы для ошибок:
$$\left| \sqrt{n} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_{k-1}(x_k q_{k-1} + q_{k-2})},$$
а для промежуточной дроби с параметром \(t\)
$$\left| \sqrt{n} - \frac{p_t}{q_t} \right| = \frac{x_k - t}{(t q_{k-1} + q_{k-2})(x_k q_{k-1} + q_{k-2})}.$$
Следовательно, промежуточная дробь лучше тогда и только тогда, когда
$$q_{k-1} x_k < 2 t q_{k-1} + q_{k-2}.$$
Подставляя \(x_k = \frac{\sqrt{n} + m_k}{d_k}\), получаем
$$q_{k-1} \sqrt{n} < R,$$
где
$$R = d_k (2 t q_{k-1} + q_{k-2}) - q_{k-1} m_k.$$
Это и есть целочисленный критерий, используемый в реализациях. Если \(R \le 0\), промежуточная дробь победить не может. Если \(R > q_{k-1}(a_0+1)\), она гарантированно лучше, потому что \(\sqrt{n} < a_0+1\). В оставшемся случае обе стороны положительны, и сравнение сводится к
$$R^2 > n q_{k-1}^2.$$
Так весь алгоритм обходится без каких-либо ошибок округления.
Её цепная дробь равна
$$\sqrt{13} = [3; 1,1,1,1,6,\dots].$$
Первые подходящие дроби таковы:
$$\frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}, \frac{119}{33}, \dots$$
Сначала возьмём \(D=20\). Последняя допустимая подходящая дробь — \(\frac{18}{5}\), поскольку следующий знаменатель \(33\) уже слишком велик. В точке отсечения имеем \(m_k=3\), \(d_k=1\), а также \(q_{k-1}=5\) и \(q_{k-2}=3\). Тогда
$$t = \left\lfloor \frac{20-3}{5} \right\rfloor = 3,$$
поэтому граничная промежуточная дробь имеет знаменатель \(q_t = 3 \cdot 5 + 3 = 18\), то есть это \(\frac{65}{18}\). Сравнительная величина равна
$$R = 1 \cdot (2 \cdot 3 \cdot 5 + 3) - 5 \cdot 3 = 18.$$
Поскольку \(5\sqrt{13} \approx 18.0278\), получаем \(R < 5\sqrt{13}\). Значит, \(\frac{65}{18}\) хуже, чем \(\frac{18}{5}\), и искомый знаменатель равен \(5\).
Теперь изменим границу на \(D=30\). Тогда
$$t = \left\lfloor \frac{30-3}{5} \right\rfloor = 5,$$
и граничная промежуточная дробь становится \(\frac{101}{28}\). На этот раз
$$R = 1 \cdot (2 \cdot 5 \cdot 5 + 3) - 5 \cdot 3 = 38,$$
а \(38 > 5\sqrt{13}\). Следовательно, \(\frac{101}{28}\) лучше, чем \(\frac{18}{5}\), и наилучший знаменатель равен \(28\). Именно такое поведение проверяют реализации на малых тестах.
Реализации на C++, Python и Java следуют одной и той же математической схеме: сразу пропускают полные квадраты, для каждого оставшегося \(n\) строят цепную дробь числа \(\sqrt{n}\) по целочисленной рекурсии, останавливаются на первом подходящем знаменателе, превысившем \(10^{12}\), а затем выбирают между предыдущей подходящей дробью и единственной граничной промежуточной дробью.
Для каждого не-квадрата вычисление стартует с \(a_0=\lfloor \sqrt{n} \rfloor\). Далее одновременно обновляются состояние \((m_k,d_k,a_k)\) и числители со знаменателями подходящих дробей. Поэтому в момент первого выхода за границу все данные для окончательного выбора уже готовы.
Как только появляется первый слишком большой подходящий знаменатель, временным ответом становится \(q_{k-1}\). Если между этим значением и границей \(D\) ещё есть место, реализация вычисляет \(t = \left\lfloor \frac{D-q_{k-2}}{q_{k-1}} \right\rfloor\) и строит знаменатель граничной промежуточной дроби \(t q_{k-1} + q_{k-2}\).
Окончательное решение принимает точный критерий, описанный выше. Компилируемые версии используют более широкую целочисленную арифметику для промежуточных величин, а Python получает произвольную точность автоматически. Версия на C++ дополнительно проверяет алгоритм на маленьких входах прямым перебором перед полным запуском.
Когда лучший знаменатель для данного \(n\) найден, он прибавляется к общей сумме. Реализация на C++ распределяет разные значения \(n\) между несколькими потоками, а Python и Java выполняют ту же математику последовательно. Основное правило выбора во всех трёх языках одно и то же.
Для фиксированного \(n\) цикл продолжается лишь до тех пор, пока некоторый знаменатель подходящей дроби впервые не превысит \(D\). Так как все частные коэффициенты удовлетворяют \(a_k \ge 1\), знаменатели подчиняются неравенству \(q_k \ge q_{k-1} + q_{k-2}\), то есть растут не медленнее чисел Фибоначчи. Значит, число шагов цепной дроби равно \(O(\log D)\).
Каждый шаг выполняет только константное число целочисленных операций. Следовательно, суммарная работа по всем не-квадратам \(n \le N\) составляет \(O(N \log D)\), где в этой задаче \(N=100000\), \(D=10^{12}\). Память равна \(O(1)\) на рабочий поток, не считая накопленной суммы. Практическая эффективность достигается тем, что вместо безнадёжного перебора до \(10^{12}\) используется очень короткий проход по цепной дроби для каждого \(n\).
لكل عدد صحيح غير مربع \(2 \le n \le 100000\)، المطلوب هو إيجاد الكسر المختزل \(\frac{p}{q}\) الذي يحقق أصغر خطأ ممكن \( \left| \sqrt{n} - \frac{p}{q} \right| \) تحت القيد \(1 \le q \le 10^{12}\)، ثم جمع جميع المقامات الفائزة \(q\).
بما أن \(\sqrt{n}\) يكون غير نسبي كلما كان \(n\) غير مربع، فلا توجد حالة تعادل: لكل \(n\) من هذا النوع يوجد كسر مختزل وحيد هو الأقرب. الصعوبة الحقيقية هي حد المقام الضخم \(10^{12}\). لذلك لا تقوم الحلول بتجربة كل المقامات، بل تعتمد على الكسر المستمر لـ \(\sqrt{n}\)، ثم تختزل القرار النهائي إلى مقارنة صحيحة تمامًا بين مرشحين اثنين فقط.
الأساس النظري هنا هو حقيقة كلاسيكية: عندما نفرض حدًا أعلى على المقام، فإن أفضل تقريب نسبي لعدد غير نسبي لا بد أن يكون إما من متقاربات الكسر المستمر، أو من الكسور الوسيطة الواقعة بين متقاربين متتاليين. وبالنسبة إلى \(\sqrt{n}\)، يمكن تتبع هذه البنية بالكامل باستخدام حسابات صحيحة فقط.
لنكتب \(a_0 = \lfloor \sqrt{n} \rfloor\). عندما لا يكون \(n\) مربعًا، يصبح الكسر المستمر لـ \(\sqrt{n}\) دوريًا بعد الحد الأول، ويمكن تمثيل حالة اللاعقلية التربيعية القياسية على الصورة
$$x_k = \frac{\sqrt{n} + m_k}{d_k}, \qquad a_k = \lfloor x_k \rfloor.$$
وتنتقل الحالة التالية بالكامل بواسطة علاقات صحيحة:
$$m_{k+1} = d_k a_k - m_k,$$
$$d_{k+1} = \frac{n - m_{k+1}^2}{d_k},$$
$$a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$$
وهذه هي العلاقات نفسها التي تحفظها التطبيقات. وبهذا نحصل على معاملات الكسر المستمر لـ \(\sqrt{n}\) من دون أي اعتماد على التقريب العشري.
إذا كان
$$\sqrt{n} = [a_0; a_1, a_2, a_3, \dots],$$
فإن المتقاربات تحقق
$$p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},$$
مع القيم الابتدائية \(p_{-2}=0\)، \(p_{-1}=1\)، \(q_{-2}=1\)، \(q_{-1}=0\). وهذه المتقاربات هي أفضل التقريبات الرئيسية.
وبين كل متقاربين متتاليين تظهر أيضًا أشباه المتقاربات أو الكسور الوسيطة:
$$\frac{p_t}{q_t} = \frac{t p_{k-1} + p_{k-2}}{t q_{k-1} + q_{k-2}}, \qquad 1 \le t < a_k.$$
لذلك، تحت القيد \(q \le D\)، لا يمكن أن يكون الكسر الأمثل إلا المتقارب الأخير الذي ما زال مقامه ضمن الحد، أو أحد هذه الكسور الوسيطة المرتبطة بالخطوة التالية من الكسر المستمر. ولا حاجة للنظر إلى أي كسور أخرى.
ليكن \(k\) هو أول فهرس يحقق \(q_k > D\). عندئذ يكون \(q_{k-1} \le D\)، أي إن المتقارب السابق ما زال مسموحًا، بينما المتقارب الكامل التالي صار أكبر من الحد.
كل كسر وسيط مسموح به على هذه الحافة الأخيرة يملك مقامًا من الشكل
$$q_t = t q_{k-1} + q_{k-2}.$$
ومن ثم فإن أكبر اختيار مسموح هو
$$t = \left\lfloor \frac{D - q_{k-2}}{q_{k-1}} \right\rfloor,$$
وهو الذي يعطي شبه المتقارب الحدّي بحيث \(q_t \le D < q_{t+1}\). وبما أن \(q_k = a_k q_{k-1} + q_{k-2} > D\)، فإن هذا يضمن تلقائيًا أن \(0 \le t < a_k\).
وعلى الحافة نفسها، كلما ازداد \(t\) ازداد المقام وتحسن التقريب أيضًا. لهذا السبب لا يلزم فحص جميع الكسور الوسيطة بعد فرض الحد \(D\)؛ يكفي مقارنة آخر متقارب مسموح مع شبه المتقارب الحدّي فقط.
الهوية الأساسية هي
$$\sqrt{n} = \frac{p_{k-2} + x_k p_{k-1}}{q_{k-2} + x_k q_{k-1}}, \qquad x_k = \frac{\sqrt{n} + m_k}{d_k}.$$
ومنها نحصل على الخطأ الدقيق للمتقارب الأخير المسموح:
$$\left| \sqrt{n} - \frac{p_{k-1}}{q_{k-1}} \right| = \frac{1}{q_{k-1}(x_k q_{k-1} + q_{k-2})},$$
ولشبه المتقارب ذي المعامل \(t\):
$$\left| \sqrt{n} - \frac{p_t}{q_t} \right| = \frac{x_k - t}{(t q_{k-1} + q_{k-2})(x_k q_{k-1} + q_{k-2})}.$$
إذن يكون شبه المتقارب أفضل تحديدًا عندما
$$q_{k-1} x_k < 2 t q_{k-1} + q_{k-2}.$$
وبالتعويض عن \(x_k = \frac{\sqrt{n} + m_k}{d_k}\) نحصل على
$$q_{k-1} \sqrt{n} < R,$$
حيث
$$R = d_k (2 t q_{k-1} + q_{k-2}) - q_{k-1} m_k.$$
هذا هو الاختبار الصحيح الذي تستعمله التطبيقات. فإذا كان \(R \le 0\) فلا يمكن لشبه المتقارب أن يفوز. وإذا كان \(R > q_{k-1}(a_0+1)\)، فإنه يفوز مباشرة لأن \(\sqrt{n} < a_0+1\). وفي الحالة المتبقية يكون الطرفان موجبين، فتصير المقارنة المكافئة
$$R^2 > n q_{k-1}^2.$$
وهكذا يبقى القرار كله ضمن الحساب الصحيح التام من دون أخطاء تقريب.
لدينا
$$\sqrt{13} = [3; 1,1,1,1,6,\dots].$$
وأول المتقاربات هي
$$\frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}, \frac{119}{33}, \dots$$
لنأخذ أولًا \(D=20\). آخر متقارب مسموح هو \(\frac{18}{5}\)، لأن المقام التالي \(33\) أكبر من الحد. عند نقطة التوقف تكون الحالة \(m_k=3\)، \(d_k=1\)، وكذلك \(q_{k-1}=5\) و\(q_{k-2}=3\). ومن ثم
$$t = \left\lfloor \frac{20-3}{5} \right\rfloor = 3,$$
فيكون مقام شبه المتقارب الحدّي \(q_t = 3 \cdot 5 + 3 = 18\)، أي إن الكسر هو \(\frac{65}{18}\). أما قيمة المقارنة فهي
$$R = 1 \cdot (2 \cdot 3 \cdot 5 + 3) - 5 \cdot 3 = 18.$$
وبما أن \(5\sqrt{13} \approx 18.0278\)، فإن \(R < 5\sqrt{13}\)، وهذا يعني أن \(\frac{65}{18}\) أسوأ من \(\frac{18}{5}\). إذن المقام الفائز هو \(5\).
إذا رفعنا الحد إلى \(D=30\)، نحصل على
$$t = \left\lfloor \frac{30-3}{5} \right\rfloor = 5,$$
وعندها يصبح شبه المتقارب الحدّي هو \(\frac{101}{28}\). هذه المرة
$$R = 1 \cdot (2 \cdot 5 \cdot 5 + 3) - 5 \cdot 3 = 38,$$
و\(38 > 5\sqrt{13}\)، لذلك يكون \(\frac{101}{28}\) أقرب إلى \(\sqrt{13}\) من \(\frac{18}{5}\)، ويصبح أفضل مقام هو \(28\). وهذا بالضبط ما تتحقق منه التطبيقات في الأمثلة الصغيرة.
تنفذ تطبيقات C++ وPython وJava السلسلة الرياضية نفسها: تتجاوز الأعداد المربعة مباشرة، وتولد الكسر المستمر لكل \(\sqrt{n}\) بواسطة العلاقات الصحيحة السابقة، ثم تتوقف عند أول متقارب يتجاوز مقامه \(10^{12}\)، وبعد ذلك تختار بين المتقارب السابق وشبه متقارب حدّي واحد فقط.
لكل \(n\) غير مربع تبدأ العملية من \(a_0=\lfloor \sqrt{n} \rfloor\)، ثم تُحدَّث حالة \((m_k,d_k,a_k)\) مع بسط ومقام المتقاربات بالتوازي. وبهذا، عندما يتجاوز المقام الحد لأول مرة، تكون كل البيانات اللازمة للحسم النهائي جاهزة بالفعل.
عند ظهور أول متقارب كبير جدًا، يُؤخذ \(q_{k-1}\) بوصفه الجواب المؤقت. وإذا كان الحد \(D\) يسمح بمقام أكبر قليلًا، تُحسب القيمة \(t = \left\lfloor \frac{D-q_{k-2}}{q_{k-1}} \right\rfloor\)، ثم يُبنى مقام شبه المتقارب الحدّي \(t q_{k-1} + q_{k-2}\).
ويُحسم القرار النهائي باستخدام معيار الأعداد الصحيحة المذكور أعلاه. تستعمل النسخ المترجمة أنواعًا عددية أوسع للقيم الوسيطة، بينما تعتمد Python تلقائيًا على الأعداد الصحيحة ذات الدقة غير المحدودة. كما تتضمن نسخة C++ تحققًا دقيقًا على حالات صغيرة بمقارنتها مع بحث مباشر قبل تنفيذ الحساب الكامل.
بعد معرفة المقام الفائز لقيمة معينة من \(n\)، يُضاف إلى المجموع الكلي. توزع نسخة C++ قيم \(n\) المختلفة على عدة خيوط عمل، بينما تنفذ نسختا Python وJava المنطق نفسه على نحو تسلسلي. القاعدة الرياضية الأساسية واحدة في اللغات الثلاث.
لكل \(n\) ثابتة، تستمر الحلقة فقط حتى يتجاوز مقام أحد المتقاربات الحد \(D\). وبما أن كل معامل جزئي يحقق \(a_k \ge 1\)، فإن المقامات تحقق \(q_k \ge q_{k-1} + q_{k-2}\)، أي إنها تنمو على الأقل بسرعة أعداد فيبوناتشي. لذلك يكون عدد خطوات الكسر المستمر \(O(\log D)\).
كل خطوة تحتاج إلى عدد ثابت من العمليات الصحيحة. ومن ثم يكون العمل الكلي عبر جميع الأعداد غير المربعة \(n \le N\) مساويًا لـ \(O(N \log D)\)، وهنا \(N=100000\) و\(D=10^{12}\). أما الذاكرة فهي \(O(1)\) لكل عامل، باستثناء المجموع الجاري. والسرعة العملية تأتي من استبدال فحص مستحيل يمتد حتى \(10^{12}\) بخطوات قليلة جدًا من الكسر المستمر لكل \(n\).