A hybrid integer is a number of the form \(p^q q^p\) where \(p\) and \(q\) are distinct primes. By unique factorization, two different prime pairs cannot produce the same number, so counting hybrid integers up to \(B^E\) is equivalent to counting prime pairs \(p<q\) such that
$$p^q q^p \le B^E.$$
The target input is \(B=800800\) and \(E=800800\). Direct evaluation of the powers is completely impractical, so the solution converts the inequality into a logarithmic comparison and then counts valid prime pairs with a monotone sweep.
Define
$$H(B,E)=\#\{(p,q): p<q,\ p^q q^p \le B^E\},$$
where \(p\) and \(q\) are prime. The problem is to compute \(H(800800,800800)\).
Because every hybrid integer is determined by its two prime bases, we can work directly with ordered pairs \(p<q\). There is no need to build the integer \(p^q q^p\) itself. We only need to decide whether the pair lies below the threshold \(B^E\).
This turns the original number-theoretic question into a comparison problem on prime pairs. Once a pair \((p,q)\) is accepted, it contributes exactly one hybrid integer.
Let
$$\Lambda = E\ln B.$$
Since the natural logarithm is strictly increasing on positive numbers,
$$p^q q^p \le B^E \iff \ln(p^q q^p)\le \ln(B^E).$$
Using \(\ln(a^b)=b\ln a\), this becomes
$$q\ln p + p\ln q \le \Lambda.$$
This is the key transformation used by the implementations: enormous powers disappear, replaced by a sum of two moderate logarithmic terms.
Every admissible pair satisfies \(p\ge 2\), so \(\ln p \ge \ln 2\). Therefore
$$q\ln 2 \le q\ln p \le q\ln p + p\ln q \le \Lambda.$$
Hence any valid right prime must satisfy
$$q \le \frac{\Lambda}{\ln 2}.$$
So it is sufficient to generate all primes up to a bound of the shape
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
The small constant cushion used in practice is only there to absorb truncation and floating-point edge effects; mathematically, the search interval is already determined by the inequality above.
Fix a prime \(p\), and consider
$$f_p(x)=x\ln p + p\ln x \qquad (x>1).$$
Its derivative is
$$f_p'(x)=\ln p + \frac{p}{x} > 0,$$
so \(f_p(x)\) is strictly increasing. That means that for a fixed left prime \(p\), the admissible right primes \(q\) form an initial segment of the prime list: once the inequality fails for some \(q\), it fails for all larger primes as well.
There is a second monotonicity. For a fixed right prime \(q\), the quantity
$$g_q(x)=q\ln x + x\ln q$$
also increases with \(x\), since
$$g_q'(x)=\frac{q}{x}+\ln q > 0.$$
Therefore, as the left prime moves forward through the sorted prime list, the largest valid right prime can only stay where it is or move left. This is exactly why one descending right pointer is enough for the whole count.
Suppose the primes are \(r_0<r_1<\dots<r_{m-1}\). For a fixed index \(i\), let \(j\) be the largest index with \(i<j\) and
$$r_j\ln r_i + r_i\ln r_j \le \Lambda.$$
Then every prime \(r_k\) with \(i<k\le j\) is also valid, and every \(r_k\) with \(k>j\) is invalid. So the contribution of the left prime \(r_i\) is exactly
$$j-i.$$
Summing these contiguous block lengths over all left indices counts every admissible pair exactly once.
Here
$$\Lambda=\ln 800.$$
The bound for the larger prime is
$$q\le \frac{\ln 800}{\ln 2}=\log_2 800 < 10,$$
so we only need the primes \(2,3,5,7\).
Now test the possible pairs:
$$\begin{aligned} (2,3)&:&3\ln 2 + 2\ln 3 = \ln(72) \le \ln(800),\\ (2,5)&:&5\ln 2 + 2\ln 5 = \ln(800),\\ (2,7)&:&7\ln 2 + 2\ln 7 = \ln(6272) > \ln(800),\\ (3,5)&:&5\ln 3 + 3\ln 5 = \ln(6075) > \ln(800). \end{aligned}$$
All remaining pairs are even larger, so the only hybrid integers not exceeding \(800\) are
$$2^3 3^2 = 72,\qquad 2^5 5^2 = 800.$$
Thus \(H(800,1)=2\), matching the small checkpoint used by the implementations.
The C++, Python, and Java implementations follow the same pipeline. First they compute \(\Lambda=E\ln B\) in floating point and derive a safe upper limit slightly above \(\Lambda/\ln 2\). Then they generate every prime up to that limit with a sieve of Eratosthenes.
Next they precompute \(\ln p\) once for each prime so the inner comparison never recalculates logarithms. After that, they place one pointer at the beginning of the prime list and another at the end. For each left prime, the right pointer moves left until the inequality \(q\ln p + p\ln q \le \Lambda\) becomes true. At that moment, all primes between the two pointers form valid pairs with the chosen left prime, so the implementation adds the size of that block to the answer.
Because the right pointer only moves in one direction, the counting pass is linear in the number of generated primes. A tiny numerical tolerance is included in the comparison so that boundary cases representing exact equality are not lost to floating-point rounding.
Let
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
Generating all primes up to \(Q\) by sieve costs \(O(Q\log\log Q)\) time and \(O(Q)\) memory. Precomputing the logarithms costs \(O(\pi(Q))\) time and memory proportional to the prime list. The two-pointer sweep is \(O(\pi(Q))\), because the left pointer visits each prime once and the right pointer can only move left across the list once.
Therefore the overall running time is
$$O(Q\log\log Q),$$
with linear memory
$$O(Q).$$
Eine Hybrid-Zahl hat die Form \(p^q q^p\), wobei \(p\) und \(q\) verschiedene Primzahlen sind. Wegen der eindeutigen Primfaktorzerlegung kann dieselbe Zahl nicht aus zwei verschiedenen Primzahlpaaren entstehen. Also genügt es, Primzahlpaare \(p<q\) zu zählen, für die
$$p^q q^p \le B^E$$
gilt. Im Zielproblem ist \(B=800800\) und \(E=800800\). Die Potenzen selbst sind viel zu groß für direkte Berechnung, deshalb arbeitet die Lösung vollständig mit Logarithmen und einer monotonen Zählstrategie.
Wir definieren
$$H(B,E)=\#\{(p,q): p<q,\ p^q q^p \le B^E\},$$
wobei \(p\) und \(q\) Primzahlen sind. Gesucht ist also \(H(800800,800800)\).
Jede zulässige Hybrid-Zahl wird eindeutig durch ihre beiden Primzahlen bestimmt. Darum muss man die Zahl \(p^q q^p\) gar nicht ausrechnen; es reicht zu prüfen, ob das zugehörige Paar unter der Schranke \(B^E\) bleibt.
Damit wird aus der ursprünglichen Fragestellung ein Problem über geordnete Primzahlpaare \(p<q\). Jedes gültige Paar liefert genau eine Hybrid-Zahl.
Setze
$$\Lambda = E\ln B.$$
Da der natürliche Logarithmus auf den positiven Zahlen streng monoton wächst, ist
$$p^q q^p \le B^E \iff \ln(p^q q^p)\le \ln(B^E).$$
Mit \(\ln(a^b)=b\ln a\) folgt
$$q\ln p + p\ln q \le \Lambda.$$
Genau diese Form verwenden die Implementierungen. Riesige Potenzen werden dadurch durch eine handliche Summenungleichung ersetzt.
Für jedes zulässige Paar gilt \(p\ge 2\), also \(\ln p\ge \ln 2\). Deshalb
$$q\ln 2 \le q\ln p \le q\ln p + p\ln q \le \Lambda.$$
Somit muss die größere Primzahl die Bedingung
$$q \le \frac{\Lambda}{\ln 2}$$
erfüllen. Es genügt also, alle Primzahlen bis zu einer Grenze der Form
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1)$$
zu erzeugen. Die kleine additive Reserve in der Implementierung dient nur dazu, Rundungs- und Abschneideeffekte sicher abzufangen.
Fixiere eine Primzahl \(p\) und betrachte
$$f_p(x)=x\ln p + p\ln x \qquad (x>1).$$
Dann ist
$$f_p'(x)=\ln p + \frac{p}{x} > 0,$$
also wächst \(f_p(x)\) streng. Für eine feste linke Primzahl \(p\) bilden die zulässigen rechten Primzahlen daher einen zusammenhängenden Anfangsblock der sortierten Primliste: Sobald die Ungleichung für ein \(q\) fehlschlägt, scheitert sie auch für jedes größere \(q\).
Ebenso ist für festes \(q\) die Funktion
$$g_q(x)=q\ln x + x\ln q$$
streng wachsend, denn
$$g_q'(x)=\frac{q}{x}+\ln q > 0.$$
Deshalb kann sich die größte gültige rechte Primzahl beim Voranschreiten der linken Primzahl nur nach links bewegen oder stehen bleiben. Genau das macht einen einzigen rückwärts laufenden rechten Zeiger möglich.
Seien die Primzahlen \(r_0<r_1<\dots<r_{m-1}\). Für einen festen Index \(i\) sei \(j\) der größte Index mit \(i<j\) und
$$r_j\ln r_i + r_i\ln r_j \le \Lambda.$$
Dann sind genau die Primzahlen \(r_k\) mit \(i<k\le j\) gültige Partner für \(r_i\). Also trägt die linke Primzahl \(r_i\) genau
$$j-i$$
Paare bei. Die Summe dieser Blocklängen über alle linken Indizes zählt jedes gültige Paar genau einmal.
Hier ist
$$\Lambda=\ln 800.$$
Die obere Schranke für die größere Primzahl lautet
$$q\le \frac{\ln 800}{\ln 2}=\log_2 800 < 10,$$
also kommen nur \(2,3,5,7\) in Frage.
Nun prüfen wir die möglichen Paare:
$$\begin{aligned} (2,3)&:&3\ln 2 + 2\ln 3 = \ln(72) \le \ln(800),\\ (2,5)&:&5\ln 2 + 2\ln 5 = \ln(800),\\ (2,7)&:&7\ln 2 + 2\ln 7 = \ln(6272) > \ln(800),\\ (3,5)&:&5\ln 3 + 3\ln 5 = \ln(6075) > \ln(800). \end{aligned}$$
Alle übrigen Paare sind erst recht zu groß. Damit sind die einzigen Hybrid-Zahlen bis \(800\)
$$2^3 3^2 = 72,\qquad 2^5 5^2 = 800.$$
Folglich gilt \(H(800,1)=2\), genau wie im kleinen Test der Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst wird \(\Lambda=E\ln B\) numerisch bestimmt und daraus eine sichere Primzahlgrenze knapp oberhalb von \(\Lambda/\ln 2\) berechnet. Dann werden mit einem Sieb alle Primzahlen bis zu dieser Grenze erzeugt.
Anschließend wird für jede Primzahl ihr Logarithmus einmal vorab gespeichert. In der Zählphase steht ein Zeiger am Anfang der Primliste und ein zweiter am Ende. Für jede linke Primzahl wandert der rechte Zeiger so lange nach links, bis die Ungleichung \(q\ln p + p\ln q \le \Lambda\) erfüllt ist. Dann sind alle Primzahlen zwischen beiden Zeigern gültige Partner, und ihre Anzahl wird sofort zum Ergebnis addiert.
Da sich der rechte Zeiger über die gesamte Laufzeit nur in eine Richtung bewegt, ist dieser Durchlauf linear in der Anzahl der erzeugten Primzahlen. Eine winzige numerische Toleranz schützt dabei Randfälle, in denen Gleichheit wegen Rundung sonst fälschlich als Verletzung der Ungleichung erscheinen könnte.
Sei
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
Das Sieb bis \(Q\) benötigt \(O(Q\log\log Q)\) Zeit und \(O(Q)\) Speicher. Das Vorberechnen der Logarithmen kostet \(O(\pi(Q))\). Der Zwei-Zeiger-Durchlauf ist ebenfalls \(O(\pi(Q))\), weil der linke Zeiger jede Primzahl einmal besucht und der rechte Zeiger höchstens einmal über die Liste nach links läuft.
Insgesamt ergibt sich also die Laufzeit
$$O(Q\log\log Q)$$
bei linearem Speicherverbrauch
$$O(Q).$$
Bir hibrit tamsayı, farklı iki asal \(p\) ve \(q\) için \(p^q q^p\) biçimindeki sayıdır. Asal çarpanlara ayrışım tek olduğundan, iki farklı asal çifti aynı sayıyı üretemez. Bu yüzden \(B^E\) eşiğine kadar olan hibrit tamsayıları saymak,
$$p^q q^p \le B^E$$
koşulunu sağlayan \(p<q\) asal çiftlerini saymakla aynıdır. Hedef giriş \(B=800800\) ve \(E=800800\) değerleridir. Doğrudan üs hesaplamak mümkün olmadığından çözüm eşitsizliği logaritmik biçime çevirir ve geçerli çiftleri monoton bir taramayla sayar.
Şunu tanımlayalım:
$$H(B,E)=\#\{(p,q): p<q,\ p^q q^p \le B^E\},$$
burada \(p\) ve \(q\) asaldır. Aranan değer \(H(800800,800800)\)'dir.
Her uygun hibrit tamsayı, tabanındaki iki asal tarafından tekil olarak belirlenir. Bu nedenle \(p^q q^p\) sayısını gerçekten oluşturmaya gerek yoktur; yalnızca ilgili asal çiftinin \(B^E\) eşiğinin altında kalıp kalmadığını bilmek yeterlidir.
Böylece soru doğrudan \(p<q\) sıralı asal çiftleri üzerine kurulmuş bir sayım problemine dönüşür. Kabul edilen her çift tam olarak bir hibrit tamsayıya karşılık gelir.
Şimdi
$$\Lambda = E\ln B$$
tanımını yapalım. Doğal logaritma pozitif sayılarda sıkı artan olduğundan
$$p^q q^p \le B^E \iff \ln(p^q q^p)\le \ln(B^E).$$
\(\ln(a^b)=b\ln a\) özdeşliği ile bu,
$$q\ln p + p\ln q \le \Lambda$$
şeklini alır. Uygulamanın asıl kilit noktası budur: devasa üsler yerine orta büyüklükte iki logaritmik terim karşılaştırılır.
Her uygun çift için \(p\ge 2\) olduğundan \(\ln p\ge \ln 2\) yazabiliriz. O halde
$$q\ln 2 \le q\ln p \le q\ln p + p\ln q \le \Lambda.$$
Demek ki büyük asal mutlaka
$$q \le \frac{\Lambda}{\ln 2}$$
koşulunu sağlar. Bu yüzden
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1)$$
biçimindeki bir üst sınıra kadar bütün asalları üretmek yeterlidir. Uygulamadaki küçük sabit pay sadece kesme ve yuvarlama etkilerine karşı güvenlik tamponudur.
Sabit bir asal \(p\) için
$$f_p(x)=x\ln p + p\ln x \qquad (x>1)$$
fonksiyonunu inceleyelim. Türevi
$$f_p'(x)=\ln p + \frac{p}{x} > 0$$
olduğundan \(f_p(x)\) sıkı artandır. Yani sol taraftaki asal \(p\) sabitken, uygun sağ asal değerleri sıralı asal listesinin kesintisiz bir başlangıç bloğunu oluşturur: eşitsizlik bir \(q\) için bozulduğu anda daha büyük her asal için de bozulur.
Aynı zamanda sabit \(q\) için
$$g_q(x)=q\ln x + x\ln q$$
fonksiyonu da artandır; çünkü
$$g_q'(x)=\frac{q}{x}+\ln q > 0.$$
Bu ikinci monotonluk şunu söyler: sol asal büyüdükçe geçerli en büyük sağ asal ya yerinde kalır ya da sola kayar. Bu nedenle tüm sayım boyunca tek bir sağ işaretçiyi yalnızca sola hareket ettirmek yeterlidir.
Asal liste \(r_0<r_1<\dots<r_{m-1}\) olsun. Sabit bir \(i\) için, \(i<j\) koşuluyla
$$r_j\ln r_i + r_i\ln r_j \le \Lambda$$
eşitsizliğini sağlayan en büyük indeksi \(j\) ile gösterelim. O zaman \(i<k\le j\) aralığındaki her \(r_k\) uygundur; buna karşılık \(k>j\) olan her asal artık çok büyüktür.
Dolayısıyla sol uçtaki \(r_i\) asalı toplam sonuca tam olarak
$$j-i$$
adet çift katkısı yapar. Tüm \(i\) değerlerinde bu katkıları toplamak, her uygun asal çiftini tam bir kez sayar.
Bu durumda
$$\Lambda=\ln 800$$
olur. Büyük asal için üst sınır
$$q\le \frac{\ln 800}{\ln 2}=\log_2 800 < 10$$
olduğundan yalnızca \(2,3,5,7\) asallarına bakmamız yeterlidir.
Olası çiftleri kontrol edelim:
$$\begin{aligned} (2,3)&:&3\ln 2 + 2\ln 3 = \ln(72) \le \ln(800),\\ (2,5)&:&5\ln 2 + 2\ln 5 = \ln(800),\\ (2,7)&:&7\ln 2 + 2\ln 7 = \ln(6272) > \ln(800),\\ (3,5)&:&5\ln 3 + 3\ln 5 = \ln(6075) > \ln(800). \end{aligned}$$
Kalan tüm çiftler daha da büyüktür. Bu yüzden \(800\)'ü aşmayan hibrit tamsayılar yalnızca
$$2^3 3^2 = 72,\qquad 2^5 5^2 = 800$$
olur. Sonuç olarak \(H(800,1)=2\) elde edilir; bu da uygulamanın küçük doğrulama değerine tam uyar.
C++, Python ve Java uygulamaları aynı hattı izler. Önce \(\Lambda=E\ln B\) kayan nokta aritmetiğiyle hesaplanır ve buradan \(\Lambda/\ln 2\) değerinin biraz üstünde güvenli bir asal üst sınırı türetilir. Ardından bu sınıra kadar tüm asallar Eratosthenes eleği ile üretilir.
Sonraki adımda her asal için \(\ln p\) değeri bir kez önceden hesaplanır. Sayım aşamasında bir işaretçi listenin başında, diğer işaretçi sonunda durur. Her sol asal için sağ işaretçi, \(q\ln p + p\ln q \le \Lambda\) sağlanana kadar sola kaydırılır. Bu noktada iki işaretçi arasındaki bütün asallar geçerli ortaklar olduğundan, blok uzunluğu doğrudan sonuca eklenir.
Sağ işaretçi tüm çalışma boyunca yalnızca tek yönde hareket ettiği için bu tarama, üretilen asal sayısı cinsinden lineerdir. Sınırdaki eşitlik durumlarının kayan nokta yuvarlaması nedeniyle yanlışlıkla dışlanmaması için karşılaştırmada çok küçük bir tolerans da kullanılır.
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1)$$
olsun. \(Q\)'ya kadar elek kurmanın maliyeti \(O(Q\log\log Q)\) zaman ve \(O(Q)\) bellektir. Logaritma tablosunu hazırlamak \(O(\pi(Q))\) sürer. İki işaretçili tarama da \(O(\pi(Q))\) zamanda tamamlanır; çünkü sol işaretçi her asalı bir kez ziyaret eder ve sağ işaretçi liste üzerinde toplamda en fazla bir kez sola yürür.
Dolayısıyla toplam çalışma süresi
$$O(Q\log\log Q)$$
ve bellek kullanımı
$$O(Q)$$
olur.
Un entero híbrido es un número de la forma \(p^q q^p\), donde \(p\) y \(q\) son primos distintos. Por la factorización prima única, dos pares de primos diferentes no pueden producir el mismo valor, así que contar los enteros híbridos que no superan \(B^E\) equivale a contar pares primos \(p<q\) que satisfacen
$$p^q q^p \le B^E.$$
La entrada objetivo es \(B=800800\) y \(E=800800\). Evaluar directamente esas potencias es inviable, por lo que la solución traslada todo al espacio logarítmico y luego aprovecha una estructura monótona para contar los pares válidos.
Definimos
$$H(B,E)=\#\{(p,q): p<q,\ p^q q^p \le B^E\},$$
donde \(p\) y \(q\) son primos. Lo que debemos calcular es \(H(800800,800800)\).
Cada entero híbrido queda determinado de forma única por sus dos primos base. Por eso no hace falta construir el número \(p^q q^p\); basta con decidir si el par correspondiente queda por debajo del umbral \(B^E\).
La pregunta original se convierte así en un problema de conteo sobre pares ordenados \(p<q\). Cada par aceptado aporta exactamente un entero híbrido.
Sea
$$\Lambda = E\ln B.$$
Como el logaritmo natural es estrictamente creciente en los números positivos, se cumple
$$p^q q^p \le B^E \iff \ln(p^q q^p)\le \ln(B^E).$$
Aplicando \(\ln(a^b)=b\ln a\), obtenemos
$$q\ln p + p\ln q \le \Lambda.$$
Ese es el paso decisivo de la solución: las potencias gigantes se sustituyen por una comparación entre dos términos logarítmicos manejables.
En cualquier par válido se tiene \(p\ge 2\), luego \(\ln p\ge \ln 2\). Por tanto,
$$q\ln 2 \le q\ln p \le q\ln p + p\ln q \le \Lambda.$$
De aquí se deduce que el primo mayor debe satisfacer
$$q \le \frac{\Lambda}{\ln 2}.$$
Por consiguiente, basta generar todos los primos hasta una cota de la forma
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
El pequeño margen aditivo usado en la práctica solo sirve para cubrir efectos de truncamiento y redondeo.
Fijemos un primo \(p\) y consideremos
$$f_p(x)=x\ln p + p\ln x \qquad (x>1).$$
Su derivada es
$$f_p'(x)=\ln p + \frac{p}{x} > 0,$$
así que \(f_p(x)\) crece estrictamente. Para un primo izquierdo fijo \(p\), los primos derechos válidos forman un bloque inicial continuo de la lista ordenada: en cuanto la desigualdad falla para un cierto \(q\), falla también para todos los mayores.
Además, para un primo derecho fijo \(q\), la función
$$g_q(x)=q\ln x + x\ln q$$
también es creciente porque
$$g_q'(x)=\frac{q}{x}+\ln q > 0.$$
Eso implica que, cuando el primo izquierdo aumenta, el mayor primo derecho admisible nunca puede desplazarse hacia la derecha. Por eso un único puntero derecho que solo retrocede basta para todo el conteo.
Sea la lista de primos \(r_0<r_1<\dots<r_{m-1}\). Para un índice fijo \(i\), definamos \(j\) como el mayor índice con \(i<j\) tal que
$$r_j\ln r_i + r_i\ln r_j \le \Lambda.$$
Entonces los índices \(k\) con \(i<k\le j\) son exactamente los compañeros válidos de \(r_i\). En consecuencia, el primo izquierdo \(r_i\) aporta
$$j-i$$
pares al total. Sumando estas longitudes de bloque sobre todos los \(i\), cada par válido se cuenta una sola vez.
Aquí
$$\Lambda=\ln 800.$$
La cota para el primo mayor es
$$q\le \frac{\ln 800}{\ln 2}=\log_2 800 < 10,$$
de modo que solo necesitamos revisar \(2,3,5,7\).
Probamos los pares posibles:
$$\begin{aligned} (2,3)&:&3\ln 2 + 2\ln 3 = \ln(72) \le \ln(800),\\ (2,5)&:&5\ln 2 + 2\ln 5 = \ln(800),\\ (2,7)&:&7\ln 2 + 2\ln 7 = \ln(6272) > \ln(800),\\ (3,5)&:&5\ln 3 + 3\ln 5 = \ln(6075) > \ln(800). \end{aligned}$$
Todos los demás pares son todavía mayores. Por tanto, los únicos enteros híbridos que no superan \(800\) son
$$2^3 3^2 = 72,\qquad 2^5 5^2 = 800.$$
Así, \(H(800,1)=2\), que coincide con la verificación pequeña de las implementaciones.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero calculan \(\Lambda=E\ln B\) en coma flotante y obtienen a partir de ahí un límite superior seguro, ligeramente por encima de \(\Lambda/\ln 2\). Después generan todos los primos hasta ese límite mediante una criba de Eratóstenes.
Luego almacenan una vez el valor \(\ln p\) de cada primo, para no repetir cálculos dentro del barrido. En la fase de conteo, un puntero comienza al inicio de la lista y otro al final. Para cada primo izquierdo, el puntero derecho se desplaza hacia la izquierda hasta que la desigualdad \(q\ln p + p\ln q \le \Lambda\) vuelve a ser cierta. En ese instante, todos los primos entre ambos punteros forman pares válidos con el primo fijo, y se suma directamente el tamaño de ese bloque.
Como el puntero derecho nunca retrocede hacia la derecha, el barrido completo es lineal en el número de primos generados. La comparación usa además una tolerancia numérica diminuta para que los casos de igualdad exacta no se pierdan por redondeo en coma flotante.
Sea
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
La criba hasta \(Q\) cuesta \(O(Q\log\log Q)\) tiempo y \(O(Q)\) memoria. Precalcular los logaritmos requiere \(O(\pi(Q))\). El barrido con dos punteros también es \(O(\pi(Q))\), porque el puntero izquierdo visita cada primo una vez y el derecho solo puede desplazarse hacia la izquierda una cantidad total lineal.
En consecuencia, el coste total es
$$O(Q\log\log Q)$$
con consumo de memoria
$$O(Q).$$
混合整数是形如 \(p^q q^p\) 的数，其中 \(p\) 和 \(q\) 是两个不同的素数。由于算术基本定理保证素因子分解唯一，不同的素数对不可能产生同一个值，因此统计不超过 \(B^E\) 的混合整数，等价于统计满足
$$p^q q^p \le B^E$$
的素数对 \(p<q\)。目标输入是 \(B=800800\)、\(E=800800\)。直接计算这些幂几乎不可能，所以解法先把不等式改写成对数形式，再利用有序素数表上的单调性完成计数。
定义
$$H(B,E)=\#\{(p,q): p<q,\ p^q q^p \le B^E\},$$
其中 \(p\) 与 \(q\) 都是素数。题目要求的就是 \(H(800800,800800)\)。
每一个混合整数都由它的两个素数底数唯一确定，所以我们根本不需要真的把 \(p^q q^p\) 算出来。只要能判断对应的素数对是否落在阈值 \(B^E\) 之内，就已经完成了这一步。
因此，原题本质上变成了一个关于有序素数对 \(p<q\) 的计数问题。每找到一个合法的素数对，就恰好对应一个混合整数。
设
$$\Lambda = E\ln B.$$
由于自然对数在正实数上严格递增，有
$$p^q q^p \le B^E \iff \ln(p^q q^p)\le \ln(B^E).$$
再利用 \(\ln(a^b)=b\ln a\)，可得
$$q\ln p + p\ln q \le \Lambda.$$
这就是整个方法的关键变形。原本无法直接处理的超大幂，被替换成了两个普通对数项的和，数值规模一下子变得可控。
任何合法素数对都满足 \(p\ge 2\)，因此 \(\ln p\ge \ln 2\)。于是
$$q\ln 2 \le q\ln p \le q\ln p + p\ln q \le \Lambda.$$
这立刻推出右侧较大的素数必须满足
$$q \le \frac{\Lambda}{\ln 2}.$$
所以只要生成不超过
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1)$$
的全部素数，就已经覆盖了所有可能出现的候选。实现里额外加上的一个很小常数，只是为了给浮点截断和边界舍入留出保险余量，数学上真正的范围已经由上式确定。
固定左侧素数 \(p\)，考虑函数
$$f_p(x)=x\ln p + p\ln x \qquad (x>1).$$
它的导数为
$$f_p'(x)=\ln p + \frac{p}{x} > 0,$$
所以 \(f_p(x)\) 严格递增。这意味着：当左侧素数 \(p\) 固定时，满足条件的右侧素数在排好序的素数表中一定形成一个连续的前缀。一旦某个 \(q\) 已经让不等式失效，更大的素数只会更不可能满足条件。
再固定右侧素数 \(q\)，看函数
$$g_q(x)=q\ln x + x\ln q.$$
同样有
$$g_q'(x)=\frac{q}{x}+\ln q > 0,$$
因此它对 \(x\) 也是严格递增的。于是，当左侧素数逐步增大时，最大的可行右侧素数不可能向右移动，只可能保持不变或向左收缩。这正是双指针算法成立的原因。
设素数表为 \(r_0<r_1<\dots<r_{m-1}\)。固定一个左端索引 \(i\)，设 \(j\) 是满足 \(i<j\) 且
$$r_j\ln r_i + r_i\ln r_j \le \Lambda$$
的最大索引。那么对所有 \(i<k\le j\)，素数 \(r_k\) 都是 \(r_i\) 的合法搭档；而所有 \(k>j\) 的素数都已经太大，不再满足条件。
因此，左端素数 \(r_i\) 对总答案的贡献就是
$$j-i.$$
把所有左端点的这类连续区间长度加起来，就会把每一个合法素数对恰好统计一次，而且不会重数。
这时
$$\Lambda=\ln 800.$$
较大素数的上界为
$$q\le \frac{\ln 800}{\ln 2}=\log_2 800 < 10,$$
所以只需要检查素数 \(2,3,5,7\)。
逐个验证可能的素数对：
$$\begin{aligned} (2,3)&:&3\ln 2 + 2\ln 3 = \ln(72) \le \ln(800),\\ (2,5)&:&5\ln 2 + 2\ln 5 = \ln(800),\\ (2,7)&:&7\ln 2 + 2\ln 7 = \ln(6272) > \ln(800),\\ (3,5)&:&5\ln 3 + 3\ln 5 = \ln(6075) > \ln(800). \end{aligned}$$
其他组合只会更大，因此不超过 \(800\) 的混合整数只有两个：
$$2^3 3^2 = 72,\qquad 2^5 5^2 = 800.$$
所以 \(H(800,1)=2\)。这正好与实现中使用的小型校验结果一致。
C++、Python 和 Java 实现遵循完全相同的流程。首先用浮点数计算 \(\Lambda=E\ln B\)，并据此取一个略高于 \(\Lambda/\ln 2\) 的安全上界。然后用埃拉托斯特尼筛生成不超过这个上界的全部素数。
接下来，程序会把每个素数的 \(\ln p\) 预先存好，避免在计数循环里重复求对数。真正计数时，一个指针从素数表左端向右枚举，另一个指针从右端开始。对于当前左端素数，如果最右端候选还不满足 \(q\ln p + p\ln q \le \Lambda\)，就把右指针不断左移，直到条件重新成立。此时从左指针之后到右指针为止的所有素数都能与当前左端组成合法配对，因此可以一次性把这一整段的长度加入答案。
由于右指针在整个运行过程中只会向左移动，不会反复来回，所以这一扫描阶段对素数表长度是线性的。为了避免浮点舍入把本来恰好相等的边界情况误判为超出阈值，实现还在比较时加入了一个极小的容差。
记
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
筛到 \(Q\) 的时间复杂度是 \(O(Q\log\log Q)\)，空间复杂度是 \(O(Q)\)。预计算素数对数需要 \(O(\pi(Q))\) 时间。双指针扫描同样是 \(O(\pi(Q))\)，因为左指针访问每个素数一次，而右指针在整个过程中最多只会从表尾向左走过一遍。
因此，总体时间复杂度为
$$O(Q\log\log Q),$$
总体空间复杂度为
$$O(Q).$$
Гибридное число имеет вид \(p^q q^p\), где \(p\) и \(q\) — разные простые числа. Благодаря единственности разложения на простые множители одно и то же число не может быть получено из двух разных пар простых. Значит, чтобы посчитать гибридные числа, не превосходящие \(B^E\), достаточно посчитать пары простых \(p<q\), для которых
$$p^q q^p \le B^E.$$
В задаче нужно вычислить это для \(B=800800\) и \(E=800800\). Напрямую работать с такими степенями нельзя, поэтому решение переходит к логарифмам и затем использует монотонный проход по списку простых.
Обозначим
$$H(B,E)=\#\{(p,q): p<q,\ p^q q^p \le B^E\},$$
где \(p\) и \(q\) — простые числа. Требуется найти \(H(800800,800800)\).
Каждое гибридное число однозначно определяется своей парой простых оснований. Поэтому само число \(p^q q^p\) строить не требуется: достаточно понять, удовлетворяет ли соответствующая пара порогу \(B^E\).
Тем самым исходная задача превращается в задачу подсчета упорядоченных пар \(p<q\). Каждая допустимая пара дает ровно одно гибридное число.
Положим
$$\Lambda = E\ln B.$$
Так как натуральный логарифм строго возрастает на положительных числах, имеем
$$p^q q^p \le B^E \iff \ln(p^q q^p)\le \ln(B^E).$$
Используя формулу \(\ln(a^b)=b\ln a\), получаем
$$q\ln p + p\ln q \le \Lambda.$$
Именно здесь происходит главный выигрыш: вместо гигантских степеней остается сравнение двух логарифмических слагаемых умеренного размера.
В любой допустимой паре \(p\ge 2\), а значит \(\ln p\ge \ln 2\). Следовательно,
$$q\ln 2 \le q\ln p \le q\ln p + p\ln q \le \Lambda.$$
Отсюда немедленно следует верхняя граница
$$q \le \frac{\Lambda}{\ln 2}.$$
Поэтому достаточно сгенерировать все простые числа до величины вида
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
Небольшой запас в реализации нужен только как страховка от эффектов усечения и погрешностей округления.
Зафиксируем левое простое \(p\) и рассмотрим функцию
$$f_p(x)=x\ln p + p\ln x \qquad (x>1).$$
Ее производная равна
$$f_p'(x)=\ln p + \frac{p}{x} > 0,$$
то есть \(f_p(x)\) строго возрастает. Значит, для фиксированного левого простого все допустимые правые простые образуют начальный непрерывный блок в отсортированном списке: как только неравенство перестало выполняться для некоторого \(q\), оно уже не выполнится ни для какого большего простого.
Аналогично, для фиксированного правого простого \(q\) функция
$$g_q(x)=q\ln x + x\ln q$$
тоже возрастает, потому что
$$g_q'(x)=\frac{q}{x}+\ln q > 0.$$
Следовательно, когда левое простое увеличивается, максимальный допустимый правый индекс никогда не может сдвинуться вправо. Именно поэтому достаточно одного правого указателя, который движется только влево.
Пусть список простых имеет вид \(r_0<r_1<\dots<r_{m-1}\). Для фиксированного \(i\) обозначим через \(j\) наибольший индекс, удовлетворяющий \(i<j\) и условию
$$r_j\ln r_i + r_i\ln r_j \le \Lambda.$$
Тогда именно простые \(r_k\) с \(i<k\le j\) образуют допустимые пары с \(r_i\), а все \(k>j\) уже слишком велики. Следовательно, вклад левого простого \(r_i\) в ответ равен
$$j-i.$$
Суммируя такие длины блоков по всем \(i\), мы учитываем каждую допустимую пару ровно один раз.
Здесь
$$\Lambda=\ln 800.$$
Верхняя граница для большего простого равна
$$q\le \frac{\ln 800}{\ln 2}=\log_2 800 < 10,$$
поэтому нужно проверить только простые \(2,3,5,7\).
Перебираем возможные пары:
$$\begin{aligned} (2,3)&:&3\ln 2 + 2\ln 3 = \ln(72) \le \ln(800),\\ (2,5)&:&5\ln 2 + 2\ln 5 = \ln(800),\\ (2,7)&:&7\ln 2 + 2\ln 7 = \ln(6272) > \ln(800),\\ (3,5)&:&5\ln 3 + 3\ln 5 = \ln(6075) > \ln(800). \end{aligned}$$
Остальные пары только больше. Значит, не превосходят \(800\) лишь два гибридных числа:
$$2^3 3^2 = 72,\qquad 2^5 5^2 = 800.$$
Следовательно, \(H(800,1)=2\), что совпадает с малой проверкой в реализации.
Реализации на C++, Python и Java устроены одинаково. Сначала в плавающей точке вычисляется \(\Lambda=E\ln B\), затем берется безопасная верхняя граница немного выше \(\Lambda/\ln 2\). После этого с помощью решета Эратосфена строится список всех простых до этой границы.
Далее для каждого простого один раз сохраняется значение \(\ln p\), чтобы не пересчитывать логарифмы внутри основного цикла. На этапе подсчета один указатель проходит список слева направо, а второй стартует справа. Для каждого левого простого правый указатель сдвигается влево, пока не станет истинным неравенство \(q\ln p + p\ln q \le \Lambda\). В этот момент весь блок простых между указателями образует допустимые пары с текущим левым простым, и длина блока сразу добавляется к ответу.
Поскольку правый указатель за все время движется только в одном направлении, этот проход линейный по числу найденных простых. Чтобы случаи точного равенства не выпадали из-за ошибок округления, в сравнении используется очень маленький численный допуск.
Пусть
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
Построение решета до \(Q\) требует \(O(Q\log\log Q)\) времени и \(O(Q)\) памяти. Предварительный расчет логарифмов занимает \(O(\pi(Q))\). Двухуказательный проход также имеет сложность \(O(\pi(Q))\), потому что левый указатель посещает каждый простой один раз, а правый может пройти список справа налево только один раз.
Итак, общая асимптотика по времени равна
$$O(Q\log\log Q),$$
а по памяти
$$O(Q).$$
العدد الهجين هو عدد من الصورة \(p^q q^p\)، حيث إن \(p\) و\(q\) عددان أوليان مختلفان. وبسبب وحيدية التحليل إلى عوامل أولية، لا يمكن لزوجين مختلفين من الأعداد الأولية أن ينتجا العدد نفسه. لذلك فإن عدّ الأعداد الهجينة التي لا تتجاوز \(B^E\) يكافئ عدّ أزواج الأعداد الأولية \(p<q\) التي تحقق
$$p^q q^p \le B^E.$$
في هذه المسألة تكون القيمتان المستهدفتان هما \(B=800800\) و\(E=800800\). الحساب المباشر لهذه القوى غير عملي تمامًا، لذا تنقل الحلول الشرط إلى صيغة لوغاريتمية ثم تستفيد من خاصية الرتابة في قائمة الأعداد الأولية المرتبة.
لنعرّف
$$H(B,E)=\#\{(p,q): p<q,\ p^q q^p \le B^E\},$$
حيث إن \(p\) و\(q\) أوليان. المطلوب إذًا هو حساب \(H(800800,800800)\).
كل عدد هجين صالح يتحدد بصورة وحيدة بواسطة العددين الأوليين اللذين يبنيانه. لهذا لا حاجة إلى تكوين العدد \(p^q q^p\) نفسه؛ يكفي أن نعرف هل الزوج الموافق يقع تحت الحد \(B^E\) أم لا.
بهذه الطريقة تتحول المسألة الأصلية إلى مسألة عدّ لأزواج مرتبة \(p<q\). وكل زوج مقبول يضيف عددًا هجينًا واحدًا فقط إلى الإجابة.
لنضع
$$\Lambda = E\ln B.$$
وبما أن اللوغاريتم الطبيعي دالة متزايدة تمامًا على الأعداد الموجبة، فإن
$$p^q q^p \le B^E \iff \ln(p^q q^p)\le \ln(B^E).$$
وباستخدام العلاقة \(\ln(a^b)=b\ln a\) نحصل على
$$q\ln p + p\ln q \le \Lambda.$$
هذه هي النقلة الأساسية في الحل: القوى الضخمة تختفي، ويبقى لدينا مجموع حدين لوغاريتميين يمكن التعامل معهما عدديًا بسهولة.
في كل زوج صالح لدينا \(p\ge 2\)، وبالتالي \(\ln p\ge \ln 2\). ومن ثم
$$q\ln 2 \le q\ln p \le q\ln p + p\ln q \le \Lambda.$$
إذن لا بد أن يحقق العدد الأولي الأكبر الشرط
$$q \le \frac{\Lambda}{\ln 2}.$$
ولهذا يكفي توليد جميع الأعداد الأولية حتى حد من الشكل
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
والزيادة الصغيرة الثابتة المستعملة عمليًا ليست جزءًا من البرهان الرياضي، بل مجرد هامش أمان ضد التقريب والقطع في الحسابات العشرية.
ثبّت عددًا أوليًا أيسر \(p\)، واعتبر الدالة
$$f_p(x)=x\ln p + p\ln x \qquad (x>1).$$
مشتقتها هي
$$f_p'(x)=\ln p + \frac{p}{x} > 0,$$
ولذلك فهي دالة متزايدة تمامًا. هذا يعني أنه عند تثبيت \(p\)، فإن الأعداد الأولية اليمنى المقبولة تشكل مقطعًا أوليًا متصلًا من قائمة الأعداد الأولية المرتبة: إذا فشلت المتراجحة عند قيمة معيّنة من \(q\)، فإنها ستفشل أيضًا عند كل عدد أولي أكبر.
وبالمثل، إذا ثبّتنا \(q\)، فإن الدالة
$$g_q(x)=q\ln x + x\ln q$$
متزايدة أيضًا لأن
$$g_q'(x)=\frac{q}{x}+\ln q > 0.$$
ومن هنا نستنتج أن أكبر شريك أيمن صالح لا يمكنه أن يتحرك إلى اليمين عندما يكبر الطرف الأيسر؛ إما أن يبقى في مكانه أو يتحرك إلى اليسار. وهذا هو الأساس الذي يجعل مؤشّرًا أيمن واحدًا كافيًا طوال عملية العد.
لنكتب قائمة الأعداد الأولية على الصورة \(r_0<r_1<\dots<r_{m-1}\). ولعدد ثابت من الفهارس \(i\)، ليكن \(j\) هو أكبر فهرس يحقق \(i<j\) والمتراجحة
$$r_j\ln r_i + r_i\ln r_j \le \Lambda.$$
عندئذ تكون جميع القيم \(r_k\) ذات الفهارس \(i<k\le j\) شركاء صالحين للعدد \(r_i\)، بينما تصبح كل القيم ذات \(k>j\) كبيرة أكثر من اللازم. لذا فإن مساهمة الطرف الأيسر \(r_i\) في الجواب هي
$$j-i.$$
وجمع هذه الأطوال على جميع الفهارس اليسرى يعدّ كل زوج صالح مرة واحدة بالضبط من دون تكرار.
لدينا هنا
$$\Lambda=\ln 800.$$
والحد الأعلى للعدد الأولي الأكبر هو
$$q\le \frac{\ln 800}{\ln 2}=\log_2 800 < 10,$$
ولذلك يكفي فحص الأعداد الأولية \(2,3,5,7\) فقط.
نختبر الأزواج الممكنة:
$$\begin{aligned} (2,3)&:&3\ln 2 + 2\ln 3 = \ln(72) \le \ln(800),\\ (2,5)&:&5\ln 2 + 2\ln 5 = \ln(800),\\ (2,7)&:&7\ln 2 + 2\ln 7 = \ln(6272) > \ln(800),\\ (3,5)&:&5\ln 3 + 3\ln 5 = \ln(6075) > \ln(800). \end{aligned}$$
أما بقية الأزواج فستكون أكبر من ذلك قطعًا. إذن العددان الهجينان الوحيدان اللذان لا يتجاوزان \(800\) هما
$$2^3 3^2 = 72,\qquad 2^5 5^2 = 800.$$
وعليه نحصل على \(H(800,1)=2\)، وهو نفس مقدار التحقق الصغير المستعمل في التنفيذ.
تنفذ إصدارات C++ وPython وJava الفكرة نفسها خطوة بخطوة. أولًا يُحسب \(\Lambda=E\ln B\) باستخدام أعداد عشرية، ثم يُشتق حد علوي آمن يقع قليلًا فوق \(\Lambda/\ln 2\). بعد ذلك تُولَّد جميع الأعداد الأولية حتى هذا الحد بواسطة غربال إراتوستينس.
ثم تُحسب قيمة \(\ln p\) لكل عدد أولي مرة واحدة فقط وتُخزَّن للاستعمال اللاحق. في مرحلة العد يتحرك مؤشر من يسار قائمة الأعداد الأولية، بينما يبدأ مؤشر آخر من يمينها. ولكل عدد أولي أيسر، يتحرك المؤشر الأيمن إلى اليسار حتى تصبح المتراجحة \(q\ln p + p\ln q \le \Lambda\) صحيحة. عند تلك اللحظة تكون جميع الأعداد الأولية الواقعة بين المؤشرين شركاء صالحين لذلك الطرف الأيسر، فيُضاف طول هذا المقطع دفعة واحدة إلى الناتج.
وبما أن المؤشر الأيمن لا يتحرك إلا في اتجاه واحد خلال التشغيل كله، فإن مرحلة المسح هذه خطية في عدد الأعداد الأولية المولدة. كما تُستعمل سماحية عددية صغيرة جدًا حتى لا تؤدي أخطاء التقريب العشري إلى استبعاد الحالات الحدية التي تحقق المساواة تمامًا.
ليكن
$$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$$
توليد جميع الأعداد الأولية حتى \(Q\) بالغربال يحتاج إلى زمن \(O(Q\log\log Q)\) وذاكرة \(O(Q)\). حساب اللوغاريتمات المسبقة يكلف \(O(\pi(Q))\). أما مسح المؤشرين فتكلفته أيضًا \(O(\pi(Q))\)، لأن المؤشر الأيسر يزور كل عدد أولي مرة واحدة، والمؤشر الأيمن لا يستطيع أن يعبر القائمة نحو اليسار إلا مرة واحدة إجمالًا.
ومن ثم فإن الزمن الكلي هو
$$O(Q\log\log Q),$$
واستهلاك الذاكرة هو
$$O(Q).$$