For every ordered pair \((x,y)\) with \(2 \le x,y \le N\), the problem asks for the number \(D(N)\) of distinct proto-logarithmic values that can occur. The central observation used by the C++, Python, and Java implementations is that every integer \(n \ge 2\) has a unique canonical form
$$n=r^k,$$
where \(r\) is not a perfect power and \(k \ge 1\) is maximal. Once both inputs are rewritten in that form, all duplicates are controlled by primitive bases and by reduced exponent ratios, so the count can be expressed using only \(L=\lfloor \log_2 N \rfloor\) and some short arithmetic tables.
We write the final answer as
$$D(N)=\operatorname{Rat}(N)+\operatorname{Irr}(N),$$
where the first term counts values from the equal-base branch and the second counts values from the distinct-base branch.
Every integer \(n \ge 2\) can be written uniquely as \(n=r^k\) with \(r\) not a perfect power. Call such an \(r\) a primitive base. For a fixed primitive base \(r\), define its exponent capacity by
$$A(r)=\max\{e \ge 1 : r^e \le N\}.$$
So the numbers generated by \(r\) inside the range \([2,N]\) are exactly
$$r,r^2,\dots,r^{A(r)}.$$
If we rewrite an ordered pair as
$$x=r^u,\qquad y=s^v,$$
with \(1 \le u \le A(r)\) and \(1 \le v \le A(s)\), then the problem depends only on the ordered primitive bases \((r,s)\) and on the reduced fraction \(v/u\). This mirrors the usual identity
$$\log_{r^u}(s^v)=\frac{v}{u}\cdot\frac{\log s}{\log r},$$
which explains why the equal-base branch becomes rational and the distinct-base branch behaves like an irrational family indexed by \((r,s)\).
Let
$$U(M)=\#\{r \in \mathbb{Z}_{\ge 2} : r \le M,\ \forall a,b \in \mathbb{Z}_{\ge 2},\ r \ne a^b\}.$$
Every integer in \([2,M]\) has a unique representation \(r^e\) with primitive base \(r\), so counting all integers up to \(M\) gives
$$M-1=\sum_{e=1}^{\lfloor \log_2 M \rfloor} U\!\left(\left\lfloor M^{1/e}\right\rfloor\right).$$
Applying Möbius inversion yields the exact formula
$$U(M)=\sum_{d=1}^{\lfloor \log_2 M \rfloor} \mu(d)\left(\left\lfloor M^{1/d}\right\rfloor-1\right).$$
Now define \(B_A(N)\) to be the number of primitive bases whose exponent capacity is exactly \(A\). Then
$$B_A(N)=U\!\left(\left\lfloor N^{1/A}\right\rfloor\right)-U\!\left(\left\lfloor N^{1/(A+1)}\right\rfloor\right).$$
This partitions all primitive bases according to the largest exponent they can support inside the range.
For fixed bounds \(A\) and \(B\), define
$$Q(A,B)=\#\{(u,v): 1 \le u \le A,\ 1 \le v \le B,\ \gcd(u,v)=1\}.$$
This is exactly the number of distinct reduced fractions \(v/u\) that can appear when the denominator exponent is at most \(A\) and the numerator exponent is at most \(B\).
Using the standard Möbius count of visible lattice points,
$$Q(A,B)=\sum_{d=1}^{\min(A,B)} \mu(d)\left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor.$$
The implementations precompute this entire table once for all \(1 \le A,B \le L\), where
$$L=\lfloor \log_2 N \rfloor.$$
When the primitive bases coincide, say \(r=s\), the value depends only on the reduced fraction \(v/u\). Therefore the total number of distinct rational values is exactly the number of reduced positive fractions with both numerator and denominator at most \(L\):
$$\operatorname{Rat}(N)=Q(L,L).$$
This works because the primitive base \(2\) alone already supports exponents \(1,2,\dots,L\), since \(2^L \le N\) by definition of \(L\).
When \(r \ne s\), the value belongs to the distinct-base branch. For a fixed ordered pair of primitive bases \((r,s)\), the only collisions come from reducing the fraction \(v/u\), so that pair contributes exactly \(Q(A(r),A(s))\) distinct values.
How many ordered primitive-base pairs have capacities \(A\) and \(B\)? If \(A \ne B\), the capacities already force different bases, so the count is
$$P_{A,B}(N)=B_A(N)\,B_B(N).$$
If \(A=B\), we must exclude choosing the same primitive base twice, so
$$P_{A,A}(N)=B_A(N)\bigl(B_A(N)-1\bigr).$$
Hence the entire irrational branch is
$$\operatorname{Irr}(N)=\sum_{A=1}^{L}\sum_{B=1}^{L} P_{A,B}(N)\,Q(A,B).$$
Here \(L=\lfloor \log_2 5 \rfloor=2\). The primitive bases not exceeding \(5\) are \(2,3,5\). Their exponent capacities are
$$A(2)=2,\qquad A(3)=1,\qquad A(5)=1.$$
So the capacity classes are
$$B_1(5)=2,\qquad B_2(5)=1.$$
The reduced-ratio counts are
$$Q(1,1)=1,\qquad Q(1,2)=2,\qquad Q(2,1)=2,\qquad Q(2,2)=3.$$
The rational branch contributes
$$\operatorname{Rat}(5)=Q(2,2)=3,$$
corresponding to the reduced fractions \(1\), \(2\), and \(1/2\).
For the irrational branch, the ordered-pair counts are
$$P_{1,1}(5)=2,\qquad P_{1,2}(5)=2,\qquad P_{2,1}(5)=2,\qquad P_{2,2}(5)=0.$$
Therefore
$$\operatorname{Irr}(5)=2 \cdot 1 + 2 \cdot 2 + 2 \cdot 2 = 10,$$
and the total is
$$D(5)=3+10=13.$$
This matches the first exact checkpoint used by the implementations.
The C++, Python, and Java implementations first compute \(L=\lfloor \log_2 N \rfloor\) and build the Möbius values \(\mu(1),\dots,\mu(L)\) with a sieve. Because all later formulas depend only on exponent bounds up to \(L\), this immediately compresses the problem from a search over numbers up to \(N\) into a search over exponents up to roughly \(60\) for the target input.
Next, the implementation evaluates exact integer \(k\)-th roots such as \(\lfloor N^{1/k} \rfloor\). It starts from a floating-point estimate and then corrects it with integer power checks, so no rounding error leaks into the Möbius sums. Those exact roots feed the formula for \(U(M)\), and from there the code derives every \(B_A(N)\).
After that, the implementation fills the table \(Q(A,B)\) for all \(1 \le A,B \le L\) using the Möbius formula for coprime exponent pairs. Once this table exists, the rational part is just the single lookup \(Q(L,L)\).
The remaining work is the double sum for the irrational part. Off the diagonal \(A \ne B\), the number of ordered base pairs is \(B_A(N)B_B(N)\). On the diagonal, the code uses \(B_A(N)(B_A(N)-1)\) so that a primitive base is not paired with itself in the distinct-base branch.
For the full target \(N=10^{18}\), the answer is reported modulo \(10^9\). For smaller checkpoints, the implementations also support exact arithmetic, and the built-in validations verify values such as \(D(5)=13\), \(D(10)=69\), \(D(100)=9607\), and \(D(10000)=99959605\).
Let \(L=\lfloor \log_2 N \rfloor\). The Möbius sieve is \(O(L)\). Building the coprime-ratio table requires
$$\sum_{A=1}^{L}\sum_{B=1}^{L} O(\min(A,B))=O(L^3)$$
operations and is the dominant asymptotic cost in the local implementations. The final irrational double sum is \(O(L^2)\), and the storage cost is \(O(L^2)\) because the \(Q(A,B)\) table is kept in memory. For the target input \(N=10^{18}\), we only have \(L=59\), so the method is easily fast enough.
Für jedes geordnete Paar \((x,y)\) mit \(2 \le x,y \le N\) soll die Anzahl \(D(N)\) verschiedener proto-logarithmischer Werte bestimmt werden. Die zentrale Beobachtung der C++-, Python- und Java-Implementierungen ist, dass jede ganze Zahl \(n \ge 2\) eine eindeutige kanonische Form
$$n=r^k$$
besitzt, wobei \(r\) keine perfekte Potenz ist und \(k \ge 1\) maximal gewählt wird. Nach dieser Normalisierung hängen alle Kollisionen nur noch von primitiven Basen und vom gekürzten Exponentenverhältnis ab. Dadurch schrumpft die Aufgabe auf Rechnungen mit \(L=\lfloor \log_2 N \rfloor\) und einigen kleinen Tabellen.
Wir zerlegen die Antwort in
$$D(N)=\operatorname{Rat}(N)+\operatorname{Irr}(N),$$
wobei der erste Term den gleichbasigen Zweig und der zweite Term den verschiedenbasigen Zweig zählt.
Jede ganze Zahl \(n \ge 2\) lässt sich eindeutig als \(n=r^k\) schreiben, wobei \(r\) keine perfekte Potenz ist. Ein solches \(r\) nennen wir eine primitive Basis. Für eine feste primitive Basis \(r\) definieren wir ihre Exponentenkapazität durch
$$A(r)=\max\{e \ge 1 : r^e \le N\}.$$
Die von \(r\) im Bereich \([2,N]\) erzeugten Zahlen sind also genau
$$r,r^2,\dots,r^{A(r)}.$$
Schreibt man ein geordnetes Paar als
$$x=r^u,\qquad y=s^v,$$
mit \(1 \le u \le A(r)\) und \(1 \le v \le A(s)\), dann hängt das Problem nur noch vom geordneten Paar primitiver Basen \((r,s)\) und vom gekürzten Bruch \(v/u\) ab. Das spiegelt die übliche Identität
$$\log_{r^u}(s^v)=\frac{v}{u}\cdot\frac{\log s}{\log r}$$
wider und erklärt, warum der gleichbasige Fall rational und der verschiedenbasige Fall eine irrationale Familie bildet.
Setze
$$U(M)=\#\{r \in \mathbb{Z}_{\ge 2} : r \le M,\ \forall a,b \in \mathbb{Z}_{\ge 2},\ r \ne a^b\}.$$
Jede Zahl in \([2,M]\) hat genau eine Darstellung \(r^e\) mit primitiver Basis \(r\). Daher gilt
$$M-1=\sum_{e=1}^{\lfloor \log_2 M \rfloor} U\!\left(\left\lfloor M^{1/e}\right\rfloor\right).$$
Mit Möbius-Inversion folgt die exakte Formel
$$U(M)=\sum_{d=1}^{\lfloor \log_2 M \rfloor} \mu(d)\left(\left\lfloor M^{1/d}\right\rfloor-1\right).$$
Sei nun \(B_A(N)\) die Anzahl primitiver Basen mit Exponentenkapazität genau \(A\). Dann ist
$$B_A(N)=U\!\left(\left\lfloor N^{1/A}\right\rfloor\right)-U\!\left(\left\lfloor N^{1/(A+1)}\right\rfloor\right).$$
Damit werden alle primitiven Basen nach dem größten im Bereich erlaubten Exponenten klassifiziert.
Für feste Schranken \(A\) und \(B\) definieren wir
$$Q(A,B)=\#\{(u,v): 1 \le u \le A,\ 1 \le v \le B,\ \gcd(u,v)=1\}.$$
Das ist genau die Anzahl verschiedener gekürzter Brüche \(v/u\), die bei Nennerexponenten bis \(A\) und Zählerexponenten bis \(B\) auftreten können.
Mit der Standardformel für sichtbare Gitterpunkte erhält man
$$Q(A,B)=\sum_{d=1}^{\min(A,B)} \mu(d)\left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor.$$
Diese gesamte Tabelle wird für alle \(1 \le A,B \le L\) vorab berechnet, wobei
$$L=\lfloor \log_2 N \rfloor.$$
Wenn die primitiven Basen gleich sind, also \(r=s\), hängt der Wert nur vom gekürzten Bruch \(v/u\) ab. Deshalb ist die Anzahl verschiedener rationaler Werte genau die Zahl reduzierter positiver Brüche mit Zähler und Nenner höchstens \(L\):
$$\operatorname{Rat}(N)=Q(L,L).$$
Dass dies genügt, liegt daran, dass schon die primitive Basis \(2\) alle Exponenten \(1,2,\dots,L\) realisieren kann, weil \(2^L \le N\) gilt.
Wenn \(r \ne s\), befindet man sich im verschiedenbasigen Zweig. Für ein festes geordnetes Paar primitiver Basen \((r,s)\) entstehen Kollisionen nur durch Kürzen des Bruchs \(v/u\), also liefert dieses Paar genau \(Q(A(r),A(s))\) verschiedene Werte.
Wie viele geordnete primitive Basenpaare haben Kapazitäten \(A\) und \(B\)? Für \(A \ne B\) erzwingen die Kapazitäten bereits verschiedene Basen, also
$$P_{A,B}(N)=B_A(N)\,B_B(N).$$
Für \(A=B\) muss die Wahl derselben primitiven Basis ausgeschlossen werden, daher
$$P_{A,A}(N)=B_A(N)\bigl(B_A(N)-1\bigr).$$
Damit ist der gesamte irrationale Anteil
$$\operatorname{Irr}(N)=\sum_{A=1}^{L}\sum_{B=1}^{L} P_{A,B}(N)\,Q(A,B).$$
Hier ist \(L=\lfloor \log_2 5 \rfloor=2\). Die primitiven Basen bis \(5\) sind \(2,3,5\). Ihre Exponentenkapazitäten lauten
$$A(2)=2,\qquad A(3)=1,\qquad A(5)=1.$$
Also sind die Kapazitätsklassen
$$B_1(5)=2,\qquad B_2(5)=1.$$
Für die reduzierten Exponentenverhältnisse gilt
$$Q(1,1)=1,\qquad Q(1,2)=2,\qquad Q(2,1)=2,\qquad Q(2,2)=3.$$
Der rationale Zweig liefert
$$\operatorname{Rat}(5)=Q(2,2)=3,$$
also die Werte \(1\), \(2\) und \(1/2\).
Für den irrationalen Zweig sind die geordneten Paarzahlen
$$P_{1,1}(5)=2,\qquad P_{1,2}(5)=2,\qquad P_{2,1}(5)=2,\qquad P_{2,2}(5)=0.$$
Folglich
$$\operatorname{Irr}(5)=2 \cdot 1 + 2 \cdot 2 + 2 \cdot 2 = 10,$$
und insgesamt
$$D(5)=3+10=13.$$
Das ist genau der erste exakte Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen berechnen zuerst \(L=\lfloor \log_2 N \rfloor\) und erzeugen mit einem Sieb die Werte \(\mu(1),\dots,\mu(L)\). Da alle späteren Formeln nur Exponentengrenzen bis \(L\) verwenden, wird das Problem damit von Zahlen bis \(N\) auf Exponenten bis ungefähr \(60\) für die Zieleingabe reduziert.
Anschließend berechnet die Implementierung exakte ganzzahlige \(k\)-te Wurzeln wie \(\lfloor N^{1/k} \rfloor\). Sie startet mit einer Gleitkomma-Näherung und korrigiert diese mit ganzzahligen Potenztests, damit keine Rundungsfehler in die Möbius-Summen gelangen. Diese exakten Wurzeln speisen die Formel für \(U(M)\), aus der dann alle \(B_A(N)\) folgen.
Danach wird die gesamte Tabelle \(Q(A,B)\) für \(1 \le A,B \le L\) über die Möbius-Formel für teilerfremde Exponentenpaare aufgebaut. Ist diese Tabelle vorhanden, ist der rationale Anteil einfach der einzelne Tabellenwert \(Q(L,L)\).
Die restliche Arbeit ist die Doppelsumme des irrationalen Anteils. Außerhalb der Diagonale \(A \ne B\) ist die Anzahl geordneter Basenpaare \(B_A(N)B_B(N)\). Auf der Diagonale verwendet der Code \(B_A(N)(B_A(N)-1)\), damit eine primitive Basis im verschiedenbasigen Zweig nicht mit sich selbst gepaart wird.
Für das volle Ziel \(N=10^{18}\) wird das Ergebnis modulo \(10^9\) ausgegeben. Für kleinere Kontrollwerte unterstützen die Implementierungen auch exakte Arithmetik; geprüft werden unter anderem \(D(5)=13\), \(D(10)=69\), \(D(100)=9607\) und \(D(10000)=99959605\).
Mit \(L=\lfloor \log_2 N \rfloor\) kostet das Möbius-Sieb \(O(L)\). Der Aufbau der Tabelle der teilerfremden Exponentenverhältnisse benötigt
$$\sum_{A=1}^{L}\sum_{B=1}^{L} O(\min(A,B))=O(L^3)$$
Operationen und dominiert damit die asymptotische Laufzeit der lokalen Implementierungen. Die abschließende Doppelsumme für den irrationalen Anteil kostet \(O(L^2)\), und der Speicherbedarf beträgt \(O(L^2)\), weil die Tabelle \(Q(A,B)\) gespeichert wird. Für die Zieleingabe \(N=10^{18}\) ist \(L=59\), also bleibt die Methode sehr leichtgewichtig.
\(2 \le x,y \le N\) koşulunu sağlayan her sıralı \((x,y)\) çifti için, problem farklı proto-logaritmik değerlerin sayısı olan \(D(N)\)'yi istiyor. C++, Python ve Java uygulamalarının kullandığı temel gözlem, her \(n \ge 2\) tamsayısının
$$n=r^k$$
şeklinde tekil bir kanonik gösterime sahip olmasıdır; burada \(r\) perfect power değildir ve \(k \ge 1\) mümkün olan en büyük üstür. İki giriş bu biçime çevrildiğinde bütün çakışmalar yalnızca ilkel tabanlara ve sadeleşmiş üs oranlarına bağlı kalır. Böylece devasa arama uzayı, \(L=\lfloor \log_2 N \rfloor\) ve birkaç küçük tabloyla çözülebilen bir sayım problemine dönüşür.
Nihai cevabı
$$D(N)=\operatorname{Rat}(N)+\operatorname{Irr}(N)$$
şeklinde ayıracağız. İlk terim aynı tabanlı dalı, ikinci terim farklı tabanlı dalı sayar.
Her \(n \ge 2\) sayısı, \(r\) perfect power olmayacak şekilde tekil olarak \(n=r^k\) biçiminde yazılır. Böyle bir \(r\)'ye ilkel taban diyelim. Sabit bir ilkel taban \(r\) için üs kapasitesini
$$A(r)=\max\{e \ge 1 : r^e \le N\}$$
diye tanımlayalım. O halde \(r\)'nin \([2,N]\) aralığında üretebildiği sayılar tam olarak
$$r,r^2,\dots,r^{A(r)}$$
olur. Bir sıralı çifti
$$x=r^u,\qquad y=s^v$$
biçiminde yazdığımızda, burada \(1 \le u \le A(r)\) ve \(1 \le v \le A(s)\), problem artık yalnızca sıralı ilkel taban çifti \((r,s)\) ile sadeleşmiş \(v/u\) kesrine bağlıdır. Bu durum
$$\log_{r^u}(s^v)=\frac{v}{u}\cdot\frac{\log s}{\log r}$$
özdeşliğini yansıtır; aynı tabanlı durumda neden rasyonel, farklı tabanlı durumda ise neden irrasyonel bir aile oluştuğunu açıklar.
Şunu tanımlayalım:
$$U(M)=\#\{r \in \mathbb{Z}_{\ge 2} : r \le M,\ \forall a,b \in \mathbb{Z}_{\ge 2},\ r \ne a^b\}.$$
\([2,M]\) aralığındaki her sayı tekil olarak bir ilkel tabanın kuvvetidir. Bu yüzden
$$M-1=\sum_{e=1}^{\lfloor \log_2 M \rfloor} U\!\left(\left\lfloor M^{1/e}\right\rfloor\right)$$
eşitliği elde edilir. Buna Möbius terslemesi uygularsak
$$U(M)=\sum_{d=1}^{\lfloor \log_2 M \rfloor} \mu(d)\left(\left\lfloor M^{1/d}\right\rfloor-1\right)$$
formülünü buluruz.
Şimdi \(B_A(N)\), üs kapasitesi tam olarak \(A\) olan ilkel tabanların sayısı olsun. O zaman
$$B_A(N)=U\!\left(\left\lfloor N^{1/A}\right\rfloor\right)-U\!\left(\left\lfloor N^{1/(A+1)}\right\rfloor\right)$$
olur. Böylece bütün ilkel tabanlar, aralık içinde destekleyebildikleri en büyük üse göre sınıflanmış olur.
Sabit \(A\) ve \(B\) sınırları için
$$Q(A,B)=\#\{(u,v): 1 \le u \le A,\ 1 \le v \le B,\ \gcd(u,v)=1\}$$
tanımını yapalım. Bu, pay en fazla \(B\), payda en fazla \(A\) olacak şekilde ortaya çıkabilecek farklı sadeleşmiş \(v/u\) kesirlerinin tam sayısıdır.
Görünür kafes noktaları için standart Möbius sayımı bize
$$Q(A,B)=\sum_{d=1}^{\min(A,B)} \mu(d)\left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor$$
formülünü verir. Uygulamalar bu tabloyu tüm \(1 \le A,B \le L\) için önceden hesaplar; burada
$$L=\lfloor \log_2 N \rfloor.$$
Eğer ilkel tabanlar aynıysa, yani \(r=s\), değer yalnızca sadeleşmiş \(v/u\) oranına bağlıdır. Dolayısıyla farklı rasyonel değerlerin toplam sayısı, payı ve paydası en fazla \(L\) olan indirgenmiş pozitif kesirlerin sayısıdır:
$$\operatorname{Rat}(N)=Q(L,L).$$
Bunun yeterli olmasının nedeni, yalnızca ilkel taban \(2\)'nin bile \(2^L \le N\) olduğundan \(1,2,\dots,L\) üslerinin hepsini sağlayabilmesidir.
Eğer \(r \ne s\) ise farklı tabanlı dala geçeriz. Sabit bir sıralı ilkel taban çifti \((r,s)\) için tek çakışma kaynağı \(v/u\) oranının sadeleşmesidir; dolayısıyla bu çift tam olarak \(Q(A(r),A(s))\) farklı değer üretir.
Peki kapasitesi \(A\) ve \(B\) olan sıralı ilkel taban çiftlerinin sayısı nedir? \(A \ne B\) olduğunda kapasite sınıfları zaten tabanların farklı olmasını zorunlu kılar, bu yüzden
$$P_{A,B}(N)=B_A(N)\,B_B(N).$$
\(A=B\) olduğunda ise aynı ilkel tabanı iki kez seçmeyi dışlamamız gerekir:
$$P_{A,A}(N)=B_A(N)\bigl(B_A(N)-1\bigr).$$
Böylece irrasyonel kısmın tamamı
$$\operatorname{Irr}(N)=\sum_{A=1}^{L}\sum_{B=1}^{L} P_{A,B}(N)\,Q(A,B)$$
şeklinde yazılır.
Burada \(L=\lfloor \log_2 5 \rfloor=2\). \(5\)'e kadar olan ilkel tabanlar \(2,3,5\)'tir. Bunların üs kapasiteleri
$$A(2)=2,\qquad A(3)=1,\qquad A(5)=1$$
olur. Dolayısıyla sınıflar
$$B_1(5)=2,\qquad B_2(5)=1$$
şeklindedir.
Sadeleşmiş oran sayıları ise
$$Q(1,1)=1,\qquad Q(1,2)=2,\qquad Q(2,1)=2,\qquad Q(2,2)=3$$
olarak bulunur.
Rasyonel dalın katkısı
$$\operatorname{Rat}(5)=Q(2,2)=3$$
olup bunlar \(1\), \(2\) ve \(1/2\) değerleridir.
İrrasyonel dal için sıralı çift sayıları
$$P_{1,1}(5)=2,\qquad P_{1,2}(5)=2,\qquad P_{2,1}(5)=2,\qquad P_{2,2}(5)=0$$
olur. Bu yüzden
$$\operatorname{Irr}(5)=2 \cdot 1 + 2 \cdot 2 + 2 \cdot 2 = 10$$
ve toplam sonuç
$$D(5)=3+10=13$$
çıkar. Bu, uygulamaların kullandığı ilk tam doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları önce \(L=\lfloor \log_2 N \rfloor\) değerini hesaplar ve \(\mu(1),\dots,\mu(L)\) değerlerini bir elek ile üretir. Sonraki tüm formüller yalnızca \(L\)'ye kadar üs sınırlarına bağlı olduğundan, sayı uzayı \(N\)'e kadar taranmak yerine yaklaşık \(60\)'lık bir üs uzayına sıkıştırılmış olur.
Ardından uygulama \(\lfloor N^{1/k} \rfloor\) gibi tam sayısal \(k\). kökleri hesaplar. Önce kayan noktalı bir tahmin alır, sonra bunu tam sayı kuvvet kontrolleriyle yukarı veya aşağı düzelterek yuvarlama hatalarının Möbius toplamlarına sızmasını engeller. Bu tam kökler, \(U(M)\) formülünde kullanılır ve oradan tüm \(B_A(N)\) değerleri elde edilir.
Sonraki adım, \(1 \le A,B \le L\) için tüm \(Q(A,B)\) tablosunu Möbius formülüyle doldurmaktır. Bu tablo hazır olduktan sonra rasyonel kısım yalnızca tek bir tablo okumasına, yani \(Q(L,L)\)'ye indirgenir.
Kalan iş irrasyonel kısım için çift toplamı yürütmektir. Köşegen dışı \(A \ne B\) durumunda sıralı taban çifti sayısı \(B_A(N)B_B(N)\) olur. Köşegen üzerinde ise aynı ilkel tabanın farklı tabanlı dalda kendisiyle eşleşmemesi için \(B_A(N)(B_A(N)-1)\) kullanılır.
Hedef giriş \(N=10^{18}\) için sonuç \(10^9\) modunda verilir. Daha küçük denetim noktalarında uygulamalar tam sayı aritmetiğiyle de çalışır; yerleşik doğrulamalar arasında \(D(5)=13\), \(D(10)=69\), \(D(100)=9607\) ve \(D(10000)=99959605\) bulunur.
\(L=\lfloor \log_2 N \rfloor\) olmak üzere Möbius eleği \(O(L)\) zamandadır. Aralarında asal üs oranları tablosunu kurmak için gereken işlem sayısı
$$\sum_{A=1}^{L}\sum_{B=1}^{L} O(\min(A,B))=O(L^3)$$
olur ve yerel uygulamalarda asimptotik olarak baskın maliyet budur. Son irrasyonel çift toplamı \(O(L^2)\), bellek kullanımı ise \(Q(A,B)\) tablosu saklandığı için \(O(L^2)\)'dir. Hedef giriş \(N=10^{18}\) için \(L=59\) olduğundan yöntem pratikte son derece hafiftir.
Para cada par ordenado \((x,y)\) con \(2 \le x,y \le N\), el problema pide el número \(D(N)\) de valores proto-logarítmicos distintos que pueden aparecer. La observación central usada por las implementaciones en C++, Python y Java es que todo entero \(n \ge 2\) tiene una forma canónica única
$$n=r^k,$$
donde \(r\) no es una potencia perfecta y \(k \ge 1\) es máximo. Una vez que ambos argumentos se reescriben así, todas las colisiones quedan controladas únicamente por las bases primitivas y por la razón reducida de exponentes. Eso convierte una búsqueda gigantesca en un recuento corto basado en \(L=\lfloor \log_2 N \rfloor\).
Escribiremos la respuesta final como
$$D(N)=\operatorname{Rat}(N)+\operatorname{Irr}(N),$$
donde el primer término cuenta la rama con la misma base y el segundo la rama con bases distintas.
Todo entero \(n \ge 2\) se puede escribir de manera única como \(n=r^k\), con \(r\) no potencia perfecta. A tal \(r\) lo llamaremos base primitiva. Para una base primitiva fija \(r\), definimos su capacidad de exponente por
$$A(r)=\max\{e \ge 1 : r^e \le N\}.$$
Así, los números producidos por \(r\) dentro del rango \([2,N]\) son exactamente
$$r,r^2,\dots,r^{A(r)}.$$
Si reescribimos un par ordenado como
$$x=r^u,\qquad y=s^v,$$
con \(1 \le u \le A(r)\) y \(1 \le v \le A(s)\), entonces el problema depende solo del par ordenado de bases primitivas \((r,s)\) y de la fracción reducida \(v/u\). Esto refleja la identidad habitual
$$\log_{r^u}(s^v)=\frac{v}{u}\cdot\frac{\log s}{\log r},$$
que explica por qué la rama con la misma base es racional y la rama con bases distintas forma una familia irracional.
Definamos
$$U(M)=\#\{r \in \mathbb{Z}_{\ge 2} : r \le M,\ \forall a,b \in \mathbb{Z}_{\ge 2},\ r \ne a^b\}.$$
Cada entero en \([2,M]\) tiene una representación única \(r^e\) con base primitiva \(r\), por lo que
$$M-1=\sum_{e=1}^{\lfloor \log_2 M \rfloor} U\!\left(\left\lfloor M^{1/e}\right\rfloor\right).$$
Aplicando inversión de Möbius se obtiene la fórmula exacta
$$U(M)=\sum_{d=1}^{\lfloor \log_2 M \rfloor} \mu(d)\left(\left\lfloor M^{1/d}\right\rfloor-1\right).$$
Sea ahora \(B_A(N)\) el número de bases primitivas cuya capacidad de exponente es exactamente \(A\). Entonces
$$B_A(N)=U\!\left(\left\lfloor N^{1/A}\right\rfloor\right)-U\!\left(\left\lfloor N^{1/(A+1)}\right\rfloor\right).$$
Esto clasifica todas las bases primitivas según el mayor exponente que pueden sostener dentro del rango.
Para cotas fijas \(A\) y \(B\), definimos
$$Q(A,B)=\#\{(u,v): 1 \le u \le A,\ 1 \le v \le B,\ \gcd(u,v)=1\}.$$
Ese número coincide exactamente con la cantidad de fracciones reducidas distintas \(v/u\) que pueden aparecer cuando el exponente del denominador no supera \(A\) y el del numerador no supera \(B\).
Usando el recuento clásico de puntos visibles de la retícula,
$$Q(A,B)=\sum_{d=1}^{\min(A,B)} \mu(d)\left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor.$$
Las implementaciones precalculan toda esta tabla para \(1 \le A,B \le L\), donde
$$L=\lfloor \log_2 N \rfloor.$$
Cuando las bases primitivas coinciden, es decir, \(r=s\), el valor depende solo de la fracción reducida \(v/u\). Por eso, el número total de valores racionales distintos es exactamente el número de fracciones positivas reducidas con numerador y denominador a lo sumo \(L\):
$$\operatorname{Rat}(N)=Q(L,L).$$
Esto funciona porque la base primitiva \(2\) por sí sola ya admite los exponentes \(1,2,\dots,L\), pues \(2^L \le N\).
Cuando \(r \ne s\), estamos en la rama de bases distintas. Para un par ordenado fijo de bases primitivas \((r,s)\), las únicas colisiones internas vienen de reducir la fracción \(v/u\), así que ese par aporta exactamente \(Q(A(r),A(s))\) valores distintos.
¿Cuántos pares ordenados de bases primitivas tienen capacidades \(A\) y \(B\)? Si \(A \ne B\), las capacidades ya obligan a que las bases sean distintas, de modo que
$$P_{A,B}(N)=B_A(N)\,B_B(N).$$
Si \(A=B\), debemos excluir escoger la misma base primitiva dos veces, y por tanto
$$P_{A,A}(N)=B_A(N)\bigl(B_A(N)-1\bigr).$$
En consecuencia, toda la rama irracional es
$$\operatorname{Irr}(N)=\sum_{A=1}^{L}\sum_{B=1}^{L} P_{A,B}(N)\,Q(A,B).$$
Aquí \(L=\lfloor \log_2 5 \rfloor=2\). Las bases primitivas no mayores que \(5\) son \(2,3,5\). Sus capacidades de exponente son
$$A(2)=2,\qquad A(3)=1,\qquad A(5)=1.$$
Por tanto, las clases de capacidad son
$$B_1(5)=2,\qquad B_2(5)=1.$$
Los recuentos de razones reducidas son
$$Q(1,1)=1,\qquad Q(1,2)=2,\qquad Q(2,1)=2,\qquad Q(2,2)=3.$$
La rama racional aporta
$$\operatorname{Rat}(5)=Q(2,2)=3,$$
correspondientes a \(1\), \(2\) y \(1/2\).
Para la rama irracional, los recuentos de pares ordenados son
$$P_{1,1}(5)=2,\qquad P_{1,2}(5)=2,\qquad P_{2,1}(5)=2,\qquad P_{2,2}(5)=0.$$
Así,
$$\operatorname{Irr}(5)=2 \cdot 1 + 2 \cdot 2 + 2 \cdot 2 = 10,$$
y el total es
$$D(5)=3+10=13.$$
Esto coincide con el primer punto de control exacto usado por las implementaciones.
Las implementaciones en C++, Python y Java comienzan calculando \(L=\lfloor \log_2 N \rfloor\) y construyendo los valores \(\mu(1),\dots,\mu(L)\) mediante un cribado. Como todas las fórmulas posteriores solo dependen de cotas de exponente hasta \(L\), el problema queda comprimido desde números de tamaño \(N\) a exponentes de tamaño alrededor de \(60\) para la entrada objetivo.
Después, la implementación evalúa raíces enteras exactas como \(\lfloor N^{1/k} \rfloor\). Parte de una aproximación en coma flotante y la corrige con comprobaciones enteras de potencias, de modo que ningún error de redondeo contamine las sumas de Möbius. Esas raíces exactas alimentan la fórmula de \(U(M)\), y a partir de ahí se obtienen todos los valores \(B_A(N)\).
Luego se llena la tabla completa \(Q(A,B)\) para \(1 \le A,B \le L\) usando la fórmula de Möbius para pares de exponentes coprimos. Una vez construida esa tabla, la parte racional se reduce a una sola consulta: \(Q(L,L)\).
El trabajo restante es la suma doble de la parte irracional. Fuera de la diagonal \(A \ne B\), el número de pares ordenados de bases es \(B_A(N)B_B(N)\). En la diagonal, el código usa \(B_A(N)(B_A(N)-1)\) para impedir que una base primitiva se empareje consigo misma en la rama de bases distintas.
Para el objetivo \(N=10^{18}\), la respuesta se informa módulo \(10^9\). Para comprobaciones pequeñas, las implementaciones también admiten aritmética exacta y verifican valores como \(D(5)=13\), \(D(10)=69\), \(D(100)=9607\) y \(D(10000)=99959605\).
Sea \(L=\lfloor \log_2 N \rfloor\). El cribado de Möbius cuesta \(O(L)\). La construcción de la tabla de razones coprimas requiere
$$\sum_{A=1}^{L}\sum_{B=1}^{L} O(\min(A,B))=O(L^3)$$
operaciones y domina el coste asintótico en las implementaciones locales. La suma doble final de la parte irracional es \(O(L^2)\), y la memoria es \(O(L^2)\) porque la tabla \(Q(A,B)\) se mantiene completa en memoria. Para la entrada objetivo \(N=10^{18}\), solo tenemos \(L=59\), así que el método es claramente suficiente.
对所有满足 \(2 \le x,y \le N\) 的有序整数对 \((x,y)\)，题目要求统计会出现多少个不同的 proto-logarithmic 值，记为 \(D(N)\)。C++、Python 和 Java 实现都建立在同一个关键事实上：每个 \(n \ge 2\) 都能唯一写成
$$n=r^k,$$
其中 \(r\) 不是完美幂，而 \(k \ge 1\) 取到最大。把输入都改写成这种标准形之后，所有重复值都只与“原始底数”以及约分后的指数比有关。于是原本看起来像是要在 \(2\) 到 \(N\) 之间暴力比较的大问题，被压缩成只需要处理 \(L=\lfloor \log_2 N \rfloor\) 级别指数上界的小规模计数问题。
把最终答案拆成两部分：
$$D(N)=\operatorname{Rat}(N)+\operatorname{Irr}(N),$$
其中 \(\operatorname{Rat}(N)\) 统计同一原始底数产生的有理部分，\(\operatorname{Irr}(N)\) 统计不同原始底数产生的“无理分支”。
任意 \(n \ge 2\) 都可以唯一写成 \(n=r^k\)，其中 \(r\) 不是完美幂。下面把这样的 \(r\) 称为原始底数。对固定的原始底数 \(r\)，定义它在范围 \([2,N]\) 内能支持的最大指数为
$$A(r)=\max\{e \ge 1 : r^e \le N\}.$$
于是，由 \(r\) 在区间 \([2,N]\) 内生成的数恰好是
$$r,r^2,\dots,r^{A(r)}.$$
如果把一个有序对写成
$$x=r^u,\qquad y=s^v,$$
其中 \(1 \le u \le A(r)\)，\(1 \le v \le A(s)\)，那么题目中的值只取决于有序原始底数对 \((r,s)\) 以及约分后的分数 \(v/u\)。这与普通对数恒等式
$$\log_{r^u}(s^v)=\frac{v}{u}\cdot\frac{\log s}{\log r}$$
完全一致：当 \(r=s\) 时，值退化成有理数；当 \(r \ne s\) 时，值落入一个由有序底数对决定的无理族中，而族内重复只来自 \(v/u\) 的约分。
定义
$$U(M)=\#\{r \in \mathbb{Z}_{\ge 2} : r \le M,\ \forall a,b \in \mathbb{Z}_{\ge 2},\ r \ne a^b\}.$$
区间 \([2,M]\) 中的每个整数都能唯一写成某个原始底数的幂，因此把所有整数按“原始底数 + 指数”分组后，有
$$M-1=\sum_{e=1}^{\lfloor \log_2 M \rfloor} U\!\left(\left\lfloor M^{1/e}\right\rfloor\right).$$
对这个关系做 Möbius 反演，就得到
$$U(M)=\sum_{d=1}^{\lfloor \log_2 M \rfloor} \mu(d)\left(\left\lfloor M^{1/d}\right\rfloor-1\right).$$
现在令 \(B_A(N)\) 表示“指数容量恰好等于 \(A\)”的原始底数个数，则
$$B_A(N)=U\!\left(\left\lfloor N^{1/A}\right\rfloor\right)-U\!\left(\left\lfloor N^{1/(A+1)}\right\rfloor\right).$$
这一步把所有原始底数按照它们最多能支持到几次幂进行分类。后面的双重计数都会只依赖这些类别，而不会再依赖具体的底数大小。
对固定的上界 \(A\) 和 \(B\)，定义
$$Q(A,B)=\#\{(u,v): 1 \le u \le A,\ 1 \le v \le B,\ \gcd(u,v)=1\}.$$
它恰好等于所有可能出现的不同约分分数 \(v/u\) 的个数，其中分母指数最多为 \(A\)，分子指数最多为 \(B\)。换句话说，\(Q(A,B)\) 就是在一个 \(A \times B\) 的指数矩形里，统计可见格点的数量。
标准的 Möbius 计数公式给出
$$Q(A,B)=\sum_{d=1}^{\min(A,B)} \mu(d)\left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor.$$
实现会一次性把所有 \(1 \le A,B \le L\) 的 \(Q(A,B)\) 都预计算出来，其中
$$L=\lfloor \log_2 N \rfloor.$$
当原始底数相同，即 \(r=s\) 时，值只由约分后的 \(v/u\) 决定。因此所有不同有理值的总数，就是分子和分母都不超过 \(L\) 的所有既约正分数的个数：
$$\operatorname{Rat}(N)=Q(L,L).$$
为什么这一条足够？因为原始底数 \(2\) 本身就已经能实现全部指数 \(1,2,\dots,L\)，这是由 \(2^L \le N\) 直接保证的。所以所有可能的既约分数都一定能真正出现。
当 \(r \ne s\) 时，就进入不同底数的分支。对固定的有序原始底数对 \((r,s)\)，内部所有重复都只来自 \(v/u\) 的约分，因此这个有序底数对贡献的不同值个数正好是 \(Q(A(r),A(s))\)。
接下来要数的是：指数容量分别为 \(A\) 和 \(B\) 的有序原始底数对有多少个？如果 \(A \ne B\)，两者已经不可能是同一个原始底数，所以
$$P_{A,B}(N)=B_A(N)\,B_B(N).$$
如果 \(A=B\)，则必须排除“同一个原始底数配对自己”的情况，因此
$$P_{A,A}(N)=B_A(N)\bigl(B_A(N)-1\bigr).$$
于是整个无理分支就是
$$\operatorname{Irr}(N)=\sum_{A=1}^{L}\sum_{B=1}^{L} P_{A,B}(N)\,Q(A,B).$$
这正是实现所累加的双重求和形式。
此时 \(L=\lfloor \log_2 5 \rfloor=2\)。不超过 \(5\) 的原始底数是 \(2,3,5\)。它们的指数容量分别为
$$A(2)=2,\qquad A(3)=1,\qquad A(5)=1.$$
因此容量分类为
$$B_1(5)=2,\qquad B_2(5)=1.$$
约分指数比的数量为
$$Q(1,1)=1,\qquad Q(1,2)=2,\qquad Q(2,1)=2,\qquad Q(2,2)=3.$$
有理部分贡献
$$\operatorname{Rat}(5)=Q(2,2)=3,$$
对应的就是 \(1\)、\(2\) 和 \(1/2\)。
无理部分中，各个容量对对应的有序底数对个数为
$$P_{1,1}(5)=2,\qquad P_{1,2}(5)=2,\qquad P_{2,1}(5)=2,\qquad P_{2,2}(5)=0.$$
所以
$$\operatorname{Irr}(5)=2 \cdot 1 + 2 \cdot 2 + 2 \cdot 2 = 10,$$
从而总数为
$$D(5)=3+10=13.$$
这与实现中使用的第一个精确校验点完全一致。
C++、Python 和 Java 实现首先计算 \(L=\lfloor \log_2 N \rfloor\)，再用筛法构造 \(\mu(1),\dots,\mu(L)\)。由于后面的公式只需要处理不超过 \(L\) 的指数上界，原问题就从“遍历所有不超过 \(N\) 的整数对”压缩成了“遍历不超过 \(L\) 的指数状态”，对目标输入来说 \(L\) 只有几十。
接着，实现会精确计算诸如 \(\lfloor N^{1/k} \rfloor\) 这样的整数 \(k\) 次根。它先用浮点数求一个近似值，再通过整数乘幂比较向上或向下修正，确保根值绝对正确，不会把舍入误差带入 Möbius 求和。随后利用这些整数根求出所有 \(U(M)\)，再进一步得到每个 \(B_A(N)\)。
然后，程序为所有 \(1 \le A,B \le L\) 预计算整张 \(Q(A,B)\) 表，也就是既约指数比的数量表。有了这张表之后，有理部分只需要读取一次 \(Q(L,L)\) 即可。
剩下的工作是无理部分的双重求和。对于 \(A \ne B\) 的格子，贡献系数是 \(B_A(N)B_B(N)\)。对于对角线 \(A=B\) 的格子，则使用 \(B_A(N)(B_A(N)-1)\)，以确保不同底数分支里不会把同一个原始底数和自己配对。
在目标输入 \(N=10^{18}\) 下，结果按 \(10^9\) 取模输出。对于较小的测试点，实现也支持精确整数运算，并验证了 \(D(5)=13\)、\(D(10)=69\)、\(D(100)=9607\)、\(D(10000)=99959605\) 这些检查值。
设 \(L=\lfloor \log_2 N \rfloor\)。Möbius 筛法是 \(O(L)\)。构造既约指数比表所需的运算量为
$$\sum_{A=1}^{L}\sum_{B=1}^{L} O(\min(A,B))=O(L^3),$$
这也是本地实现中的主导渐近成本。最后的无理部分双重求和是 \(O(L^2)\)，空间复杂度为 \(O(L^2)\)，因为整张 \(Q(A,B)\) 表会保存在内存中。对于目标输入 \(N=10^{18}\)，只有 \(L=59\)，因此这套方法非常轻量。
Для каждой упорядоченной пары \((x,y)\), где \(2 \le x,y \le N\), требуется посчитать число \(D(N)\) различных значений proto-логарифмической функции. Ключевое наблюдение, на котором основаны реализации на C++, Python и Java, состоит в том, что любое целое \(n \ge 2\) имеет единственную каноническую запись
$$n=r^k,$$
где \(r\) не является совершенной степенью, а \(k \ge 1\) максимально. После такого приведения все совпадения определяются только примитивными основаниями и сокращённым отношением показателей. Поэтому задача сводится не к перебору чисел до \(N\), а к компактному счёту с параметром \(L=\lfloor \log_2 N \rfloor\).
Разобьём ответ на две части:
$$D(N)=\operatorname{Rat}(N)+\operatorname{Irr}(N),$$
где первая часть отвечает за ветвь с одинаковым примитивным основанием, а вторая — за ветвь с разными основаниями.
Каждое целое \(n \ge 2\) единственным образом представляется как \(n=r^k\), где \(r\) не является совершенной степенью. Такое \(r\) будем называть примитивным основанием. Для фиксированного примитивного основания \(r\) определим его показательную ёмкость:
$$A(r)=\max\{e \ge 1 : r^e \le N\}.$$
Тогда все числа из диапазона \([2,N]\), порождаемые этим основанием, равны
$$r,r^2,\dots,r^{A(r)}.$$
Если записать упорядоченную пару в виде
$$x=r^u,\qquad y=s^v,$$
где \(1 \le u \le A(r)\) и \(1 \le v \le A(s)\), то задача зависит только от упорядоченной пары примитивных оснований \((r,s)\) и от сокращённой дроби \(v/u\). Это отражает обычную формулу
$$\log_{r^u}(s^v)=\frac{v}{u}\cdot\frac{\log s}{\log r},$$
из которой видно, почему при \(r=s\) возникает рациональная ветвь, а при \(r \ne s\) — иррациональная семья значений.
Обозначим
$$U(M)=\#\{r \in \mathbb{Z}_{\ge 2} : r \le M,\ \forall a,b \in \mathbb{Z}_{\ge 2},\ r \ne a^b\}.$$
Каждое число из \([2,M]\) единственным образом записывается как степень примитивного основания, поэтому
$$M-1=\sum_{e=1}^{\lfloor \log_2 M \rfloor} U\!\left(\left\lfloor M^{1/e}\right\rfloor\right).$$
Применяя обращение Мёбиуса, получаем точную формулу
$$U(M)=\sum_{d=1}^{\lfloor \log_2 M \rfloor} \mu(d)\left(\left\lfloor M^{1/d}\right\rfloor-1\right).$$
Теперь пусть \(B_A(N)\) — число примитивных оснований с показательным пределом ровно \(A\). Тогда
$$B_A(N)=U\!\left(\left\lfloor N^{1/A}\right\rfloor\right)-U\!\left(\left\lfloor N^{1/(A+1)}\right\rfloor\right).$$
Так все примитивные основания разбиваются по максимальному допустимому показателю внутри диапазона.
Для фиксированных границ \(A\) и \(B\) введём
$$Q(A,B)=\#\{(u,v): 1 \le u \le A,\ 1 \le v \le B,\ \gcd(u,v)=1\}.$$
Это в точности число различных сокращённых дробей \(v/u\), которые могут возникнуть при ограничениях \(u \le A\) и \(v \le B\).
Стандартная формула для видимых точек решётки даёт
$$Q(A,B)=\sum_{d=1}^{\min(A,B)} \mu(d)\left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor.$$
Реализации заранее строят всю эту таблицу для \(1 \le A,B \le L\), где
$$L=\lfloor \log_2 N \rfloor.$$
Если примитивные основания совпадают, то есть \(r=s\), значение определяется только сокращённой дробью \(v/u\). Следовательно, число различных рациональных значений равно числу всех положительных несократимых дробей, у которых и числитель, и знаменатель не превосходят \(L\):
$$\operatorname{Rat}(N)=Q(L,L).$$
Этого достаточно, потому что уже одно примитивное основание \(2\) реализует показатели \(1,2,\dots,L\), так как \(2^L \le N\).
Если \(r \ne s\), мы попадаем в ветвь с различными основаниями. Для фиксированной упорядоченной пары примитивных оснований \((r,s)\) все внутренние совпадения возникают только из сокращения \(v/u\), поэтому такая пара даёт ровно \(Q(A(r),A(s))\) различных значений.
Сколько существует упорядоченных пар примитивных оснований с ёмкостями \(A\) и \(B\)? Если \(A \ne B\), одинаковое основание выбрать нельзя уже по самой классификации, поэтому
$$P_{A,B}(N)=B_A(N)\,B_B(N).$$
Если \(A=B\), нужно исключить случай, когда одно и то же примитивное основание берётся дважды, то есть
$$P_{A,A}(N)=B_A(N)\bigl(B_A(N)-1\bigr).$$
Тем самым весь иррациональный вклад равен
$$\operatorname{Irr}(N)=\sum_{A=1}^{L}\sum_{B=1}^{L} P_{A,B}(N)\,Q(A,B).$$
Здесь \(L=\lfloor \log_2 5 \rfloor=2\). Примитивные основания, не превосходящие \(5\), — это \(2\), \(3\) и \(5\). Их показательныe ёмкости равны
$$A(2)=2,\qquad A(3)=1,\qquad A(5)=1.$$
Следовательно, классы ёмкости таковы:
$$B_1(5)=2,\qquad B_2(5)=1.$$
Числа сокращённых отношений показателей равны
$$Q(1,1)=1,\qquad Q(1,2)=2,\qquad Q(2,1)=2,\qquad Q(2,2)=3.$$
Рациональная часть даёт
$$\operatorname{Rat}(5)=Q(2,2)=3,$$
то есть значения \(1\), \(2\) и \(1/2\).
Для иррациональной части количества упорядоченных пар равны
$$P_{1,1}(5)=2,\qquad P_{1,2}(5)=2,\qquad P_{2,1}(5)=2,\qquad P_{2,2}(5)=0.$$
Поэтому
$$\operatorname{Irr}(5)=2 \cdot 1 + 2 \cdot 2 + 2 \cdot 2 = 10,$$
а итоговый ответ
$$D(5)=3+10=13.$$
Это совпадает с первым точным контрольным значением, используемым в реализациях.
Реализации на C++, Python и Java сначала вычисляют \(L=\lfloor \log_2 N \rfloor\), а затем строят значения \(\mu(1),\dots,\mu(L)\) с помощью решета. Так как все последующие формулы зависят только от ограничений на показатели до \(L\), задача сразу сжимается от чисел порядка \(N\) до таблиц размера примерно \(60 \times 60\) для целевого ввода.
После этого код вычисляет точные целые \(k\)-е корни вида \(\lfloor N^{1/k} \rfloor\). Сначала берётся вещественная оценка, затем она корректируется вверх или вниз проверками целочисленных степеней. Благодаря этому ошибки округления не попадают в суммы Мёбиуса. Эти корни используются для вычисления всех значений \(U(M)\), а затем и всех \(B_A(N)\).
Далее строится полная таблица \(Q(A,B)\) для всех \(1 \le A,B \le L\) по формуле Мёбиуса для взаимно простых пар показателей. После этого рациональная часть сводится к одному обращению к таблице: \(Q(L,L)\).
Оставшаяся работа — двойная сумма для иррациональной части. Вне диагонали \(A \ne B\) коэффициент равен \(B_A(N)B_B(N)\). На диагонали используется \(B_A(N)(B_A(N)-1)\), чтобы в ветви с разными основаниями не спаривать примитивное основание само с собой.
Для целевого значения \(N=10^{18}\) ответ выводится по модулю \(10^9\). Для малых контрольных примеров реализации также умеют считать точно и проверяют значения \(D(5)=13\), \(D(10)=69\), \(D(100)=9607\) и \(D(10000)=99959605\).
Пусть \(L=\lfloor \log_2 N \rfloor\). Решето Мёбиуса работает за \(O(L)\). Построение таблицы взаимно простых отношений требует
$$\sum_{A=1}^{L}\sum_{B=1}^{L} O(\min(A,B))=O(L^3)$$
операций и является главным асимптотическим слагаемым в локальных реализациях. Финальная двойная сумма для иррациональной части занимает \(O(L^2)\), а память — \(O(L^2)\), поскольку таблица \(Q(A,B)\) хранится целиком. Для целевого ввода \(N=10^{18}\) имеем всего \(L=59\), так что метод легко укладывается в практические пределы.
لكل زوج مرتب \((x,y)\) يحقق \(2 \le x,y \le N\)، تطلب المسألة حساب عدد القيم المختلفة للدالة proto-logarithmic، ولنرمز إليه بـ \(D(N)\). الفكرة الأساسية التي تعتمد عليها تطبيقات C++ وPython وJava هي أن كل عدد صحيح \(n \ge 2\) يملك تمثيلًا قانونيًا وحيدًا على الصورة
$$n=r^k,$$
حيث إن \(r\) ليست قوة تامة، و\(k \ge 1\) هو أكبر أس ممكن. بعد إعادة كتابة المدخلين بهذه الصورة، تصبح جميع حالات التطابق محكومة فقط بالأسس البدائية وبالنسبة المختزلة بين الأسين. وهكذا تتحول المسألة من فضاء بحث ضخم جدًا إلى عدّ صغير يعتمد على \(L=\lfloor \log_2 N \rfloor\) وبعض الجداول الحسابية القصيرة.
سنكتب الجواب النهائي على الصورة
$$D(N)=\operatorname{Rat}(N)+\operatorname{Irr}(N),$$
حيث يحصي الحد الأول الفرع العقلاني الناتج من تساوي الأساس البدائي، ويحـصي الحد الثاني الفرع اللاعقلاني الناتج من اختلاف الأساسين.
كل عدد صحيح \(n \ge 2\) يمكن كتابته بصورة وحيدة \(n=r^k\) بحيث تكون \(r\) غير قوة تامة. سنسمي هذا \(r\) أساسًا بدائيًا. وبالنسبة إلى أساس بدائي ثابت \(r\)، نعرّف سعته الأسية كما يلي:
$$A(r)=\max\{e \ge 1 : r^e \le N\}.$$
وعندئذ فإن جميع الأعداد التي يولدها \(r\) داخل المجال \([2,N]\) هي بالضبط
$$r,r^2,\dots,r^{A(r)}.$$
إذا كتبنا زوجًا مرتبًا بالشكل
$$x=r^u,\qquad y=s^v,$$
مع \(1 \le u \le A(r)\) و\(1 \le v \le A(s)\)، فإن قيمة المسألة لا تعتمد إلا على الزوج المرتب من الأساسين البدائيين \((r,s)\) وعلى الكسر المختزل \(v/u\). وهذا يعكس الهوية المعتادة
$$\log_{r^u}(s^v)=\frac{v}{u}\cdot\frac{\log s}{\log r},$$
ومنها يتضح لماذا يتحول الفرع ذو الأساس نفسه إلى قيمة عقلانية، ولماذا يشكل الفرع ذو الأساسين المختلفين عائلة من القيم اللاعقلانية.
لنعرّف
$$U(M)=\#\{r \in \mathbb{Z}_{\ge 2} : r \le M,\ \forall a,b \in \mathbb{Z}_{\ge 2},\ r \ne a^b\}.$$
كل عدد في المجال \([2,M]\) يملك تمثيلًا وحيدًا على شكل قوة لأساس بدائي، ولذلك نحصل على
$$M-1=\sum_{e=1}^{\lfloor \log_2 M \rfloor} U\!\left(\left\lfloor M^{1/e}\right\rfloor\right).$$
وبتطبيق انعكاس Möbius نحصل على الصيغة الدقيقة
$$U(M)=\sum_{d=1}^{\lfloor \log_2 M \rfloor} \mu(d)\left(\left\lfloor M^{1/d}\right\rfloor-1\right).$$
ولنفرض الآن أن \(B_A(N)\) هو عدد الأسس البدائية التي تملك سعة أسية تساوي \(A\) تمامًا. عندئذ
$$B_A(N)=U\!\left(\left\lfloor N^{1/A}\right\rfloor\right)-U\!\left(\left\lfloor N^{1/(A+1)}\right\rfloor\right).$$
وبذلك نصنف كل أساس بدائي بحسب أكبر أس يمكنه دعمه داخل المجال المطلوب.
لحدين ثابتين \(A\) و\(B\)، نعرّف
$$Q(A,B)=\#\{(u,v): 1 \le u \le A,\ 1 \le v \le B,\ \gcd(u,v)=1\}.$$
هذا هو تمامًا عدد الكسور المختزلة المختلفة \(v/u\) التي يمكن أن تظهر عندما لا يتجاوز أس المقام \(A\) ولا يتجاوز أس البسط \(B\).
وباستخدام صيغة Möbius القياسية لعدّ نقاط الشبكة المرئية نحصل على
$$Q(A,B)=\sum_{d=1}^{\min(A,B)} \mu(d)\left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor.$$
تقوم التطبيقات بحساب هذه المصفوفة كاملة مسبقًا لكل \(1 \le A,B \le L\)، حيث
$$L=\lfloor \log_2 N \rfloor.$$
عندما يتساوى الأساسان البدائيان، أي \(r=s\)، تصبح القيمة معتمدة فقط على الكسر المختزل \(v/u\). لذلك فإن عدد القيم العقلانية المختلفة يساوي عدد الكسور الموجبة المختزلة التي لا يتجاوز فيها كل من البسط والمقام \(L\):
$$\operatorname{Rat}(N)=Q(L,L).$$
والسبب في كفاية ذلك هو أن الأساس البدائي \(2\) وحده يحقق جميع الأسس \(1,2,\dots,L\)، لأن \(2^L \le N\).
عندما \(r \ne s\) نكون في فرع الأساسين المختلفين. بالنسبة إلى زوج بدائي مرتب ثابت \((r,s)\)، فإن جميع حالات التطابق الداخلية تأتي فقط من اختزال \(v/u\)، ولهذا يساهم هذا الزوج بعدد يساوي بالضبط \(Q(A(r),A(s))\) من القيم المختلفة.
كم عدد الأزواج المرتبة من الأسس البدائية التي تملك السعتين \(A\) و\(B\)؟ إذا كان \(A \ne B\)، فإن اختلاف السعة يفرض تلقائيًا أن الأساسين مختلفان، ولذلك
$$P_{A,B}(N)=B_A(N)\,B_B(N).$$
أما إذا كان \(A=B\)، فيجب استبعاد اختيار الأساس البدائي نفسه مرتين، ولهذا
$$P_{A,A}(N)=B_A(N)\bigl(B_A(N)-1\bigr).$$
ومن ثم فإن كامل الجزء اللاعقلاني هو
$$\operatorname{Irr}(N)=\sum_{A=1}^{L}\sum_{B=1}^{L} P_{A,B}(N)\,Q(A,B).$$
لدينا هنا \(L=\lfloor \log_2 5 \rfloor=2\). الأسس البدائية التي لا تتجاوز \(5\) هي \(2\) و\(3\) و\(5\). وسعاتها الأسية هي
$$A(2)=2,\qquad A(3)=1,\qquad A(5)=1.$$
إذًا تصبح فئات السعة
$$B_1(5)=2,\qquad B_2(5)=1.$$
أما أعداد النسب المختزلة فهي
$$Q(1,1)=1,\qquad Q(1,2)=2,\qquad Q(2,1)=2,\qquad Q(2,2)=3.$$
الفرع العقلاني يعطي
$$\operatorname{Rat}(5)=Q(2,2)=3,$$
وهي القيم \(1\) و\(2\) و\(1/2\).
وفي الفرع اللاعقلاني تكون أعداد الأزواج المرتبة
$$P_{1,1}(5)=2,\qquad P_{1,2}(5)=2,\qquad P_{2,1}(5)=2,\qquad P_{2,2}(5)=0.$$
ولذلك
$$\operatorname{Irr}(5)=2 \cdot 1 + 2 \cdot 2 + 2 \cdot 2 = 10,$$
ومن ثم يكون المجموع
$$D(5)=3+10=13.$$
وهذا يطابق أول نقطة تحقق دقيقة تستخدمها التطبيقات.
تبدأ تطبيقات C++ وPython وJava بحساب \(L=\lfloor \log_2 N \rfloor\)، ثم تبني قيم \(\mu(1),\dots,\mu(L)\) باستخدام غربال. ولأن كل الصيغ اللاحقة تعتمد فقط على حدود أسية حتى \(L\)، تتحول المسألة فورًا من فضاء أعداد حتى \(N\) إلى فضاء أسس حجمه يقارب \(60\) فقط في المدخل المستهدف.
بعد ذلك، تحسب الشيفرة الجذور الصحيحة الدقيقة من نوع \(\lfloor N^{1/k} \rfloor\). تبدأ بتقدير عشري تقريبي، ثم تصححه صعودًا أو هبوطًا بواسطة اختبارات قوى صحيحة، لكي لا تدخل أي أخطاء تقريب إلى مجاميع Möbius. هذه الجذور الدقيقة تُستخدم لحساب جميع قيم \(U(M)\)، ومنها تُستخرج جميع قيم \(B_A(N)\).
ثم تُملأ المصفوفة الكاملة \(Q(A,B)\) لكل \(1 \le A,B \le L\) باستخدام صيغة Möbius الخاصة بالأزواج المتباينة أوليًا. وبعد بناء هذه المصفوفة، يصبح الجزء العقلاني مجرد قراءة وحيدة للقيمة \(Q(L,L)\).
العمل المتبقي هو المجموع المزدوج الخاص بالجزء اللاعقلاني. خارج القطر \(A \ne B\)، يكون معامل الأزواج المرتبة هو \(B_A(N)B_B(N)\). وعلى القطر، تستخدم الشيفرة \(B_A(N)(B_A(N)-1)\) حتى لا يُقترن الأساس البدائي بنفسه داخل فرع الأساسين المختلفين.
بالنسبة إلى الهدف \(N=10^{18}\)، يُعطى الجواب بترديد \(10^9\). أما في نقاط الفحص الصغيرة، فتدعم التطبيقات حسابًا صحيحًا بالكامل، وتتحقق من القيم \(D(5)=13\) و\(D(10)=69\) و\(D(100)=9607\) و\(D(10000)=99959605\).
لنفرض أن \(L=\lfloor \log_2 N \rfloor\). غربال Möbius يكلف \(O(L)\). وبناء جدول النسب المتباينة أوليًا يحتاج إلى
$$\sum_{A=1}^{L}\sum_{B=1}^{L} O(\min(A,B))=O(L^3)$$
عملية، وهو الحد المسيطر على التعقيد asymptotically في التطبيقات المحلية. أما المجموع المزدوج الأخير للفرع اللاعقلاني فهو \(O(L^2)\)، واستهلاك الذاكرة هو \(O(L^2)\) لأن جدول \(Q(A,B)\) يُخزَّن كاملًا في الذاكرة. وعند المدخل الهدف \(N=10^{18}\) يكون لدينا فقط \(L=59\)، ولذلك تبقى الطريقة عملية جدًا.