We must count all reduced proper fractions \(a/b\) with \(0 \lt a \lt b \le 1{,}000{,}000\) and \(\gcd(a,b)=1\). Equivalently, if \(F_N\) is the Farey sequence of order \(N\), the requested quantity is \(|F_N|-2\), because the two boundary fractions \(0/1\) and \(1/1\) are excluded.
The implementations do not enumerate fractions directly. Instead, they group the count by denominator and reduce the problem to one exact summation over Euler's totient function.
Let \(T(N)\) denote the number of reduced proper fractions with denominator at most \(N\). The decisive observation is that for each fixed denominator, the allowed numerators are counted by a standard arithmetic function, so the whole problem collapses to a sieve followed by a sum.
Fix a denominator \(d \ge 2\). The admissible numerators are the integers \(a\) with \(1 \le a \lt d\) and \(\gcd(a,d)=1\). By definition, the number of such integers is Euler's totient:
$$\varphi(d)=\#\{\,1 \le a \lt d : \gcd(a,d)=1\,\}.$$
Therefore the full answer is
$$T(N)=\sum_{d=2}^{N}\varphi(d).$$
That identity is the real content of the problem: every reduced proper fraction appears exactly once, classified by its denominator.
If the distinct prime divisors of \(d\) are \(p_1,\dots,p_k\), then
$$\varphi(d)=d\prod_{p\mid d}\left(1-\frac{1}{p}\right).$$
The implementations use this product formula in sieve form. They start from \(\varphi(d)=d\) for every \(d\). When a prime \(p\) is processed, every multiple of \(p\) must lose exactly the fraction \(\frac{1}{p}\) of the numbers still being counted, so the update becomes
$$\varphi(m)\leftarrow \varphi(m)-\frac{\varphi(m)}{p}, \quad p\mid m.$$
This is exact integer arithmetic. Before prime \(p\) is handled, the entry for \(m\) has already been adjusted for smaller prime divisors of \(m\), but the factor \(p\) from the original number \(m\) is still present. So the current value remains divisible by \(p\), and no floating-point approximation is involved.
The loop scans \(2,3,4,\dots,N\). At the moment it reaches \(i\), the equality \(\varphi(i)=i\) means that no smaller prime has modified that entry. A composite number would already have been touched by its smallest prime factor, so an unchanged entry must be prime.
This is the key invariant behind the sieve: unchanged entries identify primes, and each discovered prime updates all of its multiples exactly once.
For denominator \(5\), every numerator \(1,2,3,4\) is coprime to \(5\), so \(\varphi(5)=4\). For denominator \(6\), only \(1\) and \(5\) survive because \(2,3,4\) share a common factor with \(6\), so \(\varphi(6)=2\).
Continuing through all denominators from \(2\) to \(8\) gives
$$\varphi(2)=1,\ \varphi(3)=2,\ \varphi(4)=2,\ \varphi(5)=4,\ \varphi(6)=2,\ \varphi(7)=6,\ \varphi(8)=4.$$
Hence
$$T(8)=1+2+2+4+2+6+4=21.$$
This small case makes the structure visible and is also the checkpoint used by the implementations that include a built-in sanity test.
Each individual totient value satisfies \(\varphi(d)\le d\le 10^6\), so the table itself fits comfortably in 32-bit integers. The final sum does not: it grows on the order of \(N^2\). As a result, the accumulator must use a 64-bit integer type in C++ and Java, while Python relies on arbitrary-precision integers automatically.
The C++, Python, and Java implementations allocate an array of length \(N+1\) and store the index itself in each position. After this step, the table represents the unreduced starting point \(\varphi(d)=d\).
The main loop runs from \(2\) to \(N\). Whenever an entry is still equal to its index, the current number is prime. The implementation then visits every multiple of that prime and applies the exact update \(\varphi(m)\leftarrow \varphi(m)-\varphi(m)/p\).
By the end of the sweep, each table entry has received one multiplicative correction for every distinct prime dividing its index, so the array contains all totient values up to the limit.
The final pass computes \(\varphi(2)+\varphi(3)+\cdots+\varphi(N)\). Two of the implementations also verify the checkpoint \(T(8)=21\) before the full run, which is a simple guard against an indexing or sieve mistake.
Initializing the table costs \(O(N)\). The sieve work is
$$\sum_{p\le N}\frac{N}{p}=O(N\log\log N),$$
where the sum is over primes. The final accumulation is another \(O(N)\) pass, so the overall running time is \(O(N\log\log N)\).
The space usage is \(O(N)\) for the totient table. For \(N=10^6\), this is easily practical, which is why the direct summatory-totient method is the natural exact solution.
Gesucht ist die Anzahl aller gekürzten echten Brüche \(a/b\) mit \(0 \lt a \lt b \le 1{,}000{,}000\) und \(\gcd(a,b)=1\). Äquivalent dazu kann man die Farey-Folge \(F_N\) der Ordnung \(N\) betrachten: Der gesuchte Wert ist \(|F_N|-2\), weil die beiden Randbrüche \(0/1\) und \(1/1\) nicht mitgezählt werden.
Die Implementierungen erzeugen diese Brüche nicht einzeln. Stattdessen gruppieren sie nach dem Nenner und reduzieren die Aufgabe auf eine exakte Summation über die Eulersche \(\varphi\)-Funktion.
Sei \(T(N)\) die Anzahl der gekürzten echten Brüche mit Nenner höchstens \(N\). Der entscheidende Schritt ist, für jeden festen Nenner zu zählen, wie viele Zähler zulässig sind. Genau das liefert eine klassische zahlentheoretische Funktion.
Fixiere einen Nenner \(d \ge 2\). Zulässig sind genau die Zähler \(a\) mit \(1 \le a \lt d\) und \(\gcd(a,d)=1\). Per Definition ist deren Anzahl die Eulersche Totientfunktion:
$$\varphi(d)=\#\{\,1 \le a \lt d : \gcd(a,d)=1\,\}.$$
Daraus folgt unmittelbar
$$T(N)=\sum_{d=2}^{N}\varphi(d).$$
Damit ist der kombinatorische Kern bereits gelöst: Jeder gekürzte echte Bruch wird genau einmal über seinen Nenner erfasst.
Hat \(d\) die verschiedenen Primteiler \(p_1,\dots,p_k\), dann gilt
$$\varphi(d)=d\prod_{p\mid d}\left(1-\frac{1}{p}\right).$$
Die Implementierungen setzen diese Produktformel als Sieb um. Zunächst wird \(\varphi(d)=d\) für alle \(d\) gesetzt. Wenn eine Primzahl \(p\) verarbeitet wird, muss bei jedem Vielfachen von \(p\) genau der Anteil \(\frac{1}{p}\) der noch gezählten Werte entfernt werden. Deshalb lautet das Update
$$\varphi(m)\leftarrow \varphi(m)-\frac{\varphi(m)}{p}, \quad p\mid m.$$
Das ist exakte Ganzzahlarithmetik. Bevor \(p\) an der Reihe ist, wurde der Eintrag für \(m\) zwar schon um kleinere Primteiler korrigiert, aber der Faktor \(p\) aus dem ursprünglichen \(m\) ist noch vorhanden. Daher bleibt der aktuelle Wert durch \(p\) teilbar.
Die Schleife läuft über \(2,3,4,\dots,N\). Wenn beim Erreichen von \(i\) noch \(\varphi(i)=i\) gilt, dann hat kein kleinerer Primteiler diesen Eintrag verändert. Eine zusammengesetzte Zahl wäre aber bereits von ihrem kleinsten Primteiler bearbeitet worden. Also bedeutet ein unveränderter Eintrag genau: \(i\) ist prim.
Diese Invariante verleiht dem Verfahren seine Eratosthenes-Struktur: Unveränderte Einträge markieren Primzahlen, und jede gefundene Primzahl aktualisiert all ihre Vielfachen.
Beim Nenner \(5\) sind alle Zähler \(1,2,3,4\) teilerfremd zu \(5\), also \(\varphi(5)=4\). Beim Nenner \(6\) bleiben nur \(1\) und \(5\) übrig, weil \(2,3,4\) einen gemeinsamen Teiler mit \(6\) haben; daher \(\varphi(6)=2\).
Für alle Nenner von \(2\) bis \(8\) erhält man
$$\varphi(2)=1,\ \varphi(3)=2,\ \varphi(4)=2,\ \varphi(5)=4,\ \varphi(6)=2,\ \varphi(7)=6,\ \varphi(8)=4.$$
Also
$$T(8)=1+2+2+4+2+6+4=21.$$
Dieses kleine Beispiel macht die Struktur greifbar und dient zugleich als Prüfpunkt in den Implementierungen, die einen eingebauten Test enthalten.
Jeder einzelne Totientwert erfüllt \(\varphi(d)\le d\le 10^6\), sodass das Array selbst problemlos mit 32-Bit-Einträgen auskommt. Die Endsumme wächst jedoch in der Größenordnung von \(N^2\). Deshalb muss der Akkumulator in C++ und Java 64 Bit breit sein; Python verwendet automatisch Ganzzahlen mit beliebiger Genauigkeit.
Die C++-, Python- und Java-Implementierungen erzeugen ein Array der Länge \(N+1\) und schreiben an jede Position zunächst ihren eigenen Index. Damit repräsentiert die Tabelle den Ausgangszustand \(\varphi(d)=d\).
Die Hauptschleife läuft von \(2\) bis \(N\). Immer wenn ein Eintrag noch gleich seinem Index ist, handelt es sich um eine Primzahl. Anschließend werden alle Vielfachen dieser Primzahl besucht und mit \(\varphi(m)\leftarrow \varphi(m)-\varphi(m)/p\) aktualisiert.
Nach Abschluss dieses Durchlaufs hat jeder Eintrag genau eine Korrektur für jeden verschiedenen Primteiler seines Index erhalten. Damit stehen alle Totientwerte bis zum Limit direkt im Array.
Zum Schluss wird \(\varphi(2)+\varphi(3)+\cdots+\varphi(N)\) addiert. Zwei der Implementierungen prüfen vorher noch den Kontrollwert \(T(8)=21\), um einen Indexierungs- oder Siebfehler früh zu erkennen.
Die Initialisierung kostet \(O(N)\). Die Siebarbeit ist
$$\sum_{p\le N}\frac{N}{p}=O(N\log\log N),$$
wobei über alle Primzahlen \(p\) summiert wird. Das abschließende Addieren ist ein weiterer \(O(N)\)-Durchlauf, also liegt die Gesamtlaufzeit bei \(O(N\log\log N)\).
Der Speicherbedarf beträgt \(O(N)\) für die Totient-Tabelle. Für \(N=10^6\) ist das problemlos praktikabel; deshalb ist die summatorische Totient-Methode hier die naheliegende exakte Lösung.
İstenen şey, \(0 \lt a \lt b \le 1{,}000{,}000\) ve \(\gcd(a,b)=1\) koşullarını sağlayan tüm indirgenmiş öz kesirlerin \(a/b\) sayısını bulmaktır. Aynı problem, \(N\) mertebesindeki Farey dizisi \(F_N\) üzerinden de ifade edilebilir: Aranan değer \(|F_N|-2\)'dir, çünkü \(0/1\) ve \(1/1\) uç kesirleri sayıya dahil edilmez.
Uygulamalar kesirleri tek tek üretmez. Bunun yerine sayımı paydaya göre ayırır ve problemi Euler'in totient fonksiyonu üzerinde tek bir kesin toplama indirger.
\(T(N)\), paydası en fazla \(N\) olan indirgenmiş öz kesirlerin sayısı olsun. Belirleyici fikir şudur: sabit bir payda için geçerli payların sayısı doğrudan standart bir aritmetik fonksiyonla ölçülür. Böylece tüm problem bir eleğe ve ardından bir toplamaya dönüşür.
Sabit bir \(d \ge 2\) paydası alalım. Geçerli paylar, \(1 \le a \lt d\) ve \(\gcd(a,d)=1\) koşulunu sağlayan tamsayılardır. Tanım gereği bunların sayısı Euler totienti \(\varphi(d)\)'dir:
$$\varphi(d)=\#\{\,1 \le a \lt d : \gcd(a,d)=1\,\}.$$
Dolayısıyla toplam cevap
$$T(N)=\sum_{d=2}^{N}\varphi(d).$$
Problemin asıl kombinatorik içeriği budur: Her indirgenmiş öz kesir, paydasına göre tam bir kez sayılır.
\(d\)'nin farklı asal bölenleri \(p_1,\dots,p_k\) ise
$$\varphi(d)=d\prod_{p\mid d}\left(1-\frac{1}{p}\right)$$
eşitliği geçerlidir. Uygulamalar tam olarak bu çarpım formülünü elek biçimine çevirir. Başlangıçta her \(d\) için \(\varphi(d)=d\) alınır. Bir asal \(p\) işlendiğinde, \(p\)'nin her katında halen sayımda kalan değerlerin tam \(\frac{1}{p}\)'lik kısmı çıkarılmalıdır. Bu da şu güncellemeyi verir:
$$\varphi(m)\leftarrow \varphi(m)-\frac{\varphi(m)}{p}, \quad p\mid m.$$
Burada kayan nokta yoktur; işlem tam sayı aritmetiğidir. \(p\) işlenmeden önce \(m\) değeri daha küçük asal bölenler için düzeltilmiş olsa bile, başlangıçtaki \(m\) sayısından gelen \(p\) çarpanı hâlâ içeride kaldığı için mevcut değer \(p\)'ye tam bölünür.
Döngü \(2,3,4,\dots,N\) şeklinde ilerler. Bir \(i\) değerine gelindiğinde hâlâ \(\varphi(i)=i\) ise, bu girişe daha küçük hiçbir asal dokunmamış demektir. Bileşik bir sayı ise en küçük asal böleni tarafından zaten güncellenmiş olurdu. Bu yüzden değişmeden kalan her giriş asaldır.
Eleğin iskeleti bu değişmezden gelir: Değişmeden kalan girişler asal sayıları tanımlar, bulunan her asal da bütün katlarını bir kez günceller.
\(5\) paydası için \(1,2,3,4\) paylarının hepsi \(5\) ile aralarında asal olduğundan \(\varphi(5)=4\) olur. \(6\) paydası için ise yalnızca \(1\) ve \(5\) kalır; çünkü \(2,3,4\), \(6\) ile ortak bölen paylaşır. Bu yüzden \(\varphi(6)=2\).
\(2\)'den \(8\)'e kadar bütün paydalar için değerler
$$\varphi(2)=1,\ \varphi(3)=2,\ \varphi(4)=2,\ \varphi(5)=4,\ \varphi(6)=2,\ \varphi(7)=6,\ \varphi(8)=4$$
şeklindedir. O halde
$$T(8)=1+2+2+4+2+6+4=21.$$
Bu küçük örnek hem matematiği görünür hale getirir hem de yerleşik kontrol içeren uygulamalarda kullanılan doğrulama noktasıdır.
Tek tek \(\varphi(d)\) değerleri \(\varphi(d)\le d\le 10^6\) olduğu için tabloyu 32 bit tamsayılarla tutmak yeterlidir. Ancak son toplam yaklaşık \(N^2\) ölçeğinde büyür. Bu nedenle C++ ve Java sürümlerinde toplam değişkeni 64 bit olmak zorundadır; Python ise bunu kendiliğinden büyük tamsayılarla yönetir.
C++, Python ve Java uygulamaları \(N+1\) uzunluğunda bir dizi ayırır ve her konuma kendi indeksini yazar. Böylece tablo başlangıçta \(\varphi(d)=d\) durumunu temsil eder.
Ana döngü \(2\)'den \(N\)'e kadar gider. Bir giriş hâlâ kendi indeksine eşitse o sayı asaldır. Ardından bu asalin bütün katları ziyaret edilir ve \(\varphi(m)\leftarrow \varphi(m)-\varphi(m)/p\) güncellemesi uygulanır.
Döngü bittiğinde her giriş, indeksini bölen her farklı asal için bir düzeltme almış olur. Böylece tablo, sınıra kadar tüm totient değerlerini içerir.
Son geçişte \(\varphi(2)+\varphi(3)+\cdots+\varphi(N)\) toplanır. Uygulamaların ikisi ayrıca tam çalıştırmadan önce \(T(8)=21\) kontrolünü yapar; bu, indeksleme veya elek hatasını erkenden yakalamak için yararlıdır.
Başlatma adımı \(O(N)\) sürer. Elek maliyeti
$$\sum_{p\le N}\frac{N}{p}=O(N\log\log N)$$
şeklindedir; burada toplam asallar üzerindedir. Son toplama da ek bir \(O(N)\) geçiş olduğundan toplam çalışma süresi \(O(N\log\log N)\) olur.
Bellek kullanımı, totient tablosu için \(O(N)\)'dir. \(N=10^6\) için bu yaklaşım oldukça pratiktir; bu yüzden bu problem için doğal kesin çözüm doğrudan summatory totient yöntemidir.
Debemos contar todas las fracciones propias reducidas \(a/b\) con \(0 \lt a \lt b \le 1{,}000{,}000\) y \(\gcd(a,b)=1\). De forma equivalente, si \(F_N\) es la secuencia de Farey de orden \(N\), la cantidad pedida es \(|F_N|-2\), porque las fracciones extremas \(0/1\) y \(1/1\) no se incluyen.
Las implementaciones no enumeran las fracciones una por una. En cambio, agrupan el conteo por denominador y convierten el problema en una suma exacta sobre la función totiente de Euler.
Sea \(T(N)\) el número de fracciones propias reducidas con denominador a lo sumo \(N\). La idea decisiva es que, para cada denominador fijo, el número de numeradores válidos lo da una función aritmética estándar. Así, todo el problema se reduce a un tamiz y después a una suma.
Fijemos un denominador \(d \ge 2\). Los numeradores admitidos son los enteros \(a\) tales que \(1 \le a \lt d\) y \(\gcd(a,d)=1\). Por definición, su cantidad es el totiente de Euler:
$$\varphi(d)=\#\{\,1 \le a \lt d : \gcd(a,d)=1\,\}.$$
Por lo tanto, la respuesta completa es
$$T(N)=\sum_{d=2}^{N}\varphi(d).$$
Ese es el contenido combinatorio real del problema: cada fracción propia reducida aparece exactamente una vez, clasificada por su denominador.
Si los divisores primos distintos de \(d\) son \(p_1,\dots,p_k\), entonces
$$\varphi(d)=d\prod_{p\mid d}\left(1-\frac{1}{p}\right).$$
Las implementaciones usan esta fórmula producto en forma de tamiz. Se empieza con \(\varphi(d)=d\) para todo \(d\). Cuando se procesa un primo \(p\), cada múltiplo de \(p\) debe perder exactamente la fracción \(\frac{1}{p}\) de los valores que todavía siguen contándose. Por eso la actualización es
$$\varphi(m)\leftarrow \varphi(m)-\frac{\varphi(m)}{p}, \quad p\mid m.$$
Esto es aritmética entera exacta. Antes de tratar a \(p\), la entrada correspondiente a \(m\) ya fue corregida por los primos menores que dividen a \(m\), pero el factor \(p\) procedente del número original \(m\) sigue presente. Por eso el valor actual continúa siendo divisible por \(p\).
El recorrido avanza por \(2,3,4,\dots,N\). Cuando llega a \(i\), la igualdad \(\varphi(i)=i\) significa que ningún primo menor ha modificado todavía esa casilla. Un número compuesto ya habría sido tocado por su menor factor primo. Por tanto, una entrada que permanece intacta identifica exactamente a un primo.
Esa es la invariante central del tamiz: las entradas no modificadas señalan los primos y cada primo descubierto actualiza todos sus múltiplos una vez.
Para el denominador \(5\), todos los numeradores \(1,2,3,4\) son coprimos con \(5\), así que \(\varphi(5)=4\). Para el denominador \(6\), solo sobreviven \(1\) y \(5\), porque \(2,3,4\) comparten un factor con \(6\); por tanto \(\varphi(6)=2\).
Continuando con todos los denominadores desde \(2\) hasta \(8\), obtenemos
$$\varphi(2)=1,\ \varphi(3)=2,\ \varphi(4)=2,\ \varphi(5)=4,\ \varphi(6)=2,\ \varphi(7)=6,\ \varphi(8)=4.$$
Luego
$$T(8)=1+2+2+4+2+6+4=21.$$
Este caso pequeño deja visible la mecánica del problema y además coincide con la comprobación interna usada por las implementaciones que incluyen una prueba de consistencia.
Cada valor individual cumple \(\varphi(d)\le d\le 10^6\), así que la tabla cabe sin dificultad en enteros de 32 bits. El total acumulado no: crece en el orden de \(N^2\). Por eso el acumulador debe ser de 64 bits en C++ y Java, mientras que Python lo maneja con enteros de precisión arbitraria.
Las implementaciones en C++, Python y Java reservan un arreglo de longitud \(N+1\) y colocan el propio índice en cada posición. Tras este paso, la tabla representa el estado inicial \(\varphi(d)=d\).
El bucle principal va de \(2\) a \(N\). Cuando una entrada sigue siendo igual a su índice, el número actual es primo. Entonces la implementación recorre todos sus múltiplos y aplica la actualización exacta \(\varphi(m)\leftarrow \varphi(m)-\varphi(m)/p\).
Al terminar el barrido, cada posición ha recibido una corrección por cada primo distinto que divide a su índice, así que el arreglo contiene todos los valores de \(\varphi\) hasta el límite.
La última pasada suma \(\varphi(2)+\varphi(3)+\cdots+\varphi(N)\). Dos de las implementaciones también verifican antes el punto de control \(T(8)=21\), útil para detectar un error de índices o de tamizado.
La inicialización cuesta \(O(N)\). El trabajo del tamiz es
$$\sum_{p\le N}\frac{N}{p}=O(N\log\log N),$$
donde la suma recorre los primos. La acumulación final es otro paso \(O(N)\), de modo que el tiempo total es \(O(N\log\log N)\).
El espacio utilizado es \(O(N)\) para la tabla de totientes. Para \(N=10^6\), este método es completamente práctico, y por eso la suma de totientes es la solución exacta natural para este problema.
题目要求统计所有满足 \(0 \lt a \lt b \le 1{,}000{,}000\) 且 \(\gcd(a,b)=1\) 的既约真分数 \(a/b\) 的个数。等价地，若 \(F_N\) 表示 \(N\) 阶 Farey 序列，那么所求数量就是 \(|F_N|-2\)，因为端点 \(0/1\) 和 \(1/1\) 不计入答案。
实现并不会逐个生成这些分数，而是按分母分类，把整个问题化成对欧拉函数的一次精确求和。
记 \(T(N)\) 为分母不超过 \(N\) 的既约真分数总数。关键观察是：对于固定分母，合法分子的个数正好由一个标准数论函数给出，因此问题最终会收缩成“先筛出所有 \(\varphi\) 值，再把它们加起来”。
固定一个分母 \(d \ge 2\)。合法分子是所有满足 \(1 \le a \lt d\) 且 \(\gcd(a,d)=1\) 的整数。按照定义，这个数量就是欧拉函数：
$$\varphi(d)=\#\{\,1 \le a \lt d : \gcd(a,d)=1\,\}.$$
因此总答案满足
$$T(N)=\sum_{d=2}^{N}\varphi(d).$$
这一步已经抓住了题目的本质：每一个既约真分数都恰好按自己的分母被统计一次，不会重复，也不会遗漏。
如果 \(d\) 的不同质因子是 \(p_1,\dots,p_k\)，那么有经典公式
$$\varphi(d)=d\prod_{p\mid d}\left(1-\frac{1}{p}\right).$$
实现使用的正是这个乘积公式的筛法版本。最开始先令每个位置都是 \(\varphi(d)=d\)。当处理某个质数 \(p\) 时，所有 \(p\) 的倍数都必须去掉当前仍被计数元素中的 \(\frac{1}{p}\)。于是更新式写成
$$\varphi(m)\leftarrow \varphi(m)-\frac{\varphi(m)}{p}, \quad p\mid m.$$
这不是近似，而是完全精确的整数运算。在处理 \(p\) 之前，\(m\) 对应的位置可能已经按更小的质因子做过修正，但原始数字 \(m\) 中携带的 \(p\) 因子仍然保留在当前值里，所以此时一定还能被 \(p\) 整除。
主循环依次扫描 \(2,3,4,\dots,N\)。当扫描到 \(i\) 时，如果仍然有 \(\varphi(i)=i\)，就说明没有任何更小的质数修改过这个位置。合数一定会先被它的最小质因子碰到，因此“值还等于下标”与“当前数是质数”完全等价。
这正是整个筛法的核心不变量：未被改变的项标记出质数，而每发现一个质数，就把它的所有倍数统一更新一遍。
以分母 \(5\) 为例，分子 \(1,2,3,4\) 全都与 \(5\) 互素，所以 \(\varphi(5)=4\)。分母 \(6\) 时，只有 \(1\) 和 \(5\) 合法，因为 \(2,3,4\) 都与 \(6\) 共享公因子，因此 \(\varphi(6)=2\)。
继续列出 \(2\) 到 \(8\) 的所有值，可得
$$\varphi(2)=1,\ \varphi(3)=2,\ \varphi(4)=2,\ \varphi(5)=4,\ \varphi(6)=2,\ \varphi(7)=6,\ \varphi(8)=4.$$
于是
$$T(8)=1+2+2+4+2+6+4=21.$$
这个小例子把“按分母计数”的结构展示得很清楚，也正是带有内置校验的实现所使用的检查点。
单个欧拉函数值始终满足 \(\varphi(d)\le d\le 10^6\)，因此表中的元素用 32 位整数就足够了。但最终总和的规模大约是 \(N^2\)，远大于 32 位范围，所以在 C++ 和 Java 中必须使用 64 位整数来累加；Python 则自动使用任意精度整数。
C++、Python 和 Java 三种实现都会先分配一个长度为 \(N+1\) 的数组，并把每个位置初始化为它自己的下标。这样一来，整张表就从 \(\varphi(d)=d\) 的原始状态开始。
主循环从 \(2\) 走到 \(N\)。如果当前位置的值还等于下标，就说明当前数字是质数。实现随后遍历这个质数的所有倍数，并执行精确更新 \(\varphi(m)\leftarrow \varphi(m)-\varphi(m)/p\)。
当整个筛法结束后，每个位置都已经针对其所有不同质因子各做过一次修正，所以数组中保存的就是从 \(1\) 到 \(N\) 的全部欧拉函数值。
最后一次遍历把 \(\varphi(2)+\varphi(3)+\cdots+\varphi(N)\) 相加即可。其中两种实现还会在正式计算前先验证 \(T(8)=21\)，用来防止索引或筛法更新出现错误。
初始化数组需要 \(O(N)\) 时间。筛法的总工作量为
$$\sum_{p\le N}\frac{N}{p}=O(N\log\log N),$$
这里求和范围是所有质数 \(p\)。最终求和又是一次 \(O(N)\) 扫描，因此总时间复杂度为 \(O(N\log\log N)\)。
空间复杂度是 \(O(N)\)，主要来自那张欧拉函数表。对 \(N=10^6\) 来说，这个规模非常容易处理，所以“筛出所有 \(\varphi\) 再求和”就是这道题最自然的精确算法。
Нужно посчитать все несократимые правильные дроби \(a/b\), для которых \(0 \lt a \lt b \le 1{,}000{,}000\) и \(\gcd(a,b)=1\). Эквивалентная формулировка использует последовательность Фарея \(F_N\): искомое число равно \(|F_N|-2\), потому что граничные дроби \(0/1\) и \(1/1\) в ответ не входят.
Реализации не перебирают дроби по одной. Вместо этого они считают вклад каждого знаменателя и сводят задачу к точной сумме значений функции Эйлера.
Обозначим через \(T(N)\) число несократимых правильных дробей со знаменателем не больше \(N\). Главная идея состоит в том, что для фиксированного знаменателя количество допустимых числителей выражается через стандартную арифметическую функцию. После этого остаётся только просеять все значения \(\varphi\) и сложить их.
Зафиксируем знаменатель \(d \ge 2\). Подходящими являются те и только те числители \(a\), для которых \(1 \le a \lt d\) и \(\gcd(a,d)=1\). По определению количество таких чисел равно функции Эйлера:
$$\varphi(d)=\#\{\,1 \le a \lt d : \gcd(a,d)=1\,\}.$$
Следовательно, полный ответ имеет вид
$$T(N)=\sum_{d=2}^{N}\varphi(d).$$
Это и есть настоящий комбинаторный стержень задачи: каждая несократимая правильная дробь ровно один раз учитывается своим знаменателем.
Если различные простые делители числа \(d\) равны \(p_1,\dots,p_k\), то
$$\varphi(d)=d\prod_{p\mid d}\left(1-\frac{1}{p}\right).$$
Реализации используют именно эту формулу в виде решета. Сначала для всех \(d\) записывается \(\varphi(d)=d\). Когда обрабатывается простое число \(p\), у каждого кратного \(p\) нужно убрать ровно долю \(\frac{1}{p}\) от значений, которые ещё считаются. Поэтому выполняется обновление
$$\varphi(m)\leftarrow \varphi(m)-\frac{\varphi(m)}{p}, \quad p\mid m.$$
Это точная целочисленная операция. До обработки \(p\) значение для \(m\) уже могло быть скорректировано по меньшим простым делителям, но множитель \(p\), пришедший из исходного числа \(m\), всё ещё сохраняется. Поэтому текущее значение по-прежнему делится на \(p\) без остатка.
Основной цикл идёт по \(2,3,4,\dots,N\). Когда алгоритм доходит до \(i\), равенство \(\varphi(i)=i\) означает, что ни один меньший простой делитель ещё не менял эту ячейку. Составное число уже было бы затронуто своим наименьшим простым делителем. Значит, неизменённая ячейка однозначно указывает на простое число.
Именно этот инвариант делает метод похожим на решето Эратосфена: неизменённые записи обнаруживают простые, а каждый найденный простой обновляет все свои кратные.
Для знаменателя \(5\) все числители \(1,2,3,4\) взаимно просты с \(5\), поэтому \(\varphi(5)=4\). Для знаменателя \(6\) подходят только \(1\) и \(5\), поскольку \(2,3,4\) имеют с \(6\) общий делитель; значит \(\varphi(6)=2\).
Если выписать все значения от \(2\) до \(8\), получится
$$\varphi(2)=1,\ \varphi(3)=2,\ \varphi(4)=2,\ \varphi(5)=4,\ \varphi(6)=2,\ \varphi(7)=6,\ \varphi(8)=4.$$
Тогда
$$T(8)=1+2+2+4+2+6+4=21.$$
Этот маленький пример наглядно показывает устройство задачи и одновременно служит контрольной проверкой в тех реализациях, где встроен тест корректности.
Каждое отдельное значение удовлетворяет неравенству \(\varphi(d)\le d\le 10^6\), поэтому сама таблица спокойно помещается в 32-битные целые. Но итоговая сумма растёт как величина порядка \(N^2\), и 32 бит для неё уже недостаточно. Поэтому в C++ и Java накопитель должен быть 64-битным, а Python использует целые произвольной точности.
Реализации на C++, Python и Java выделяют массив длины \(N+1\) и записывают в каждую позицию её собственный индекс. После этого таблица находится в исходном состоянии \(\varphi(d)=d\).
Главный цикл идёт от \(2\) до \(N\). Если значение по-прежнему равно индексу, текущее число является простым. Затем алгоритм проходит по всем его кратным и применяет точное обновление \(\varphi(m)\leftarrow \varphi(m)-\varphi(m)/p\).
После завершения прохода каждая ячейка уже получила по одной коррекции для каждого различного простого делителя своего индекса, так что массив содержит все значения функции Эйлера до заданного предела.
Последний проход просто вычисляет сумму \(\varphi(2)+\varphi(3)+\cdots+\varphi(N)\). Две реализации перед полным запуском дополнительно проверяют контрольное равенство \(T(8)=21\), чтобы быстро поймать ошибку индексации или обновления решета.
Инициализация требует \(O(N)\) времени. Стоимость решета равна
$$\sum_{p\le N}\frac{N}{p}=O(N\log\log N),$$
где суммирование ведётся по простым \(p\). Финальное сложение — это ещё один проход за \(O(N)\), поэтому общая временная сложность равна \(O(N\log\log N)\).
Память составляет \(O(N)\) и в основном уходит на таблицу значений \(\varphi\). При \(N=10^6\) такой объём легко реалистичен, поэтому прямой подсчёт суммарной функции Эйлера здесь является естественным точным методом.
المطلوب هو عدّ جميع الكسور الحقيقية المختزلة \(a/b\) التي تحقق \(0 \lt a \lt b \le 1{,}000{,}000\) و \(\gcd(a,b)=1\). ويمكن صياغة المسألة بشكل مكافئ عبر متتالية فاري \(F_N\): فالكمية المطلوبة هي \(|F_N|-2\)، لأن الكسرين الحدّيين \(0/1\) و\(1/1\) لا يدخلان في العد.
التنفيذ لا يولّد هذه الكسور واحدًا واحدًا، بل يجمعها بحسب المقام ويحوّل المسألة إلى مجموع دقيق لقيم دالة أويلر \(\varphi\).
لنرمز بـ \(T(N)\) إلى عدد الكسور الحقيقية المختزلة التي لا يزيد مقامها على \(N\). الفكرة الحاسمة هي أن عدد البسوط الصالحة لكل مقام ثابت يُعطى مباشرةً بواسطة دالة عددية معروفة، وعندها تنكمش المسألة كلها إلى غربال ثم عملية جمع واحدة.
ثبّت مقامًا \(d \ge 2\). البسوط المسموح بها هي الأعداد الصحيحة \(a\) التي تحقق \(1 \le a \lt d\) و \(\gcd(a,d)=1\). وبحسب التعريف فإن عددها هو دالة أويلر:
$$\varphi(d)=\#\{\,1 \le a \lt d : \gcd(a,d)=1\,\}.$$
ومن ثم يكون الجواب الكلي
$$T(N)=\sum_{d=2}^{N}\varphi(d).$$
هذه هي البنية الجوهرية للمسألة: كل كسر حقيقي مختزل يُحسب مرة واحدة بالضبط عبر مقامه.
إذا كانت القواسم الأولية المميزة للعدد \(d\) هي \(p_1,\dots,p_k\)، فلدينا الصيغة
$$\varphi(d)=d\prod_{p\mid d}\left(1-\frac{1}{p}\right).$$
التنفيذ يستعمل هذه الصيغة الضربية بصيغة غربالية. في البداية نضع \(\varphi(d)=d\) لكل \(d\). وعند معالجة عدد أولي \(p\)، يجب أن نحذف من كل مضاعف لـ \(p\) نسبة \(\frac{1}{p}\) تمامًا من القيم التي لا تزال محسوبة، ولذلك تصبح خطوة التحديث
$$\varphi(m)\leftarrow \varphi(m)-\frac{\varphi(m)}{p}, \quad p\mid m.$$
وهذه عملية صحيحة تمامًا في الحساب الصحيح، لا تقريب فيها. فقبل الوصول إلى \(p\)، تكون قيمة \(m\) قد عُدِّلت بسبب القواسم الأولية الأصغر، لكن العامل \(p\) القادم من العدد الأصلي \(m\) ما زال موجودًا، ولذلك تبقى القيمة الحالية قابلة للقسمة على \(p\) دون باقٍ.
الحلقة الرئيسة تمر على \(2,3,4,\dots,N\). وعندما نصل إلى \(i\)، فإن بقاء \(\varphi(i)=i\) يعني أن أي عدد أولي أصغر لم يغيّر هذه الخانة بعد. أما العدد المركب فلا بد أن يكون قد مُسَّ سابقًا بواسطة أصغر قاسم أولي له. لذلك فإن الخانة غير المعدّلة تدل بالضبط على أن \(i\) عدد أولي.
هذا هو الثابت الأساسي الذي يجعل الغربال يعمل: الخانات التي بقيت كما هي تكشف الأعداد الأولية، وكل عدد أولي مكتشف يحدّث جميع مضاعفاته مرة واحدة.
عند المقام \(5\)، تكون البسوط \(1,2,3,4\) كلها أولية نسبيًا مع \(5\)، ومن ثم \(\varphi(5)=4\). وعند المقام \(6\)، لا يبقى إلا \(1\) و\(5\)، لأن \(2,3,4\) تشترك مع \(6\) في عامل غير تافه، ولذلك \(\varphi(6)=2\).
وباستكمال القيم من \(2\) إلى \(8\) نحصل على
$$\varphi(2)=1,\ \varphi(3)=2,\ \varphi(4)=2,\ \varphi(5)=4,\ \varphi(6)=2,\ \varphi(7)=6,\ \varphi(8)=4.$$
إذن
$$T(8)=1+2+2+4+2+6+4=21.$$
هذا المثال الصغير يوضح بنية العد بوضوح، وهو أيضًا نقطة التحقق التي تستخدمها بعض التطبيقات قبل الحساب الكامل.
كل قيمة منفردة تحقق \(\varphi(d)\le d\le 10^6\)، ولذلك تكفي الأعداد الصحيحة ذات 32 بت لتخزين الجدول نفسه. أما المجموع النهائي فينمو بمقدار من رتبة \(N^2\)، ولذلك لا يكفيه 32 بت. لهذا يجب أن يكون المجمّع من نوع 64 بت في C++ وJava، بينما يتولى Python ذلك تلقائيًا باستخدام أعداد صحيحة غير محدودة الدقة.
تقوم تطبيقات C++ وPython وJava بإنشاء مصفوفة طولها \(N+1\)، ثم تضع في كل خانة قيمة فهرسها نفسه. بعد هذه الخطوة يصبح الجدول ممثلًا للحالة الابتدائية \(\varphi(d)=d\).
تمتد الحلقة الرئيسة من \(2\) إلى \(N\). وإذا كانت الخانة ما تزال مساوية لفهرسها، فهذا يعني أن العدد الحالي أولي. عندئذٍ تمر الشيفرة على جميع مضاعفاته وتنفّذ التحديث الدقيق \(\varphi(m)\leftarrow \varphi(m)-\varphi(m)/p\).
وعندما ينتهي هذا المرور، تكون كل خانة قد تلقّت تصحيحًا واحدًا لكل قاسم أولي مميز يقسم فهرسها، فتحتوي المصفوفة على جميع قيم \(\varphi\) حتى الحد المطلوب.
الخطوة الأخيرة هي جمع \(\varphi(2)+\varphi(3)+\cdots+\varphi(N)\). كما أن اثنتين من التطبيقات تتحققان أولًا من قيمة الضبط \(T(8)=21\) لتقليل احتمال تمرير خطأ في الفهرسة أو في تحديثات الغربال.
تهيئة الجدول تكلف \(O(N)\). أما عمل الغربال الكلي فهو
$$\sum_{p\le N}\frac{N}{p}=O(N\log\log N),$$
حيث يمتد الجمع على الأعداد الأولية \(p\). وخطوة التجميع الأخيرة هي مرور آخر بتكلفة \(O(N)\)، لذا فإن التعقيد الزمني الكلي هو \(O(N\log\log N)\).
أما استهلاك الذاكرة فهو \(O(N)\) بسبب جدول قيم \(\varphi\). وعند \(N=10^6\) يبقى هذا عمليًا جدًا، ولهذا يكون أسلوب جمع دالة أويلر مباشرة هو الحل الدقيق الطبيعي لهذه المسألة.