Let \(S(N)\) be the sum of \(x+y+z\) over all primitive positive integer solutions of
$$z^2=16x^2+y^4,$$
with \(\gcd(x,y,z)=1\) and the problem's size bound \(z\le N\). The final result is required modulo \(10^9\). A naive search over \(x\) and \(y\) is far too expensive, so the key task is to describe every primitive solution by a small set of parameters and then iterate only those parameters.
The implementations split the equation into two cases according to the parity of \(y\). Each case leads to a complete parametrization, and the search range becomes a fourth-root range instead of a direct scan over coordinates.
Rearrange the equation as
$$(z-4x)(z+4x)=y^4.$$
Define
$$a=z-4x,\qquad b=z+4x.$$
Then \(ab=y^4\), \(a\lt b\), and \(a,b\) have the same parity. The primitive condition strongly limits their common divisor. This is where the parity of \(y\) matters:
If \(y\) is odd, then \(a\) and \(b\) are odd and in fact coprime.
If \(y\) is even, the power of \(2\) inside \(a\) and \(b\) is no longer symmetric, producing a second family.
Assume \(y\) is odd. Then \(y^4\) is odd, so both \(a\) and \(b\) are odd. Any common divisor \(d\) of \(a\) and \(b\) also divides
$$b-a=8x,\qquad a+b=2z.$$
Because \(d\) is odd, it must divide both \(x\) and \(z\). Since \(d\mid ab=y^4\), it also divides \(y\). Therefore \(d\mid \gcd(x,y,z)\), so primitiveness forces \(d=1\).
Now \(a\) and \(b\) are coprime and their product is a fourth power, so each factor must itself be a fourth power. Write
$$a=p^4,\qquad b=q^4,$$
with \(p\) and \(q\) positive, odd, coprime, and \(p\lt q\). Solving
$$z-4x=p^4,\qquad z+4x=q^4$$
gives
$$x=\frac{q^4-p^4}{8},\qquad y=pq,\qquad z=\frac{p^4+q^4}{2}.$$
These formulas are exactly the first branch used by the implementation.
Now assume \(y\) is even. In a primitive solution, \(x\) cannot be even, otherwise \(z\) would also be even and the gcd would be at least \(2\). So \(x\) is odd. Since \(y^4\) is divisible by \(16\), the equation shows that \(z\) is divisible by \(4\). Write
$$z=4u,\qquad y=2w.$$
Then
$$u^2=x^2+w^4.$$
If \(w\) were odd, then \(x^2\equiv1\pmod{16}\) and \(w^4\equiv1\pmod{16}\), which would force \(u^2\equiv2\pmod{16}\), impossible. Hence \(w\) is even, so we may write
$$y=4t,\qquad z=4u,$$
and the equation becomes
$$(u-x)(u+x)=16t^4.$$
Because \(u\) and \(x\) are odd, both factors are even. Their difference is \(2x\), which is divisible by \(2\) but not by \(4\), so the common power of \(2\) is exactly one factor \(2\). After ordering the factors, we must have
$$u+x=2s^4,\qquad u-x=8r^4,$$
or the same equations with the two sides swapped. Here \(r\) and \(s\) are coprime, and \(s\) must be odd. Adding and subtracting gives
$$x=\left|s^4-4r^4\right|,\qquad t=rs,\qquad z=4\left(s^4+4r^4\right).$$
Since \(y=4t\), we obtain the second family
$$x=\left|s^4-4r^4\right|,\qquad y=4rs,\qquad z=4\left(s^4+4r^4\right),$$
with \(s\) odd and \(\gcd(r,s)=1\). The absolute value simply accounts for which of \(u-x\) and \(u+x\) receives the factor \(8\).
The parametrizations are only useful if their parameter ranges are tight. The bound on \(z\) gives clean fourth-root limits.
For the first family,
$$z=\frac{p^4+q^4}{2}\le N.$$
Therefore \(q^4\le 2N\), so
$$q\le \left\lfloor(2N)^{1/4}\right\rfloor.$$
For each fixed odd \(q\), the remaining bound is
$$p^4\le 2N-q^4,\qquad p\lt q,$$
so the implementation chooses the largest admissible odd \(p\) from those two constraints.
For the second family,
$$z=4\left(s^4+4r^4\right)\le N.$$
This implies
$$s^4\le \frac N4,\qquad r^4\le \frac{N/4-s^4}{4}.$$
Hence
$$s\le \left\lfloor\left(\frac N4\right)^{1/4}\right\rfloor,\qquad r\le \left\lfloor\left(\frac{N/4-s^4}{4}\right)^{1/4}\right\rfloor.$$
So both branches are searched in fourth-root sized loops instead of scanning all \(x\) and \(y\).
The small checkpoint \(S(100)=81\) follows immediately from the two families.
In the first family, \(q\le \lfloor 200^{1/4}\rfloor=3\). The only admissible odd coprime pair with \(p\lt q\) is \((p,q)=(1,3)\), which gives
$$x=\frac{3^4-1^4}{8}=10,\qquad y=1\cdot3=3,\qquad z=\frac{1^4+3^4}{2}=41.$$
Its contribution is
$$10+3+41=54.$$
In the second family, \(s\le \lfloor 25^{1/4}\rfloor=2\), so the only odd choice is \(s=1\). Then \(r=1\) is the only admissible value, giving
$$x=\left|1^4-4\cdot1^4\right|=3,\qquad y=4\cdot1\cdot1=4,\qquad z=4(1+4)=20.$$
Its contribution is
$$3+4+20=27.$$
Therefore
$$S(100)=54+27=81,$$
which matches the small exact check used by the implementation.
If we denote the two admissible parameter sets by
$$\mathcal{A}_N=\left\{(p,q): p,q\text{ odd},\ 1\le p\lt q,\ \gcd(p,q)=1,\ \frac{p^4+q^4}{2}\le N\right\}$$
and
$$\mathcal{B}_N=\left\{(r,s): s\text{ odd},\ r\ge1,\ \gcd(r,s)=1,\ 4\left(s^4+4r^4\right)\le N\right\},$$
then the desired sum is
$$S(N)=\sum_{(p,q)\in\mathcal{A}_N}\left(\frac{q^4-p^4}{8}+pq+\frac{p^4+q^4}{2}\right)+\sum_{(r,s)\in\mathcal{B}_N}\left(\left|s^4-4r^4\right|+4rs+4\left(s^4+4r^4\right)\right).$$
The two sums are disjoint because the first family always has odd \(y\), while the second always has \(y\) divisible by \(4\).
The C++, Python, and Java implementations all follow the same structure. First they compute exact integer fourth roots. Each version starts from a floating-point estimate and then corrects it upward or downward with integer comparisons, so boundary cases remain exact.
Next, the first branch iterates over odd \(q\), derives the largest legal odd \(p\), filters by \(\gcd(p,q)=1\), and forms the triple from the odd-\(y\) parametrization. The second branch iterates over odd \(s\), derives the largest legal \(r\), filters by \(\gcd(r,s)=1\), and forms the triple from the even-\(y\) parametrization. In both branches the code still checks the generated coordinates against the problem bound before adding the contribution.
The final accumulation adds \(x+y+z\) modulo \(10^9\). One implementation also keeps small exact checkpoints and compares a tiny bound against direct enumeration, which confirms that the parametrized search matches brute force on test cases where brute force is still feasible.
The outer parameters \(q\) and \(s\) run only up to \(O(N^{1/4})\). For each outer value, the inner parameter range is also fourth-root sized, so the total number of candidate parameter pairs across both families is \(O(N^{1/2})\). Each candidate requires only a few arithmetic operations and one gcd computation, so the runtime is near \(O(N^{1/2})\) arithmetic steps, or \(O(N^{1/2}\log N)\) if gcd cost is counted explicitly. Memory usage is \(O(1)\).
Sei \(S(N)\) die Summe von \(x+y+z\) über alle primitiven positiven ganzzahligen Lösungen von
$$z^2=16x^2+y^4,$$
mit \(\gcd(x,y,z)=1\) und der Schranke \(z\le N\). Das Endergebnis wird modulo \(10^9\) verlangt. Eine direkte Suche über \(x\) und \(y\) ist viel zu teuer, daher muss man alle primitiven Lösungen durch wenige Parameter beschreiben und nur diese Parameter durchlaufen.
Die Implementierungen zerlegen die Gleichung in zwei Fälle, je nachdem ob \(y\) ungerade oder gerade ist. Jeder Fall führt zu einer vollständigen Parametrisierung, und die Suchgrenzen schrumpfen von einer Koordinatensuche auf Schleifen der Größenordnung vierter Wurzeln.
Man schreibt
$$(z-4x)(z+4x)=y^4.$$
Setze
$$a=z-4x,\qquad b=z+4x.$$
Dann gilt \(ab=y^4\), \(a\lt b\), und beide Faktoren haben dieselbe Parität. Die Bedingung der Primitivität schränkt ihren gemeinsamen Teiler stark ein. Genau hier verzweigt die Rechnung:
Ist \(y\) ungerade, dann sind \(a\) und \(b\) ungerade und sogar teilerfremd.
Ist \(y\) gerade, dann verteilt sich die Zweierpotenz in \(a\) und \(b\) asymmetrisch, was zu einer zweiten Familie führt.
Sei \(y\) ungerade. Dann ist \(y^4\) ungerade, also sind auch \(a\) und \(b\) ungerade. Jeder gemeinsame Teiler \(d\) von \(a\) und \(b\) teilt zugleich
$$b-a=8x,\qquad a+b=2z.$$
Weil \(d\) ungerade ist, teilt es sowohl \(x\) als auch \(z\). Da außerdem \(d\mid ab=y^4\) gilt, teilt \(d\) auch \(y\). Also teilt \(d\) den Wert \(\gcd(x,y,z)\), und wegen der Primitivität folgt \(d=1\).
Nun sind \(a\) und \(b\) teilerfremd und ihr Produkt ist eine vierte Potenz, also muss jeder Faktor selbst eine vierte Potenz sein. Schreibe
$$a=p^4,\qquad b=q^4,$$
wobei \(p\) und \(q\) positiv, ungerade, teilerfremd und \(p\lt q\) sind. Aus
$$z-4x=p^4,\qquad z+4x=q^4$$
folgt
$$x=\frac{q^4-p^4}{8},\qquad y=pq,\qquad z=\frac{p^4+q^4}{2}.$$
Genau diese Formeln verwendet der erste Zweig der Implementierung.
Sei nun \(y\) gerade. In einer primitiven Lösung kann \(x\) dann nicht gerade sein, denn sonst wäre auch \(z\) gerade und der ggT mindestens \(2\). Also ist \(x\) ungerade. Weil \(y^4\) durch \(16\) teilbar ist, zeigt die Gleichung, dass \(z\) durch \(4\) teilbar sein muss. Schreibe
$$z=4u,\qquad y=2w.$$
Dann gilt
$$u^2=x^2+w^4.$$
Wäre \(w\) ungerade, so ergäben \(x^2\equiv1\pmod{16}\) und \(w^4\equiv1\pmod{16}\) die unmögliche Kongruenz \(u^2\equiv2\pmod{16}\). Also ist \(w\) gerade, daher schreiben wir
$$y=4t,\qquad z=4u,$$
und erhalten
$$(u-x)(u+x)=16t^4.$$
Da \(u\) und \(x\) ungerade sind, sind beide Faktoren gerade. Ihre Differenz ist \(2x\), also genau durch \(2\), aber nicht durch \(4\), teilbar. Der gemeinsame Zweieranteil ist deshalb genau ein Faktor \(2\). Nach geeigneter Anordnung müssen die Faktoren die Form
$$u+x=2s^4,\qquad u-x=8r^4,$$
oder vertauscht haben. Hier sind \(r\) und \(s\) teilerfremd, und \(s\) ist ungerade. Durch Addieren und Subtrahieren folgt
$$x=\left|s^4-4r^4\right|,\qquad t=rs,\qquad z=4\left(s^4+4r^4\right).$$
Wegen \(y=4t\) entsteht also die zweite Familie
$$x=\left|s^4-4r^4\right|,\qquad y=4rs,\qquad z=4\left(s^4+4r^4\right),$$
mit \(s\) ungerade und \(\gcd(r,s)=1\). Der Betrag deckt lediglich die beiden möglichen Zuordnungen der Faktoren \(u-x\) und \(u+x\) ab.
Die Parametrisierungen sind nur dann praktisch, wenn man enge Schleifengrenzen daraus gewinnt. Die Schranke für \(z\) liefert genau solche Grenzen.
Für die erste Familie gilt
$$z=\frac{p^4+q^4}{2}\le N.$$
Daraus folgt \(q^4\le 2N\), also
$$q\le \left\lfloor(2N)^{1/4}\right\rfloor.$$
Für festes ungerades \(q\) bleibt
$$p^4\le 2N-q^4,\qquad p\lt q,$$
sodass die Implementierung den größten zulässigen ungeraden Wert von \(p\) aus beiden Bedingungen bestimmt.
Für die zweite Familie gilt
$$z=4\left(s^4+4r^4\right)\le N.$$
Daraus erhält man
$$s^4\le \frac N4,\qquad r^4\le \frac{N/4-s^4}{4}.$$
Also
$$s\le \left\lfloor\left(\frac N4\right)^{1/4}\right\rfloor,\qquad r\le \left\lfloor\left(\frac{N/4-s^4}{4}\right)^{1/4}\right\rfloor.$$
Beide Zweige arbeiten damit in Schleifen von vierter-Wurzel-Größe statt mit einer direkten Suche über \(x\) und \(y\).
Der kleine Kontrollwert \(S(100)=81\) folgt direkt aus den beiden Familien.
In der ersten Familie gilt \(q\le \lfloor 200^{1/4}\rfloor=3\). Das einzige zulässige ungerade teilerfremde Paar mit \(p\lt q\) ist \((p,q)=(1,3)\). Daraus folgt
$$x=\frac{3^4-1^4}{8}=10,\qquad y=1\cdot3=3,\qquad z=\frac{1^4+3^4}{2}=41.$$
Sein Beitrag ist
$$10+3+41=54.$$
In der zweiten Familie gilt \(s\le \lfloor 25^{1/4}\rfloor=2\), also ist nur \(s=1\) möglich. Dann ist \(r=1\) der einzige zulässige Wert, und man erhält
$$x=\left|1^4-4\cdot1^4\right|=3,\qquad y=4\cdot1\cdot1=4,\qquad z=4(1+4)=20.$$
Sein Beitrag ist
$$3+4+20=27.$$
Somit
$$S(100)=54+27=81,$$
genau der kleine exakte Prüfwert aus der Implementierung.
Bezeichnen wir die beiden zulässigen Parametermengen mit
$$\mathcal{A}_N=\left\{(p,q): p,q\text{ ungerade},\ 1\le p\lt q,\ \gcd(p,q)=1,\ \frac{p^4+q^4}{2}\le N\right\}$$
und
$$\mathcal{B}_N=\left\{(r,s): s\text{ ungerade},\ r\ge1,\ \gcd(r,s)=1,\ 4\left(s^4+4r^4\right)\le N\right\},$$
dann lautet die gesuchte Summe
$$S(N)=\sum_{(p,q)\in\mathcal{A}_N}\left(\frac{q^4-p^4}{8}+pq+\frac{p^4+q^4}{2}\right)+\sum_{(r,s)\in\mathcal{B}_N}\left(\left|s^4-4r^4\right|+4rs+4\left(s^4+4r^4\right)\right).$$
Die beiden Summen überschneiden sich nicht, weil die erste Familie immer ungerades \(y\) hat, die zweite dagegen stets \(y\), das durch \(4\) teilbar ist.
Die C++-, Python- und Java-Implementierungen haben alle dieselbe Struktur. Zuerst berechnen sie exakte ganzzahlige vierte Wurzeln. Jede Version startet mit einer Fließkomma-Näherung und korrigiert sie danach per ganzzahligem Vergleich nach oben oder unten, damit Randfälle exakt bleiben.
Danach iteriert der erste Zweig über ungerade \(q\), bestimmt den größten zulässigen ungeraden Wert von \(p\), filtert mit \(\gcd(p,q)=1\) und erzeugt das Tripel aus der Parametrisierung für ungerades \(y\). Der zweite Zweig iteriert über ungerade \(s\), bestimmt den größten zulässigen Wert von \(r\), filtert mit \(\gcd(r,s)=1\) und erzeugt das Tripel aus der Parametrisierung für gerades \(y\). In beiden Zweigen prüft der Code die erzeugten Koordinaten nochmals gegen die Problemschranke, bevor ihr Beitrag addiert wird.
Am Ende wird \(x+y+z\) modulo \(10^9\) aufsummiert. Eine Implementierung enthält zusätzlich kleine exakte Prüfwerte und vergleicht für eine sehr kleine Schranke mit einer direkten Enumeration; so wird bestätigt, dass die parametrisierte Suche auf kleinen Testfällen dieselben Ergebnisse wie Brute Force liefert.
Die äußeren Parameter \(q\) und \(s\) laufen nur bis \(O(N^{1/4})\). Für jeden äußeren Wert ist auch der innere Parameterbereich von vierter-Wurzel-Größe, sodass die Gesamtzahl der geprüften Parameterpaare über beide Familien hinweg \(O(N^{1/2})\) beträgt. Jeder Kandidat benötigt nur einige arithmetische Operationen und eine ggT-Berechnung. Damit liegt die Laufzeit nahe bei \(O(N^{1/2})\) arithmetischen Schritten beziehungsweise bei \(O(N^{1/2}\log N)\), wenn man die Kosten des ggT explizit mitzählt. Der Speicherbedarf ist \(O(1)\).
\(S(N)\),
$$z^2=16x^2+y^4$$
denklemine ait tüm ilkel pozitif tamsayı çözümlerinde \(x+y+z\) toplamını ifade etsin. Burada \(\gcd(x,y,z)=1\) ve problem sınırı \(z\le N\) koşulu vardır. Sonuç \(10^9\) modunda istenir. \(x\) ve \(y\) üzerinde doğrudan tarama yapmak çok pahalı olduğu için asıl amaç, bütün ilkel çözümleri az sayıda parametreyle üretip yalnızca bu parametreleri dolaşmaktır.
Uygulamalar denklemi \(y\)'nin tek veya çift olmasına göre iki ayrı duruma ayırır. Her durum eksiksiz bir parametrizasyon verir ve arama alanı koordinatlar üzerinden kaba kuvvet taraması yerine dördüncü kök ölçeğine iner.
Denklemi
$$(z-4x)(z+4x)=y^4$$
şeklinde yazalım. Şimdi
$$a=z-4x,\qquad b=z+4x$$
tanımlarını yapalım. Böylece \(ab=y^4\), \(a\lt b\) ve \(a\) ile \(b\) aynı paritededir. İlkel olma şartı, bu iki çarpanın ortak bölenini ciddi biçimde sınırlar. Kritik ayrım da burada oluşur:
\(y\) tekse \(a\) ve \(b\) hem tektir hem de aralarında asaldır.
\(y\) çiftse \(a\) ve \(b\) içindeki \(2\) kuvvetleri simetrik dağılmaz ve ikinci bir aile ortaya çıkar.
\(y\)'nin tek olduğunu varsayalım. O halde \(y^4\) de tektir; dolayısıyla \(a\) ve \(b\) de tektir. \(a\) ve \(b\)'nin herhangi bir ortak böleni \(d\), şu fark ve toplamı da böler:
$$b-a=8x,\qquad a+b=2z.$$
\(d\) tek olduğu için hem \(x\)'i hem de \(z\)'yi böler. Ayrıca \(d\mid ab=y^4\) olduğundan \(y\)'yi de böler. Böylece \(d\), \(\gcd(x,y,z)\)'yi böler; ilkel çözümde bunun tek mümkün değeri \(1\)'dir.
Artık \(a\) ve \(b\) aralarında asaldır ve çarpımları bir dördüncü kuvvettir. O halde her biri ayrı ayrı dördüncü kuvvet olmalıdır. Yazalım:
$$a=p^4,\qquad b=q^4,$$
burada \(p\) ve \(q\) pozitif, tek, aralarında asal ve \(p\lt q\) olur. Şu sistemi çözünce
$$z-4x=p^4,\qquad z+4x=q^4$$
elde edilir:
$$x=\frac{q^4-p^4}{8},\qquad y=pq,\qquad z=\frac{p^4+q^4}{2}.$$
Bu, uygulamanın kullandığı ilk üretim ailesidir.
Şimdi \(y\)'nin çift olduğunu varsayalım. İlkel bir çözümde \(x\) çift olamaz; aksi halde \(z\) de çift olur ve ortak bölen en az \(2\) olurdu. Demek ki \(x\) tektir. \(y^4\) sayısı \(16\)'ya bölündüğü için denklem \(z\)'nin de \(4\)'e bölündüğünü gösterir. Yazalım:
$$z=4u,\qquad y=2w.$$
O zaman
$$u^2=x^2+w^4$$
elde edilir. Eğer \(w\) tek olsaydı, \(x^2\equiv1\pmod{16}\) ve \(w^4\equiv1\pmod{16}\) olacağından \(u^2\equiv2\pmod{16}\) çıkardı; bu imkansızdır. Dolayısıyla \(w\) çifttir. Bu yüzden
$$y=4t,\qquad z=4u$$
yazıp
$$(u-x)(u+x)=16t^4$$
eşitliğine geçeriz. \(u\) ve \(x\) tek olduğundan her iki çarpan da çifttir. Aralarındaki fark \(2x\) olduğundan, ortak \(2\) kuvveti tam olarak tek bir \(2\) çarpanıdır. Bu yüzden uygun sıralamayla
$$u+x=2s^4,\qquad u-x=8r^4,$$
veya bunun tersi olmak zorundadır. Burada \(r\) ve \(s\) aralarında asaldır ve \(s\) tektir. Toplayıp çıkarınca
$$x=\left|s^4-4r^4\right|,\qquad t=rs,\qquad z=4\left(s^4+4r^4\right)$$
bulunur. \(y=4t\) olduğu için ikinci aile
$$x=\left|s^4-4r^4\right|,\qquad y=4rs,\qquad z=4\left(s^4+4r^4\right)$$
şeklini alır; burada \(s\) tek ve \(\gcd(r,s)=1\) şartları vardır. Mutlak değer, \(8\) katsayısının hangi çarpana gittiğine göre iki olası sırayı tek formülde toplar.
Parametrizasyonların işe yaraması için döngü sınırlarının sıkı olması gerekir. \(z\) üzerindeki sınır bunu doğrudan sağlar.
Birinci ailede
$$z=\frac{p^4+q^4}{2}\le N$$
olduğundan \(q^4\le 2N\) ve dolayısıyla
$$q\le \left\lfloor(2N)^{1/4}\right\rfloor$$
elde edilir. Sabit tek bir \(q\) için geriye
$$p^4\le 2N-q^4,\qquad p\lt q$$
koşulları kalır; uygulama bu iki koşuldan gelen en büyük uygun tek \(p\) değerini seçer.
İkinci ailede ise
$$z=4\left(s^4+4r^4\right)\le N$$
eşitsizliği
$$s^4\le \frac N4,\qquad r^4\le \frac{N/4-s^4}{4}$$
sonucunu verir. Buradan
$$s\le \left\lfloor\left(\frac N4\right)^{1/4}\right\rfloor,\qquad r\le \left\lfloor\left(\frac{N/4-s^4}{4}\right)^{1/4}\right\rfloor$$
çıkar. Böylece her iki kol da koordinat düzleminde dolaşmak yerine dördüncü kök büyüklüğünde aralıklarda çalışır.
Küçük kontrol değeri \(S(100)=81\), iki aileden hemen çıkar.
Birinci ailede \(q\le \lfloor 200^{1/4}\rfloor=3\). \(p\lt q\) koşuluyla uygun tek ve aralarında asal tek çift sadece \((p,q)=(1,3)\)'tür. Bu da
$$x=\frac{3^4-1^4}{8}=10,\qquad y=1\cdot3=3,\qquad z=\frac{1^4+3^4}{2}=41$$
üçlüsünü verir. Katkısı
$$10+3+41=54$$
olur.
İkinci ailede \(s\le \lfloor 25^{1/4}\rfloor=2\) olduğundan tek seçenek \(s=1\)'dir. O zaman uygun tek değer \(r=1\) olur ve
$$x=\left|1^4-4\cdot1^4\right|=3,\qquad y=4\cdot1\cdot1=4,\qquad z=4(1+4)=20$$
elde edilir. Bunun katkısı da
$$3+4+20=27$$
olur. Dolayısıyla
$$S(100)=54+27=81,$$
ki bu da uygulamanın küçük tam kontrolüyle aynıdır.
İki geçerli parametre kümesini
$$\mathcal{A}_N=\left\{(p,q): p,q\text{ tek},\ 1\le p\lt q,\ \gcd(p,q)=1,\ \frac{p^4+q^4}{2}\le N\right\}$$
ve
$$\mathcal{B}_N=\left\{(r,s): s\text{ tek},\ r\ge1,\ \gcd(r,s)=1,\ 4\left(s^4+4r^4\right)\le N\right\}$$
olarak tanımlarsak aranan toplam
$$S(N)=\sum_{(p,q)\in\mathcal{A}_N}\left(\frac{q^4-p^4}{8}+pq+\frac{p^4+q^4}{2}\right)+\sum_{(r,s)\in\mathcal{B}_N}\left(\left|s^4-4r^4\right|+4rs+4\left(s^4+4r^4\right)\right)$$
şeklindedir. İki toplam çakışmaz; çünkü ilk ailede \(y\) daima tektir, ikinci ailede ise \(y\) her zaman \(4\)'ün katıdır.
C++, Python ve Java uygulamalarının yapısı aynıdır. Önce tam sayı dördüncü kökleri güvenli biçimde hesaplanır. Her sürüm, kayan noktalı bir ilk tahmin alır ve sonra tam sayı karşılaştırmalarıyla bu tahmini yukarı veya aşağı düzelterek sınır noktalarında hatayı ortadan kaldırır.
Ardından ilk kol tek \(q\) değerleri üzerinde dolaşır, en büyük uygun tek \(p\) değerini çıkarır, \(\gcd(p,q)=1\) filtresini uygular ve tek-\(y\) parametrizasyonundan üçlüyü üretir. İkinci kol tek \(s\) değerleri üzerinde dolaşır, en büyük uygun \(r\) değerini hesaplar, \(\gcd(r,s)=1\) filtresini uygular ve çift-\(y\) parametrizasyonundan üçlüyü üretir. Her iki kolda da üretilen koordinatlar toplama eklenmeden önce problem sınırına göre yeniden doğrulanır.
Son aşamada \(x+y+z\) toplamı \(10^9\) modunda biriktirilir. Uygulamalardan biri ayrıca küçük tam kontrol değerleri tutar ve çok küçük bir sınır için parametrik yöntemi doğrudan taramayla karşılaştırır; böylece parametrizasyonun kaba kuvvetle aynı çözümleri verdiği doğrulanır.
Dış döngülerdeki \(q\) ve \(s\) parametreleri yalnızca \(O(N^{1/4})\) seviyesine kadar gider. Her dış değer için iç parametre aralığı da dördüncü kök ölçeğindedir; dolayısıyla iki ailenin toplam aday parametre çifti sayısı \(O(N^{1/2})\) olur. Her aday için sadece birkaç aritmetik işlem ve bir gcd hesabı yapılır. Bu nedenle çalışma süresi aritmetik adım sayısı bakımından \(O(N^{1/2})\)'ye yakındır; gcd maliyetini açık sayarsak \(O(N^{1/2}\log N)\) denebilir. Bellek kullanımı \(O(1)\)'dir.
Sea \(S(N)\) la suma de \(x+y+z\) sobre todas las soluciones enteras positivas primitivas de
$$z^2=16x^2+y^4,$$
con \(\gcd(x,y,z)=1\) y la cota \(z\le N\). El resultado final se pide módulo \(10^9\). Un barrido directo sobre \(x\) e \(y\) es demasiado costoso, así que la idea central es describir todas las soluciones primitivas mediante unos pocos parámetros y recorrer solo esos parámetros.
Las implementaciones separan la ecuación en dos casos según la paridad de \(y\). Cada caso produce una parametrización completa, y el espacio de búsqueda baja desde un recorrido por coordenadas hasta bucles del orden de la cuarta raíz.
Reescribimos
$$(z-4x)(z+4x)=y^4.$$
Definimos
$$a=z-4x,\qquad b=z+4x.$$
Entonces \(ab=y^4\), \(a\lt b\), y ambos factores tienen la misma paridad. La condición de primitividad restringe con fuerza su divisor común. Ahí aparece la bifurcación clave:
Si \(y\) es impar, \(a\) y \(b\) son impares y además coprimos.
Si \(y\) es par, la potencia de \(2\) no se reparte de forma simétrica entre \(a\) y \(b\), y surge una segunda familia.
Supongamos que \(y\) es impar. Entonces \(y^4\) también es impar, de modo que \(a\) y \(b\) son impares. Cualquier divisor común \(d\) de \(a\) y \(b\) divide también
$$b-a=8x,\qquad a+b=2z.$$
Como \(d\) es impar, debe dividir a \(x\) y a \(z\). Además, de \(d\mid ab=y^4\) se deduce que divide a \(y\). Por tanto \(d\mid \gcd(x,y,z)\), y la primitividad obliga a que \(d=1\).
Ahora \(a\) y \(b\) son coprimos y su producto es una cuarta potencia, así que cada uno debe ser una cuarta potencia. Escribimos
$$a=p^4,\qquad b=q^4,$$
con \(p\) y \(q\) positivos, impares, coprimos y \(p\lt q\). Al resolver
$$z-4x=p^4,\qquad z+4x=q^4$$
obtenemos
$$x=\frac{q^4-p^4}{8},\qquad y=pq,\qquad z=\frac{p^4+q^4}{2}.$$
Estas son exactamente las fórmulas de la primera rama de la implementación.
Supongamos ahora que \(y\) es par. En una solución primitiva, \(x\) no puede ser par, porque entonces \(z\) también lo sería y el gcd sería al menos \(2\). Así que \(x\) es impar. Como \(y^4\) es múltiplo de \(16\), la ecuación implica que \(z\) es múltiplo de \(4\). Escribimos
$$z=4u,\qquad y=2w.$$
Entonces
$$u^2=x^2+w^4.$$
Si \(w\) fuera impar, tendríamos \(x^2\equiv1\pmod{16}\) y \(w^4\equiv1\pmod{16}\), lo cual forzaría \(u^2\equiv2\pmod{16}\), imposible. Por tanto \(w\) es par, y podemos escribir
$$y=4t,\qquad z=4u,$$
de modo que
$$(u-x)(u+x)=16t^4.$$
Como \(u\) y \(x\) son impares, ambos factores son pares. Su diferencia es \(2x\), divisible por \(2\) pero no por \(4\), así que la potencia común de \(2\) es exactamente una sola. Tras ordenar los factores, deben tener la forma
$$u+x=2s^4,\qquad u-x=8r^4,$$
o bien la forma intercambiada. Aquí \(r\) y \(s\) son coprimos y \(s\) es impar. Sumando y restando se obtiene
$$x=\left|s^4-4r^4\right|,\qquad t=rs,\qquad z=4\left(s^4+4r^4\right).$$
Como \(y=4t\), la segunda familia queda
$$x=\left|s^4-4r^4\right|,\qquad y=4rs,\qquad z=4\left(s^4+4r^4\right),$$
con \(s\) impar y \(\gcd(r,s)=1\). El valor absoluto solo recoge las dos posibles asignaciones del factor \(8\) entre \(u-x\) y \(u+x\).
Las parametrizaciones solo son útiles si producen límites de iteración estrechos. La cota sobre \(z\) los da de forma natural.
En la primera familia,
$$z=\frac{p^4+q^4}{2}\le N.$$
Por tanto \(q^4\le 2N\), y así
$$q\le \left\lfloor(2N)^{1/4}\right\rfloor.$$
Para cada \(q\) impar fijo, queda
$$p^4\le 2N-q^4,\qquad p\lt q,$$
de modo que la implementación toma el mayor \(p\) impar que satisface ambas condiciones.
En la segunda familia,
$$z=4\left(s^4+4r^4\right)\le N,$$
lo que implica
$$s^4\le \frac N4,\qquad r^4\le \frac{N/4-s^4}{4}.$$
Luego
$$s\le \left\lfloor\left(\frac N4\right)^{1/4}\right\rfloor,\qquad r\le \left\lfloor\left(\frac{N/4-s^4}{4}\right)^{1/4}\right\rfloor.$$
Así, ambas ramas se recorren con bucles de tamaño cuarta raíz en lugar de escanear directamente todas las coordenadas.
El punto de control pequeño \(S(100)=81\) sale inmediatamente de las dos familias.
En la primera familia, \(q\le \lfloor 200^{1/4}\rfloor=3\). El único par impar coprimo con \(p\lt q\) es \((p,q)=(1,3)\), que produce
$$x=\frac{3^4-1^4}{8}=10,\qquad y=1\cdot3=3,\qquad z=\frac{1^4+3^4}{2}=41.$$
Su contribución es
$$10+3+41=54.$$
En la segunda familia, \(s\le \lfloor 25^{1/4}\rfloor=2\), así que la única opción impar es \(s=1\). Entonces \(r=1\) es el único valor admisible, y obtenemos
$$x=\left|1^4-4\cdot1^4\right|=3,\qquad y=4\cdot1\cdot1=4,\qquad z=4(1+4)=20.$$
Su contribución es
$$3+4+20=27.$$
Por lo tanto,
$$S(100)=54+27=81,$$
que coincide con la comprobación exacta pequeña de la implementación.
Si llamamos
$$\mathcal{A}_N=\left\{(p,q): p,q\text{ impares},\ 1\le p\lt q,\ \gcd(p,q)=1,\ \frac{p^4+q^4}{2}\le N\right\}$$
y
$$\mathcal{B}_N=\left\{(r,s): s\text{ impar},\ r\ge1,\ \gcd(r,s)=1,\ 4\left(s^4+4r^4\right)\le N\right\},$$
entonces la suma buscada es
$$S(N)=\sum_{(p,q)\in\mathcal{A}_N}\left(\frac{q^4-p^4}{8}+pq+\frac{p^4+q^4}{2}\right)+\sum_{(r,s)\in\mathcal{B}_N}\left(\left|s^4-4r^4\right|+4rs+4\left(s^4+4r^4\right)\right).$$
Las dos sumas no se solapan porque la primera familia siempre tiene \(y\) impar, mientras que la segunda siempre produce \(y\) múltiplo de \(4\).
Las implementaciones en C++, Python y Java siguen exactamente la misma estructura. Primero calculan raíces cuartas enteras exactas. Cada versión parte de una estimación en coma flotante y luego la corrige hacia arriba o hacia abajo con comparaciones enteras, para que los casos de borde sean exactos.
Después, la primera rama recorre valores impares de \(q\), calcula el mayor \(p\) impar permitido, filtra con \(\gcd(p,q)=1\) y construye el triple usando la parametrización del caso impar. La segunda rama recorre valores impares de \(s\), calcula el mayor \(r\) admisible, filtra con \(\gcd(r,s)=1\) y construye el triple usando la parametrización del caso par. En ambas ramas, el código vuelve a comprobar las coordenadas generadas frente a la cota del problema antes de sumar la contribución.
La acumulación final suma \(x+y+z\) módulo \(10^9\). Una de las implementaciones también incluye verificaciones exactas pequeñas y compara un límite diminuto con enumeración directa, confirmando que la búsqueda parametrizada coincide con la fuerza bruta cuando esta aún es viable.
Los parámetros externos \(q\) y \(s\) solo llegan hasta \(O(N^{1/4})\). Para cada valor externo, el rango interno también tiene tamaño de cuarta raíz, así que el número total de pares candidatos a través de las dos familias es \(O(N^{1/2})\). Cada candidato requiere unas pocas operaciones aritméticas y un cálculo de gcd, por lo que el tiempo de ejecución está cerca de \(O(N^{1/2})\) en pasos aritméticos, o de \(O(N^{1/2}\log N)\) si se cuenta explícitamente el costo del gcd. La memoria usada es \(O(1)\).
设 \(S(N)\) 表示方程
$$z^2=16x^2+y^4$$
的所有原始正整数解上 \(x+y+z\) 的总和，其中 \(\gcd(x,y,z)=1\)，并满足题目的规模约束 \(z\le N\)。最终答案要求对 \(10^9\) 取模。若直接枚举 \(x\) 与 \(y\)，搜索空间会非常大，因此真正的关键是把所有原始解写成少量参数的形式，然后只枚举这些参数。
实现采用按 \(y\) 的奇偶性分类的方法。奇数情形和偶数情形分别给出完整参数化，于是搜索不再是坐标平面上的暴力扫描，而变成四次根量级的循环。
把原方程改写为
$$(z-4x)(z+4x)=y^4.$$
记
$$a=z-4x,\qquad b=z+4x.$$
于是有 \(ab=y^4\)，并且 \(a\lt b\)，同时 \(a,b\) 具有相同奇偶性。原始性条件会强烈限制这两个因子的公因数，而这正是分支出现的地方：
若 \(y\) 为奇数，则 \(a,b\) 都是奇数，而且实际上互素。
若 \(y\) 为偶数，则 \(a,b\) 中的 \(2\) 进赋值不再对称，从而产生第二组参数化。
先设 \(y\) 为奇数。此时 \(y^4\) 也是奇数，所以 \(a,b\) 都是奇数。若 \(d\) 同时整除 \(a\) 和 \(b\)，那么它也整除
$$b-a=8x,\qquad a+b=2z.$$
由于 \(d\) 是奇数，它必须同时整除 \(x\) 和 \(z\)。另一方面，\(d\mid ab=y^4\) 说明 \(d\) 也整除 \(y\)。因此 \(d\mid \gcd(x,y,z)\)，而原始性要求 \(\gcd(x,y,z)=1\)，所以只能有 \(d=1\)。
现在 \(a\) 与 \(b\) 互素，且乘积是四次幂，因此每个因子本身都必须是四次幂。写成
$$a=p^4,\qquad b=q^4,$$
其中 \(p,q\) 为正奇数，\(\gcd(p,q)=1\)，并且 \(p\lt q\)。解方程组
$$z-4x=p^4,\qquad z+4x=q^4$$
便得到
$$x=\frac{q^4-p^4}{8},\qquad y=pq,\qquad z=\frac{p^4+q^4}{2}.$$
这正是实现中第一条分支所使用的公式。
现在设 \(y\) 为偶数。在原始解中，\(x\) 不可能也是偶数，否则由原方程可知 \(z\) 也会是偶数，从而三者公因数至少为 \(2\)。所以 \(x\) 必为奇数。因为 \(y^4\) 可被 \(16\) 整除，原方程说明 \(z\) 必可被 \(4\) 整除。于是写作
$$z=4u,\qquad y=2w.$$
代入后有
$$u^2=x^2+w^4.$$
如果 \(w\) 是奇数，那么 \(x^2\equiv1\pmod{16}\) 且 \(w^4\equiv1\pmod{16}\)，从而会推出 \(u^2\equiv2\pmod{16}\)，这是不可能的。所以 \(w\) 必为偶数，于是可以进一步写成
$$y=4t,\qquad z=4u,$$
此时方程化为
$$(u-x)(u+x)=16t^4.$$
由于 \(u\) 与 \(x\) 都是奇数，两个因子都为偶数。它们的差是 \(2x\)，只含有一个 \(2\) 的因子，因此两者公共的 \(2\) 进部分恰好只有一个 \(2\)。把大小顺序整理好以后，只能写成
$$u+x=2s^4,\qquad u-x=8r^4,$$
或者把两式交换。这里 \(r,s\) 互素，而且 \(s\) 必须是奇数。把两式相加相减可得
$$x=\left|s^4-4r^4\right|,\qquad t=rs,\qquad z=4\left(s^4+4r^4\right).$$
再由 \(y=4t\)，得到第二族参数化
$$x=\left|s^4-4r^4\right|,\qquad y=4rs,\qquad z=4\left(s^4+4r^4\right),$$
其中 \(s\) 为奇数，且 \(\gcd(r,s)=1\)。绝对值只是把 \(8\) 这个因子究竟落在 \(u-x\) 还是 \(u+x\) 上的两种情况统一写进一个公式。
参数化只有在枚举范围足够紧时才真正有效。这里 \(z\le N\) 正好给出非常干净的四次根界。
对第一族，
$$z=\frac{p^4+q^4}{2}\le N.$$
因此 \(q^4\le 2N\)，于是
$$q\le \left\lfloor(2N)^{1/4}\right\rfloor.$$
在固定某个奇数 \(q\) 以后，剩下的条件是
$$p^4\le 2N-q^4,\qquad p\lt q,$$
所以实现会从这两个条件中取出允许的最大奇数 \(p\)。
对第二族，
$$z=4\left(s^4+4r^4\right)\le N,$$
于是有
$$s^4\le \frac N4,\qquad r^4\le \frac{N/4-s^4}{4}.$$
也就是
$$s\le \left\lfloor\left(\frac N4\right)^{1/4}\right\rfloor,\qquad r\le \left\lfloor\left(\frac{N/4-s^4}{4}\right)^{1/4}\right\rfloor.$$
这样，两条分支都只需要四次根量级的循环，而不必直接扫描所有可能的坐标。
小规模校验值 \(S(100)=81\) 可以直接由两族参数化算出。
在第一族中，\(q\le \lfloor 200^{1/4}\rfloor=3\)。满足 \(p\lt q\) 且互素的奇数对只有 \((p,q)=(1,3)\)，从而得到
$$x=\frac{3^4-1^4}{8}=10,\qquad y=1\cdot3=3,\qquad z=\frac{1^4+3^4}{2}=41.$$
它的贡献为
$$10+3+41=54.$$
在第二族中，\(s\le \lfloor 25^{1/4}\rfloor=2\)，因此唯一的奇数选择是 \(s=1\)。这时唯一允许的 \(r\) 是 \(1\)，于是得到
$$x=\left|1^4-4\cdot1^4\right|=3,\qquad y=4\cdot1\cdot1=4,\qquad z=4(1+4)=20.$$
它的贡献为
$$3+4+20=27.$$
因此
$$S(100)=54+27=81,$$
这与实现中的小范围精确校验完全一致。
如果把两组可行参数分别记为
$$\mathcal{A}_N=\left\{(p,q): p,q\text{ 为奇数},\ 1\le p\lt q,\ \gcd(p,q)=1,\ \frac{p^4+q^4}{2}\le N\right\}$$
和
$$\mathcal{B}_N=\left\{(r,s): s\text{ 为奇数},\ r\ge1,\ \gcd(r,s)=1,\ 4\left(s^4+4r^4\right)\le N\right\},$$
那么目标和就是
$$S(N)=\sum_{(p,q)\in\mathcal{A}_N}\left(\frac{q^4-p^4}{8}+pq+\frac{p^4+q^4}{2}\right)+\sum_{(r,s)\in\mathcal{B}_N}\left(\left|s^4-4r^4\right|+4rs+4\left(s^4+4r^4\right)\right).$$
两部分没有重叠，因为第一族的 \(y\) 永远是奇数，而第二族的 \(y\) 永远是 \(4\) 的倍数。
C++、Python 和 Java 实现都遵循同样的流程。第一步是计算精确的整数四次根。每个版本都先用浮点数给出一个初始近似，再通过整数比较向上或向下修正，因此边界值不会出错。
然后第一条分支枚举奇数 \(q\)，计算允许的最大奇数 \(p\)，用 \(\gcd(p,q)=1\) 过滤，并按奇数情形的参数化公式构造三元组。第二条分支枚举奇数 \(s\)，计算允许的最大 \(r\)，用 \(\gcd(r,s)=1\) 过滤，并按偶数情形的参数化公式构造三元组。两条分支都会在累加之前再次检查生成出的坐标是否满足题目约束。
最后把每个合法三元组的 \(x+y+z\) 按 \(10^9\) 取模累加。其中一个实现还保留了小规模的精确检查，并把极小范围的结果与直接枚举进行对照，用来验证参数化搜索与暴力方法一致。
外层参数 \(q\) 与 \(s\) 只需要枚举到 \(O(N^{1/4})\)。对于每个外层值，内层参数范围也是四次根量级，因此两族参数化合起来的候选参数对总数为 \(O(N^{1/2})\)。每个候选只需常数次算术运算和一次 gcd 计算，所以运行时间可以看作接近 \(O(N^{1/2})\) 的算术步骤；如果把 gcd 成本单独计入，则可写成 \(O(N^{1/2}\log N)\)。额外空间复杂度为 \(O(1)\)。
Пусть \(S(N)\) обозначает сумму \(x+y+z\) по всем примитивным положительным целочисленным решениям уравнения
$$z^2=16x^2+y^4,$$
где \(\gcd(x,y,z)=1\) и выполняется ограничение \(z\le N\). Окончательный ответ нужен по модулю \(10^9\). Полный перебор по \(x\) и \(y\) слишком дорог, поэтому нужно описать все примитивные решения через небольшое число параметров и перебирать уже только эти параметры.
Реализации разбивают задачу на два случая по четности \(y\). В каждом случае получается полная параметризация, а диапазон перебора уменьшается до масштабов четвертого корня вместо прямого просмотра координат.
Перепишем уравнение в виде
$$(z-4x)(z+4x)=y^4.$$
Обозначим
$$a=z-4x,\qquad b=z+4x.$$
Тогда \(ab=y^4\), \(a\lt b\), и оба множителя имеют одинаковую четность. Условие примитивности сильно ограничивает их общий делитель. Именно здесь и возникает разветвление:
Если \(y\) нечетно, то \(a\) и \(b\) нечетны и, более того, взаимно просты.
Если \(y\) четно, то степень двойки распределяется между \(a\) и \(b\) несимметрично, и возникает второе семейство.
Пусть \(y\) нечетно. Тогда и \(y^4\) нечетно, значит \(a\) и \(b\) тоже нечетны. Любой общий делитель \(d\) чисел \(a\) и \(b\) делит также
$$b-a=8x,\qquad a+b=2z.$$
Поскольку \(d\) нечетен, он делит и \(x\), и \(z\). Кроме того, из \(d\mid ab=y^4\) следует, что \(d\) делит \(y\). Значит, \(d\mid \gcd(x,y,z)\), а примитивность дает \(d=1\).
Итак, \(a\) и \(b\) взаимно просты, а их произведение является четвертой степенью, следовательно, каждый множитель сам обязан быть четвертой степенью. Пишем
$$a=p^4,\qquad b=q^4,$$
где \(p\) и \(q\) положительны, нечетны, взаимно просты и \(p\lt q\). Решая систему
$$z-4x=p^4,\qquad z+4x=q^4,$$
получаем
$$x=\frac{q^4-p^4}{8},\qquad y=pq,\qquad z=\frac{p^4+q^4}{2}.$$
Именно эта формула используется в первой ветви реализации.
Теперь пусть \(y\) четно. В примитивном решении \(x\) не может быть четным, иначе и \(z\) было бы четным, а общий делитель был бы не меньше \(2\). Значит, \(x\) нечетно. Так как \(y^4\) делится на \(16\), исходное уравнение показывает, что \(z\) делится на \(4\). Запишем
$$z=4u,\qquad y=2w.$$
Тогда
$$u^2=x^2+w^4.$$
Если бы \(w\) было нечетным, то из сравнений \(x^2\equiv1\pmod{16}\) и \(w^4\equiv1\pmod{16}\) следовало бы невозможное \(u^2\equiv2\pmod{16}\). Поэтому \(w\) обязательно четно, и можно написать
$$y=4t,\qquad z=4u,$$
после чего получаем
$$(u-x)(u+x)=16t^4.$$
Так как \(u\) и \(x\) нечетны, оба множителя четны. Их разность равна \(2x\), то есть делится на \(2\), но не на \(4\), поэтому общая двойка у них ровно одна. После упорядочивания множители обязаны иметь вид
$$u+x=2s^4,\qquad u-x=8r^4,$$
или наоборот. Здесь \(r\) и \(s\) взаимно просты, а \(s\) должно быть нечетным. Складывая и вычитая, получаем
$$x=\left|s^4-4r^4\right|,\qquad t=rs,\qquad z=4\left(s^4+4r^4\right).$$
Так как \(y=4t\), получаем второе семейство
$$x=\left|s^4-4r^4\right|,\qquad y=4rs,\qquad z=4\left(s^4+4r^4\right),$$
где \(s\) нечетно и \(\gcd(r,s)=1\). Модуль нужен лишь для того, чтобы одной формулой охватить оба возможных распределения коэффициента \(8\) между \(u-x\) и \(u+x\).
Параметризации полезны только тогда, когда из них получаются узкие границы перебора. Ограничение \(z\le N\) как раз дает такие границы.
Для первого семейства
$$z=\frac{p^4+q^4}{2}\le N.$$
Отсюда \(q^4\le 2N\), значит
$$q\le \left\lfloor(2N)^{1/4}\right\rfloor.$$
Для фиксированного нечетного \(q\) остаются условия
$$p^4\le 2N-q^4,\qquad p\lt q,$$
поэтому реализация выбирает наибольшее допустимое нечетное \(p\), удовлетворяющее обоим ограничениям.
Для второго семейства
$$z=4\left(s^4+4r^4\right)\le N,$$
то есть
$$s^4\le \frac N4,\qquad r^4\le \frac{N/4-s^4}{4}.$$
Следовательно,
$$s\le \left\lfloor\left(\frac N4\right)^{1/4}\right\rfloor,\qquad r\le \left\lfloor\left(\frac{N/4-s^4}{4}\right)^{1/4}\right\rfloor.$$
Таким образом, обе ветви просматриваются в диапазонах порядка четвертого корня, а не через полный перебор координат.
Малый контрольный результат \(S(100)=81\) напрямую получается из двух семейств.
В первом семействе \(q\le \lfloor 200^{1/4}\rfloor=3\). Единственная допустимая нечетная взаимно простая пара с \(p\lt q\) это \((p,q)=(1,3)\). Она дает
$$x=\frac{3^4-1^4}{8}=10,\qquad y=1\cdot3=3,\qquad z=\frac{1^4+3^4}{2}=41.$$
Ее вклад равен
$$10+3+41=54.$$
Во втором семействе \(s\le \lfloor 25^{1/4}\rfloor=2\), поэтому единственный нечетный выбор это \(s=1\). Тогда единственное допустимое значение \(r\) равно \(1\), и получается
$$x=\left|1^4-4\cdot1^4\right|=3,\qquad y=4\cdot1\cdot1=4,\qquad z=4(1+4)=20.$$
Его вклад равен
$$3+4+20=27.$$
Следовательно,
$$S(100)=54+27=81,$$
что совпадает с малой точной проверкой в реализации.
Если обозначить множества допустимых параметров через
$$\mathcal{A}_N=\left\{(p,q): p,q\text{ нечетны},\ 1\le p\lt q,\ \gcd(p,q)=1,\ \frac{p^4+q^4}{2}\le N\right\}$$
и
$$\mathcal{B}_N=\left\{(r,s): s\text{ нечетно},\ r\ge1,\ \gcd(r,s)=1,\ 4\left(s^4+4r^4\right)\le N\right\},$$
то искомая сумма равна
$$S(N)=\sum_{(p,q)\in\mathcal{A}_N}\left(\frac{q^4-p^4}{8}+pq+\frac{p^4+q^4}{2}\right)+\sum_{(r,s)\in\mathcal{B}_N}\left(\left|s^4-4r^4\right|+4rs+4\left(s^4+4r^4\right)\right).$$
Эти две суммы не пересекаются, потому что в первом семействе \(y\) всегда нечетно, а во втором всегда делится на \(4\).
Реализации на C++, Python и Java устроены одинаково. Сначала они вычисляют точные целочисленные четвертые корни. В каждой версии берется начальная оценка с плавающей точкой, а затем она корректируется вверх или вниз целочисленными сравнениями, чтобы границы были точными.
После этого первая ветвь перебирает нечетные значения \(q\), находит максимально допустимое нечетное \(p\), фильтрует пары по условию \(\gcd(p,q)=1\) и строит тройку по параметризации для нечетного случая. Вторая ветвь перебирает нечетные значения \(s\), находит максимально допустимое \(r\), фильтрует по \(\gcd(r,s)=1\) и строит тройку по параметризации для четного случая. В обеих ветвях перед добавлением вклада код еще раз проверяет, что сгенерированные координаты лежат в допустимой области.
Финальное накопление суммирует \(x+y+z\) по модулю \(10^9\). В одной из реализаций есть и малые точные проверки, включая сравнение с прямым перебором на очень маленькой границе, что подтверждает совпадение параметризованного метода с brute force там, где brute force еще возможен.
Внешние параметры \(q\) и \(s\) перебираются только до \(O(N^{1/4})\). Для каждого внешнего значения внутренний диапазон тоже имеет размер порядка четвертого корня, поэтому суммарное число кандидатных пар параметров по двум семействам равно \(O(N^{1/2})\). На каждый кандидат приходится лишь несколько арифметических действий и одно вычисление gcd, так что время работы близко к \(O(N^{1/2})\) арифметических шагов, либо \(O(N^{1/2}\log N)\), если явно учитывать стоимость gcd. Память равна \(O(1)\).
لتكن \(S(N)\) هي مجموع \(x+y+z\) على جميع الحلول الصحيحة الموجبة الأولية للمعادلة
$$z^2=16x^2+y^4,$$
مع الشرط \(\gcd(x,y,z)=1\) ومع القيد \(z\le N\). والمطلوب في النهاية هو الناتج بترديد \(10^9\). المسح المباشر على \(x\) و\(y\) مكلف جدًا، لذلك الفكرة الأساسية هي وصف كل الحلول الأولية بعدد صغير من المعلمات ثم تعداد هذه المعلمات فقط.
تعتمد التطبيقات على تقسيم المسألة بحسب فردية أو زوجية \(y\). كل حالة تعطي بارامتريّة كاملة، وبذلك ينخفض مجال البحث من تعداد مباشر للإحداثيات إلى حلقات بحجم من رتبة الجذر الرابع.
نكتب المعادلة على الصورة
$$(z-4x)(z+4x)=y^4.$$
ولنعرّف
$$a=z-4x,\qquad b=z+4x.$$
عندئذٍ \(ab=y^4\) و\(a\lt b\)، كما أن \(a\) و\(b\) لهما نفس الزوجية. شرط الأولية يفرض قيودًا قوية على القاسم المشترك لهذين العاملين، وهنا بالضبط يظهر التشعب:
إذا كانت \(y\) فردية فإن \(a\) و\(b\) فرديان، بل ومتحابان أوليًا.
أما إذا كانت \(y\) زوجية فإن أسّ \(2\) لا يتوزع بين \(a\) و\(b\) بشكل متماثل، ومن هنا تنشأ العائلة الثانية.
افترض أن \(y\) فردية. عندها يكون \(y^4\) فرديًا أيضًا، وبالتالي يكون \(a\) و\(b\) فرديين. إذا كان \(d\) قاسمًا مشتركًا لـ \(a\) و\(b\)، فهو يقسم أيضًا
$$b-a=8x,\qquad a+b=2z.$$
وبما أن \(d\) فردي، فلا بد أن يقسم \(x\) و\(z\). ومن جهة أخرى، لأن \(d\mid ab=y^4\)، فهو يقسم \(y\) أيضًا. إذن \(d\mid \gcd(x,y,z)\)، لكن أولية الحل تفرض أن يكون هذا القاسم \(1\) فقط.
أصبح لدينا الآن عاملان متحابان أوليًا وحاصلهما قوة رابعة، ولذلك يجب أن يكون كل واحد منهما قوة رابعة بحد ذاته. نكتب
$$a=p^4,\qquad b=q^4,$$
حيث \(p\) و\(q\) موجبان وفرديان ومتحابان أوليًا و\(p\lt q\). بحل النظام
$$z-4x=p^4,\qquad z+4x=q^4$$
نحصل على
$$x=\frac{q^4-p^4}{8},\qquad y=pq,\qquad z=\frac{p^4+q^4}{2}.$$
وهذه هي الصيغة نفسها التي يستخدمها الفرع الأول في التنفيذ.
الآن افترض أن \(y\) زوجية. في حل أولي لا يمكن أن يكون \(x\) زوجيًا، لأنه عندئذٍ سيكون \(z\) زوجيًا أيضًا ويصبح القاسم المشترك على الأقل \(2\). إذن \(x\) فردي. وبما أن \(y^4\) من مضاعفات \(16\)، فإن المعادلة تُظهر أن \(z\) من مضاعفات \(4\). نكتب
$$z=4u,\qquad y=2w.$$
فتصبح
$$u^2=x^2+w^4.$$
ولو كان \(w\) فرديًا لكان \(x^2\equiv1\pmod{16}\) و\(w^4\equiv1\pmod{16}\)، ومن ثم يلزم \(u^2\equiv2\pmod{16}\)، وهذا مستحيل. لذلك لا بد أن يكون \(w\) زوجيًا، فنكتب
$$y=4t,\qquad z=4u,$$
فنحصل على
$$(u-x)(u+x)=16t^4.$$
بما أن \(u\) و\(x\) فرديان، فكلا العاملين زوجي. والفرق بينهما هو \(2x\)، وهو يقبل القسمة على \(2\) ولا يقبل القسمة على \(4\)، لذا فالجزء المشترك من قوى \(2\) هو عامل واحد فقط من \(2\). وبعد ترتيب العاملين يمكن أن نكتب
$$u+x=2s^4,\qquad u-x=8r^4,$$
أو بالعكس. هنا \(r\) و\(s\) متحابان أوليًا، و\(s\) يجب أن يكون فرديًا. بالجمع والطرح نحصل على
$$x=\left|s^4-4r^4\right|,\qquad t=rs,\qquad z=4\left(s^4+4r^4\right).$$
وبما أن \(y=4t\)، فإن العائلة الثانية هي
$$x=\left|s^4-4r^4\right|,\qquad y=4rs,\qquad z=4\left(s^4+4r^4\right),$$
مع شرط أن يكون \(s\) فرديًا و\(\gcd(r,s)=1\). والقيمة المطلقة لا تفعل أكثر من توحيد حالتي إسناد العامل \(8\) إلى \(u-x\) أو إلى \(u+x\) في صيغة واحدة.
لا تصبح البارامتريّات مفيدة إلا إذا أعطت حدودًا ضيقة للحلقات. والقيد \(z\le N\) يعطي ذلك مباشرة.
في العائلة الأولى،
$$z=\frac{p^4+q^4}{2}\le N.$$
ومن ثم \(q^4\le 2N\)، أي
$$q\le \left\lfloor(2N)^{1/4}\right\rfloor.$$
وبعد تثبيت \(q\) الفردي تبقى الشروط
$$p^4\le 2N-q^4,\qquad p\lt q,$$
ولذلك يختار التنفيذ أكبر قيمة فردية ممكنة لـ \(p\) تحقق هذين الشرطين.
وفي العائلة الثانية،
$$z=4\left(s^4+4r^4\right)\le N,$$
فتنتج الحدود
$$s^4\le \frac N4,\qquad r^4\le \frac{N/4-s^4}{4}.$$
أي أن
$$s\le \left\lfloor\left(\frac N4\right)^{1/4}\right\rfloor,\qquad r\le \left\lfloor\left(\frac{N/4-s^4}{4}\right)^{1/4}\right\rfloor.$$
وبذلك يُستكشف كل فرع بحلقات من رتبة الجذر الرابع بدلًا من تعداد جميع الإحداثيات مباشرة.
قيمة التحقق الصغيرة \(S(100)=81\) تظهر مباشرة من العائلتين.
في العائلة الأولى لدينا \(q\le \lfloor 200^{1/4}\rfloor=3\). والزوج الفردي المتحاب أوليًا الوحيد الذي يحقق \(p\lt q\) هو \((p,q)=(1,3)\)، ومنه نحصل على
$$x=\frac{3^4-1^4}{8}=10,\qquad y=1\cdot3=3,\qquad z=\frac{1^4+3^4}{2}=41.$$
ومساهمته هي
$$10+3+41=54.$$
أما في العائلة الثانية فلدينا \(s\le \lfloor 25^{1/4}\rfloor=2\)، ولذلك فالخيار الفردي الوحيد هو \(s=1\). وعندها تكون القيمة المسموح بها الوحيدة لـ \(r\) هي \(1\)، فنحصل على
$$x=\left|1^4-4\cdot1^4\right|=3,\qquad y=4\cdot1\cdot1=4,\qquad z=4(1+4)=20.$$
ومساهمته هي
$$3+4+20=27.$$
إذن
$$S(100)=54+27=81,$$
وهي بالضبط قيمة الفحص الصغيرة المستخدمة في التنفيذ.
إذا رمزنا إلى مجموعتي المعلمات المسموح بها بـ
$$\mathcal{A}_N=\left\{(p,q): p,q\text{ odd},\ 1\le p\lt q,\ \gcd(p,q)=1,\ \frac{p^4+q^4}{2}\le N\right\}$$
و
$$\mathcal{B}_N=\left\{(r,s): s\text{ odd},\ r\ge1,\ \gcd(r,s)=1,\ 4\left(s^4+4r^4\right)\le N\right\},$$
فإن المجموع المطلوب هو
$$S(N)=\sum_{(p,q)\in\mathcal{A}_N}\left(\frac{q^4-p^4}{8}+pq+\frac{p^4+q^4}{2}\right)+\sum_{(r,s)\in\mathcal{B}_N}\left(\left|s^4-4r^4\right|+4rs+4\left(s^4+4r^4\right)\right).$$
ولا يوجد تداخل بين المجموعين لأن العائلة الأولى تعطي دائمًا \(y\) فرديًا، بينما تعطي العائلة الثانية دائمًا \(y\) قابلًا للقسمة على \(4\).
تتبع تطبيقات C++ وPython وJava البنية نفسها. أولًا تُحسب الجذور الرابعة الصحيحة بدقة. تبدأ كل نسخة بتقدير عشري تقريبي، ثم تُصحح هذه القيمة صعودًا أو هبوطًا بواسطة مقارنات صحيحة حتى تبقى الحدود الدقيقة سليمة.
بعد ذلك يقوم الفرع الأول بتعداد قيم \(q\) الفردية، ويستخرج أكبر قيمة فردية ممكنة لـ \(p\)، ثم يطبق شرط \(\gcd(p,q)=1\)، وبعدها يبني الثلاثي من بارامتريّة الحالة الفردية. أما الفرع الثاني فيعدد قيم \(s\) الفردية، ويستخرج أكبر قيمة مسموحة لـ \(r\)، ويطبق شرط \(\gcd(r,s)=1\)، ثم يبني الثلاثي من بارامتريّة الحالة الزوجية. وفي كلا الفرعين يعاد التحقق من أن الإحداثيات المولدة تقع ضمن قيد المسألة قبل إضافتها إلى المجموع.
في النهاية يُجمع \(x+y+z\) بترديد \(10^9\). كما أن إحدى النسخ تحتوي على اختبارات دقيقة صغيرة، بما في ذلك مقارنة مجال صغير جدًا مع تعداد مباشر، للتأكد من أن البحث البارامتري يطابق brute force عندما يكون ذلك ممكنًا.
المعاملان الخارجيان \(q\) و\(s\) لا يصلان إلا إلى \(O(N^{1/4})\). ولكل قيمة خارجية يكون المجال الداخلي أيضًا من رتبة الجذر الرابع، ولذلك فإن العدد الكلي لأزواج المعلمات المرشحة عبر العائلتين هو \(O(N^{1/2})\). وكل مرشح يحتاج إلى عدد ثابت من العمليات الحسابية بالإضافة إلى حساب gcd واحد، لذا فإن زمن التنفيذ قريب من \(O(N^{1/2})\) من حيث الخطوات الحسابية، أو \(O(N^{1/2}\log N)\) إذا حُسبت كلفة gcd صراحةً. واستهلاك الذاكرة هو \(O(1)\).