Let \(M=10^9\). For each integer \(n\), we want the positive residue \(x\in\{1,2,\dots,M-1\}\) satisfying
$$n^x \equiv x \pmod{M}.$$
If no positive fixed point exists, we set \(f(n)=0\). The required sum is
$$\sum_{n=2}^{10^6} f(n).$$
The checkpoint values used by the implementations are \(f(4)=411728896\), \(f(10)=0\), \(f(157)=743757\), and
$$\sum_{n=2}^{1000} f(n)=442530011399.$$
Define the map
$$F_n(x)=n^x \bmod M.$$
Then the desired values are exactly the positive fixed points of \(F_n\):
$$F_n(x)=x.$$
Because all arithmetic is reduced modulo \(M\), every iterate lies in the finite set \(\{0,1,\dots,M-1\}\). It is also useful to remember that
$$M=10^9=2^9\cdot 5^9,$$
so the equation means that the last nine decimal digits of \(n^x\) must reproduce \(x\) itself.
The implementations study the orbit generated by
$$x_0=0,\qquad x_{k+1}=F_n(x_k)=n^{x_k}\bmod M.$$
The first step is always
$$x_1=n^0 \bmod M=1,$$
so after the initial state the sequence immediately moves into positive exponents. Each later term is obtained by taking the previous residue as an exponent and then keeping only the last nine digits.
If at some stage
$$x_{k+1}=x_k>0,$$
the orbit has stabilized at a positive fixed point, and that value is returned as \(f(n)\).
The state space is finite, so every orbit must eventually repeat. In other words, there exist indices \(i<j\) with
$$x_i=x_j.$$
Since the map \(F_n\) is deterministic, repeating one value forces the entire future tail to repeat as well. Therefore the orbit can end in only two ways:
$$\text{fixed point} \qquad \text{or} \qquad \text{nontrivial cycle}.$$
If the repetition happens at a genuine fixed point, we are done. If a previously seen value reappears without equality to the current state, the orbit has entered a cycle that is not a positive fixed point, so the implementations return \(0\).
The checkpoint \(f(10)=0\) is not accidental. Suppose \(10\mid n\) and \(2\le n\le 10^6\). Then the orbit begins
$$0 \to 1 \to n.$$
Now \(n\ge 10\), so \(n^n\) contains at least \(10\) factors of \(10\). Hence
$$n^n \equiv 0 \pmod{10^9}.$$
Therefore the orbit becomes
$$0 \to 1 \to n \to 0 \to 1 \to n \to \cdots,$$
a cycle of length \(3\) with no positive fixed point. So every such \(n\) contributes \(0\).
For \(n=157\), the iterates are
$$0 \to 1 \to 157 \to 201583757 \to 204743757 \to 400743757 \to 743757 \to 743757.$$
The last value equals its own image, so
$$f(157)=743757.$$
For \(n=4\), the same procedure produces
$$0 \to 1 \to 4 \to 256 \to 6084096 \to 261392896 \to 264208896 \to 405328896 \to 363728896 \to 51728896 \to 211728896 \to 411728896,$$
and one more application still gives \(411728896\), matching the published checkpoint.
A naive computation of \(n^x\) would require \(x\) multiplications, which is impossible when \(x\) may be close to \(10^9\). The implementations therefore use repeated squaring. Writing
$$x=\sum_{i=0}^{t} b_i 2^i,\qquad b_i\in\{0,1\},$$
we can compute \(n^x \bmod M\) by repeatedly squaring the base and multiplying it into the accumulator only when \(b_i=1\). This reduces one modular-power evaluation to \(O(\log x)\) modular multiplications instead of \(O(x)\).
The C++, Python, and Java implementations all use the same strategy. For each \(n\), they iterate the map \(x\mapsto n^x \bmod 10^9\) starting from \(0\), evaluate each modular power by binary exponentiation, and store the residues already seen on that single orbit. If the new residue equals the current one and is positive, the algorithm returns it immediately. If the new residue has appeared earlier, the orbit is declared cyclic without a positive fixed point and the result is \(0\). The outer loop simply sums these values for all \(2\le n\le 10^6\).
Let \(I(n)\) be the number of orbit steps examined for a given \(n\). Each step needs one modular exponentiation, and the exponent is always less than \(M\), so one step costs \(O(\log M)\). Therefore
$$f(n)\text{ is computed in }O(I(n)\log M)\text{ time and }O(I(n))\text{ memory.}$$
Summing over all \(n\) gives
$$O\left(\sum_{n=2}^{10^6} I(n)\log M\right).$$
In practice the observed orbit lengths are small, which is why the direct iteration used by the implementations is fast enough for the target range.
Sei \(M=10^9\). Für jedes \(n\) suchen wir einen positiven Rest \(x\in\{1,2,\dots,M-1\}\) mit
$$n^x \equiv x \pmod{M}.$$
Falls kein positiver Fixpunkt existiert, setzen wir \(f(n)=0\). Gesucht ist die Summe
$$\sum_{n=2}^{10^6} f(n).$$
Die in den Implementierungen verwendeten Kontrollwerte sind \(f(4)=411728896\), \(f(10)=0\), \(f(157)=743757\) und
$$\sum_{n=2}^{1000} f(n)=442530011399.$$
Definiere die Abbildung
$$F_n(x)=n^x \bmod M.$$
Dann sind die gesuchten Werte genau die positiven Fixpunkte von \(F_n\):
$$F_n(x)=x.$$
Da jede Rechnung modulo \(M\) erfolgt, liegen alle Iterierten in der endlichen Menge \(\{0,1,\dots,M-1\}\). Außerdem gilt
$$M=10^9=2^9\cdot 5^9,$$
also bedeutet die Kongruenz, dass die letzten neun Dezimalstellen von \(n^x\) genau wieder \(x\) ergeben.
Die Implementierungen betrachten die Folge
$$x_0=0,\qquad x_{k+1}=F_n(x_k)=n^{x_k}\bmod M.$$
Der erste Schritt ist immer
$$x_1=n^0 \bmod M=1,$$
also gelangt die Bahn nach dem Start sofort zu positiven Exponenten. Jeder weitere Wert entsteht, indem man den vorherigen Rest als Exponenten verwendet und wieder nur die letzten neun Stellen behält.
Tritt irgendwann
$$x_{k+1}=x_k>0$$
ein, dann ist die Bahn auf einem positiven Fixpunkt stabil geworden, und genau dieser Wert wird zurückgegeben.
Der Zustandsraum ist endlich, also muss jede Bahn irgendwann einen Wert wiederholen. Es gibt also Indizes \(i<j\) mit
$$x_i=x_j.$$
Weil \(F_n\) deterministisch ist, erzwingt eine Wiederholung die Wiederholung des gesamten restlichen Verlaufs. Daher gibt es entlang dieser Bahn nur zwei mögliche Endverhalten:
$$\text{Fixpunkt} \qquad \text{oder} \qquad \text{nichttrivialer Zyklus}.$$
Ist die Wiederholung ein echter Fixpunkt, ist die Suche beendet. Taucht dagegen ein früherer Zustand erneut auf, ohne dass Gleichheit mit dem aktuellen Zustand vorliegt, dann ist die Bahn in einen Zyklus ohne positiven Fixpunkt geraten, und die Implementierungen liefern \(0\).
Der Kontrollwert \(f(10)=0\) lässt sich direkt erklären. Sei \(10\mid n\) und \(2\le n\le 10^6\). Dann beginnt die Bahn mit
$$0 \to 1 \to n.$$
Wegen \(n\ge 10\) enthält \(n^n\) mindestens \(10\) Faktoren \(10\). Also gilt
$$n^n \equiv 0 \pmod{10^9}.$$
Damit wird die Folge zu
$$0 \to 1 \to n \to 0 \to 1 \to n \to \cdots,$$
also zu einem Zyklus der Länge \(3\) ohne positiven Fixpunkt. Solche \(n\) tragen daher nichts zur Summe bei.
Für \(n=157\) erhält man
$$0 \to 1 \to 157 \to 201583757 \to 204743757 \to 400743757 \to 743757 \to 743757.$$
Der letzte Wert ist ein Fixpunkt, also
$$f(157)=743757.$$
Für \(n=4\) liefert dieselbe Iteration
$$0 \to 1 \to 4 \to 256 \to 6084096 \to 261392896 \to 264208896 \to 405328896 \to 363728896 \to 51728896 \to 211728896 \to 411728896,$$
und eine weitere Anwendung ergibt wieder \(411728896\). Damit stimmt der Kontrollwert exakt.
Ein naives Ausmultiplizieren von \(n^x\) würde \(x\) Multiplikationen benötigen und ist deshalb unbrauchbar. Die Implementierungen verwenden wiederholtes Quadrieren. Schreibt man
$$x=\sum_{i=0}^{t} b_i 2^i,\qquad b_i\in\{0,1\},$$
dann kann \(n^x \bmod M\) berechnet werden, indem man die Basis fortlaufend quadriert und nur bei \(b_i=1\) in das Ergebnis multipliziert. So sinkt der Aufwand pro Potenz von \(O(x)\) auf \(O(\log x)\).
Die C++-, Python- und Java-Implementierungen folgen alle derselben Struktur. Für jedes \(n\) iterieren sie die Abbildung \(x\mapsto n^x \bmod 10^9\) ab dem Startwert \(0\), berechnen jede Potenz per binärer Exponentiation und speichern nur die bereits besuchten Reste dieser einen Bahn. Wenn der neue Rest dem aktuellen positiven Rest entspricht, wird er sofort zurückgegeben. Wenn der neue Rest schon früher vorkam, wird die Bahn als zyklisch ohne positiven Fixpunkt eingestuft und das Ergebnis ist \(0\). Die äußere Schleife summiert diese Werte für alle \(2\le n\le 10^6\).
Sei \(I(n)\) die Zahl der untersuchten Bahn-Schritte für ein gegebenes \(n\). Jeder Schritt benötigt eine modulare Potenzberechnung, und der Exponent ist stets kleiner als \(M\), daher kostet ein Schritt \(O(\log M)\). Somit gilt
$$f(n)\text{ wird in }O(I(n)\log M)\text{ Zeit und }O(I(n))\text{ Speicher berechnet.}$$
Für die Gesamtsumme ergibt sich
$$O\left(\sum_{n=2}^{10^6} I(n)\log M\right).$$
In der Praxis bleiben die Bahnlängen klein, weshalb diese direkte Iteration für den geforderten Bereich schnell genug ist.
\(M=10^9\) olsun. Her \(n\) için
$$n^x \equiv x \pmod{M}$$
koşulunu sağlayan pozitif kalan \(x\in\{1,2,\dots,M-1\}\) aranır. Eğer böyle bir pozitif sabit nokta yoksa \(f(n)=0\) alınır. İstenen toplam
$$\sum_{n=2}^{10^6} f(n)$$
şeklindedir. Uygulamaların doğruladığı kontrol değerleri \(f(4)=411728896\), \(f(10)=0\), \(f(157)=743757\) ve
$$\sum_{n=2}^{1000} f(n)=442530011399$$
eşitliğidir.
Şu dönüşümü tanımlayalım:
$$F_n(x)=n^x \bmod M.$$
O zaman aranan değerler, \(F_n\) dönüşümünün pozitif sabit noktalarıdır:
$$F_n(x)=x.$$
Tüm hesaplar \(M\) modunda yapıldığı için her terim \(\{0,1,\dots,M-1\}\) kümesinde kalır. Ayrıca
$$M=10^9=2^9\cdot 5^9,$$
dolayısıyla denklem, \(n^x\)'in son dokuz basamağının yine \(x\)'i vermesi anlamına gelir.
Uygulamalar şu diziyi kullanır:
$$x_0=0,\qquad x_{k+1}=F_n(x_k)=n^{x_k}\bmod M.$$
İlk adım her zaman
$$x_1=n^0 \bmod M=1$$
olduğu için başlangıçtan hemen sonra pozitif üslere geçilir. Daha sonraki her terim, önceki kalanın üs olarak kullanılıp tekrar son dokuz basamağa indirgenmesiyle elde edilir.
Eğer bir aşamada
$$x_{k+1}=x_k>0$$
olursa, dizi pozitif bir sabit noktaya oturmuştur ve bu değer döndürülür.
Durum uzayı sonludur; bu yüzden her yörünge sonunda bir değeri yeniden ziyaret etmek zorundadır. Yani bazı \(i<j\) için
$$x_i=x_j$$
olur. \(F_n\) deterministik olduğu için bir değer tekrarlandığında ondan sonraki tüm kuyruk da aynı şekilde tekrar eder. Bu nedenle yörüngenin son davranışı yalnızca iki tip olabilir:
$$\text{sabit nokta} \qquad \text{veya} \qquad \text{trivial olmayan döngü}.$$
Eğer tekrar gerçek bir sabit noktada gerçekleşirse işlem biter. Aksi halde daha önce görülmüş bir değer yeniden ortaya çıkmışsa, dizi pozitif sabit nokta içermeyen bir döngüye girmiştir ve uygulamalar \(0\) döndürür.
\(f(10)=0\) sonucu doğrudan açıklanabilir. \(10\mid n\) ve \(2\le n\le 10^6\) olsun. Yörünge şu şekilde başlar:
$$0 \to 1 \to n.$$
Burada \(n\ge 10\) olduğundan \(n^n\) ifadesi en az \(10\) tane \(10\) çarpanı içerir. Dolayısıyla
$$n^n \equiv 0 \pmod{10^9}.$$
Böylece dizi
$$0 \to 1 \to n \to 0 \to 1 \to n \to \cdots$$
şeklindeki uzunluğu \(3\) olan döngüye girer. Pozitif sabit nokta olmadığı için bu tür tüm \(n\) değerleri toplamda \(0\) katkı verir.
\(n=157\) için yörünge
$$0 \to 1 \to 157 \to 201583757 \to 204743757 \to 400743757 \to 743757 \to 743757$$
olur. Son değer kendi görüntüsüne eşit olduğu için
$$f(157)=743757$$
elde edilir.
\(n=4\) için aynı süreç
$$0 \to 1 \to 4 \to 256 \to 6084096 \to 261392896 \to 264208896 \to 405328896 \to 363728896 \to 51728896 \to 211728896 \to 411728896$$
değerlerine ulaşır ve bir sonraki adım yine \(411728896\) verir. Böylece kontrol değeri doğrulanır.
\(n^x\)'i doğrudan çarparak bulmak \(x\) kadar çarpma gerektirir; \(x\) ise \(10^9\)'a çok yakın olabilir. Bu yüzden uygulamalar tekrar eden karesini alma yöntemini kullanır. Eğer
$$x=\sum_{i=0}^{t} b_i 2^i,\qquad b_i\in\{0,1\}$$
şeklinde ikili açılım yazılırsa, taban ardışık olarak karesini alarak ilerletilir ve yalnızca \(b_i=1\) olduğunda sonuca çarpılır. Böylece tek bir modüler üs hesabı \(O(x)\) yerine \(O(\log x)\) maliyetli olur.
C++, Python ve Java uygulamalarının yapısı aynıdır. Her \(n\) için \(x\mapsto n^x \bmod 10^9\) dönüşümü \(0\)'dan başlayarak yinelenir, her adımda modüler üs değeri ikili üs alma ile bulunur ve sadece o \(n\)'ye ait kısa yörüngede görülen kalanlar saklanır. Yeni kalan mevcut kalana eşit ve pozitifse sonuç hemen döndürülür. Yeni kalan daha önce görülmüşse, yörünge pozitif sabit nokta içermeyen bir döngüye girmiş sayılır ve sonuç \(0\) olur. Dış döngü bu değerleri \(2\le n\le 10^6\) aralığında toplayarak nihai toplamı üretir.
Belirli bir \(n\) için incelenen yörünge adımı sayısına \(I(n)\) diyelim. Her adımda bir modüler üs hesabı yapılır ve üs her zaman \(M\)'den küçüktür; bu yüzden bir adımın maliyeti \(O(\log M)\)'dir. Sonuç olarak
$$f(n)\text{ değeri }O(I(n)\log M)\text{ zamanda ve }O(I(n))\text{ bellekle hesaplanır.}$$
Tüm toplam için maliyet
$$O\left(\sum_{n=2}^{10^6} I(n)\log M\right)$$
olur. Pratikte yörüngeler kısa kaldığı için doğrudan yineleme yaklaşımı hedef aralıkta yeterince hızlıdır.
Sea \(M=10^9\). Para cada \(n\), buscamos un residuo positivo \(x\in\{1,2,\dots,M-1\}\) tal que
$$n^x \equiv x \pmod{M}.$$
Si no existe un punto fijo positivo, definimos \(f(n)=0\). La suma pedida es
$$\sum_{n=2}^{10^6} f(n).$$
Los valores de control usados por las implementaciones son \(f(4)=411728896\), \(f(10)=0\), \(f(157)=743757\) y
$$\sum_{n=2}^{1000} f(n)=442530011399.$$
Definimos la aplicación
$$F_n(x)=n^x \bmod M.$$
Entonces los valores buscados son precisamente los puntos fijos positivos de \(F_n\):
$$F_n(x)=x.$$
Como todas las operaciones se reducen módulo \(M\), cada iteración queda dentro del conjunto finito \(\{0,1,\dots,M-1\}\). Además,
$$M=10^9=2^9\cdot 5^9,$$
de modo que la congruencia expresa que las últimas nueve cifras decimales de \(n^x\) deben reproducir exactamente a \(x\).
Las implementaciones estudian la sucesión
$$x_0=0,\qquad x_{k+1}=F_n(x_k)=n^{x_k}\bmod M.$$
El primer paso siempre es
$$x_1=n^0 \bmod M=1,$$
así que tras el estado inicial la órbita entra enseguida en exponentes positivos. Cada término posterior se obtiene usando el residuo anterior como exponente y conservando solo las últimas nueve cifras.
Si en algún momento
$$x_{k+1}=x_k>0,$$
la órbita se ha estabilizado en un punto fijo positivo y ese valor se devuelve como \(f(n)\).
El espacio de estados es finito, así que toda órbita debe repetir un valor tarde o temprano. Es decir, existen índices \(i<j\) tales que
$$x_i=x_j.$$
Como \(F_n\) es determinista, repetir un estado obliga a repetir todo el tramo futuro. Por lo tanto, el comportamiento final de la órbita solo puede ser de dos tipos:
$$\text{punto fijo} \qquad \text{o} \qquad \text{ciclo no trivial}.$$
Si la repetición ocurre en un punto fijo verdadero, hemos terminado. Si reaparece un valor ya visto sin que haya igualdad con el estado actual, la órbita ha entrado en un ciclo sin punto fijo positivo y las implementaciones devuelven \(0\).
El valor de control \(f(10)=0\) tiene una explicación inmediata. Supongamos que \(10\mid n\) y \(2\le n\le 10^6\). Entonces la órbita empieza como
$$0 \to 1 \to n.$$
Como \(n\ge 10\), la potencia \(n^n\) contiene al menos \(10\) factores \(10\). En consecuencia,
$$n^n \equiv 0 \pmod{10^9}.$$
La sucesión pasa a ser
$$0 \to 1 \to n \to 0 \to 1 \to n \to \cdots,$$
un ciclo de longitud \(3\) sin punto fijo positivo. Por eso todo múltiplo de \(10\) aporta \(0\).
Para \(n=157\), las iteraciones son
$$0 \to 1 \to 157 \to 201583757 \to 204743757 \to 400743757 \to 743757 \to 743757.$$
El último valor es ya un punto fijo, de modo que
$$f(157)=743757.$$
Para \(n=4\), el mismo proceso produce
$$0 \to 1 \to 4 \to 256 \to 6084096 \to 261392896 \to 264208896 \to 405328896 \to 363728896 \to 51728896 \to 211728896 \to 411728896,$$
y una iteración adicional vuelve a dar \(411728896\), exactamente el valor de referencia.
Calcular \(n^x\) por multiplicación directa exigiría \(x\) productos, lo cual es inviable cuando \(x\) puede acercarse a \(10^9\). Las implementaciones usan exponenciación binaria. Si escribimos
$$x=\sum_{i=0}^{t} b_i 2^i,\qquad b_i\in\{0,1\},$$
podemos obtener \(n^x \bmod M\) elevando sucesivamente al cuadrado la base y multiplicando al acumulador solo cuando \(b_i=1\). Así, una potencia modular cuesta \(O(\log x)\) en lugar de \(O(x)\).
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Para cada \(n\), iteran la aplicación \(x\mapsto n^x \bmod 10^9\) empezando en \(0\), calculan cada potencia modular mediante exponenciación binaria y guardan los residuos ya visitados en esa única órbita. Si el nuevo residuo coincide con el actual y es positivo, el algoritmo lo devuelve enseguida. Si el nuevo residuo ya apareció antes, la órbita se clasifica como cíclica sin punto fijo positivo y el resultado es \(0\). El bucle exterior suma estos valores para todos los enteros \(2\le n\le 10^6\).
Sea \(I(n)\) el número de pasos de órbita inspeccionados para un valor dado de \(n\). Cada paso requiere una exponenciación modular y el exponente siempre es menor que \(M\), así que cada paso cuesta \(O(\log M)\). Por tanto,
$$f(n)\text{ se calcula en }O(I(n)\log M)\text{ tiempo y }O(I(n))\text{ memoria.}$$
Para la suma completa obtenemos
$$O\left(\sum_{n=2}^{10^6} I(n)\log M\right).$$
En la práctica, las órbitas observadas son cortas, por lo que esta iteración directa resulta suficientemente eficiente para el rango del problema.
设 \(M=10^9\)。对每个 \(n\)，我们要找一个正剩余 \(x\in\{1,2,\dots,M-1\}\)，使得
$$n^x \equiv x \pmod{M}.$$
如果不存在正的不动点，就定义 \(f(n)=0\)。目标是计算
$$\sum_{n=2}^{10^6} f(n).$$
实现中使用的校验值为 \(f(4)=411728896\)、\(f(10)=0\)、\(f(157)=743757\)，以及
$$\sum_{n=2}^{1000} f(n)=442530011399.$$
定义映射
$$F_n(x)=n^x \bmod M.$$
那么所求值正是 \(F_n\) 的正不动点：
$$F_n(x)=x.$$
由于每一步都对 \(M\) 取模，所以所有迭代值都落在有限集合 \(\{0,1,\dots,M-1\}\) 中。同时
$$M=10^9=2^9\cdot 5^9,$$
因此这个同余条件的含义是：\(n^x\) 的最后九位十进制数字必须恰好等于 \(x\) 本身。
实现采用如下迭代：
$$x_0=0,\qquad x_{k+1}=F_n(x_k)=n^{x_k}\bmod M.$$
第一步恒为
$$x_1=n^0 \bmod M=1,$$
所以序列在起点之后立刻进入正指数区域。此后的每一项，都是把前一项当作指数，再只保留结果的最后九位。
如果某一步出现
$$x_{k+1}=x_k>0,$$
就说明轨道已经稳定在一个正不动点上，该值就是返回结果。
状态空间是有限的，所以任意轨道最终都必须重复某个值。也就是说，必然存在 \(i<j\) 使得
$$x_i=x_j.$$
由于 \(F_n\) 是确定性的，一旦某个状态重复，之后的整个尾部也会重复。因此这条轨道最终只有两种可能：
$$\text{到达不动点} \qquad \text{或} \qquad \text{进入非平凡循环}.$$
如果重复发生在真正的不动点上，我们就得到了答案。否则，若新状态只是重复出现而并非与当前状态相同，就说明轨道进入了不包含正不动点的循环，实现在这种情况下返回 \(0\)。
校验值 \(f(10)=0\) 可以直接解释。设 \(10\mid n\) 且 \(2\le n\le 10^6\)。此时轨道开头为
$$0 \to 1 \to n.$$
因为 \(n\ge 10\)，所以 \(n^n\) 至少含有 \(10\) 个因子 \(10\)。于是
$$n^n \equiv 0 \pmod{10^9}.$$
轨道因此变成
$$0 \to 1 \to n \to 0 \to 1 \to n \to \cdots,$$
也就是一个长度为 \(3\) 的循环，没有正不动点，所以这类 \(n\) 的贡献都是 \(0\)。
对 \(n=157\)，迭代序列为
$$0 \to 1 \to 157 \to 201583757 \to 204743757 \to 400743757 \to 743757 \to 743757.$$
最后一个值已经满足不动点条件，因此
$$f(157)=743757.$$
对 \(n=4\)，同样的过程得到
$$0 \to 1 \to 4 \to 256 \to 6084096 \to 261392896 \to 264208896 \to 405328896 \to 363728896 \to 51728896 \to 211728896 \to 411728896,$$
再迭代一次仍然是 \(411728896\)，这与题目给出的校验值一致。
如果直接做 \(x\) 次乘法来求 \(n^x\)，当 \(x\) 接近 \(10^9\) 时显然不可行。实现采用二进制快速幂。把
$$x=\sum_{i=0}^{t} b_i 2^i,\qquad b_i\in\{0,1\}$$
写成二进制展开后，只需不断平方当前底数，并在 \(b_i=1\) 时乘入结果。这样一次模幂计算的代价就从 \(O(x)\) 降到 \(O(\log x)\)。
C++、Python 和 Java 实现都采用完全相同的结构。对于每个 \(n\)，程序从 \(0\) 开始迭代映射 \(x\mapsto n^x \bmod 10^9\)，每一步都用二进制快速幂计算模幂，并且只记录当前这条轨道上已经出现过的剩余类。如果新的剩余类与当前值相同且为正数，就立刻返回该值；如果新的剩余类已经在更早时出现过，则说明轨道进入了不含正不动点的循环，于是返回 \(0\)。外层循环再把所有 \(2\le n\le 10^6\) 的结果相加。
记某个给定 \(n\) 所检查的轨道步数为 \(I(n)\)。每一步需要一次模幂运算，而指数始终小于 \(M\)，所以单步代价为 \(O(\log M)\)。因此
$$f(n)\text{ 的计算复杂度为 }O(I(n)\log M)\text{，空间复杂度为 }O(I(n)).$$
对整个求和过程，总复杂度为
$$O\left(\sum_{n=2}^{10^6} I(n)\log M\right).$$
在实际运行中，轨道长度通常较短，因此这种直接迭代的方法足以处理目标范围。
Положим \(M=10^9\). Для каждого \(n\) требуется найти положительный остаток \(x\in\{1,2,\dots,M-1\}\), удовлетворяющий условию
$$n^x \equiv x \pmod{M}.$$
Если положительной неподвижной точки нет, то по определению \(f(n)=0\). Нужно вычислить сумму
$$\sum_{n=2}^{10^6} f(n).$$
Контрольные значения, используемые реализациями: \(f(4)=411728896\), \(f(10)=0\), \(f(157)=743757\), а также
$$\sum_{n=2}^{1000} f(n)=442530011399.$$
Рассмотрим отображение
$$F_n(x)=n^x \bmod M.$$
Тогда искомые значения — это в точности положительные неподвижные точки \(F_n\):
$$F_n(x)=x.$$
Поскольку все вычисления ведутся по модулю \(M\), каждая итерация лежит в конечном множестве \(\{0,1,\dots,M-1\}\). Кроме того,
$$M=10^9=2^9\cdot 5^9,$$
то есть условие означает, что последние девять десятичных цифр числа \(n^x\) должны совпасть с самим \(x\).
Реализации исследуют последовательность
$$x_0=0,\qquad x_{k+1}=F_n(x_k)=n^{x_k}\bmod M.$$
Первый шаг всегда равен
$$x_1=n^0 \bmod M=1,$$
поэтому после начального состояния орбита сразу переходит к положительным показателям. Каждый следующий член получается так: предыдущий остаток используется как показатель, а затем сохраняются только последние девять цифр.
Если на некотором шаге выполнено
$$x_{k+1}=x_k>0,$$
то орбита стабилизировалась на положительной неподвижной точке, и именно это значение возвращается.
Пространство состояний конечно, следовательно, любая орбита рано или поздно повторит некоторое значение. То есть существуют индексы \(i<j\), для которых
$$x_i=x_j.$$
Так как отображение \(F_n\) детерминировано, повтор одного состояния принуждает к повторению всего дальнейшего хвоста. Поэтому возможны только два конечных сценария:
$$\text{неподвижная точка} \qquad \text{или} \qquad \text{нетривиальный цикл}.$$
Если повторение произошло в настоящей неподвижной точке, задача решена. Если же встретилось ранее виденное значение без совпадения с текущим состоянием, значит орбита вошла в цикл без положительной неподвижной точки, и реализации возвращают \(0\).
Контрольное значение \(f(10)=0\) объясняется очень просто. Пусть \(10\mid n\) и \(2\le n\le 10^6\). Тогда начало орбиты имеет вид
$$0 \to 1 \to n.$$
Поскольку \(n\ge 10\), число \(n^n\) содержит по меньшей мере \(10\) множителей \(10\). Значит,
$$n^n \equiv 0 \pmod{10^9}.$$
Следовательно, орбита превращается в цикл
$$0 \to 1 \to n \to 0 \to 1 \to n \to \cdots,$$
длины \(3\), в котором нет положительной неподвижной точки. Поэтому любой такой \(n\) даёт вклад \(0\).
Для \(n=157\) последовательность имеет вид
$$0 \to 1 \to 157 \to 201583757 \to 204743757 \to 400743757 \to 743757 \to 743757.$$
Последнее значение уже является неподвижной точкой, поэтому
$$f(157)=743757.$$
Для \(n=4\) тот же процесс даёт
$$0 \to 1 \to 4 \to 256 \to 6084096 \to 261392896 \to 264208896 \to 405328896 \to 363728896 \to 51728896 \to 211728896 \to 411728896,$$
и ещё одно применение отображения снова приводит к \(411728896\). Это точно совпадает с контрольным значением.
Наивное вычисление \(n^x\) потребовало бы \(x\) умножений, что невозможно при \(x\), близком к \(10^9\). Поэтому реализации используют двоичное возведение в степень. Если записать
$$x=\sum_{i=0}^{t} b_i 2^i,\qquad b_i\in\{0,1\},$$
то \(n^x \bmod M\) можно найти, последовательно возводя основание в квадрат и домножая его в результат только при \(b_i=1\). Стоимость одной модульной степени снижается с \(O(x)\) до \(O(\log x)\).
Реализации на C++, Python и Java устроены одинаково. Для каждого \(n\) они итерируют отображение \(x\mapsto n^x \bmod 10^9\), начиная с \(0\), каждую модульную степень вычисляют быстрым двоичным методом и хранят только уже посещённые остатки текущей орбиты. Если новый остаток совпал с текущим и он положителен, алгоритм немедленно возвращает его. Если новый остаток уже встречался раньше, орбита классифицируется как циклическая без положительной неподвижной точки, и результатом становится \(0\). Внешний цикл суммирует эти значения для всех \(2\le n\le 10^6\).
Обозначим через \(I(n)\) число просмотренных шагов орбиты для данного \(n\). Каждый шаг требует одной модульной степени, а показатель всегда меньше \(M\), значит стоимость шага равна \(O(\log M)\). Следовательно,
$$f(n)\text{ вычисляется за }O(I(n)\log M)\text{ времени и }O(I(n))\text{ памяти.}$$
Для полной суммы получаем
$$O\left(\sum_{n=2}^{10^6} I(n)\log M\right).$$
На практике длины орбит малы, поэтому прямой итерационный метод оказывается достаточно быстрым для целевого диапазона.
لنضع \(M=10^9\). لكل عدد \(n\) نبحث عن باقٍ موجب \(x\in\{1,2,\dots,M-1\}\) يحقق
$$n^x \equiv x \pmod{M}.$$
إذا لم توجد نقطة تثبيت موجبة فإننا نعرّف \(f(n)=0\). والمطلوب هو حساب
$$\sum_{n=2}^{10^6} f(n).$$
قيم التحقق التي تعتمد عليها التطبيقات هي \(f(4)=411728896\)، و\(f(10)=0\)، و\(f(157)=743757\)، وكذلك
$$\sum_{n=2}^{1000} f(n)=442530011399.$$
نعرّف الدالة
$$F_n(x)=n^x \bmod M.$$
وعندئذ تكون القيم المطلوبة هي نقاط التثبيت الموجبة لهذه الدالة:
$$F_n(x)=x.$$
وبما أن كل الحسابات تؤخذ بترديد \(M\)، فإن كل قيمة في التتابع تقع داخل المجموعة المنتهية \(\{0,1,\dots,M-1\}\). كما أن
$$M=10^9=2^9\cdot 5^9,$$
ولذلك فالمعادلة تعني أن آخر تسع خانات عشرية من \(n^x\) يجب أن تعيد العدد \(x\) نفسه.
تستخدم التطبيقات المتتالية
$$x_0=0,\qquad x_{k+1}=F_n(x_k)=n^{x_k}\bmod M.$$
والخطوة الأولى دائمًا هي
$$x_1=n^0 \bmod M=1,$$
ولذلك ينتقل المدار مباشرة بعد البداية إلى أسس موجبة. وكل حد لاحق يُنتج من استعمال الباقي السابق كأس ثم أخذ آخر تسع خانات فقط.
إذا تحقق في مرحلة ما
$$x_{k+1}=x_k>0,$$
فهذا يعني أن المدار استقر عند نقطة تثبيت موجبة، وهذه هي القيمة التي تُعاد.
فضاء الحالات منتهٍ، ولذلك لا بد أن يكرر أي مدار قيمة ما في النهاية. أي توجد فهارس \(i<j\) بحيث
$$x_i=x_j.$$
وبما أن \(F_n\) دالة حتمية، فإن تكرار حالة واحدة يفرض تكرار الذيل كله بعد ذلك. لذلك لا يوجد في النهاية إلا احتمالان فقط: الوصول إلى نقطة تثبيت، أو الدخول في دورة غير تافهة.
إذا وقع التكرار عند نقطة تثبيت حقيقية فنحن انتهينا. أما إذا ظهرت قيمة سبق أن شوهدت من قبل من دون أن تكون مساوية للحالة الحالية، فهذا يعني أن المدار دخل دورة لا تحتوي على نقطة تثبيت موجبة، وعندها تعيد التطبيقات القيمة \(0\).
النتيجة \(f(10)=0\) يمكن تفسيرها مباشرة. افترض أن \(10\mid n\) و\(2\le n\le 10^6\). عندئذ يبدأ المدار بالشكل
$$0 \to 1 \to n.$$
وبما أن \(n\ge 10\)، فإن \(n^n\) يحتوي على ما لا يقل عن عشرة عوامل من \(10\). ومن ثم
$$n^n \equiv 0 \pmod{10^9}.$$
فيصبح المدار
$$0 \to 1 \to n \to 0 \to 1 \to n \to \cdots,$$
أي دورة طولها \(3\) من دون نقطة تثبيت موجبة. ولهذا تساهم جميع هذه القيم بصفر.
عندما \(n=157\) نحصل على
$$0 \to 1 \to 157 \to 201583757 \to 204743757 \to 400743757 \to 743757 \to 743757.$$
القيمة الأخيرة ثابتة تحت التطبيق، ولذلك
$$f(157)=743757.$$
وعندما \(n=4\) ينتج نفس الإجراء
$$0 \to 1 \to 4 \to 256 \to 6084096 \to 261392896 \to 264208896 \to 405328896 \to 363728896 \to 51728896 \to 211728896 \to 411728896,$$
ثم تعطي خطوة إضافية القيمة \(411728896\) مرة أخرى، وهذا يطابق قيمة التحقق المعطاة.
الحساب المباشر لـ \(n^x\) يحتاج إلى \(x\) عملية ضرب، وهذا غير عملي عندما يقترب \(x\) من \(10^9\). لذلك تستخدم التطبيقات طريقة التربيع المتكرر. فإذا كتبنا
$$x=\sum_{i=0}^{t} b_i 2^i,\qquad b_i\in\{0,1\},$$
أمكن حساب \(n^x \bmod M\) عبر تربيع الأساس تباعًا وضربه في الناتج فقط عندما يكون \(b_i=1\). وهكذا تنخفض كلفة حساب قوة معيارية واحدة من \(O(x)\) إلى \(O(\log x)\).
تتبع تطبيقات C++ وPython وJava البنية نفسها. لكل \(n\)، تكرر التحويل \(x\mapsto n^x \bmod 10^9\) ابتداءً من \(0\)، وتحسب كل قوة معيارية باستخدام الأس السريع الثنائي، وتخزن فقط البواقي التي ظهرت في هذا المدار الواحد. إذا كان الباقي الجديد مساويًا للحالة الحالية وكان موجبًا، تُعاد هذه القيمة مباشرة. وإذا كان الباقي الجديد قد ظهر سابقًا، فيُصنَّف المدار على أنه دوري من دون نقطة تثبيت موجبة وتكون النتيجة \(0\). ثم تجمع الحلقة الخارجية هذه القيم لكل \(2\le n\le 10^6\).
لنرمز بعدد خطوات المدار المفحوصة لعدد معين \(n\) بالرمز \(I(n)\). كل خطوة تحتاج إلى قوة معيارية واحدة، والأس دائمًا أصغر من \(M\)، لذا فتكلفة الخطوة الواحدة هي \(O(\log M)\). وبالتالي فإن حساب \(f(n)\) يحتاج إلى زمن \(O(I(n)\log M)\) وذاكرة \(O(I(n))\).
أما المجموع الكامل فتكون كلفته
$$O\left(\sum_{n=2}^{10^6} I(n)\log M\right).$$
عمليًا تبقى أطوال المدارات قصيرة، ولهذا يكون التكرار المباشر المعتمد في التطبيقات كافيًا للنطاق المطلوب.