For each positive integer \(n\), define
$$a(n)=\#\left\{d\in\mathbb{Z}_{>0}: d\mid 2n^2,\ d\le n\right\}.$$
The problem asks for
$$F(N)=\sum_{n=1}^{N} a(n).$$
A brute-force method would test every \(d\le n\) for every \(n\le N\), which is far too slow for the large target value. The successful approach is to count admissible pairs \((n,d)\) in a structured way, then compress the remaining sums with Möbius inversion and quotient-block floor sums.
Instead of viewing the problem as a separate divisor search for each \(n\), we count all valid pairs \((n,d)\) at once.
By definition, \(F(N)\) counts pairs \((n,d)\) such that
$$1\le n\le N,\qquad d\mid 2n^2,\qquad d\le n.$$
So we may write
$$F(N)=\#\left\{(n,d):1\le n\le N,\ d\mid 2n^2,\ d\le n\right\}.$$
The inequality \(d\le n\) and the divisibility condition interact naturally with \(\gcd(n,d)\), so that is the right quantity to isolate first.
For any counted pair, set
$$g=\gcd(n,d),\qquad n=g\,m,\qquad d=g\,u,\qquad \gcd(m,u)=1.$$
Because \(d\le n\), we immediately have
$$u\le m.$$
Also, from \(d\mid 2n^2\) we get
$$g\,u \mid 2g^2m^2,$$
and after dividing by \(g\),
$$u\mid 2g\,m^2.$$
Since \(\gcd(u,m)=1\), every prime factor of \(u\) must come from \(2g\), so in fact
$$u\mid 2g.$$
That condition leads to two natural cases: \(u\) odd and \(u\) even.
If \(u\) is odd, then \(u\mid 2g\) forces \(u\mid g\). Write
$$g=u\,t.$$
Substituting back gives
$$d=u^2t,\qquad n=u\,m\,t,\qquad \gcd(m,u)=1,\qquad m\ge u.$$
For fixed \(u\) and \(m\), the parameter \(t\) can be any positive integer with \(u m t\le N\), so it contributes
$$\left\lfloor\frac{N}{u m}\right\rfloor$$
choices. Therefore the odd contribution is
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{\substack{m\ge u\\ \gcd(m,u)=1}}\left\lfloor\frac{N}{u m}\right\rfloor.$$
The range \(u\le \sqrt N\) is automatic because \(n=u m t\ge u^2\).
If \(u\) is even, write
$$u=2w.$$
Then \(u\mid 2g\) becomes \(w\mid g\), so we may set
$$g=w\,t.$$
Now
$$d=2w^2t,\qquad n=w\,m\,t,\qquad \gcd(m,2w)=1,\qquad m\ge 2w.$$
The condition \(\gcd(m,2w)=1\) means in particular that \(m\) must be odd, and also \(\gcd(m,w)=1\). For fixed \(w\) and \(m\), the number of possible \(t\) is
$$\left\lfloor\frac{N}{w m}\right\rfloor.$$
So the even contribution is
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{m\ge 2w\\ m\text{ odd}\\ \gcd(m,w)=1}}\left\lfloor\frac{N}{w m}\right\rfloor.$$
Again the range follows from \(n=wmt\ge 2w^2\). The full answer is simply
$$F(N)=C_{\mathrm{odd}}(N)+C_{\mathrm{even}}(N).$$
The remaining obstacle is the condition \(\gcd(m,u)=1\) or \(\gcd(m,w)=1\). This is handled with the Möbius function:
$$[\gcd(x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d).$$
Applying this to the odd branch gives
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{d\mid u}^{\mathrm{sqfree}}\mu(d)\sum_{r\ge \lceil u/d\rceil}\left\lfloor\frac{\left\lfloor N/(ud)\right\rfloor}{r}\right\rfloor.$$
Here \(d\) runs over the squarefree divisors of \(u\), and we rewrote \(m=d r\).
For the even branch, only odd squarefree divisors matter because \(m\) is already odd. That yields
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{d\mid w\\ d\text{ odd}}}^{\mathrm{sqfree}}\mu(d)\sum_{\substack{r\ge \lceil 2w/d\rceil\\ r\text{ odd}}}\left\lfloor\frac{\left\lfloor N/(wd)\right\rfloor}{r}\right\rfloor.$$
These are exactly the two families of sums evaluated by the implementation.
Define the tail floor sum
$$\operatorname{FS}(X,L)=\sum_{m=L}^{X}\left\lfloor\frac{X}{m}\right\rfloor.$$
Then the odd-denominator version is obtained by subtracting the even denominators:
$$\sum_{\substack{m\ge L\\ m\text{ odd}}}\left\lfloor\frac{X}{m}\right\rfloor=\operatorname{FS}(X,L)-\operatorname{FS}\left(\left\lfloor\frac{X}{2}\right\rfloor,\left\lceil\frac{L}{2}\right\rceil\right).$$
This identity is the key to turning the even branch into the same kind of floor-sum object as the odd branch. The implementation then evaluates \(\operatorname{FS}(X,L)\) in quotient blocks, using the fact that \(\left\lfloor X/m\right\rfloor\) is constant on long intervals.
The implementation checks the small value \(F(15)=63\). Using the branch formulas, we can see why.
For the odd branch, \(u\le \sqrt{15}\), so \(u=1\) or \(u=3\).
When \(u=1\), every \(m\ge 1\) is coprime to \(1\), so
$$\sum_{m=1}^{15}\left\lfloor\frac{15}{m}\right\rfloor=45.$$
When \(u=3\), we need \(m\ge 3\), \(\gcd(m,3)=1\), and \(\left\lfloor 15/(3m)\right\rfloor>0\). Only \(m=4,5\) contribute, giving
$$\left\lfloor\frac{15}{12}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=1+1=2.$$
Hence
$$C_{\mathrm{odd}}(15)=45+2=47.$$
For the even branch, \(w\le \sqrt{15/2}\), so \(w=1,2\).
When \(w=1\), the odd integers \(m\ge 2\) that contribute are \(3,5,7,9,11,13,15\), so
$$\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{5}\right\rfloor+\left\lfloor\frac{15}{7}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor+\left\lfloor\frac{15}{11}\right\rfloor+\left\lfloor\frac{15}{13}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=14.$$
When \(w=2\), we need odd \(m\ge 4\), and only \(m=5,7\) contribute:
$$\left\lfloor\frac{15}{10}\right\rfloor+\left\lfloor\frac{15}{14}\right\rfloor=1+1=2.$$
Thus
$$C_{\mathrm{even}}(15)=14+2=16,$$
and finally
$$F(15)=47+16=63.$$
The C++, Python, and Java implementations all follow the same mathematical decomposition. The optimized computation first determines the two outer ranges, \(\lfloor\sqrt N\rfloor\) for the odd branch and \(\lfloor\sqrt{N/2}\rfloor\) for the even branch.
Next, it precomputes for every integer up to that range all squarefree divisors together with the corresponding Möbius sign. This is done by extracting the distinct prime factors of each integer and enumerating their subsets, because every subset produces one squarefree divisor and its sign \((-1)^k\).
The main summation then iterates through the odd and even branches exactly as in the formulas above. Each inner tail sum is reduced to \(\operatorname{FS}(X,L)\), and \(\operatorname{FS}(X,L)\) is not evaluated term-by-term. Instead, the implementation groups consecutive denominators that give the same quotient \(\left\lfloor X/m\right\rfloor\), so one arithmetic step handles an entire block.
For large inputs, the C++ implementation can split the odd and even ranges into independent blocks and process them in parallel. The Python and Java implementations reuse that same optimized native computation and only return the final numeric output. Before the full run, the program also checks small checkpoints and compares against a direct brute-force count on a small limit.
Let
$$M=\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\sqrt{N/2}\right\rfloor\right).$$
Building the smallest-prime-factor sieve up to \(M\) costs \(O(M\log\log M)\) time and \(O(M)\) memory. The stored squarefree-divisor cache contains \(\sum_{k\le M}2^{\omega(k)}\) entries, whose average order is \(O(M\log M)\), so that cache dominates memory usage in practice.
The two outer summations only run to order \(\sqrt N\), not to \(N\). For each cached divisor entry, the remaining work is a quotient-block floor sum rather than a linear scan over all denominators. The exact worst-case expression is messy because it depends on both divisor structure and quotient-block lengths, but the practical behavior is close to \(N^{1/2+o(1)}\), which is dramatically better than the quadratic brute-force definition.
Für jede positive ganze Zahl \(n\) definieren wir
$$a(n)=\#\left\{d\in\mathbb{Z}_{>0}: d\mid 2n^2,\ d\le n\right\}.$$
Gesucht ist dann
$$F(N)=\sum_{n=1}^{N} a(n).$$
Ein brutaler Ansatz würde für jedes \(n\le N\) alle \(d\le n\) testen. Das ist für den großen Zielwert viel zu langsam. Die funktionierende Lösung zählt deshalb zulässige Paare \((n,d)\) strukturell, entfernt die Koprimätsbedingungen per Möbius-Inversion und beschleunigt die verbleibenden Summen mit Quotientenblöcken.
Statt jede Zahl \(n\) einzeln zu behandeln, zählen wir alle gültigen Paare \((n,d)\) in einem einzigen Rahmen.
Nach Definition zählt \(F(N)\) genau die Paare \((n,d)\) mit
$$1\le n\le N,\qquad d\mid 2n^2,\qquad d\le n.$$
Also
$$F(N)=\#\left\{(n,d):1\le n\le N,\ d\mid 2n^2,\ d\le n\right\}.$$
Die Bedingung \(d\le n\) und die Teilbarkeit durch \(2n^2\) lassen sich sehr natürlich über \(\gcd(n,d)\) beschreiben.
Für ein gezähltes Paar setzen wir
$$g=\gcd(n,d),\qquad n=g\,m,\qquad d=g\,u,\qquad \gcd(m,u)=1.$$
Aus \(d\le n\) folgt sofort
$$u\le m.$$
Weiter liefert \(d\mid 2n^2\) die Beziehung
$$g\,u \mid 2g^2m^2,$$
also nach Kürzen von \(g\)
$$u\mid 2g\,m^2.$$
Wegen \(\gcd(u,m)=1\) können die Primfaktoren von \(u\) nicht aus \(m\) stammen; sie müssen vollständig in \(2g\) liegen. Daher gilt sogar
$$u\mid 2g.$$
Damit zerfällt das Problem sofort in einen ungeraden und einen geraden Zweig.
Ist \(u\) ungerade, dann erzwingt \(u\mid 2g\) bereits \(u\mid g\). Wir schreiben also
$$g=u\,t.$$
Dann werden die Größen zu
$$d=u^2t,\qquad n=u\,m\,t,\qquad \gcd(m,u)=1,\qquad m\ge u.$$
Für festes \(u\) und \(m\) kann \(t\) jede positive ganze Zahl mit \(umt\le N\) sein. Die Anzahl dieser Möglichkeiten ist
$$\left\lfloor\frac{N}{u m}\right\rfloor.$$
Somit ist der ungerade Beitrag
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{\substack{m\ge u\\ \gcd(m,u)=1}}\left\lfloor\frac{N}{u m}\right\rfloor.$$
Die Schranke \(u\le\sqrt N\) folgt aus \(n=u m t\ge u^2\).
Ist \(u\) gerade, schreiben wir
$$u=2w.$$
Dann wird aus \(u\mid 2g\) die Bedingung \(w\mid g\), also
$$g=w\,t.$$
Damit erhalten wir
$$d=2w^2t,\qquad n=w\,m\,t,\qquad \gcd(m,2w)=1,\qquad m\ge 2w.$$
Insbesondere ist \(m\) ungerade und zudem teilerfremd zu \(w\). Für festes \(w\) und \(m\) gibt es
$$\left\lfloor\frac{N}{w m}\right\rfloor$$
Möglichkeiten für \(t\). Also
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{m\ge 2w\\ m\text{ odd}\\ \gcd(m,w)=1}}\left\lfloor\frac{N}{w m}\right\rfloor.$$
Und insgesamt gilt
$$F(N)=C_{\mathrm{odd}}(N)+C_{\mathrm{even}}(N).$$
Die verbleibende Bedingung \(\gcd(\cdot,\cdot)=1\) wird mit
$$[\gcd(x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d)$$
behandelt. Für den ungeraden Zweig ergibt sich
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{d\mid u}^{\mathrm{sqfree}}\mu(d)\sum_{r\ge \lceil u/d\rceil}\left\lfloor\frac{\left\lfloor N/(ud)\right\rfloor}{r}\right\rfloor.$$
Hier läuft \(d\) über die quadratfreien Teiler von \(u\), und wir haben \(m=d r\) geschrieben.
Für den geraden Zweig reichen ungerade quadratfreie Teiler, weil \(m\) ohnehin ungerade ist:
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{d\mid w\\ d\text{ odd}}}^{\mathrm{sqfree}}\mu(d)\sum_{\substack{r\ge \lceil 2w/d\rceil\\ r\text{ odd}}}\left\lfloor\frac{\left\lfloor N/(wd)\right\rfloor}{r}\right\rfloor.$$
Genau diese beiden Summenfamilien wertet die Implementierung aus.
Definiere
$$\operatorname{FS}(X,L)=\sum_{m=L}^{X}\left\lfloor\frac{X}{m}\right\rfloor.$$
Dann gilt
$$\sum_{\substack{m\ge L\\ m\text{ odd}}}\left\lfloor\frac{X}{m}\right\rfloor=\operatorname{FS}(X,L)-\operatorname{FS}\left(\left\lfloor\frac{X}{2}\right\rfloor,\left\lceil\frac{L}{2}\right\rceil\right).$$
Der zweite Term entfernt genau die geraden Nenner. Damit wird auch der gerade Zweig auf dieselbe Floor-Summen-Struktur zurückgeführt. Anschließend werden Intervalle mit konstantem Quotienten \(\left\lfloor X/m\right\rfloor\) blockweise verarbeitet.
Die Implementierung prüft den kleinen Wert \(F(15)=63\). Das lässt sich direkt aus den Zweigen nachvollziehen.
Im ungeraden Zweig gilt \(u\le \sqrt{15}\), also \(u=1\) oder \(u=3\).
Für \(u=1\) ist jedes \(m\ge 1\) teilerfremd zu \(1\), also
$$\sum_{m=1}^{15}\left\lfloor\frac{15}{m}\right\rfloor=45.$$
Für \(u=3\) brauchen wir \(m\ge 3\), \(\gcd(m,3)=1\) und \(\left\lfloor 15/(3m)\right\rfloor>0\). Nur \(m=4,5\) tragen bei:
$$\left\lfloor\frac{15}{12}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=1+1=2.$$
Daher
$$C_{\mathrm{odd}}(15)=45+2=47.$$
Im geraden Zweig gilt \(w\le \sqrt{15/2}\), also \(w=1,2\).
Für \(w=1\) tragen die ungeraden \(m\ge 2\), nämlich \(3,5,7,9,11,13,15\), den Gesamtwert
$$\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{5}\right\rfloor+\left\lfloor\frac{15}{7}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor+\left\lfloor\frac{15}{11}\right\rfloor+\left\lfloor\frac{15}{13}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=14$$
bei. Für \(w=2\) bleiben nur \(m=5,7\):
$$\left\lfloor\frac{15}{10}\right\rfloor+\left\lfloor\frac{15}{14}\right\rfloor=1+1=2.$$
Also
$$C_{\mathrm{even}}(15)=14+2=16,$$
und damit
$$F(15)=47+16=63.$$
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Zerlegung. Zuerst werden die beiden Außenbereiche bestimmt: \(\lfloor\sqrt N\rfloor\) für den ungeraden Zweig und \(\lfloor\sqrt{N/2}\rfloor\) für den geraden Zweig.
Danach werden für jede Zahl bis zu dieser Grenze alle quadratfreien Teiler zusammen mit dem passenden Möbius-Vorzeichen vorab erzeugt. Grundlage dafür sind die verschiedenen Primfaktoren jeder Zahl; jede Teilmenge dieser Primfaktoren liefert genau einen quadratfreien Teiler und das Vorzeichen \((-1)^k\).
In der Hauptsumme werden dann die beiden Zweige aus den Formeln abgearbeitet. Jede innere Schwanzsumme wird auf \(\operatorname{FS}(X,L)\) zurückgeführt. Diese Floor-Summe wird nicht termweise, sondern blockweise berechnet: ganze Intervalle von Nennern mit gleichem Quotienten \(\left\lfloor X/m\right\rfloor\) werden in einem Schritt zusammengefasst.
Für große Eingaben kann die C++-Implementierung unabhängige Blöcke der ungeraden und geraden Zweige parallel ausführen. Die Python- und Java-Implementierungen verwenden dieselbe optimierte native Berechnung und liefern nur die fertige Zahl zurück. Zusätzlich werden vor dem großen Lauf kleine Kontrollwerte sowie ein brutaler Kreuztest auf kleinem Bereich ausgeführt.
Sei
$$M=\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\sqrt{N/2}\right\rfloor\right).$$
Das Sieb für die kleinsten Primfaktoren bis \(M\) benötigt \(O(M\log\log M)\) Zeit und \(O(M)\) Speicher. Der Cache der quadratfreien Teiler enthält \(\sum_{k\le M}2^{\omega(k)}\) Einträge; seine mittlere Größenordnung ist \(O(M\log M)\) und er dominiert praktisch den Speicherverbrauch.
Die beiden Hauptsummen laufen nur bis in die Größenordnung \(\sqrt N\), nicht bis \(N\). Für jeden gecachten Teilereintrag wird anschließend eine Floor-Summe in Quotientenblöcken statt einer linearen Nenner-Schleife ausgewertet. Eine exakte Worst-Case-Formel ist unhandlich, weil sowohl die Teilerstruktur als auch die Blocklängen eingehen, aber das praktische Verhalten liegt nahe bei \(N^{1/2+o(1)}\) und ist damit massiv besser als der quadratische Brute-Force-Ansatz.
Her pozitif tamsayı \(n\) için
$$a(n)=\#\left\{d\in\mathbb{Z}_{>0}: d\mid 2n^2,\ d\le n\right\}$$
tanımını yapalım. Problem şu toplamı istiyor:
$$F(N)=\sum_{n=1}^{N} a(n).$$
Doğrudan yöntem, her \(n\le N\) için tüm \(d\le n\) değerlerini deneyip \(d\mid 2n^2\) olup olmadığını kontrol eder. Büyük hedef değer için bu yaklaşım çok yavaştır. Etkili çözüm ise geçerli \((n,d)\) çiftlerini yapısal olarak sayar, aradaki aralarında asal olma şartlarını Möbius terslemesiyle kaldırır ve kalan toplamları bölüm plato bloklarıyla sıkıştırır.
Problemi her \(n\) için ayrı ayrı bölen araması olarak değil, tüm uygun \((n,d)\) çiftlerinin sayımı olarak ele almak daha verimlidir.
Tanım gereği \(F(N)\), şu koşulları sağlayan \((n,d)\) çiftlerinin sayısıdır:
$$1\le n\le N,\qquad d\mid 2n^2,\qquad d\le n.$$
Dolayısıyla
$$F(N)=\#\left\{(n,d):1\le n\le N,\ d\mid 2n^2,\ d\le n\right\}.$$
\(d\le n\) eşitsizliği ile bölen olma koşulu, \(\gcd(n,d)\) üzerinden çok temiz biçimde ayrışır.
Saydığımız herhangi bir çift için
$$g=\gcd(n,d),\qquad n=g\,m,\qquad d=g\,u,\qquad \gcd(m,u)=1$$
yazalım. \(d\le n\) olduğundan hemen
$$u\le m$$
elde edilir. Ayrıca \(d\mid 2n^2\) koşulu
$$g\,u \mid 2g^2m^2$$
demektir. Buradan \(g\) sadeleştirilirse
$$u\mid 2g\,m^2$$
kalır. Fakat \(\gcd(u,m)=1\) olduğu için \(u\)'nun asal çarpanları \(m\)'den gelemez; hepsi \(2g\)'nin içinde bulunmalıdır. Yani aslında
$$u\mid 2g$$
olur. Bu da problemi tek ve çift iki kola ayırır.
Eğer \(u\) tek ise, \(u\mid 2g\) koşulu doğrudan \(u\mid g\) verir. Bu yüzden
$$g=u\,t$$
yazarız. Böylece
$$d=u^2t,\qquad n=u\,m\,t,\qquad \gcd(m,u)=1,\qquad m\ge u$$
olur. Sabit \(u\) ve \(m\) için \(t\) parametresinin alabileceği değer sayısı
$$\left\lfloor\frac{N}{u m}\right\rfloor$$
kadardır. Dolayısıyla tek kol katkısı
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ tek}}}\ \sum_{\substack{m\ge u\\ \gcd(m,u)=1}}\left\lfloor\frac{N}{u m}\right\rfloor$$
şeklindedir. Buradaki \(u\le \sqrt N\) sınırı, \(n=u m t\ge u^2\) eşitsizliğinden gelir.
Eğer \(u\) çift ise
$$u=2w$$
yazarız. Bu kez \(u\mid 2g\) koşulu \(w\mid g\) anlamına gelir; o halde
$$g=w\,t$$
alabiliriz. Sonuç olarak
$$d=2w^2t,\qquad n=w\,m\,t,\qquad \gcd(m,2w)=1,\qquad m\ge 2w$$
olur. Buradan özellikle \(m\)'nin tek olduğu ve \(\gcd(m,w)=1\) olduğu görülür. Sabit \(w\) ve \(m\) için uygun \(t\) sayısı
$$\left\lfloor\frac{N}{w m}\right\rfloor$$
kadardır. Böylece çift kol katkısı
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{m\ge 2w\\ m\text{ tek}\\ \gcd(m,w)=1}}\left\lfloor\frac{N}{w m}\right\rfloor$$
olur. Toplam sonuç da
$$F(N)=C_{\mathrm{odd}}(N)+C_{\mathrm{even}}(N)$$
şeklindedir.
Kalan temel engel \(\gcd(\cdot,\cdot)=1\) koşuludur. Bunu
$$[\gcd(x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d)$$
özdeşliğiyle kaldırırız. Tek kol için
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ tek}}}\ \sum_{d\mid u}^{\mathrm{sqfree}}\mu(d)\sum_{r\ge \lceil u/d\rceil}\left\lfloor\frac{\left\lfloor N/(ud)\right\rfloor}{r}\right\rfloor$$
elde edilir. Burada \(d\), \(u\)'nun kareden arınmış bölenleri arasında dolaşır ve \(m=d r\) dönüşümü kullanılır.
Çift kolda ise \(m\) zaten tek olduğundan yalnızca tek kareden arınmış bölenler önemlidir:
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{d\mid w\\ d\text{ tek}}}^{\mathrm{sqfree}}\mu(d)\sum_{\substack{r\ge \lceil 2w/d\rceil\\ r\text{ tek}}}\left\lfloor\frac{\left\lfloor N/(wd)\right\rfloor}{r}\right\rfloor.$$
Uygulamanın doğrudan hesapladığı iki toplam ailesi tam olarak bunlardır.
Şu kuyruk toplamını tanımlayalım:
$$\operatorname{FS}(X,L)=\sum_{m=L}^{X}\left\lfloor\frac{X}{m}\right\rfloor.$$
Yalnızca tek \(m\)'ler için gereken sürüm şu farkla elde edilir:
$$\sum_{\substack{m\ge L\\ m\text{ tek}}}\left\lfloor\frac{X}{m}\right\rfloor=\operatorname{FS}(X,L)-\operatorname{FS}\left(\left\lfloor\frac{X}{2}\right\rfloor,\left\lceil\frac{L}{2}\right\rceil\right).$$
İkinci terim tüm çift paydaları çıkarmış olur. Böylece çift kol da standart floor-toplam biçimine iner. Ardından \(\left\lfloor X/m\right\rfloor\) değerinin sabit kaldığı aralıklar tek tek değil blok halinde toplanır.
Uygulama küçük bir kontrol olarak \(F(15)=63\) değerini doğrular. Bunu kollar üzerinden doğrudan görebiliriz.
Tek kolda \(u\le \sqrt{15}\), yani yalnızca \(u=1\) ve \(u=3\) vardır.
\(u=1\) için her \(m\ge 1\) sayısı uygundur, dolayısıyla
$$\sum_{m=1}^{15}\left\lfloor\frac{15}{m}\right\rfloor=45.$$
\(u=3\) için \(m\ge 3\), \(\gcd(m,3)=1\) ve \(\left\lfloor 15/(3m)\right\rfloor>0\) gerekir. Sadece \(m=4\) ve \(m=5\) katkı verir:
$$\left\lfloor\frac{15}{12}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=1+1=2.$$
Böylece
$$C_{\mathrm{odd}}(15)=45+2=47.$$
Çift kolda \(w\le \sqrt{15/2}\), yani \(w=1,2\).
\(w=1\) için katkı veren tek \(m\ge 2\) değerleri \(3,5,7,9,11,13,15\)'tir ve toplam
$$\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{5}\right\rfloor+\left\lfloor\frac{15}{7}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor+\left\lfloor\frac{15}{11}\right\rfloor+\left\lfloor\frac{15}{13}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=14$$
olur. \(w=2\) için yalnızca \(m=5\) ve \(m=7\) kalır:
$$\left\lfloor\frac{15}{10}\right\rfloor+\left\lfloor\frac{15}{14}\right\rfloor=1+1=2.$$
Demek ki
$$C_{\mathrm{even}}(15)=14+2=16,$$
ve sonuç olarak
$$F(15)=47+16=63.$$
C++, Python ve Java uygulamalarının hepsi aynı matematiksel ayrışımı kullanır. Önce iki dış sınır hesaplanır: tek kol için \(\lfloor\sqrt N\rfloor\), çift kol için \(\lfloor\sqrt{N/2}\rfloor\).
Daha sonra bu sınıra kadar her sayı için kareden arınmış bölenler ve bunların Möbius işaretleri önceden hazırlanır. Bunun için her sayının farklı asal çarpanları bulunur; bu asal çarpanların her altkümesi bir kareden arınmış bölen ve buna karşılık gelen \((-1)^k\) işaretini üretir.
Ana toplama kısmı yukarıdaki tek ve çift kol formüllerini birebir izler. Her iç kuyruk toplamı \(\operatorname{FS}(X,L)\) biçimine dönüştürülür. Bu toplamlar tek tek terim gezilerek değil, aynı bölme sonucunu veren ardışık payda aralıkları bloklanarak hesaplanır.
Büyük girişlerde C++ uygulaması tek ve çift kol aralıklarını bağımsız bloklara ayırıp paralel çalıştırabilir. Python ve Java uygulamaları da aynı optimize yerel hesabı kullanıp yalnızca son sayısal çıktıyı döndürür. Tam çalışmadan önce küçük kontrol değerleri ve küçük bir sınırda brute-force çapraz testi de yapılır.
Şu değeri tanımlayalım:
$$M=\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\sqrt{N/2}\right\rfloor\right).$$
\(M\)'ye kadar en küçük asal çarpan süzgecini kurmak \(O(M\log\log M)\) zaman ve \(O(M)\) bellek ister. Kareden arınmış bölen önbelleğinin boyutu \(\sum_{k\le M}2^{\omega(k)}\) kadardır; bunun ortalama mertebesi \(O(M\log M)\) olduğundan pratikte bellek kullanımını esasen bu yapı belirler.
Ana toplamlar \(N\)'e kadar değil, yalnızca \(\sqrt N\) mertebesine kadar gider. Her önbellek girdisi için yapılan kalan iş de lineer payda taraması değil, bölüm plato blokları halinde floor-toplam hesabıdır. Kesin worst-case bağıntısı bölen yapısına ve blok uzunluklarına bağlı olduğu için karmaşıktır, fakat pratik davranış \(N^{1/2+o(1)}\) civarındadır ve bu da karesel brute-force tanımına göre çok büyük bir iyileşmedir.
Para cada entero positivo \(n\), definimos
$$a(n)=\#\left\{d\in\mathbb{Z}_{>0}: d\mid 2n^2,\ d\le n\right\}.$$
El problema pide calcular
$$F(N)=\sum_{n=1}^{N} a(n).$$
Un enfoque directo probaría todos los \(d\le n\) para cada \(n\le N\), lo cual es demasiado lento para el valor grande del problema. La solución eficaz cuenta los pares válidos \((n,d)\) de manera estructurada, elimina las condiciones de coprimalidad con inversión de Möbius y comprime las sumas restantes con bloques de cociente.
En lugar de mirar cada \(n\) por separado, contamos de una vez todos los pares \((n,d)\) que cumplen las restricciones.
Por definición, \(F(N)\) cuenta los pares \((n,d)\) tales que
$$1\le n\le N,\qquad d\mid 2n^2,\qquad d\le n.$$
Así que
$$F(N)=\#\left\{(n,d):1\le n\le N,\ d\mid 2n^2,\ d\le n\right\}.$$
La desigualdad \(d\le n\) y la condición de divisibilidad se organizan de forma natural si aislamos \(\gcd(n,d)\).
Para cualquier par contado, escribimos
$$g=\gcd(n,d),\qquad n=g\,m,\qquad d=g\,u,\qquad \gcd(m,u)=1.$$
De \(d\le n\) se deduce inmediatamente
$$u\le m.$$
Además, la condición \(d\mid 2n^2\) da
$$g\,u \mid 2g^2m^2,$$
y al dividir por \(g\),
$$u\mid 2g\,m^2.$$
Como \(\gcd(u,m)=1\), los factores primos de \(u\) no pueden venir de \(m\); por tanto deben estar enteramente en \(2g\), es decir,
$$u\mid 2g.$$
Eso produce dos casos naturales: \(u\) impar y \(u\) par.
Si \(u\) es impar, entonces \(u\mid 2g\) implica \(u\mid g\). Escribimos
$$g=u\,t.$$
Con ello obtenemos
$$d=u^2t,\qquad n=u\,m\,t,\qquad \gcd(m,u)=1,\qquad m\ge u.$$
Para \(u\) y \(m\) fijos, el parámetro \(t\) puede tomar exactamente
$$\left\lfloor\frac{N}{u m}\right\rfloor$$
valores positivos. Entonces
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ impar}}}\ \sum_{\substack{m\ge u\\ \gcd(m,u)=1}}\left\lfloor\frac{N}{u m}\right\rfloor.$$
La cota \(u\le \sqrt N\) sale de \(n=u m t\ge u^2\).
Si \(u\) es par, escribimos
$$u=2w.$$
Entonces \(u\mid 2g\) se convierte en \(w\mid g\), de modo que
$$g=w\,t.$$
Ahora
$$d=2w^2t,\qquad n=w\,m\,t,\qquad \gcd(m,2w)=1,\qquad m\ge 2w.$$
Esto fuerza a \(m\) a ser impar y además coprimo con \(w\). Para \(w\) y \(m\) fijos, el número de valores posibles de \(t\) es
$$\left\lfloor\frac{N}{w m}\right\rfloor.$$
Así, la contribución par es
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{m\ge 2w\\ m\text{ impar}\\ \gcd(m,w)=1}}\left\lfloor\frac{N}{w m}\right\rfloor.$$
Y el total buscado es
$$F(N)=C_{\mathrm{odd}}(N)+C_{\mathrm{even}}(N).$$
La condición \(\gcd(\cdot,\cdot)=1\) se trata con
$$[\gcd(x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d).$$
Aplicada a la rama impar, produce
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ impar}}}\ \sum_{d\mid u}^{\mathrm{sqfree}}\mu(d)\sum_{r\ge \lceil u/d\rceil}\left\lfloor\frac{\left\lfloor N/(ud)\right\rfloor}{r}\right\rfloor.$$
Aquí \(d\) recorre los divisores libres de cuadrados de \(u\), y se ha escrito \(m=d r\).
En la rama par solo hacen falta divisores libres de cuadrados e impares, porque \(m\) ya es impar:
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{d\mid w\\ d\text{ impar}}}^{\mathrm{sqfree}}\mu(d)\sum_{\substack{r\ge \lceil 2w/d\rceil\\ r\text{ impar}}}\left\lfloor\frac{\left\lfloor N/(wd)\right\rfloor}{r}\right\rfloor.$$
Estas son exactamente las dos familias de sumas que evalúa la implementación.
Definimos
$$\operatorname{FS}(X,L)=\sum_{m=L}^{X}\left\lfloor\frac{X}{m}\right\rfloor.$$
Entonces
$$\sum_{\substack{m\ge L\\ m\text{ impar}}}\left\lfloor\frac{X}{m}\right\rfloor=\operatorname{FS}(X,L)-\operatorname{FS}\left(\left\lfloor\frac{X}{2}\right\rfloor,\left\lceil\frac{L}{2}\right\rceil\right).$$
El segundo término elimina todos los denominadores pares. Con esto, la rama par queda reducida al mismo tipo de objeto que la impar. Luego \(\operatorname{FS}(X,L)\) se calcula por bloques donde el cociente \(\left\lfloor X/m\right\rfloor\) permanece constante.
La implementación verifica el pequeño valor \(F(15)=63\). Veamos cómo aparece.
En la rama impar, \(u\le \sqrt{15}\), así que solo hay \(u=1\) y \(u=3\).
Para \(u=1\), todo \(m\ge 1\) es coprimo con \(1\), de modo que
$$\sum_{m=1}^{15}\left\lfloor\frac{15}{m}\right\rfloor=45.$$
Para \(u=3\), necesitamos \(m\ge 3\), \(\gcd(m,3)=1\) y \(\left\lfloor 15/(3m)\right\rfloor>0\). Solo contribuyen \(m=4\) y \(m=5\):
$$\left\lfloor\frac{15}{12}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=1+1=2.$$
Por lo tanto,
$$C_{\mathrm{odd}}(15)=45+2=47.$$
En la rama par, \(w\le \sqrt{15/2}\), así que \(w=1,2\).
Para \(w=1\), los \(m\) impares con \(m\ge 2\) que aportan son \(3,5,7,9,11,13,15\), y la suma vale
$$\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{5}\right\rfloor+\left\lfloor\frac{15}{7}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor+\left\lfloor\frac{15}{11}\right\rfloor+\left\lfloor\frac{15}{13}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=14.$$
Para \(w=2\), solo quedan \(m=5\) y \(m=7\):
$$\left\lfloor\frac{15}{10}\right\rfloor+\left\lfloor\frac{15}{14}\right\rfloor=1+1=2.$$
Así,
$$C_{\mathrm{even}}(15)=14+2=16,$$
y finalmente
$$F(15)=47+16=63.$$
Las implementaciones en C++, Python y Java siguen la misma descomposición matemática. Primero calculan los dos rangos exteriores: \(\lfloor\sqrt N\rfloor\) para la rama impar y \(\lfloor\sqrt{N/2}\rfloor\) para la rama par.
Después precalculan, para cada entero hasta ese límite, todos sus divisores libres de cuadrados junto con el signo de Möbius correspondiente. Esto se hace a partir de los factores primos distintos de cada número: cada subconjunto genera un divisor libre de cuadrados y el signo \((-1)^k\).
La suma principal recorre exactamente las ramas impar y par descritas arriba. Cada suma de cola se convierte en \(\operatorname{FS}(X,L)\). Esa función no se evalúa denominador por denominador, sino agrupando intervalos consecutivos donde el valor de \(\left\lfloor X/m\right\rfloor\) es constante.
Para entradas grandes, la implementación en C++ puede dividir los rangos de la rama impar y la par en bloques independientes y procesarlos en paralelo. Las implementaciones en Python y Java reutilizan la misma computación nativa optimizada y solo devuelven la salida numérica final. Antes del cálculo grande, el programa también comprueba pequeños checkpoints y un cruce con fuerza bruta en un límite reducido.
Sea
$$M=\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\sqrt{N/2}\right\rfloor\right).$$
Construir la criba de factor primo más pequeño hasta \(M\) cuesta \(O(M\log\log M)\) tiempo y \(O(M)\) memoria. La caché de divisores libres de cuadrados contiene \(\sum_{k\le M}2^{\omega(k)}\) entradas; su orden medio es \(O(M\log M)\), y en la práctica domina la memoria.
Los dos bucles exteriores solo llegan al orden de \(\sqrt N\), no a \(N\). Para cada entrada de la caché, el trabajo restante es una floor-sum por bloques de cociente, no un recorrido lineal por todos los denominadores. La expresión exacta de peor caso es incómoda porque depende tanto de la estructura de divisores como de la longitud de los bloques, pero el comportamiento práctico está cerca de \(N^{1/2+o(1)}\), muy por debajo del enfoque cuadrático por fuerza bruta.
对每个正整数 \(n\)，定义
$$a(n)=\#\left\{d\in\mathbb{Z}_{>0}: d\mid 2n^2,\ d\le n\right\}.$$
题目要求计算
$$F(N)=\sum_{n=1}^{N} a(n).$$
如果直接按照定义去做，那么对每个 \(n\le N\) 都要枚举所有 \(d\le n\) 并检查 \(d\mid 2n^2\)，这在大输入下显然太慢。有效做法是把问题改写成对所有合法 \((n,d)\) 对的统一计数，再用 Möbius 反演去掉互素条件，并用商值分块来加速 floor-sum。
关键不是逐个 \(n\) 去找因子，而是一次性统计所有满足条件的 \((n,d)\) 对。
根据定义，\(F(N)\) 正是满足下列条件的二元组 \((n,d)\) 的个数：
$$1\le n\le N,\qquad d\mid 2n^2,\qquad d\le n.$$
因此可以写成
$$F(N)=\#\left\{(n,d):1\le n\le N,\ d\mid 2n^2,\ d\le n\right\}.$$
这里同时出现了“不超过 \(n\)”和“整除 \(2n^2\)”两个条件。最自然的切入点是把 \(n\) 与 \(d\) 的公因子先抽出来。
对任意一个被计数的二元组，设
$$g=\gcd(n,d),\qquad n=g\,m,\qquad d=g\,u,\qquad \gcd(m,u)=1.$$
由于 \(d\le n\)，立刻得到
$$u\le m.$$
另一方面，\(d\mid 2n^2\) 等价于
$$g\,u \mid 2g^2m^2.$$
约去一个 \(g\) 之后，得到
$$u\mid 2g\,m^2.$$
但 \(\gcd(u,m)=1\)，所以 \(u\) 的素因子不可能来自 \(m\)；它们必须全部来自 \(2g\)。于是实际上有
$$u\mid 2g.$$
这一步把问题自然分成两类：\(u\) 为奇数，或者 \(u\) 为偶数。
如果 \(u\) 是奇数，那么 \(u\mid 2g\) 直接推出 \(u\mid g\)。于是可写
$$g=u\,t.$$
代回去以后得到
$$d=u^2t,\qquad n=u\,m\,t,\qquad \gcd(m,u)=1,\qquad m\ge u.$$
在固定 \(u\) 和 \(m\) 的情况下，只要 \(umt\le N\)，\(t\) 就是合法的正整数，因此可选个数为
$$\left\lfloor\frac{N}{u m}\right\rfloor.$$
所以奇数分支贡献为
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{\substack{m\ge u\\ \gcd(m,u)=1}}\left\lfloor\frac{N}{u m}\right\rfloor.$$
之所以只需要 \(u\le \sqrt N\)，是因为 \(n=u m t\ge u^2\)。
如果 \(u\) 是偶数，就写成
$$u=2w.$$
此时 \(u\mid 2g\) 变成 \(w\mid g\)，因此可以设
$$g=w\,t.$$
于是有
$$d=2w^2t,\qquad n=w\,m\,t,\qquad \gcd(m,2w)=1,\qquad m\ge 2w.$$
这说明 \(m\) 必须是奇数，并且还满足 \(\gcd(m,w)=1\)。固定 \(w\) 和 \(m\) 后，满足 \(wmt\le N\) 的 \(t\) 有
$$\left\lfloor\frac{N}{w m}\right\rfloor$$
个，因此偶数分支为
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{m\ge 2w\\ m\text{ odd}\\ \gcd(m,w)=1}}\left\lfloor\frac{N}{w m}\right\rfloor.$$
最后总和就是
$$F(N)=C_{\mathrm{odd}}(N)+C_{\mathrm{even}}(N).$$
剩下最麻烦的是 \(\gcd(\cdot,\cdot)=1\) 的约束。标准做法是使用
$$[\gcd(x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d).$$
应用到奇数分支后得到
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{d\mid u}^{\mathrm{sqfree}}\mu(d)\sum_{r\ge \lceil u/d\rceil}\left\lfloor\frac{\left\lfloor N/(ud)\right\rfloor}{r}\right\rfloor.$$
这里 \(d\) 在 \(u\) 的平方自由因子上求和，我们把 \(m\) 写成 \(m=d r\)。
对偶数分支而言，由于 \(m\) 本身已经是奇数，因此只需要考虑 \(w\) 的奇平方自由因子：
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{d\mid w\\ d\text{ odd}}}^{\mathrm{sqfree}}\mu(d)\sum_{\substack{r\ge \lceil 2w/d\rceil\\ r\text{ odd}}}\left\lfloor\frac{\left\lfloor N/(wd)\right\rfloor}{r}\right\rfloor.$$
这正是程序真正计算的两类求和公式。
定义尾部 floor-sum：
$$\operatorname{FS}(X,L)=\sum_{m=L}^{X}\left\lfloor\frac{X}{m}\right\rfloor.$$
那么只对奇数 \(m\) 求和时，有恒等式
$$\sum_{\substack{m\ge L\\ m\text{ odd}}}\left\lfloor\frac{X}{m}\right\rfloor=\operatorname{FS}(X,L)-\operatorname{FS}\left(\left\lfloor\frac{X}{2}\right\rfloor,\left\lceil\frac{L}{2}\right\rceil\right).$$
原因很简单：第二项恰好把所有偶数分母 \(m=2r\) 的贡献减掉。这样偶数分支就被化成与奇数分支同类型的 floor-sum。接下来，\(\operatorname{FS}(X,L)\) 不是一项项求，而是按 \(\left\lfloor X/m\right\rfloor\) 保持不变的区间成块累加。
程序会检查一个小例子 \(F(15)=63\)。这个值可以手工从两条分支公式中看出来。
先看奇数分支。由于 \(u\le \sqrt{15}\)，所以只有 \(u=1\) 和 \(u=3\)。
当 \(u=1\) 时，所有 \(m\ge 1\) 都自动与 \(1\) 互素，因此
$$\sum_{m=1}^{15}\left\lfloor\frac{15}{m}\right\rfloor=45.$$
当 \(u=3\) 时，需要 \(m\ge 3\)、\(\gcd(m,3)=1\)，并且 \(\left\lfloor 15/(3m)\right\rfloor>0\)。只有 \(m=4,5\) 有贡献：
$$\left\lfloor\frac{15}{12}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=1+1=2.$$
所以
$$C_{\mathrm{odd}}(15)=45+2=47.$$
再看偶数分支。由于 \(w\le \sqrt{15/2}\)，所以 \(w=1,2\)。
当 \(w=1\) 时，满足 \(m\ge 2\) 的奇数 \(m\) 中，真正有贡献的是 \(3,5,7,9,11,13,15\)，其总和为
$$\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{5}\right\rfloor+\left\lfloor\frac{15}{7}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor+\left\lfloor\frac{15}{11}\right\rfloor+\left\lfloor\frac{15}{13}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=14.$$
当 \(w=2\) 时，只剩 \(m=5\) 和 \(m=7\)：
$$\left\lfloor\frac{15}{10}\right\rfloor+\left\lfloor\frac{15}{14}\right\rfloor=1+1=2.$$
于是
$$C_{\mathrm{even}}(15)=14+2=16,$$
最终得到
$$F(15)=47+16=63.$$
C++、Python 和 Java 实现都遵循同一套数学分解。首先求出两个外层范围：奇数分支用 \(\lfloor\sqrt N\rfloor\)，偶数分支用 \(\lfloor\sqrt{N/2}\rfloor\)。
随后，程序会为不超过该范围的每个整数预计算它的所有平方自由因子以及对应的 Möbius 符号。做法是先拿到每个整数的不同素因子，然后枚举这些素因子的所有子集；每个子集都对应一个平方自由因子，以及符号 \((-1)^k\)。
主循环严格按上面的奇数分支和偶数分支公式求和。每个内层尾和都被转写为 \(\operatorname{FS}(X,L)\)。而 \(\operatorname{FS}(X,L)\) 不会按分母逐个遍历，而是把 \(\left\lfloor X/m\right\rfloor\) 相同的连续区间合并成一个块来处理。
在大输入下，C++ 实现还可以把奇数分支和偶数分支的区间切成彼此独立的块并行计算。Python 和 Java 实现则复用同一个优化过的原生计算核心，只负责返回最后的数值结果。正式计算前，程序还会先跑小规模 checkpoint 和一个小范围的暴力交叉验证。
记
$$M=\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\sqrt{N/2}\right\rfloor\right).$$
构造到 \(M\) 为止的最小素因子筛需要 \(O(M\log\log M)\) 时间和 \(O(M)\) 内存。平方自由因子缓存一共包含 \(\sum_{k\le M}2^{\omega(k)}\) 个条目，其平均数量级是 \(O(M\log M)\)，因此它在实际中主导内存占用。
主求和的外层只跑到 \(\sqrt N\) 量级，而不是跑到 \(N\)。对每个缓存条目，剩余工作是一个按商值分块的 floor-sum，而不是对所有分母做线性扫描。严格写出最坏情形会比较繁琐，因为它同时依赖平方自由因子分布和商值块的长度，但从程序结构看，实际表现接近 \(N^{1/2+o(1)}\)，远好于按定义暴力求解的二次复杂度。
Для каждого положительного целого \(n\) определим
$$a(n)=\#\left\{d\in\mathbb{Z}_{>0}: d\mid 2n^2,\ d\le n\right\}.$$
Требуется вычислить
$$F(N)=\sum_{n=1}^{N} a(n).$$
Прямой перебор проверял бы все \(d\le n\) для каждого \(n\le N\), что слишком дорого для большого значения \(N\). Быстрый метод считает допустимые пары \((n,d)\) структурно, убирает условия взаимной простоты через функцию Мёбиуса и ускоряет оставшиеся суммы блоками одинакового частного.
Вместо отдельного поиска делителей для каждого \(n\) удобнее сразу считать все пары \((n,d)\), удовлетворяющие условиям.
По определению \(F(N)\) равно числу пар \((n,d)\), для которых
$$1\le n\le N,\qquad d\mid 2n^2,\qquad d\le n.$$
То есть
$$F(N)=\#\left\{(n,d):1\le n\le N,\ d\mid 2n^2,\ d\le n\right\}.$$
Неравенство \(d\le n\) и условие делимости удобно анализировать через \(\gcd(n,d)\).
Для любой учитываемой пары положим
$$g=\gcd(n,d),\qquad n=g\,m,\qquad d=g\,u,\qquad \gcd(m,u)=1.$$
Из условия \(d\le n\) сразу следует
$$u\le m.$$
Кроме того, из \(d\mid 2n^2\) получаем
$$g\,u \mid 2g^2m^2,$$
а после сокращения на \(g\)
$$u\mid 2g\,m^2.$$
Так как \(\gcd(u,m)=1\), простые множители \(u\) не могут прийти из \(m\); значит, все они должны сидеть в \(2g\). Следовательно, на самом деле
$$u\mid 2g.$$
Отсюда естественным образом возникают две ветви: нечетная и четная.
Если \(u\) нечетно, то из \(u\mid 2g\) сразу следует \(u\mid g\). Поэтому пишем
$$g=u\,t.$$
Тогда
$$d=u^2t,\qquad n=u\,m\,t,\qquad \gcd(m,u)=1,\qquad m\ge u.$$
При фиксированных \(u\) и \(m\) параметр \(t\) может принимать
$$\left\lfloor\frac{N}{u m}\right\rfloor$$
положительных значений. Значит, вклад нечетной ветви равен
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{\substack{m\ge u\\ \gcd(m,u)=1}}\left\lfloor\frac{N}{u m}\right\rfloor.$$
Ограничение \(u\le \sqrt N\) автоматически следует из \(n=u m t\ge u^2\).
Если \(u\) четно, пишем
$$u=2w.$$
Тогда условие \(u\mid 2g\) превращается в \(w\mid g\), то есть можно положить
$$g=w\,t.$$
После подстановки получаем
$$d=2w^2t,\qquad n=w\,m\,t,\qquad \gcd(m,2w)=1,\qquad m\ge 2w.$$
Это означает, что \(m\) обязано быть нечетным и взаимно простым с \(w\). Для фиксированных \(w\) и \(m\) число возможных \(t\) равно
$$\left\lfloor\frac{N}{w m}\right\rfloor.$$
Поэтому
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{m\ge 2w\\ m\text{ odd}\\ \gcd(m,w)=1}}\left\lfloor\frac{N}{w m}\right\rfloor.$$
И полный ответ имеет вид
$$F(N)=C_{\mathrm{odd}}(N)+C_{\mathrm{even}}(N).$$
Условие \(\gcd(\cdot,\cdot)=1\) устраняется с помощью тождества
$$[\gcd(x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d).$$
Для нечетной ветви это дает
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{d\mid u}^{\mathrm{sqfree}}\mu(d)\sum_{r\ge \lceil u/d\rceil}\left\lfloor\frac{\left\lfloor N/(ud)\right\rfloor}{r}\right\rfloor.$$
Здесь \(d\) пробегает квадратсвободные делители числа \(u\), а \(m\) переписано как \(m=d r\).
Для четной ветви нужны только нечетные квадратсвободные делители, потому что \(m\) уже нечетно:
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{d\mid w\\ d\text{ odd}}}^{\mathrm{sqfree}}\mu(d)\sum_{\substack{r\ge \lceil 2w/d\rceil\\ r\text{ odd}}}\left\lfloor\frac{\left\lfloor N/(wd)\right\rfloor}{r}\right\rfloor.$$
Именно эти две семейства сумм и вычисляет программа.
Определим хвостовую floor-сумму
$$\operatorname{FS}(X,L)=\sum_{m=L}^{X}\left\lfloor\frac{X}{m}\right\rfloor.$$
Тогда сумма только по нечетным \(m\) выражается так:
$$\sum_{\substack{m\ge L\\ m\text{ odd}}}\left\lfloor\frac{X}{m}\right\rfloor=\operatorname{FS}(X,L)-\operatorname{FS}\left(\left\lfloor\frac{X}{2}\right\rfloor,\left\lceil\frac{L}{2}\right\rceil\right).$$
Второй член вычитает все четные знаменатели. После этого четная ветвь сводится к тому же объекту, что и нечетная. Далее \(\operatorname{FS}(X,L)\) считается не по одному \(m\), а блоками, на которых значение \(\left\lfloor X/m\right\rfloor\) постоянно.
В реализации есть проверка малого значения \(F(15)=63\). Посмотрим, как оно получается из формул.
В нечетной ветви \(u\le \sqrt{15}\), значит, \(u=1\) или \(u=3\).
При \(u=1\) любое \(m\ge 1\) взаимно просто с \(1\), поэтому
$$\sum_{m=1}^{15}\left\lfloor\frac{15}{m}\right\rfloor=45.$$
При \(u=3\) требуется \(m\ge 3\), \(\gcd(m,3)=1\) и \(\left\lfloor 15/(3m)\right\rfloor>0\). Вклад дают только \(m=4\) и \(m=5\):
$$\left\lfloor\frac{15}{12}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=1+1=2.$$
Следовательно,
$$C_{\mathrm{odd}}(15)=45+2=47.$$
В четной ветви \(w\le \sqrt{15/2}\), то есть \(w=1,2\).
Для \(w=1\) подходят нечетные \(m\ge 2\): \(3,5,7,9,11,13,15\). Их суммарный вклад равен
$$\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{5}\right\rfloor+\left\lfloor\frac{15}{7}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor+\left\lfloor\frac{15}{11}\right\rfloor+\left\lfloor\frac{15}{13}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=14.$$
Для \(w=2\) остаются только \(m=5\) и \(m=7\):
$$\left\lfloor\frac{15}{10}\right\rfloor+\left\lfloor\frac{15}{14}\right\rfloor=1+1=2.$$
Значит,
$$C_{\mathrm{even}}(15)=14+2=16,$$
и в итоге
$$F(15)=47+16=63.$$
Реализации на C++, Python и Java используют одну и ту же математическую декомпозицию. Сначала вычисляются две внешние границы: \(\lfloor\sqrt N\rfloor\) для нечетной ветви и \(\lfloor\sqrt{N/2}\rfloor\) для четной.
Затем для каждого числа до этой границы заранее строится список всех его квадратсвободных делителей вместе со знаком функции Мёбиуса. Это делается через множество различных простых делителей каждого числа: любой их поднабор порождает один квадратсвободный делитель и знак \((-1)^k\).
Основной цикл проходит по нечетной и четной ветвям в точном соответствии с выведенными формулами. Каждая внутренняя хвостовая сумма сводится к \(\operatorname{FS}(X,L)\). Сама \(\operatorname{FS}(X,L)\) вычисляется не по одному знаменателю, а целыми блоками соседних значений, на которых \(\left\lfloor X/m\right\rfloor\) одинаково.
Для больших входных данных реализация на C++ умеет разбивать диапазоны нечетной и четной ветвей на независимые блоки и обрабатывать их параллельно. Реализации на Python и Java используют тот же оптимизированный нативный расчет и просто возвращают итоговый числовой результат. Перед большим запуском программа также проверяет несколько малых контрольных значений и сверяется с прямым перебором на небольшом пределе.
Пусть
$$M=\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\sqrt{N/2}\right\rfloor\right).$$
Построение решета наименьшего простого делителя до \(M\) требует \(O(M\log\log M)\) времени и \(O(M)\) памяти. Кэш квадратсвободных делителей содержит \(\sum_{k\le M}2^{\omega(k)}\) записей; его средний порядок равен \(O(M\log M)\), и именно он практически определяет память.
Обе внешние суммы идут только до порядка \(\sqrt N\), а не до \(N\). Для каждой записи кэша оставшаяся работа представляет собой floor-сумму, вычисляемую блоками одинакового частного, а не линейным перебором всех знаменателей. Точный худший случай неудобно записывать из-за зависимости и от структуры делителей, и от длин блоков, но на практике поведение близко к \(N^{1/2+o(1)}\), что на порядки лучше квадратичного определения через brute force.
لكل عدد صحيح موجب \(n\) نعرّف
$$a(n)=\#\left\{d\in\mathbb{Z}_{>0}: d\mid 2n^2,\ d\le n\right\}.$$
والمطلوب هو حساب
$$F(N)=\sum_{n=1}^{N} a(n).$$
الطريقة المباشرة ستجرب كل \(d\le n\) لكل \(n\le N\)، وهذا بطيء جدا عندما يكون \(N\) كبيرا. الفكرة الفعالة هي عد جميع الأزواج الصحيحة \((n,d)\) دفعة واحدة، ثم إزالة شروط التباين النسبي باستعمال دالة Möbius، وبعد ذلك تسريع المجاميع الباقية بواسطة تجميع حدود القسمة الصحيحة في كتل.
بدلا من البحث عن القواسم لكل \(n\) على حدة، من الأفضل عد كل الأزواج \((n,d)\) التي تحقق الشروط مرة واحدة.
بحسب التعريف فإن \(F(N)\) يساوي عدد الأزواج \((n,d)\) التي تحقق
$$1\le n\le N,\qquad d\mid 2n^2,\qquad d\le n.$$
إذن يمكن كتابة
$$F(N)=\#\left\{(n,d):1\le n\le N,\ d\mid 2n^2,\ d\le n\right\}.$$
الشرطان \(d\le n\) و \(d\mid 2n^2\) يصبحان أوضح بكثير إذا فصلنا القاسم المشترك الأكبر بين \(n\) و \(d\).
لكل زوج محسوب نضع
$$g=\gcd(n,d),\qquad n=g\,m,\qquad d=g\,u,\qquad \gcd(m,u)=1.$$
ومن الشرط \(d\le n\) نحصل مباشرة على
$$u\le m.$$
كذلك فإن \(d\mid 2n^2\) يعطي
$$g\,u \mid 2g^2m^2,$$
وبعد القسمة على \(g\) نحصل على
$$u\mid 2g\,m^2.$$
لكن بما أن \(\gcd(m,u)=1\)، فلا يمكن أن تأتي العوامل الأولية لـ \(u\) من \(m\)، ولذلك يجب أن تكون كلها موجودة داخل \(2g\). أي أن
$$u\mid 2g.$$
ومن هنا ينقسم العد طبيعيا إلى فرع فردي وفرع زوجي.
إذا كان \(u\) فرديا، فإن الشرط \(u\mid 2g\) يفرض مباشرة \(u\mid g\). لذا نكتب
$$g=u\,t.$$
وعندئذ يصبح
$$d=u^2t,\qquad n=u\,m\,t,\qquad \gcd(m,u)=1,\qquad m\ge u.$$
عند تثبيت \(u\) و \(m\)، يكون عدد القيم الممكنة لـ \(t\) هو
$$\left\lfloor\frac{N}{u m}\right\rfloor.$$
إذن مساهمة الفرع الفردي تساوي
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{\substack{m\ge u\\ \gcd(m,u)=1}}\left\lfloor\frac{N}{u m}\right\rfloor.$$
والحد \(u\le \sqrt N\) يأتي من العلاقة \(n=u m t\ge u^2\).
إذا كان \(u\) زوجيا، نكتب
$$u=2w.$$
وعندها يتحول الشرط \(u\mid 2g\) إلى \(w\mid g\)، ومن ثم يمكن أخذ
$$g=w\,t.$$
فنحصل على
$$d=2w^2t,\qquad n=w\,m\,t,\qquad \gcd(m,2w)=1,\qquad m\ge 2w.$$
وهذا يعني بالخصوص أن \(m\) يجب أن يكون فرديا وأن يحقق أيضا \(\gcd(m,w)=1\). ولأي \(w\) و \(m\) ثابتين يكون عدد القيم الممكنة لـ \(t\)
$$\left\lfloor\frac{N}{w m}\right\rfloor.$$
إذن مساهمة الفرع الزوجي هي
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{m\ge 2w\\ m\text{ odd}\\ \gcd(m,w)=1}}\left\lfloor\frac{N}{w m}\right\rfloor.$$
والنتيجة النهائية هي
$$F(N)=C_{\mathrm{odd}}(N)+C_{\mathrm{even}}(N).$$
العقبة الباقية هي شرط \(\gcd(\cdot,\cdot)=1\). ويزال هذا الشرط بالهوية
$$[\gcd(x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d).$$
بتطبيقها على الفرع الفردي نحصل على
$$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{d\mid u}^{\mathrm{sqfree}}\mu(d)\sum_{r\ge \lceil u/d\rceil}\left\lfloor\frac{\left\lfloor N/(ud)\right\rfloor}{r}\right\rfloor.$$
هنا يجري \(d\) على القواسم الخالية من المربعات لـ \(u\)، وقد كتبنا \(m=d r\).
أما في الفرع الزوجي فتكفي القواسم الفردية الخالية من المربعات، لأن \(m\) نفسه فردي أصلا:
$$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{d\mid w\\ d\text{ odd}}}^{\mathrm{sqfree}}\mu(d)\sum_{\substack{r\ge \lceil 2w/d\rceil\\ r\text{ odd}}}\left\lfloor\frac{\left\lfloor N/(wd)\right\rfloor}{r}\right\rfloor.$$
وهاتان هما عائلتا المجاميع اللتان تنفذهما الخوارزمية فعليا.
لنعرّف
$$\operatorname{FS}(X,L)=\sum_{m=L}^{X}\left\lfloor\frac{X}{m}\right\rfloor.$$
عندئذ يكون مجموع المقامات الفردية فقط مساويا لـ
$$\sum_{\substack{m\ge L\\ m\text{ odd}}}\left\lfloor\frac{X}{m}\right\rfloor=\operatorname{FS}(X,L)-\operatorname{FS}\left(\left\lfloor\frac{X}{2}\right\rfloor,\left\lceil\frac{L}{2}\right\rceil\right).$$
الحد الثاني يزيل بدقة جميع المقامات الزوجية. وهكذا يعود الفرع الزوجي إلى النوع نفسه من floor-sum الموجود في الفرع الفردي. ثم تحسب \(\operatorname{FS}(X,L)\) بدمج الفترات التي يبقى فيها \(\left\lfloor X/m\right\rfloor\) ثابتا.
تتحقق الخوارزمية من القيمة الصغيرة \(F(15)=63\). ويمكن رؤية ذلك مباشرة من الفرعين.
في الفرع الفردي لدينا \(u\le \sqrt{15}\)، أي \(u=1\) أو \(u=3\).
عندما \(u=1\)، فإن كل \(m\ge 1\) مناسب، ولذلك
$$\sum_{m=1}^{15}\left\lfloor\frac{15}{m}\right\rfloor=45.$$
وعندما \(u=3\)، نحتاج إلى \(m\ge 3\) و \(\gcd(m,3)=1\) وأن يكون \(\left\lfloor 15/(3m)\right\rfloor>0\). ولا يساهم إلا \(m=4\) و \(m=5\):
$$\left\lfloor\frac{15}{12}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=1+1=2.$$
إذن
$$C_{\mathrm{odd}}(15)=45+2=47.$$
في الفرع الزوجي لدينا \(w\le \sqrt{15/2}\)، أي \(w=1,2\).
عند \(w=1\)، القيم الفردية \(m\ge 2\) التي تساهم هي \(3,5,7,9,11,13,15\)، ومجموعها
$$\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{5}\right\rfloor+\left\lfloor\frac{15}{7}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor+\left\lfloor\frac{15}{11}\right\rfloor+\left\lfloor\frac{15}{13}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=14.$$
وعند \(w=2\)، لا يبقى إلا \(m=5\) و \(m=7\):
$$\left\lfloor\frac{15}{10}\right\rfloor+\left\lfloor\frac{15}{14}\right\rfloor=1+1=2.$$
ومن ثم
$$C_{\mathrm{even}}(15)=14+2=16,$$
وأخيرا
$$F(15)=47+16=63.$$
تنطلق تطبيقات C++ و Python و Java من التفكيك الرياضي نفسه. أولا تحسب حدّي الحلقات الخارجيتين: \(\lfloor\sqrt N\rfloor\) للفرع الفردي و \(\lfloor\sqrt{N/2}\rfloor\) للفرع الزوجي.
بعد ذلك يجري تحضير جميع القواسم الخالية من المربعات حتى هذا الحد، مع إشارة Möbius الموافقة لكل واحد منها. ويتم هذا انطلاقا من العوامل الأولية المختلفة لكل عدد؛ فكل مجموعة جزئية من هذه العوامل تعطي قاسما خاليا من المربعات وإشارة \((-1)^k\).
في المجموع الرئيسي تطبق الخوارزمية صيغ الفرعين الفردي والزوجي كما هي. كل مجموع داخلي يحوّل إلى \(\operatorname{FS}(X,L)\). وهذه الدالة لا تحسب على شكل مرور خطي على كل مقام، بل بتجميع المقامات المتتالية التي تعطي القيمة نفسها لـ \(\left\lfloor X/m\right\rfloor\).
للمدخلات الكبيرة يمكن لتطبيق C++ أن يقسم مجالي الفرعين إلى كتل مستقلة ويحسبها بالتوازي. أما تطبيقا Python و Java فيستخدمان الحساب الأصلي المحسن نفسه ويعيدان الناتج العددي النهائي فقط. وقبل التشغيل الكامل، يجري البرنامج أيضا اختبارات تحقق صغيرة ومقارنة مباشرة مع العد brute-force على حد صغير.
لنكتب
$$M=\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\sqrt{N/2}\right\rfloor\right).$$
بناء منخل أصغر عامل أولي حتى \(M\) يحتاج إلى زمن \(O(M\log\log M)\) وذاكرة \(O(M)\). أما مخزن القواسم الخالية من المربعات فيحتوي على \(\sum_{k\le M}2^{\omega(k)}\) مدخلا، ورتبته المتوسطة \(O(M\log M)\)، ولذلك فهو يهيمن عمليا على استهلاك الذاكرة.
الحلقتان الخارجيتان لا تصلان إلى \(N\) بل إلى رتبة \(\sqrt N\) فقط. ولكل مدخل في هذا المخزن، يكون العمل المتبقي عبارة عن floor-sum محسوب بكتل ذات خارج ثابت، وليس مسحا خطيا لكل المقامات. الصياغة الدقيقة لأسوأ حالة معقدة لأنها تعتمد على بنية القواسم وأطوال الكتل معا، لكن السلوك العملي قريب من \(N^{1/2+o(1)}\)، وهو أفضل بكثير من التعريف التربيعي المباشر.