For integers \(n\) and \(m\), define \(f(n,m)\) as the smallest nonnegative integer \(x\) satisfying
$$x \equiv \varphi(n)\pmod{n}, \qquad x \equiv \varphi(m)\pmod{m},$$
and define \(f(n,m)=0\) when the system has no solution. The problem asks for
$$\sum_{10^6 \le n \lt m \lt 1005000} f(n,m).$$
A brute-force search over candidate values of \(x\) would be hopeless. The efficient route is to precompute Euler's totient function once, then solve each pair with the Chinese Remainder Theorem in its non-coprime form.
For one pair \((n,m)\), write
$$a=\varphi(n), \qquad b=\varphi(m).$$
We must find the least nonnegative solution of
$$x \equiv a \pmod{n}, \qquad x \equiv b \pmod{m}.$$
The full sum is obtained by evaluating this quantity for every pair in the interval and adding the results.
The only residues that ever appear are \(\varphi(n)\) and \(\varphi(m)\), so the first job is to compute \(\varphi(k)\) for all \(k < 1005000\).
The sieve used by the implementation is the standard totient sieve: start with \(\varphi(k)=k\), and for each prime \(p\), update every multiple \(q\) of \(p\) by
$$\varphi(q)\leftarrow \varphi(q)-\frac{\varphi(q)}{p}=\varphi(q)\left(1-\frac{1}{p}\right).$$
After this preprocessing, every pair \((n,m)\) immediately gives the two residues \(a\) and \(b\).
If \(x\) satisfies both congruences, then for some integers \(u\) and \(v\),
$$x=a+nu=b+mv.$$
Subtracting the two expressions gives the linear Diophantine equation
$$nu-mv=b-a.$$
Let
$$g=\gcd(n,m).$$
A standard theorem for linear Diophantine equations says that this equation has an integer solution if and only if \(g\) divides the right-hand side. Therefore the CRT system is solvable exactly when
$$g \mid (b-a),$$
or equivalently
$$a \equiv b \pmod{g}.$$
If this compatibility test fails, then \(f(n,m)=0\).
Assume the divisibility condition holds. Write
$$n=gn_1, \qquad m=gm_1,$$
so that \(\gcd(n_1,m_1)=1\). Dividing the linear equation by \(g\) gives
$$n_1u-m_1v=\frac{b-a}{g}.$$
Reducing this relation modulo \(m_1\) eliminates the term containing \(v\) and leaves
$$n_1u \equiv \frac{b-a}{g}\pmod{m_1}.$$
Because \(n_1\) and \(m_1\) are coprime, \(n_1\) has a modular inverse modulo \(m_1\). Hence
$$u \equiv \frac{b-a}{g}\,n_1^{-1}\pmod{m_1}.$$
This is the key simplification: one non-coprime CRT system becomes one ordinary modular inverse problem.
Choose the unique representative \(u_0\) with
$$0 \le u_0 < m_1$$
that satisfies the congruence above. Then
$$x=a+nu_0$$
solves the original system.
Why is this the smallest nonnegative solution? First, \(0 \le a < n\) for every relevant \(n\), so
$$0 \le x < n+n(m_1-1)=nm_1=\operatorname{lcm}(n,m).$$
Second, all solutions to the CRT system are congruent modulo \(\operatorname{lcm}(n,m)\). Therefore the representative lying in
$$[0,\operatorname{lcm}(n,m))$$
is exactly the least nonnegative one.
Take the actual pair \((n,m)=(4,6)\). Then
$$\varphi(4)=2, \qquad \varphi(6)=2.$$
So we solve
$$x \equiv 2 \pmod{4}, \qquad x \equiv 2 \pmod{6}.$$
Here \(g=\gcd(4,6)=2\), and \(2-2=0\) is divisible by \(2\), so the system is solvable. We have
$$n_1=2, \qquad m_1=3, \qquad \frac{b-a}{g}=0,$$
hence
$$2u \equiv 0 \pmod{3},$$
so \(u_0=0\). Therefore
$$f(4,6)=x=2+4\cdot 0=2.$$
For a nontrivial shift with the same moduli, the system
$$x \equiv 2 \pmod{4}, \qquad x \equiv 4 \pmod{6}$$
leads to
$$2u \equiv 1 \pmod{3}.$$
The inverse of \(2\) modulo \(3\) is \(2\), so \(u_0 \equiv 2 \pmod{3}\), giving
$$x=2+4\cdot 2=10.$$
This matches the checkpoint used by the implementations and shows how the reduced congruence produces the minimal CRT solution directly.
The C++, Python, and Java implementations all follow the same plan. First they build a totient table up to the upper bound of the interval. Then they extract the 5000 relevant numbers \(n\) together with their totients so that the double loop only reads precomputed values.
For each pair \(n<m\), the implementation computes \(a=\varphi(n)\), \(b=\varphi(m)\), and \(g=\gcd(n,m)\). If \(a\not\equiv b\pmod{g}\), the pair contributes \(0\) and the loop moves on immediately.
Otherwise, the code divides by \(g\), uses the extended Euclidean algorithm to obtain the inverse of \(n/g\) modulo \(m/g\), normalizes the residue into the range \(0 \le u_0 < m/g\), and forms
$$x=a+nu_0.$$
The running total is accumulated in an integer type wide enough for the full answer, because the final sum is larger than what a signed 64-bit integer can safely hold.
Let \(L=10^6\), \(R=1005000\), and \(N=R-L=5000\). The totient sieve up to \(R-1\) costs
$$O(R\log\log R)$$
time and \(O(R)\) memory.
The pair loop evaluates
$$\binom{5000}{2}=12{,}497{,}500$$
CRT systems. Each one performs a gcd computation and one extended-Euclid solve on integers of size \(O(R)\), so its arithmetic cost is \(O(\log R)\). The total running time is therefore
$$O(R\log\log R + N^2\log R),$$
with \(O(R)\) memory overall. The important point is that the quadratic factor comes from only 5000 values, not from one million values.
Für ganze Zahlen \(n\) und \(m\) sei \(f(n,m)\) die kleinste nichtnegative Zahl \(x\) mit
$$x \equiv \varphi(n)\pmod{n}, \qquad x \equiv \varphi(m)\pmod{m},$$
und \(f(n,m)=0\), falls das System unlösbar ist. Gesucht ist
$$\sum_{10^6 \le n \lt m \lt 1005000} f(n,m).$$
Ein direktes Durchprobieren möglicher \(x\)-Werte ist aussichtslos. Stattdessen berechnet man die Totientwerte einmal per Sieb und löst dann jedes Paar mit dem chinesischen Restsatz in seiner nicht teilerfremden Form.
Für ein festes Paar \((n,m)\) setzen wir
$$a=\varphi(n), \qquad b=\varphi(m).$$
Damit ist die Aufgabe, die kleinste nichtnegative Lösung von
$$x \equiv a \pmod{n}, \qquad x \equiv b \pmod{m}$$
zu bestimmen. Die Gesamtsumme entsteht durch Auswertung dieses Werts für alle Paare im Intervall.
In allen Kongruenzen treten nur \(\varphi(n)\) und \(\varphi(m)\) auf. Deshalb wird zuerst \(\varphi(k)\) für alle \(k < 1005000\) berechnet.
Verwendet wird das klassische Totient-Sieb: man beginnt mit \(\varphi(k)=k\), und für jede Primzahl \(p\) aktualisiert man jedes Vielfache \(q\) von \(p\) durch
$$\varphi(q)\leftarrow \varphi(q)-\frac{\varphi(q)}{p}=\varphi(q)\left(1-\frac{1}{p}\right).$$
Nach dieser Vorarbeit liefert jedes Paar \((n,m)\) sofort die beiden Restklassen \(a\) und \(b\).
Erfüllt \(x\) beide Bedingungen, so gibt es ganze Zahlen \(u\) und \(v\) mit
$$x=a+nu=b+mv.$$
Durch Subtraktion erhält man die lineare diophantische Gleichung
$$nu-mv=b-a.$$
Sei nun
$$g=\gcd(n,m).$$
Eine Standardaussage über lineare diophantische Gleichungen besagt, dass genau dann eine ganzzahlige Lösung existiert, wenn \(g\) die rechte Seite teilt. Das CRT-System ist also genau dann lösbar, wenn
$$g \mid (b-a),$$
äquivalent zu
$$a \equiv b \pmod{g}.$$
Falls diese Bedingung fehlschlägt, gilt sofort \(f(n,m)=0\).
Nun sei die Teilbarkeitsbedingung erfüllt. Schreibe
$$n=gn_1, \qquad m=gm_1,$$
wobei \(\gcd(n_1,m_1)=1\) ist. Nach Division durch \(g\) entsteht
$$n_1u-m_1v=\frac{b-a}{g}.$$
Reduziert man diese Gleichung modulo \(m_1\), verschwindet der Term mit \(v\), und es bleibt
$$n_1u \equiv \frac{b-a}{g}\pmod{m_1}.$$
Da \(n_1\) und \(m_1\) teilerfremd sind, besitzt \(n_1\) modulo \(m_1\) ein Inverses. Also folgt
$$u \equiv \frac{b-a}{g}\,n_1^{-1}\pmod{m_1}.$$
Damit ist das ursprüngliche Problem auf eine gewöhnliche Inversenberechnung reduziert.
Wähle den eindeutigen Vertreter \(u_0\) mit
$$0 \le u_0 < m_1$$
aus der Kongruenzklasse oben. Dann ist
$$x=a+nu_0$$
eine Lösung des ursprünglichen Systems.
Warum ist dies die kleinste nichtnegative Lösung? Für alle hier relevanten \(n\) gilt \(0 \le a < n\). Also
$$0 \le x < n+n(m_1-1)=nm_1=\operatorname{lcm}(n,m).$$
Außerdem unterscheiden sich alle CRT-Lösungen um Vielfache von \(\operatorname{lcm}(n,m)\). Somit ist der Vertreter im Intervall
$$[0,\operatorname{lcm}(n,m))$$
genau die gesuchte kleinste nichtnegative Lösung.
Betrachte das echte Paar \((n,m)=(4,6)\). Dann ist
$$\varphi(4)=2, \qquad \varphi(6)=2.$$
Wir lösen also
$$x \equiv 2 \pmod{4}, \qquad x \equiv 2 \pmod{6}.$$
Hier ist \(g=\gcd(4,6)=2\), und \(2-2=0\) ist durch \(2\) teilbar. Weiter gilt
$$n_1=2, \qquad m_1=3, \qquad \frac{b-a}{g}=0,$$
also
$$2u \equiv 0 \pmod{3}.$$
Daraus folgt \(u_0=0\) und damit
$$f(4,6)=x=2+4\cdot 0=2.$$
Für einen nichttrivialen Versatz mit denselben Moduli kann man
$$x \equiv 2 \pmod{4}, \qquad x \equiv 4 \pmod{6}$$
betrachten. Dann entsteht
$$2u \equiv 1 \pmod{3},$$
das Inverse von \(2\) modulo \(3\) ist wieder \(2\), also \(u_0 \equiv 2\pmod{3}\), und man erhält
$$x=2+4\cdot 2=10.$$
Genau dieses Kontrollbeispiel bestätigt die korrekte Rekonstruktion der kleinsten CRT-Lösung.
Die C++-, Python- und Java-Implementierungen benutzen alle denselben Ablauf. Zuerst wird eine Totienttabelle bis zur oberen Intervallgrenze erzeugt. Danach werden die 5000 relevanten Zahlen \(n\) und ihre Totientwerte in linearen Feldern abgelegt, damit die Doppelschleife nur noch vorab berechnete Daten liest.
Für jedes Paar \(n<m\) werden \(a=\varphi(n)\), \(b=\varphi(m)\) und \(g=\gcd(n,m)\) bestimmt. Falls \(a\not\equiv b\pmod{g}\), trägt das Paar \(0\) bei.
Andernfalls dividiert der Code durch \(g\), bestimmt mit dem erweiterten Euklidischen Algorithmus das Inverse von \(n/g\) modulo \(m/g\), normiert den Rest in den Bereich \(0 \le u_0 < m/g\) und bildet anschließend
$$x=a+nu_0.$$
Die laufende Summe wird in einem Zahlentyp mit genügend großer Breite gehalten, weil das Endergebnis den sicheren Bereich eines vorzeichenbehafteten 64-Bit-Integerwerts überschreitet.
Mit \(L=10^6\), \(R=1005000\) und \(N=R-L=5000\) kostet das Totient-Sieb bis \(R-1\)
$$O(R\log\log R)$$
Zeit und \(O(R)\) Speicher.
Die Doppelschleife verarbeitet
$$\binom{5000}{2}=12{,}497{,}500$$
CRT-Systeme. Jedes davon braucht einen ggT und einmal erweiterten Euklid auf Zahlen der Größe \(O(R)\), also \(O(\log R)\) arithmetische Arbeit. Insgesamt ergibt sich
$$O(R\log\log R + N^2\log R)$$
bei insgesamt \(O(R)\) Speicher. Entscheidend ist, dass der quadratische Anteil nur von 5000 Werten stammt, nicht von einer Million.
Tam sayılar \(n\) ve \(m\) için \(f(n,m)\),
$$x \equiv \varphi(n)\pmod{n}, \qquad x \equiv \varphi(m)\pmod{m}$$
sistemini sağlayan en küçük negatif olmayan \(x\) değeri olarak tanımlanır; sistem çözümsüzse \(f(n,m)=0\) alınır. İstenen toplam
$$\sum_{10^6 \le n \lt m \lt 1005000} f(n,m)$$
ifadesidir. Olası \(x\) değerlerini sırayla denemek gerçek aralıkta mümkün değildir. Doğru yaklaşım, Euler phi değerlerini bir kez önceden hesaplamak ve her çifti ortak bölenli CRT formülüyle çözmektir.
Sabit bir \((n,m)\) çifti için
$$a=\varphi(n), \qquad b=\varphi(m)$$
yazalım. Böylece çözmek istediğimiz şey
$$x \equiv a \pmod{n}, \qquad x \equiv b \pmod{m}$$
sisteminin en küçük negatif olmayan çözümüdür. Genel toplam, bu değeri aralıktaki bütün çiftler için hesaplayıp toplayarak elde edilir.
Tüm çiftlerde görünen kalanlar yalnızca \(\varphi(n)\) ve \(\varphi(m)\) olduğundan, önce \(1005000\)'den küçük tüm sayılar için \(\varphi(k)\) hesaplanır.
Uygulanan eleme klasik totient eleğidir: başlangıçta \(\varphi(k)=k\) alınır; her asal \(p\) için, \(p\)'nin her katı \(q\) şu kuralla güncellenir:
$$\varphi(q)\leftarrow \varphi(q)-\frac{\varphi(q)}{p}=\varphi(q)\left(1-\frac{1}{p}\right).$$
Bu işlem tamamlandığında her \((n,m)\) çifti için gerekli iki artık sınıfı anında hazırdır.
Eğer bir \(x\) her iki kongruensi de sağlıyorsa, bazı tam sayılar \(u\) ve \(v\) için
$$x=a+nu=b+mv$$
yazılabilir. Çıkarma yapınca
$$nu-mv=b-a$$
doğrusal Diofant denklemi elde edilir. Şimdi
$$g=\gcd(n,m)$$
olsun. Doğrusal Diofant denklemlerinin temel sonucuna göre bu eşitliğin tam sayı çözümü ancak ve ancak \(g\), sağ tarafı bölüyorsa vardır. Dolayısıyla CRT sistemi tam olarak şu durumda çözülebilir:
$$g \mid (b-a),$$
yani eşdeğer biçimde
$$a \equiv b \pmod{g}.$$
Bu test başarısız olursa katkı doğrudan \(0\) olur.
Şimdi bölünebilirlik koşulunun sağlandığını varsayalım. Şöyle yazalım:
$$n=gn_1, \qquad m=gm_1,$$
burada \(\gcd(n_1,m_1)=1\)'dir. Denklemi \(g\)'ye bölünce
$$n_1u-m_1v=\frac{b-a}{g}$$
elde edilir. Bunu \(m_1\) modunda düşünürsek \(v\)'li terim yok olur ve
$$n_1u \equiv \frac{b-a}{g}\pmod{m_1}$$
kalır. \(n_1\) ile \(m_1\) aralarında asal olduğundan \(n_1\)'in \(m_1\) modundaki tersi vardır. Böylece
$$u \equiv \frac{b-a}{g}\,n_1^{-1}\pmod{m_1}$$
olur. Yani ortak bölen içeren ilk CRT sistemi, tek bir modüler ters alma problemine indirgenmiş olur.
Yukarıdaki kongruens sınıfından
$$0 \le u_0 < m_1$$
koşulunu sağlayan tek temsilciyi seçelim. O zaman
$$x=a+nu_0$$
orijinal sistemi çözer.
Bunun neden en küçük negatif olmayan çözüm olduğunu görmek kolaydır. Bu problemde ilgili tüm \(n\) değerleri için \(0 \le a < n\) olduğundan
$$0 \le x < n+n(m_1-1)=nm_1=\operatorname{lcm}(n,m).$$
Ayrıca bütün çözümler \(\operatorname{lcm}(n,m)\) modulo aynı sınıfta bulunur. Dolayısıyla
$$[0,\operatorname{lcm}(n,m))$$
aralığındaki çözüm, tam olarak en küçük negatif olmayan çözümdür.
Gerçek problemden \((n,m)=(4,6)\) çiftini alalım. O zaman
$$\varphi(4)=2, \qquad \varphi(6)=2.$$
Çözdüğümüz sistem
$$x \equiv 2 \pmod{4}, \qquad x \equiv 2 \pmod{6}$$
olur. Burada \(g=\gcd(4,6)=2\) ve \(2-2=0\) ifadesi \(2\)'ye bölünür. Ayrıca
$$n_1=2, \qquad m_1=3, \qquad \frac{b-a}{g}=0,$$
dolayısıyla
$$2u \equiv 0 \pmod{3}$$
ve \(u_0=0\) bulunur. Sonuç olarak
$$f(4,6)=x=2+4\cdot 0=2.$$
Aynı modüllerle sıfır olmayan kaymayı görmek için
$$x \equiv 2 \pmod{4}, \qquad x \equiv 4 \pmod{6}$$
sistemine bakabiliriz. Bu kez
$$2u \equiv 1 \pmod{3}$$
elde edilir. \(2\)'nin \(3\) modundaki tersi yine \(2\) olduğu için \(u_0 \equiv 2 \pmod{3}\) olur ve
$$x=2+4\cdot 2=10$$
çıkar. Uygulamanın kontrol örneği tam olarak budur.
C++, Python ve Java uygulamalarının üçü de aynı planı izler. Önce aralığın üst sınırına kadar bir phi tablosu oluşturulur. Sonra yalnızca gereken 5000 sayı ile bunların phi değerleri ayrı dizilere alınır; böylece çift döngüsü tekrar tekrar eleme yapmaz.
Her \(n<m\) çifti için uygulama \(a=\varphi(n)\), \(b=\varphi(m)\) ve \(g=\gcd(n,m)\) hesaplar. Eğer \(a\not\equiv b\pmod{g}\) ise katkı \(0\) olur ve bir sonraki çifte geçilir.
Aksi halde kod, modülleri \(g\)'ye bölerek küçültür, genişletilmiş Öklid algoritmasıyla \(n/g\)'nin \(m/g\) modundaki tersini bulur, artığı \(0 \le u_0 < m/g\) aralığına normalize eder ve
$$x=a+nu_0$$
değerini üretir. Toplam ise sonucun büyüklüğü nedeniyle yeterince geniş bir tamsayı türünde tutulur.
\(L=10^6\), \(R=1005000\) ve \(N=R-L=5000\) olmak üzere, phi eleği
$$O(R\log\log R)$$
zaman ve \(O(R)\) bellek kullanır.
Çift döngüsü
$$\binom{5000}{2}=12{,}497{,}500$$
adet CRT sistemi çözer. Her birinde bir gcd ve \(O(R)\) büyüklüğünde sayılar üzerinde bir genişletilmiş Öklid adımı vardır; bu da aritmetik olarak \(O(\log R)\) maliyet verir. Böylece toplam çalışma süresi
$$O(R\log\log R + N^2\log R)$$
olur; toplam bellek tüketimi \(O(R)\)'dir. Kritik nokta, karesel kısmın yalnızca 5000 elemanlık pencereye ait olmasıdır.
Para enteros \(n\) y \(m\), se define \(f(n,m)\) como el menor entero no negativo \(x\) que cumple
$$x \equiv \varphi(n)\pmod{n}, \qquad x \equiv \varphi(m)\pmod{m},$$
y se toma \(f(n,m)=0\) si el sistema no tiene solución. El objetivo es calcular
$$\sum_{10^6 \le n \lt m \lt 1005000} f(n,m).$$
Buscar \(x\) por fuerza bruta sería inviable. La solución eficaz consiste en precalcular todos los valores de la función phi de Euler y, para cada par, resolver un sistema CRT con módulos que no necesariamente son coprimos.
Para un par fijo \((n,m)\), escribimos
$$a=\varphi(n), \qquad b=\varphi(m).$$
Entonces debemos hallar la menor solución no negativa de
$$x \equiv a \pmod{n}, \qquad x \equiv b \pmod{m}.$$
La suma total se obtiene evaluando esta cantidad para todos los pares del intervalo.
Los únicos residuos que aparecen son \(\varphi(n)\) y \(\varphi(m)\), así que el primer paso es calcular \(\varphi(k)\) para todo \(k < 1005000\).
La implementación usa la criba clásica del totiente: se empieza con \(\varphi(k)=k\), y para cada primo \(p\), cada múltiplo \(q\) de \(p\) se actualiza mediante
$$\varphi(q)\leftarrow \varphi(q)-\frac{\varphi(q)}{p}=\varphi(q)\left(1-\frac{1}{p}\right).$$
Después de esta fase, cada par \((n,m)\) proporciona de inmediato los residuos \(a\) y \(b\).
Si un número \(x\) satisface ambas congruencias, existen enteros \(u\) y \(v\) tales que
$$x=a+nu=b+mv.$$
Al restar las dos expresiones obtenemos la ecuación diofántica lineal
$$nu-mv=b-a.$$
Sea
$$g=\gcd(n,m).$$
La teoría clásica dice que esta ecuación tiene solución entera si y solo si \(g\) divide al segundo miembro. Por tanto, el sistema CRT es resoluble exactamente cuando
$$g \mid (b-a),$$
o, de forma equivalente,
$$a \equiv b \pmod{g}.$$
Si esta condición falla, entonces \(f(n,m)=0\).
Supongamos ahora que la divisibilidad se cumple. Escribimos
$$n=gn_1, \qquad m=gm_1,$$
de modo que \(\gcd(n_1,m_1)=1\). Al dividir por \(g\), queda
$$n_1u-m_1v=\frac{b-a}{g}.$$
Si reducimos esta igualdad módulo \(m_1\), el término con \(v\) desaparece y obtenemos
$$n_1u \equiv \frac{b-a}{g}\pmod{m_1}.$$
Como \(n_1\) y \(m_1\) son coprimos, \(n_1\) tiene inverso módulo \(m_1\). Por lo tanto,
$$u \equiv \frac{b-a}{g}\,n_1^{-1}\pmod{m_1}.$$
Así, un CRT con módulos no coprimos se transforma en una sola operación de inverso modular.
Tomamos el único representante \(u_0\) con
$$0 \le u_0 < m_1$$
que satisface la congruencia anterior. Entonces
$$x=a+nu_0$$
resuelve el sistema original.
Además, esta solución es la menor no negativa. En efecto, para todos los valores relevantes de \(n\) se tiene \(0 \le a < n\), y por eso
$$0 \le x < n+n(m_1-1)=nm_1=\operatorname{lcm}(n,m).$$
Como todas las soluciones del sistema CRT difieren en múltiplos de \(\operatorname{lcm}(n,m)\), la representante situada en
$$[0,\operatorname{lcm}(n,m))$$
es exactamente la mínima solución no negativa.
Tomemos el par real \((n,m)=(4,6)\). Entonces
$$\varphi(4)=2, \qquad \varphi(6)=2.$$
Debemos resolver
$$x \equiv 2 \pmod{4}, \qquad x \equiv 2 \pmod{6}.$$
Aquí \(g=\gcd(4,6)=2\), y \(2-2=0\) es divisible por \(2\). También
$$n_1=2, \qquad m_1=3, \qquad \frac{b-a}{g}=0,$$
de modo que
$$2u \equiv 0 \pmod{3}.$$
Por tanto \(u_0=0\), y se concluye que
$$f(4,6)=x=2+4\cdot 0=2.$$
Para ver un desplazamiento no trivial con los mismos módulos, considérese
$$x \equiv 2 \pmod{4}, \qquad x \equiv 4 \pmod{6}.$$
Entonces aparece
$$2u \equiv 1 \pmod{3}.$$
El inverso de \(2\) módulo \(3\) es \(2\), así que \(u_0 \equiv 2 \pmod{3}\), y finalmente
$$x=2+4\cdot 2=10.$$
Ese valor coincide con el ejemplo de control utilizado por las implementaciones.
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Primero construyen una tabla de totientes hasta el extremo superior del intervalo. Después guardan los 5000 valores relevantes de \(n\) y sus totientes para que el bucle doble solo lea datos ya preparados.
Para cada par \(n<m\), la implementación toma \(a=\varphi(n)\), \(b=\varphi(m)\) y \(g=\gcd(n,m)\). Si \(a\not\equiv b\pmod{g}\), el aporte del par es \(0\).
En caso contrario, divide los módulos por \(g\), obtiene con Euclides extendido el inverso de \(n/g\) módulo \(m/g\), normaliza el residuo al intervalo \(0 \le u_0 < m/g\) y construye
$$x=a+nu_0.$$
La suma acumulada se mantiene en un tipo entero suficientemente grande, porque el resultado final supera con holgura lo que cabe en un entero con signo de 64 bits.
Con \(L=10^6\), \(R=1005000\) y \(N=R-L=5000\), la criba del totiente hasta \(R-1\) cuesta
$$O(R\log\log R)$$
tiempo y \(O(R)\) memoria.
El bucle de pares evalúa
$$\binom{5000}{2}=12{,}497{,}500$$
sistemas CRT. Cada uno requiere un gcd y una llamada a Euclides extendido sobre enteros de tamaño \(O(R)\), es decir, \(O(\log R)\) trabajo aritmético. El tiempo total es
$$O(R\log\log R + N^2\log R),$$
con \(O(R)\) memoria global. Lo importante es que el factor cuadrático solo afecta a una ventana de 5000 números.
对整数 \(n\) 与 \(m\)，定义 \(f(n,m)\) 为满足
$$x \equiv \varphi(n)\pmod{n}, \qquad x \equiv \varphi(m)\pmod{m}$$
的最小非负整数 \(x\)；如果这个同余组无解，就规定 \(f(n,m)=0\)。题目要求计算
$$\sum_{10^6 \le n \lt m \lt 1005000} f(n,m).$$
如果直接枚举可能的 \(x\)，即使只对一个配对也会非常低效，更不用说总共有上千万个配对。真正可行的方法是先把区间内会用到的欧拉函数值全部筛出来，然后对每一对 \((n,m)\) 用带公因子的中国剩余定理求最小解。
对一个固定配对 \((n,m)\)，记
$$a=\varphi(n), \qquad b=\varphi(m).$$
于是我们需要求解
$$x \equiv a \pmod{n}, \qquad x \equiv b \pmod{m}$$
的最小非负解。总答案就是把区间中所有 \(n<m\) 的这个值全部加起来。
每个配对真正需要的只是两个余数 \(\varphi(n)\) 和 \(\varphi(m)\)，所以第一步不是逐对现算，而是一次性计算所有 \(k<1005000\) 的 \(\varphi(k)\)。
实现采用标准的 totient 筛法。先令
$$\varphi(k)=k,$$
然后从小到大扫描整数。当某个 \(p\) 仍保持 \(\varphi(p)=p\) 时，它就是素数；接着对每个 \(p\) 的倍数 \(q\) 执行
$$\varphi(q)\leftarrow \varphi(q)-\frac{\varphi(q)}{p}=\varphi(q)\left(1-\frac{1}{p}\right).$$
这样处理完成后，每一对 \((n,m)\) 都可以在 \(O(1)\) 时间取到 \(a\) 与 \(b\)，不再重复分解质因数。
如果某个 \(x\) 同时满足这两个同余，那么一定存在整数 \(u\) 与 \(v\)，使得
$$x=a+nu=b+mv.$$
两式相减，得到
$$nu-mv=b-a.$$
这已经是一个线性不定方程。设
$$g=\gcd(n,m).$$
线性不定方程有整数解的充要条件是 \(g\) 整除右端，因此原来的 CRT 系统可解，当且仅当
$$g \mid (b-a),$$
也就是
$$a \equiv b \pmod{g}.$$
如果这个条件不成立，那么该配对没有公共解，按题意直接贡献 \(0\)。这一判断非常重要，因为它能在做任何逆元计算之前先剪掉所有无解的配对。
现在假设兼容条件成立。把两个模数同时除以最大公因数：
$$n=gn_1, \qquad m=gm_1,$$
于是 \(\gcd(n_1,m_1)=1\)。将上面的线性方程整体除以 \(g\)，得到
$$n_1u-m_1v=\frac{b-a}{g}.$$
接着对 \(m_1\) 取模，含 \(v\) 的项消失，只剩下
$$n_1u \equiv \frac{b-a}{g}\pmod{m_1}.$$
因为 \(n_1\) 与 \(m_1\) 互素，所以 \(n_1\) 在模 \(m_1\) 意义下必有逆元。于是可以直接写成
$$u \equiv \frac{b-a}{g}\,n_1^{-1}\pmod{m_1}.$$
这一步给出了整个算法的核心公式。原来看似麻烦的“带公共因子 CRT”，最终只需要一次最大公因数判断和一次扩展欧几里得求逆。
在上面的同余类中，取唯一的代表元 \(u_0\)，使其满足
$$0 \le u_0 < m_1.$$
然后定义
$$x=a+nu_0.$$
这个 \(x\) 一定满足原始的两个同余，而且它正是最小非负解。理由如下。
第一，由于题目中的 \(n\) 都大于 \(1\)，而欧拉函数满足 \(0 \le \varphi(n) < n\)，所以 \(0 \le a < n\)。再加上 \(u_0<m_1\)，可得
$$0 \le x < n+n(m_1-1)=nm_1=\operatorname{lcm}(n,m).$$
第二，CRT 的所有解彼此相差 \(\operatorname{lcm}(n,m)\) 的整数倍，因此区间
$$[0,\operatorname{lcm}(n,m))$$
中的代表元就是唯一的最小非负解。这也解释了为什么实现里只要把 \(u\) 规范化到一个标准范围，最终得到的 \(x\) 就已经是题目要求的答案。
先看题目函数本身的一个真实配对 \((n,m)=(4,6)\)。有
$$\varphi(4)=2, \qquad \varphi(6)=2.$$
因此需要解
$$x \equiv 2 \pmod{4}, \qquad x \equiv 2 \pmod{6}.$$
这里
$$g=\gcd(4,6)=2,$$
并且 \(b-a=0\)，显然能被 \(2\) 整除，所以系统有解。进一步有
$$n_1=2,\qquad m_1=3,\qquad \frac{b-a}{g}=0.$$
于是降成
$$2u \equiv 0 \pmod{3},$$
标准代表元就是 \(u_0=0\)。代回去得到
$$f(4,6)=x=2+4\cdot 0=2.$$
为了看到“非零平移”的情形，再看同样模数下的辅助例子
$$x \equiv 2 \pmod{4}, \qquad x \equiv 4 \pmod{6}.$$
这时
$$2u \equiv 1 \pmod{3}.$$
\(2\) 在模 \(3\) 下的逆元还是 \(2\)，所以
$$u_0 \equiv 2 \pmod{3}.$$
取最小非负代表 \(u_0=2\)，立刻得到
$$x=2+4\cdot 2=10.$$
这个数正是实现中的校验值之一，它展示了“先缩模、再求逆、最后重建”这一流程是如何直接产生最小解的。
C++、Python 和 Java 版本的实现步骤完全一致。它们先建立一张欧拉函数表，一直算到区间上界之前。随后把区间 \([10^6,1005000)\) 中的 5000 个整数及其对应的欧拉函数值保存下来，这样双重循环只需要读取数组，不必反复做筛法工作。
对于每一对 \(n<m\)，实现先取出 \(a=\varphi(n)\)、\(b=\varphi(m)\)，再计算 \(g=\gcd(n,m)\)。如果 \(a\not\equiv b\pmod{g}\)，这一对直接贡献 \(0\)。
如果系统可解，代码就把两个模数先除以 \(g\)，再用扩展欧几里得算法求出 \(n/g\) 在模 \(m/g\) 下的逆元，把右侧常数规范到标准余数范围，并据此得到标准代表 \(u_0\)。最后构造
$$x=a+nu_0,$$
并把它加入总和。由于最终答案超过了有符号 64 位整数的安全范围，实现使用了足够宽的整数累加器来保存精确总和。
记 \(L=10^6\)、\(R=1005000\)、\(N=R-L=5000\)。预处理欧拉函数表到 \(R-1\) 的时间复杂度为
$$O(R\log\log R),$$
空间复杂度为 \(O(R)\)。
之后需要处理的配对数量是
$$\binom{5000}{2}=12{,}497{,}500.$$
每一对只做一次 gcd 和一次扩展欧几里得，处理的是大小在 \(O(R)\) 量级的整数，因此单对代价是 \(O(\log R)\)。总时间复杂度为
$$O(R\log\log R + N^2\log R),$$
总空间复杂度仍为 \(O(R)\)。这里最值得注意的是，二次项只作用在长度 5000 的窗口上，所以完全可接受。
Для целых \(n\) и \(m\) функция \(f(n,m)\) определяется как наименьшее неотрицательное число \(x\), удовлетворяющее системе
$$x \equiv \varphi(n)\pmod{n}, \qquad x \equiv \varphi(m)\pmod{m},$$
а если система неразрешима, то полагается \(f(n,m)=0\). Требуется вычислить
$$\sum_{10^6 \le n \lt m \lt 1005000} f(n,m).$$
Перебирать кандидаты на \(x\) напрямую бессмысленно. Эффективный путь состоит в том, чтобы заранее вычислить значения функции Эйлера, а затем для каждой пары решать систему сравнений с помощью китайской теоремы об остатках в случае не обязательно взаимно простых модулей.
Для фиксированной пары \((n,m)\) обозначим
$$a=\varphi(n), \qquad b=\varphi(m).$$
Тогда нужно найти наименьшее неотрицательное решение системы
$$x \equiv a \pmod{n}, \qquad x \equiv b \pmod{m}.$$
Полный ответ получается суммированием этого значения по всем парам из заданного промежутка.
Во всех сравнениях фигурируют только остатки \(\varphi(n)\) и \(\varphi(m)\), поэтому сначала удобно найти \(\varphi(k)\) для всех \(k<1005000\).
Используется стандартное решето для функции Эйлера: сначала берут \(\varphi(k)=k\), а затем для каждого простого \(p\) обновляют каждое кратное \(q\) по формуле
$$\varphi(q)\leftarrow \varphi(q)-\frac{\varphi(q)}{p}=\varphi(q)\left(1-\frac{1}{p}\right).$$
После этой подготовки для любой пары \((n,m)\) нужные остатки \(a\) и \(b\) уже доступны мгновенно.
Если число \(x\) удовлетворяет обеим конгруэнциям, то существуют целые \(u\) и \(v\), для которых
$$x=a+nu=b+mv.$$
Вычитая одно равенство из другого, получаем линейное диофантово уравнение
$$nu-mv=b-a.$$
Пусть
$$g=\gcd(n,m).$$
Классический критерий разрешимости линейного диофантова уравнения говорит, что целочисленное решение существует тогда и только тогда, когда \(g\) делит правую часть. Значит, система CRT разрешима ровно при условии
$$g \mid (b-a),$$
или, что то же самое,
$$a \equiv b \pmod{g}.$$
Если это условие не выполняется, то вклад пары сразу равен нулю.
Предположим, что условие делимости выполнено. Разложим модули как
$$n=gn_1, \qquad m=gm_1,$$
тогда \(\gcd(n_1,m_1)=1\). Делим уравнение на \(g\) и получаем
$$n_1u-m_1v=\frac{b-a}{g}.$$
Переходя по модулю \(m_1\), избавляемся от члена с \(v\):
$$n_1u \equiv \frac{b-a}{g}\pmod{m_1}.$$
Поскольку \(n_1\) и \(m_1\) взаимно просты, у \(n_1\) существует обратный элемент по модулю \(m_1\). Следовательно,
$$u \equiv \frac{b-a}{g}\,n_1^{-1}\pmod{m_1}.$$
Именно здесь не взаимно простой CRT превращается в обычную задачу на поиск модульного обратного.
Выберем единственного представителя \(u_0\), такого что
$$0 \le u_0 < m_1.$$
Тогда
$$x=a+nu_0$$
является решением исходной системы.
Почему это минимальное неотрицательное решение? Во-первых, для всех нужных \(n\) выполняется \(0 \le a < n\), а потому
$$0 \le x < n+n(m_1-1)=nm_1=\operatorname{lcm}(n,m).$$
Во-вторых, любые два решения системы CRT отличаются на кратное \(\operatorname{lcm}(n,m)\). Следовательно, представитель из интервала
$$[0,\operatorname{lcm}(n,m))$$
и есть ровно то минимальное неотрицательное значение, которое требуется по определению \(f(n,m)\).
Возьмем реальную пару \((n,m)=(4,6)\). Тогда
$$\varphi(4)=2, \qquad \varphi(6)=2.$$
Нужно решить систему
$$x \equiv 2 \pmod{4}, \qquad x \equiv 2 \pmod{6}.$$
Здесь
$$g=\gcd(4,6)=2,$$
и разность \(b-a=0\) делится на \(2\), поэтому решение существует. Далее
$$n_1=2,\qquad m_1=3,\qquad \frac{b-a}{g}=0,$$
откуда получаем
$$2u \equiv 0 \pmod{3}.$$
Стандартный представитель равен \(u_0=0\), и значит
$$f(4,6)=x=2+4\cdot 0=2.$$
Чтобы увидеть нетривиальный сдвиг при тех же модулях, рассмотрим вспомогательную систему
$$x \equiv 2 \pmod{4}, \qquad x \equiv 4 \pmod{6}.$$
Тогда
$$2u \equiv 1 \pmod{3}.$$
Обратный к \(2\) по модулю \(3\) снова равен \(2\), так что \(u_0 \equiv 2 \pmod{3}\), и в итоге
$$x=2+4\cdot 2=10.$$
Это именно тот контрольный результат, который подтверждает корректность восстановления минимального CRT-решения.
Реализации на C++, Python и Java устроены одинаково. Сначала они строят таблицу значений функции Эйлера вплоть до верхней границы интервала. Затем сохраняют 5000 нужных значений \(n\) и соответствующие им тотиенты, чтобы двойной цикл работал только с готовыми данными.
Для каждой пары \(n<m\) реализация берет \(a=\varphi(n)\), \(b=\varphi(m)\) и вычисляет \(g=\gcd(n,m)\). Если \(a\not\equiv b\pmod{g}\), то пара сразу дает вклад \(0\).
Если же система совместна, код делит оба модуля на \(g\), с помощью расширенного алгоритма Евклида находит обратный элемент к \(n/g\) по модулю \(m/g\), нормализует остаток в диапазон \(0 \le u_0 < m/g\) и строит
$$x=a+nu_0.$$
Текущая сумма хранится в достаточно широком целочисленном типе, поскольку итоговый ответ не помещается в безопасный диапазон знакового 64-битного целого.
Пусть \(L=10^6\), \(R=1005000\) и \(N=R-L=5000\). Предварительное вычисление тотиентов до \(R-1\) требует
$$O(R\log\log R)$$
времени и \(O(R)\) памяти.
После этого двойной цикл обрабатывает
$$\binom{5000}{2}=12{,}497{,}500$$
систем CRT. Для каждой пары нужны один gcd и один расширенный Евклид на числах размера \(O(R)\), то есть \(O(\log R)\) арифметической работы. Итого получаем
$$O(R\log\log R + N^2\log R)$$
по времени и \(O(R)\) по памяти. Ключевой практический факт состоит в том, что квадратичная часть зависит только от окна длины 5000.
للعددين الصحيحين \(n\) و\(m\)، نعرّف \(f(n,m)\) بأنه أصغر عدد غير سالب \(x\) يحقق
$$x \equiv \varphi(n)\pmod{n}, \qquad x \equiv \varphi(m)\pmod{m},$$
ونأخذ \(f(n,m)=0\) إذا كان النظام غير قابل للحل. المطلوب هو حساب
$$\sum_{10^6 \le n \lt m \lt 1005000} f(n,m).$$
تجريب قيم \(x\) مباشرة غير عملي تمامًا. الطريقة الصحيحة هي أن نحسب قيم دالة أويلر مرة واحدة لكل الأعداد اللازمة، ثم نعالج كل زوج باستعمال مبرهنة البواقي الصينية عندما لا يكون المودولان أوليين بالضرورة.
لزوج ثابت \((n,m)\)، نكتب
$$a=\varphi(n), \qquad b=\varphi(m).$$
وعندها نريد أصغر حل غير سالب للنظام
$$x \equiv a \pmod{n}, \qquad x \equiv b \pmod{m}.$$
أما الجواب الكلي فينتج من جمع هذه القيمة على جميع الأزواج ضمن المجال المطلوب.
البواقي الوحيدة التي تظهر في المسألة هي \(\varphi(n)\) و\(\varphi(m)\)، لذلك تبدأ الخوارزمية بحساب \(\varphi(k)\) لكل \(k<1005000\).
الطريقة هي غربلة التوتينت القياسية: نبدأ بـ \(\varphi(k)=k\)، ثم لكل عدد أولي \(p\) نحدّث كل مضاعف \(q\) له بواسطة
$$\varphi(q)\leftarrow \varphi(q)-\frac{\varphi(q)}{p}=\varphi(q)\left(1-\frac{1}{p}\right).$$
بعد هذه الخطوة يصبح الحصول على \(a\) و\(b\) لكل زوج أمرًا مباشرًا من جدول محسوب مسبقًا.
إذا كان عدد ما \(x\) يحقق المتطابقتين معًا، فلابد أن توجد أعداد صحيحة \(u\) و\(v\) بحيث
$$x=a+nu=b+mv.$$
بطرح المعادلتين نحصل على المعادلة الديوفانتية الخطية
$$nu-mv=b-a.$$
لنضع
$$g=\gcd(n,m).$$
المعيار المعروف يقول إن هذه المعادلة تملك حلاً صحيحًا إذا وفقط إذا كان \(g\) يقسم الطرف الأيمن. إذن نظام CRT قابل للحل تمامًا عندما
$$g \mid (b-a),$$
أو بصورة مكافئة
$$a \equiv b \pmod{g}.$$
إذا فشل هذا الشرط فإن مساهمة الزوج تساوي صفرًا مباشرة.
افترض الآن أن شرط القسمة محقق. نكتب
$$n=gn_1, \qquad m=gm_1,$$
وبالتالي \(\gcd(n_1,m_1)=1\). بعد القسمة على \(g\) تصبح المعادلة
$$n_1u-m_1v=\frac{b-a}{g}.$$
وبأخذ هذه المعادلة بترديد \(m_1\) يختفي الحد الذي يحتوي على \(v\) فنحصل على
$$n_1u \equiv \frac{b-a}{g}\pmod{m_1}.$$
وبما أن \(n_1\) و\(m_1\) أوليان نسبيًا، فإن \(n_1\) يملك معكوسًا ضربيًا modulo \(m_1\). لذلك
$$u \equiv \frac{b-a}{g}\,n_1^{-1}\pmod{m_1}.$$
وهكذا تتحول مسألة CRT ذات المودولات غير المتباينة أوليًا إلى خطوة واحدة من حساب المعكوس المعياري.
نختار الممثل الوحيد \(u_0\) الذي يحقق
$$0 \le u_0 < m_1.$$
ثم نكوّن
$$x=a+nu_0.$$
هذا العدد يحقق النظام الأصلي، وهو أيضًا أصغر حل غير سالب. السبب أن \(0 \le a < n\) لجميع القيم المطلوبة هنا، ومع \(u_0<m_1\) نحصل على
$$0 \le x < n+n(m_1-1)=nm_1=\operatorname{lcm}(n,m).$$
ومن جهة أخرى، كل حلول نظام CRT تختلف بمضاعفات \(\operatorname{lcm}(n,m)\). لذلك فإن الممثل الواقع في المجال
$$[0,\operatorname{lcm}(n,m))$$
هو بالضبط الحل الأصغر غير السالب المطلوب في تعريف \(f(n,m)\).
لنأخذ الزوج الحقيقي \((n,m)=(4,6)\). عندها
$$\varphi(4)=2, \qquad \varphi(6)=2.$$
إذن النظام هو
$$x \equiv 2 \pmod{4}, \qquad x \equiv 2 \pmod{6}.$$
لدينا
$$g=\gcd(4,6)=2,$$
والفرق \(b-a=0\) يقبل القسمة على \(2\)، لذا فالنظام قابل للحل. كما أن
$$n_1=2,\qquad m_1=3,\qquad \frac{b-a}{g}=0,$$
ومن ثم
$$2u \equiv 0 \pmod{3}.$$
إذن \(u_0=0\)، ونحصل على
$$f(4,6)=x=2+4\cdot 0=2.$$
ولرؤية حالة فيها إزاحة غير صفرية مع نفس المودولين، ننظر إلى
$$x \equiv 2 \pmod{4}, \qquad x \equiv 4 \pmod{6}.$$
وهذا يعطي
$$2u \equiv 1 \pmod{3}.$$
ومعكوس \(2\) modulo \(3\) هو أيضًا \(2\)، لذلك \(u_0 \equiv 2 \pmod{3}\)، وبالتالي
$$x=2+4\cdot 2=10.$$
وهذه هي قيمة الفحص المعتمدة في التنفيذ، وهي توضح أن الاختزال ثم حساب المعكوس ثم إعادة البناء يعطي أصغر حل مباشرة.
تنفذ نسخ C++ وPython وJava الخطة نفسها. أولًا تُبنى جدول لقيم دالة أويلر حتى الحد الأعلى للمجال. ثم تُحفظ الأعداد الخمسة آلاف المطلوبة وقيم \(\varphi\) المقابلة لها حتى تعمل الحلقة الثنائية على بيانات جاهزة فقط.
لكل زوج \(n<m\)، تحسب الخوارزمية \(a=\varphi(n)\) و\(b=\varphi(m)\) و\(g=\gcd(n,m)\). إذا كان \(a\not\equiv b\pmod{g}\) فإن مساهمة هذا الزوج تساوي صفرًا.
أما إذا كان النظام قابلًا للحل، فيجري تقسيم المودولين على \(g\)، ثم يُستعمل إقليدس الموسع للحصول على معكوس \(n/g\) modulo \(m/g\)، ثم يُطبّع الباقي إلى المجال \(0 \le u_0 < m/g\)، وأخيرًا يُبنى
$$x=a+nu_0.$$
ويُجمع هذا المقدار في مجمّع عددي واسع بما يكفي لحفظ الجواب النهائي بدقة كاملة.
إذا أخذنا \(L=10^6\) و\(R=1005000\) و\(N=R-L=5000\)، فإن غربلة التوتينت حتى \(R-1\) تكلف
$$O(R\log\log R)$$
زمنًا و\(O(R)\) ذاكرة.
بعد ذلك تعالج الحلقة الثنائية
$$\binom{5000}{2}=12{,}497{,}500$$
نظام CRT. كل نظام يحتاج إلى gcd واحد وخطوة واحدة من إقليدس الموسع على أعداد بحجم \(O(R)\)، أي بتكلفة حسابية \(O(\log R)\). لذلك يكون التعقيد الكلي
$$O(R\log\log R + N^2\log R),$$
مع ذاكرة كلية \(O(R)\). الفكرة الأساسية هنا أن الجزء التربيعي يتعلق بنافذة طولها 5000 فقط، لا بالمليون كله.