Define \(g(n)\) as follows: starting from \(n\), repeatedly divide by \(7\) when possible; otherwise add \(1\), and count only those \(+1\) operations. The problem asks for the large cumulative quantity
$$F(N)=\sum_{m=1}^{N} g(m),\qquad H(k)=F\left(\frac{7^k-1}{11}\right)\pmod{M},\qquad M=1{,}117{,}117{,}717.$$
The required value is \(H(10^9)\). A direct simulation is impossible because the upper limit \(\frac{7^k-1}{11}\) is astronomically large, so the solution rewrites the process in base \(7\), turns it into a constant-size linear update, and then exploits the repeating digit pattern of \(\frac{1}{11}\) in base \(7\).
If \(n=7a+r\) with \(0\le r\le 6\), then one application of the rule gives
$$g(7a)=g(a),\qquad g(7a+r)=7-r+g(a+1)\quad (1\le r\le 6).$$
The second formula says that when the last base-\(7\) digit is \(r\neq 0\), we need exactly \(7-r\) increments to reach the next multiple of \(7\), after which the number becomes \(a+1\).
Introduce
$$f(n)=g(n+1).$$
For every positive \(n=7a+d\) with \(0\le d\le 6\), the previous recurrence becomes
$$f(7a+d)=f(a)+6-d,\qquad f(0)=0.$$
Repeatedly stripping the last base-\(7\) digit shows that if \(n=(d_m d_{m-1}\cdots d_0)_7\) is positive, then
$$f(n)=\sum_{i=0}^{m}(6-d_i).$$
So \(g(n+1)\) is just a weighted digit sum. For example, \(124=(235)_7\), hence
$$g(125)=f(124)=(6-2)+(6-3)+(6-5)=4+3+1=8,$$
which matches the small checkpoint used by the implementations.
Now define the prefix sum
$$F(N)=\sum_{m=1}^{N} g(m)=\sum_{n=0}^{N-1} f(n).$$
For a positive prefix \(n\) and a next base-\(7\) digit \(d\), split the range \(0\le x<7n+d\) into full blocks \(7a,7a+1,\dots,7a+6\) for \(0\le a<n\) and one partial block for \(a=n\). This yields
$$F(7n+d)=7F(n)+21n-6+d\,f(n)+P(d),$$
where
$$P(d)=\sum_{x=0}^{d-1}(6-x)=\frac{d(13-d)}{2}.$$
The term \(-6\) is the only correction needed for the special value \(f(0)=0\); otherwise the full-block contribution would be completely uniform.
For positive \(n\), use the augmented state
$$\mathbf{v}(n)=\begin{pmatrix}1\\ n-1\\ F(n)\\ f(n)\\ 1\end{pmatrix}.$$
Then appending one digit \(d\in\{0,\dots,6\}\) corresponds to \(n\mapsto 7n+d\), and the state evolves linearly:
$$\mathbf{v}(7n+d)=M_d\,\mathbf{v}(n),$$
with
$$M_d=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 6 & 7 & 0 & 0 & d\\ 15 & 21 & 7 & d & P(d)\\ 0 & 0 & 0 & 1 & 6-d\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \pmod{M}.$$
This is the exact matrix family used by the C++, Python, and Java implementations.
Because \(11\mid 7^{10}-1\), we have a purely periodic base-\(7\) expansion for \(\frac{1}{11}\), and in particular
$$\frac{7^{10}-1}{11}=(431162355)_7.$$
For \(k=10t\),
$$\frac{7^k-1}{11}=\frac{7^{10}-1}{11}\left(1+7^{10}+7^{20}+\cdots+7^{10(t-1)}\right).$$
Therefore its base-\(7\) digits are the block 4311623550 repeated \(t-1\) times, followed by 431162355. Since every such number begins with the digit \(4\), the implementations start directly from the state
$$\mathbf{v}(4)=\begin{pmatrix}1\\ 3\\ 12\\ 2\\ 1\end{pmatrix},$$
which already stores \(4-1\), \(F(4)=12\), and \(f(4)=2\).
A small local check comes from appending the digit \(3\) to the prefix \(4\), giving \(43_7=31\). Using \(F(4)=12\), \(f(4)=2\), and \(P(3)=15\),
$$F(31)=7\cdot 12+21\cdot 4-6+3\cdot 2+15=183.$$
So the recurrence already reproduces \(\sum_{m=1}^{31} g(m)=183\). For the first nontrivial target, \(k=10\), the upper limit is \((431162355)_7\). Starting from \(\mathbf{v}(4)\) and processing the remaining suffix 31162355 gives
$$H(10)=690409338 \pmod{M},$$
exactly the checkpoint embedded in the implementations.
The implementations precompute the seven digit-dependent matrices \(M_0,\dots,M_6\), always working modulo \(M\). They also precompute the transformations of the few fixed digit strings that appear in the base-\(7\) representation of \(\frac{7^k-1}{11}\): one short suffix for \(k=10\), one initial boundary block, one repeating 10-digit block, and one final block.
For \(k=10\), the short suffix is applied once to the initial state \(\mathbf{v}(4)\). For \(k=10t\ge 20\), the implementation applies the initial boundary block, raises the repeating block transformation to the power \(t-2\) by binary exponentiation, applies the final block, and then reads the third state component. That component is \(F\!\left(\frac{7^k-1}{11}\right)\), so it is exactly \(H(k)\).
Each matrix has fixed dimension \(5\), so one multiplication is constant-time in the asymptotic sense. The only nontrivial growth comes from raising the repeating block transformation to the power \(t-2\), where \(t=k/10\). Binary exponentiation therefore gives \(O(\log t)=O(\log k)\) matrix multiplications and \(O(1)\) extra memory.
Sei \(g(n)\) die Anzahl der \(+1\)-Operationen im folgenden Prozess: Solange \(n\) nicht \(1\) ist, wird bei Teilbarkeit durch \(7\) dividiert, sonst um \(1\) erhöht; gezählt werden nur die Erhöhungen. Gesucht ist die große Summenfunktion
$$F(N)=\sum_{m=1}^{N} g(m),\qquad H(k)=F\left(\frac{7^k-1}{11}\right)\pmod{M},\qquad M=1{,}117{,}117{,}717.$$
Benötigt wird \(H(10^9)\). Direkte Simulation scheidet aus, weil die obere Grenze \(\frac{7^k-1}{11}\) riesig ist. Deshalb formuliert die Lösung alles in Basis \(7\), schreibt die Dynamik als linearen Zustandsübergang fester Größe und nutzt dann die periodische Basis-\(7\)-Darstellung von \(\frac{1}{11}\).
Für \(n=7a+r\) mit \(0\le r\le 6\) gilt
$$g(7a)=g(a),\qquad g(7a+r)=7-r+g(a+1)\quad (1\le r\le 6).$$
Die zweite Beziehung bedeutet: Ist die letzte Basis-\(7\)-Ziffer \(r\neq 0\), dann braucht man genau \(7-r\) Inkremente bis zum nächsten Vielfachen von \(7\); nach der Division bleibt \(a+1\) übrig.
Definiere
$$f(n)=g(n+1).$$
Für jedes positive \(n=7a+d\) mit \(0\le d\le 6\) wird daraus
$$f(7a+d)=f(a)+6-d,\qquad f(0)=0.$$
Durch wiederholtes Entfernen der letzten Basis-\(7\)-Ziffer folgt für \(n=(d_m d_{m-1}\cdots d_0)_7>0\)
$$f(n)=\sum_{i=0}^{m}(6-d_i).$$
Damit ist \(g(n+1)\) nichts anderes als eine gewichtete Ziffernsumme. Beispiel: \(124=(235)_7\), also
$$g(125)=f(124)=(6-2)+(6-3)+(6-5)=4+3+1=8.$$
Nun setzen wir
$$F(N)=\sum_{m=1}^{N} g(m)=\sum_{n=0}^{N-1} f(n).$$
Für ein positives Präfix \(n\) und eine nächste Basis-\(7\)-Ziffer \(d\) zerlegt man den Bereich \(0\le x<7n+d\) in volle Blöcke \(7a,\dots,7a+6\) und einen letzten Teilblock. Daraus ergibt sich
$$F(7n+d)=7F(n)+21n-6+d\,f(n)+P(d),$$
wobei
$$P(d)=\sum_{x=0}^{d-1}(6-x)=\frac{d(13-d)}{2}.$$
Der Korrekturterm \(-6\) kommt genau vom Sonderfall \(f(0)=0\); ohne diesen Spezialwert wären alle Vollblöcke völlig gleichförmig.
Für positives \(n\) verwenden wir den augmentierten Zustand
$$\mathbf{v}(n)=\begin{pmatrix}1\\ n-1\\ F(n)\\ f(n)\\ 1\end{pmatrix}.$$
Das Anhängen einer Ziffer \(d\in\{0,\dots,6\}\) bedeutet \(n\mapsto 7n+d\), also
$$\mathbf{v}(7n+d)=M_d\,\mathbf{v}(n),$$
mit
$$M_d=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 6 & 7 & 0 & 0 & d\\ 15 & 21 & 7 & d & P(d)\\ 0 & 0 & 0 & 1 & 6-d\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \pmod{M}.$$
Genau diese Matrixfamilie wird in den C++-, Python- und Java-Implementierungen benutzt.
Weil \(11\mid 7^{10}-1\), besitzt \(\frac{1}{11}\) in Basis \(7\) eine reine Periode, insbesondere
$$\frac{7^{10}-1}{11}=(431162355)_7.$$
Für \(k=10t\) gilt dann
$$\frac{7^k-1}{11}=\frac{7^{10}-1}{11}\left(1+7^{10}+7^{20}+\cdots+7^{10(t-1)}\right).$$
Die Basis-\(7\)-Darstellung besteht also aus dem Block 4311623550, der \(t-1\)-mal wiederholt wird, gefolgt von 431162355. Da jede dieser Zahlen mit der Ziffer \(4\) beginnt, starten die Implementierungen sofort mit
$$\mathbf{v}(4)=\begin{pmatrix}1\\ 3\\ 12\\ 2\\ 1\end{pmatrix},$$
also mit bereits eingetragenen Werten für \(4-1\), \(F(4)=12\) und \(f(4)=2\).
Ein lokaler Test entsteht, wenn man an das Präfix \(4\) die Ziffer \(3\) anhängt; das ergibt \(43_7=31\). Mit \(F(4)=12\), \(f(4)=2\) und \(P(3)=15\) erhält man
$$F(31)=7\cdot 12+21\cdot 4-6+3\cdot 2+15=183.$$
Die Rekurrenz reproduziert also \(\sum_{m=1}^{31} g(m)=183\). Für das erste nichttriviale Ziel \(k=10\) ist die obere Grenze \((431162355)_7\). Beginnt man mit \(\mathbf{v}(4)\) und verarbeitet den restlichen Suffix 31162355, so folgt
$$H(10)=690409338 \pmod{M},$$
genau der Kontrollwert aus den Implementierungen.
Die Implementierungen berechnen zunächst die sieben ziffernabhängigen Matrizen \(M_0,\dots,M_6\) modulo \(M\). Danach werden die Transformationen der wenigen festen Ziffernfolgen vorbereitet, die in der Basis-\(7\)-Darstellung von \(\frac{7^k-1}{11}\) vorkommen: ein kurzer Suffix für \(k=10\), ein Anfangsblock, ein wiederholter 10-stelliger Block und ein Abschlussblock.
Für \(k=10\) wird nur der kurze Suffix einmal auf \(\mathbf{v}(4)\) angewendet. Für \(k=10t\ge 20\) kommt zuerst der Anfangsblock, dann die Potenz des Wiederholungsblocks mittels binärer Exponentiation mit Exponent \(t-2\), und zuletzt der Abschlussblock. Die dritte Zustandskomponente ist am Ende \(F\!\left(\frac{7^k-1}{11}\right)\), also genau \(H(k)\).
Die Matrizen haben feste Dimension \(5\), daher ist eine einzelne Matrixmultiplikation asymptotisch konstant teuer. Der einzige wachsende Teil ist die Potenzierung des Wiederholungsblocks mit Exponent \(t-2\), wobei \(t=k/10\). Durch binäre Exponentiation ergibt das insgesamt \(O(\log t)=O(\log k)\) Matrixmultiplikationen und \(O(1)\) Zusatzspeicher.
\(g(n)\) şu süreçteki \(+1\) adımlarının sayısı olsun: sayı \(7\)'ye bölünebiliyorsa böl, aksi halde \(1\) artır; yalnızca artırma adımlarını say. Aranan büyük toplam
$$F(N)=\sum_{m=1}^{N} g(m),\qquad H(k)=F\left(\frac{7^k-1}{11}\right)\pmod{M},\qquad M=1{,}117{,}117{,}717.$$
İstenen değer \(H(10^9)\)'dur. \(\frac{7^k-1}{11}\) olağanüstü büyük olduğu için doğrudan simülasyon yapılamaz. Bu yüzden çözüm, süreci taban \(7\)'ye çevirir, sabit boyutlu lineer bir durum güncellemesine indirger ve ardından \(\frac{1}{11}\)'in taban \(7\)'deki periyodik yazılımını kullanır.
\(n=7a+r\) ve \(0\le r\le 6\) için
$$g(7a)=g(a),\qquad g(7a+r)=7-r+g(a+1)\quad (1\le r\le 6)$$
olur. Yani son taban-\(7\) basamağı \(r\neq 0\) ise, bir sonraki \(7\) katına ulaşmak için tam \(7-r\) kez artırmak gerekir; sonra bölünce \(a+1\) kalır.
Şimdi
$$f(n)=g(n+1)$$
tanımını yapalım. Pozitif her \(n=7a+d\) için
$$f(7a+d)=f(a)+6-d,\qquad f(0)=0$$
elde edilir. Son basamağı tekrar tekrar sökerek, \(n=(d_m d_{m-1}\cdots d_0)_7>0\) iken
$$f(n)=\sum_{i=0}^{m}(6-d_i)$$
sonucuna ulaşırız. Böylece \(g(n+1)\), ağırlıklı bir taban-\(7\) basamak toplamına dönüşür. Örneğin \(124=(235)_7\) olduğundan
$$g(125)=f(124)=(6-2)+(6-3)+(6-5)=4+3+1=8$$
olur; bu da küçük kontrol değerini verir.
Artık
$$F(N)=\sum_{m=1}^{N} g(m)=\sum_{n=0}^{N-1} f(n)$$
olsun. Pozitif bir önek \(n\) ve bir sonraki taban-\(7\) basamağı \(d\) için, \(0\le x<7n+d\) aralığını tam bloklara ve son kısmi bloğa ayırınca
$$F(7n+d)=7F(n)+21n-6+d\,f(n)+P(d)$$
elde edilir. Burada
$$P(d)=\sum_{x=0}^{d-1}(6-x)=\frac{d(13-d)}{2}$$
şeklindedir. \(-6\) düzeltmesi yalnızca \(f(0)=0\) özel durumundan gelir; aksi halde tam bloklar tamamen uniform olurdu.
Pozitif \(n\) için artırılmış durum vektörü
$$\mathbf{v}(n)=\begin{pmatrix}1\\ n-1\\ F(n)\\ f(n)\\ 1\end{pmatrix}$$
olarak alınır. Bir basamak eklemek \(n\mapsto 7n+d\) demektir ve bu yüzden
$$\mathbf{v}(7n+d)=M_d\,\mathbf{v}(n)$$
şeklinde lineer bir güncelleme vardır. Matris
$$M_d=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 6 & 7 & 0 & 0 & d\\ 15 & 21 & 7 & d & P(d)\\ 0 & 0 & 0 & 1 & 6-d\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \pmod{M}$$
olur. C++, Python ve Java implementasyonları tam olarak bu matris ailesini kullanır.
\(11\mid 7^{10}-1\) olduğundan, \(\frac{1}{11}\)'in taban \(7\)'deki açılımı periyodiktir ve özellikle
$$\frac{7^{10}-1}{11}=(431162355)_7$$
olur. \(k=10t\) için
$$\frac{7^k-1}{11}=\frac{7^{10}-1}{11}\left(1+7^{10}+7^{20}+\cdots+7^{10(t-1)}\right)$$
yazılır. Bu yüzden taban-\(7\) basamak dizisi, 4311623550 bloğunun \(t-1\) kez tekrarlanması ve sona 431162355 eklenmesiyle oluşur. Bu sayıların tümü \(4\) ile başladığı için implementasyonlar doğrudan
$$\mathbf{v}(4)=\begin{pmatrix}1\\ 3\\ 12\\ 2\\ 1\end{pmatrix}$$
durumundan başlar; burada \(4-1\), \(F(4)=12\) ve \(f(4)=2\) zaten hazırdır.
Küçük bir yerel kontrol için önek \(4\)'e basamak \(3\)'ü ekleyelim; bu sayı \(43_7=31\) eder. \(F(4)=12\), \(f(4)=2\), \(P(3)=15\) kullanılırsa
$$F(31)=7\cdot 12+21\cdot 4-6+3\cdot 2+15=183$$
bulunur. Yani yineleme \(\sum_{m=1}^{31} g(m)=183\) toplamını doğru üretir. İlk anlamlı hedef olan \(k=10\) için üst sınır \((431162355)_7\)'dir. \(\mathbf{v}(4)\) durumundan başlayıp kalan 31162355 son ekini okuyunca
$$H(10)=690409338 \pmod{M}$$
elde edilir; bu da implementasyonlardaki kontrolle aynıdır.
Implementasyonlar önce \(M\) modunda yedi adet basamak-matrisini hazırlar. Daha sonra \(\frac{7^k-1}{11}\)'in taban-\(7\) yazılımında görünen sabit parça dönüşümleri önceden hesaplanır: \(k=10\) için kısa bir sonek, genel durumda ilk sınır bloğu, tekrar eden 10 basamaklı blok ve son blok.
\(k=10\) ise kısa sonek doğrudan \(\mathbf{v}(4)\) üzerine uygulanır. \(k=10t\ge 20\) ise önce başlangıç bloğu uygulanır, sonra tekrar eden bloğun dönüşümü \(t-2\) kuvvetine ikili üs alma ile yükseltilir, en son kapanış bloğu uygulanır. Son durumda üçüncü bileşen \(F\!\left(\frac{7^k-1}{11}\right)\), yani tam olarak \(H(k)\) olur.
Matris boyutu sabit olarak \(5\)'tir; dolayısıyla tek bir matris çarpımı asimptotik olarak sabit maliyetlidir. Büyüyen tek kısım, tekrar eden bloğun \(t-2\) kuvvetinin hesaplanmasıdır; burada \(t=k/10\). İkili üs alma sayesinde toplam süre \(O(\log t)=O(\log k)\), ek bellek ise \(O(1)\) kalır.
Sea \(g(n)\) el número de operaciones \(+1\) en el siguiente proceso: mientras \(n\neq 1\), si \(n\) es divisible por \(7\) se divide entre \(7\); en caso contrario se incrementa en \(1\), y solo esos incrementos se cuentan. La cantidad buscada es
$$F(N)=\sum_{m=1}^{N} g(m),\qquad H(k)=F\left(\frac{7^k-1}{11}\right)\pmod{M},\qquad M=1{,}117{,}117{,}717.$$
El objetivo final es \(H(10^9)\). Una simulación directa es inviable porque \(\frac{7^k-1}{11}\) es enorme. La solución reescribe la dinámica en base \(7\), la convierte en una actualización lineal de tamaño constante y luego aprovecha el patrón periódico de \(\frac{1}{11}\) en base \(7\).
Si \(n=7a+r\) con \(0\le r\le 6\), entonces
$$g(7a)=g(a),\qquad g(7a+r)=7-r+g(a+1)\quad (1\le r\le 6).$$
La segunda relación dice que, cuando el último dígito en base \(7\) es \(r\neq 0\), hacen falta exactamente \(7-r\) incrementos para llegar al siguiente múltiplo de \(7\), y tras dividir queda \(a+1\).
Definimos
$$f(n)=g(n+1).$$
Para todo \(n=7a+d>0\) con \(0\le d\le 6\), la recurrencia se transforma en
$$f(7a+d)=f(a)+6-d,\qquad f(0)=0.$$
Quitando repetidamente el último dígito en base \(7\), si \(n=(d_m d_{m-1}\cdots d_0)_7>0\), obtenemos
$$f(n)=\sum_{i=0}^{m}(6-d_i).$$
Por tanto \(g(n+1)\) es una suma ponderada de dígitos. Por ejemplo, \(124=(235)_7\), y entonces
$$g(125)=f(124)=(6-2)+(6-3)+(6-5)=4+3+1=8.$$
Ahora escribimos
$$F(N)=\sum_{m=1}^{N} g(m)=\sum_{n=0}^{N-1} f(n).$$
Para un prefijo positivo \(n\) y un siguiente dígito \(d\), se parte el rango \(0\le x<7n+d\) en bloques completos \(7a,\dots,7a+6\) y un bloque parcial final. El resultado es
$$F(7n+d)=7F(n)+21n-6+d\,f(n)+P(d),$$
donde
$$P(d)=\sum_{x=0}^{d-1}(6-x)=\frac{d(13-d)}{2}.$$
El término \(-6\) corrige únicamente el caso excepcional \(f(0)=0\); sin él, todos los bloques completos tendrían exactamente la misma forma.
Para \(n>0\), usamos el estado aumentado
$$\mathbf{v}(n)=\begin{pmatrix}1\\ n-1\\ F(n)\\ f(n)\\ 1\end{pmatrix}.$$
Añadir un dígito \(d\in\{0,\dots,6\}\) equivale a \(n\mapsto 7n+d\), por lo que
$$\mathbf{v}(7n+d)=M_d\,\mathbf{v}(n),$$
con
$$M_d=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 6 & 7 & 0 & 0 & d\\ 15 & 21 & 7 & d & P(d)\\ 0 & 0 & 0 & 1 & 6-d\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \pmod{M}.$$
Esta es exactamente la familia de matrices usada por las implementaciones en C++, Python y Java.
Como \(11\mid 7^{10}-1\), la expansión en base \(7\) de \(\frac{1}{11}\) es puramente periódica, y en particular
$$\frac{7^{10}-1}{11}=(431162355)_7.$$
Si \(k=10t\), entonces
$$\frac{7^k-1}{11}=\frac{7^{10}-1}{11}\left(1+7^{10}+7^{20}+\cdots+7^{10(t-1)}\right).$$
Por eso, sus dígitos en base \(7\) consisten en el bloque 4311623550 repetido \(t-1\) veces, seguido por 431162355. Como todos esos números empiezan por \(4\), las implementaciones arrancan directamente desde
$$\mathbf{v}(4)=\begin{pmatrix}1\\ 3\\ 12\\ 2\\ 1\end{pmatrix},$$
que ya contiene \(4-1\), \(F(4)=12\) y \(f(4)=2\).
Un control local sencillo consiste en añadir el dígito \(3\) al prefijo \(4\), obteniendo \(43_7=31\). Con \(F(4)=12\), \(f(4)=2\) y \(P(3)=15\), se tiene
$$F(31)=7\cdot 12+21\cdot 4-6+3\cdot 2+15=183.$$
Es decir, la recurrencia reproduce \(\sum_{m=1}^{31} g(m)=183\). Para el primer caso no trivial, \(k=10\), el límite superior es \((431162355)_7\). Partiendo de \(\mathbf{v}(4)\) y procesando el sufijo restante 31162355, se obtiene
$$H(10)=690409338 \pmod{M},$$
el mismo valor de comprobación usado por la implementación.
Las implementaciones construyen primero las siete matrices \(M_0,\dots,M_6\), siempre módulo \(M\). Después precomputan las transformaciones asociadas a las pocas cadenas fijas de dígitos que aparecen en la representación en base \(7\) de \(\frac{7^k-1}{11}\): un sufijo corto para \(k=10\), un bloque inicial, un bloque repetitivo de 10 dígitos y un bloque final.
Si \(k=10\), se aplica una sola vez el sufijo corto al estado inicial \(\mathbf{v}(4)\). Si \(k=10t\ge 20\), primero se aplica el bloque inicial, luego se eleva la transformación del bloque repetitivo a la potencia \(t-2\) mediante exponenciación binaria, y por último se aplica el bloque final. La tercera componente del estado resultante es \(F\!\left(\frac{7^k-1}{11}\right)\), es decir, exactamente \(H(k)\).
Las matrices tienen dimensión fija \(5\), de modo que una multiplicación de matrices es de coste constante en sentido asintótico. La única parte que crece es la potenciación del bloque repetitivo con exponente \(t-2\), donde \(t=k/10\). Por exponenciación binaria, el algoritmo realiza \(O(\log t)=O(\log k)\) multiplicaciones y usa \(O(1)\) memoria adicional.
定义 \(g(n)\) 为如下过程中出现的 \(+1\) 操作次数：从 \(n\) 出发，若当前数能被 \(7\) 整除就除以 \(7\)，否则加 \(1\)；只统计这些加法步数。题目最终要求的是一个很大的前缀和
$$F(N)=\sum_{m=1}^{N} g(m),\qquad H(k)=F\left(\frac{7^k-1}{11}\right)\pmod{M},\qquad M=1{,}117{,}117{,}717.$$
需要计算的是 \(H(10^9)\)。由于上界 \(\frac{7^k-1}{11}\) 本身已经极其巨大，逐个模拟每个整数完全不可行，所以实现采用了三步压缩：先把过程改写成 \(7\) 进制递推，再把递推写成固定维度的线性状态转移，最后利用 \(\frac{1}{11}\) 在 \(7\) 进制中的循环节结构，把超长数字串压缩成少量固定块和一次矩阵快速幂。
若 \(n=7a+r\)，其中 \(0\le r\le 6\)，那么原始规则可以直接写成
$$g(7a)=g(a),\qquad g(7a+r)=7-r+g(a+1)\quad (1\le r\le 6).$$
第二个式子的含义很直观：末位余数是 \(r\neq 0\) 时，需要先做 \(7-r\) 次 \(+1\)，把它补到下一个 \(7\) 的倍数，再除以 \(7\)，剩下的就是 \(a+1\)。
定义
$$f(n)=g(n+1).$$
对所有正整数 \(n=7a+d\)（\(0\le d\le 6\)），上面的递推立刻变为
$$f(7a+d)=f(a)+6-d,\qquad f(0)=0.$$
这意味着：每去掉一个最低位，就把该位的贡献 \(6-d\) 加到答案上。因此若正整数 \(n\) 的 \(7\) 进制表示为 \((d_m d_{m-1}\cdots d_0)_7\)，就有
$$f(n)=\sum_{i=0}^{m}(6-d_i).$$
也就是说，\(g(n+1)\) 根本不需要逐步模拟，它就是一个简单的加权数字和。比如 \(124=(235)_7\)，于是
$$g(125)=f(124)=(6-2)+(6-3)+(6-5)=4+3+1=8,$$
这正好对应实现里的小样例校验。
接下来定义累计和
$$F(N)=\sum_{m=1}^{N} g(m)=\sum_{n=0}^{N-1} f(n).$$
设当前已经读到一个正前缀 \(n\)，下一位要接上数字 \(d\)。那么所有小于 \(7n+d\) 的数可以拆成两部分：前面 \(n\) 个完整块 \(7a,7a+1,\dots,7a+6\)，以及最后一个长度为 \(d\) 的残块。把 \(f(7a+x)\) 的公式代入后，可得
$$F(7n+d)=7F(n)+21n-6+d\,f(n)+P(d),$$
其中
$$P(d)=\sum_{x=0}^{d-1}(6-x)=\frac{d(13-d)}{2}.$$
这里的 \(-6\) 很关键，它来自唯一的特殊点 \(f(0)=0\)。如果没有这个特例，完整块贡献会是完全统一的形式。
对于正整数 \(n\)，定义增广状态
$$\mathbf{v}(n)=\begin{pmatrix}1\\ n-1\\ F(n)\\ f(n)\\ 1\end{pmatrix}.$$
接上一位 \(d\in\{0,\dots,6\}\) 就是做映射 \(n\mapsto 7n+d\)，于是状态满足
$$\mathbf{v}(7n+d)=M_d\,\mathbf{v}(n),$$
其中
$$M_d=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 6 & 7 & 0 & 0 & d\\ 15 & 21 & 7 & d & P(d)\\ 0 & 0 & 0 & 1 & 6-d\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \pmod{M}.$$
这就是实现真正使用的七个矩阵。第一和最后一个分量都固定为 \(1\)，只是为了把常数项一起并入线性变换。
因为 \(11\mid 7^{10}-1\)，所以 \(\frac{1}{11}\) 的 \(7\) 进制展开是纯循环的，并且有
$$\frac{7^{10}-1}{11}=(431162355)_7.$$
当 \(k=10t\) 时，
$$\frac{7^k-1}{11}=\frac{7^{10}-1}{11}\left(1+7^{10}+7^{20}+\cdots+7^{10(t-1)}\right).$$
因此它的 \(7\) 进制数字串正好由 4311623550 这个 10 位块重复 \(t-1\) 次，再接上 431162355 组成。由于这些数都以数字 \(4\) 开头，实现直接从
$$\mathbf{v}(4)=\begin{pmatrix}1\\ 3\\ 12\\ 2\\ 1\end{pmatrix}$$
开始，这里已经预装了 \(4-1\)、\(F(4)=12\) 和 \(f(4)=2\)。随后只需要继续读取后缀部分，而不必重新处理第一个数字。
先看一个小例子。把前缀 \(4\) 接上数字 \(3\)，得到 \(43_7=31\)。代入上面的递推，并使用 \(F(4)=12\)、\(f(4)=2\)、\(P(3)=15\)，可得
$$F(31)=7\cdot 12+21\cdot 4-6+3\cdot 2+15=183.$$
这说明矩阵递推确实能恢复出 \(\sum_{m=1}^{31} g(m)=183\)。再看第一个真正的目标 \(k=10\)：此时上界是 \((431162355)_7\)。从 \(\mathbf{v}(4)\) 出发，把剩余后缀 31162355 逐位处理完之后，第三个分量就是
$$H(10)=690409338 \pmod{M},$$
与实现中写死的检查值完全一致。
C++、Python 和 Java 实现使用的是同一套算法。它们先构造 7 个数字矩阵 \(M_0,\dots,M_6\)，并且始终在模 \(M\) 下运算。然后，它们把 \(\frac{7^k-1}{11}\) 的 \(7\) 进制结构拆成少量固定数字块：\(k=10\) 时只有一个短后缀；更一般地，当 \(k=10t\ge 20\) 时，会有一个起始边界块、一个反复出现的 10 位块，以及一个结尾块。
算法从 \(\mathbf{v}(4)\) 开始。如果 \(t=1\)，就只应用一次短后缀的变换；如果 \(t\ge 2\)，就按“起始块 → 重复块的 \((t-2)\) 次幂 → 结尾块”的顺序作用到状态向量上。其中重复块的高次幂通过二进制快速幂计算，所以不需要按 \(t\) 次逐块扫描。最后读出的第三个分量就是 \(F\!\left(\frac{7^k-1}{11}\right)\)，也就是 \(H(k)\)。
矩阵维度固定为 \(5\)，因此单次矩阵乘法的成本在渐近意义下是常数。真正随输入增长的只有重复块变换的幂次计算，指数是 \(t-2\)，其中 \(t=k/10\)。使用二进制快速幂后，总时间复杂度为 \(O(\log t)=O(\log k)\)，额外空间复杂度为 \(O(1)\)。
Пусть \(g(n)\) обозначает число операций \(+1\) в следующем процессе: пока текущее число не стало равным \(1\), мы делим его на \(7\), если деление возможно, а иначе увеличиваем на \(1\); учитываются только шаги увеличения. Требуется вычислить большую суммарную функцию
$$F(N)=\sum_{m=1}^{N} g(m),\qquad H(k)=F\left(\frac{7^k-1}{11}\right)\pmod{M},\qquad M=1{,}117{,}117{,}717.$$
Нужное значение — \(H(10^9)\). Прямое моделирование невозможно, потому что верхняя граница \(\frac{7^k-1}{11}\) огромна. Поэтому решение переводит процесс в язык цифр по основанию \(7\), превращает его в линейное обновление состояния фиксированного размера и затем использует периодическую запись числа \(\frac{1}{11}\) в системе счисления по основанию \(7\).
Если \(n=7a+r\), где \(0\le r\le 6\), то имеем
$$g(7a)=g(a),\qquad g(7a+r)=7-r+g(a+1)\quad (1\le r\le 6).$$
Смысл второй формулы прост: когда последняя цифра в записи по основанию \(7\) равна \(r\neq 0\), требуется ровно \(7-r\) прибавлений, чтобы дойти до следующего кратного \(7\), после чего число сокращается до \(a+1\).
Введем функцию
$$f(n)=g(n+1).$$
Тогда для любого положительного \(n=7a+d\), \(0\le d\le 6\), получаем
$$f(7a+d)=f(a)+6-d,\qquad f(0)=0.$$
Если последовательно удалять последнюю цифру в записи по основанию \(7\), то для любого положительного числа \(n=(d_m d_{m-1}\cdots d_0)_7\) выходит
$$f(n)=\sum_{i=0}^{m}(6-d_i).$$
То есть \(g(n+1)\) становится просто взвешенной суммой цифр. Например, \(124=(235)_7\), поэтому
$$g(125)=f(124)=(6-2)+(6-3)+(6-5)=4+3+1=8,$$
что совпадает с одним из контрольных значений реализации.
Теперь определим
$$F(N)=\sum_{m=1}^{N} g(m)=\sum_{n=0}^{N-1} f(n).$$
Пусть \(n>0\) — уже обработанный префикс, а \(d\) — следующая цифра в основании \(7\). Если разбить диапазон \(0\le x<7n+d\) на полные блоки \(7a,\dots,7a+6\) и один хвостовой неполный блок, то получится
$$F(7n+d)=7F(n)+21n-6+d\,f(n)+P(d),$$
где
$$P(d)=\sum_{x=0}^{d-1}(6-x)=\frac{d(13-d)}{2}.$$
Поправка \(-6\) возникает только из-за исключительного значения \(f(0)=0\); без него вклад полного блока выглядел бы полностью однородно.
Для положительного \(n\) используется расширенное состояние
$$\mathbf{v}(n)=\begin{pmatrix}1\\ n-1\\ F(n)\\ f(n)\\ 1\end{pmatrix}.$$
Добавление одной цифры \(d\in\{0,\dots,6\}\) означает переход \(n\mapsto 7n+d\), а значит
$$\mathbf{v}(7n+d)=M_d\,\mathbf{v}(n),$$
где
$$M_d=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 6 & 7 & 0 & 0 & d\\ 15 & 21 & 7 & d & P(d)\\ 0 & 0 & 0 & 1 & 6-d\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \pmod{M}.$$
Именно это семейство матриц используют реализации на C++, Python и Java.
Поскольку \(11\mid 7^{10}-1\), дробь \(\frac{1}{11}\) имеет чисто периодическую запись в системе счисления по основанию \(7\). В частности,
$$\frac{7^{10}-1}{11}=(431162355)_7.$$
Если \(k=10t\), то
$$\frac{7^k-1}{11}=\frac{7^{10}-1}{11}\left(1+7^{10}+7^{20}+\cdots+7^{10(t-1)}\right).$$
Следовательно, его цифры в базе \(7\) состоят из блока 4311623550, повторенного \(t-1\) раз, после чего идет хвост 431162355. Все такие числа начинаются с цифры \(4\), поэтому реализации сразу стартуют из состояния
$$\mathbf{v}(4)=\begin{pmatrix}1\\ 3\\ 12\\ 2\\ 1\end{pmatrix},$$
где уже записаны \(4-1\), \(F(4)=12\) и \(f(4)=2\).
Локальная проверка получается, если к префиксу \(4\) приписать цифру \(3\); тогда имеем \(43_7=31\). Подставляя \(F(4)=12\), \(f(4)=2\) и \(P(3)=15\), получаем
$$F(31)=7\cdot 12+21\cdot 4-6+3\cdot 2+15=183.$$
То есть рекурсия действительно восстанавливает сумму \(\sum_{m=1}^{31} g(m)=183\). Для первого нетривиального целевого значения \(k=10\) верхняя граница равна \((431162355)_7\). Если начать с \(\mathbf{v}(4)\) и обработать оставшийся суффикс 31162355, то получится
$$H(10)=690409338 \pmod{M},$$
что точно совпадает с контрольным значением в реализации.
Во всех трех реализациях используется один и тот же прием. Сначала строятся семь матриц \(M_0,\dots,M_6\) по цифрам основания \(7\), причем все вычисления ведутся по модулю \(M\). Затем заранее вычисляются преобразования для нескольких фиксированных строк цифр, которые встречаются в записи числа \(\frac{7^k-1}{11}\): короткий суффикс для случая \(k=10\), начальный граничный блок, повторяющийся 10-значный блок и завершающий блок.
Если \(k=10\), к начальному состоянию \(\mathbf{v}(4)\) применяется только короткий суффикс. Если \(k=10t\ge 20\), сначала применяется начальный блок, затем преобразование повторяющегося блока возводится в степень \(t-2\) с помощью двоичного возведения в степень, а потом применяется завершающий блок. Третья компонента итогового состояния и есть \(F\!\left(\frac{7^k-1}{11}\right)\), то есть искомое \(H(k)\).
Размер матриц фиксирован и равен \(5\), поэтому одна матричная операция имеет постоянную асимптотическую стоимость. Единственный растущий этап — возведение преобразования повторяющегося блока в степень \(t-2\), где \(t=k/10\). За счет двоичного возведения в степень итоговое время равно \(O(\log t)=O(\log k)\), а дополнительная память остается \(O(1)\).
لتكن \(g(n)\) هي عدد عمليات \(+1\) في العملية التالية: نبدأ من \(n\)، فإذا كان العدد يقبل القسمة على \(7\) قسمناه على \(7\)، وإلا زدناه بمقدار \(1\)، مع عدّ خطوات الزيادة فقط. المطلوب في المسألة هو حساب المجموع التراكمي الكبير
$$F(N)=\sum_{m=1}^{N} g(m),\qquad H(k)=F\left(\frac{7^k-1}{11}\right)\pmod{M},\qquad M=1{,}117{,}117{,}717.$$
والقيمة المطلوبة فعليًا هي \(H(10^9)\). المحاكاة المباشرة مستحيلة لأن الحد الأعلى \(\frac{7^k-1}{11}\) هائل جدًا، ولذلك تعيد الحلول صياغة العملية بلغة الأساس \(7\)، ثم تحوّلها إلى تحديث خطي ثابت البعد، ثم تستغل البنية الدورية لتمثيل \(\frac{1}{11}\) في الأساس \(7\).
إذا كتبنا \(n=7a+r\) حيث \(0\le r\le 6\)، فإن القاعدة تعطي
$$g(7a)=g(a),\qquad g(7a+r)=7-r+g(a+1)\quad (1\le r\le 6).$$
ومعنى ذلك أن الرقم الأخير إذا كان \(r\neq 0\)، فنحتاج إلى \(7-r\) زيادات بالضبط للوصول إلى المضاعف التالي للعدد \(7\)، ثم بعد القسمة يبقى \(a+1\).
لنعرّف
$$f(n)=g(n+1).$$
عندئذٍ، لكل \(n=7a+d>0\) مع \(0\le d\le 6\)، تصبح العلاقة
$$f(7a+d)=f(a)+6-d,\qquad f(0)=0.$$
وهذا يعني أن حذف آخر رقم في التمثيل بالأساس \(7\) يضيف فقط المقدار \(6-d\). لذلك إذا كان \(n=(d_m d_{m-1}\cdots d_0)_7\) عددًا موجبًا، فإن
$$f(n)=\sum_{i=0}^{m}(6-d_i).$$
أي إن \(g(n+1)\) يصبح مجموعًا وزنيًا بسيطًا للأرقام. مثلًا \(124=(235)_7\)، ومن ثم
$$g(125)=f(124)=(6-2)+(6-3)+(6-5)=4+3+1=8,$$
وهو بالضبط أحد مقاطع التحقق الصغيرة المستخدمة في التنفيذ.
نعرّف الآن
$$F(N)=\sum_{m=1}^{N} g(m)=\sum_{n=0}^{N-1} f(n).$$
إذا كان لدينا بادئة موجبة \(n\) ورقم تالٍ \(d\) في الأساس \(7\)، فإن جميع الأعداد الأصغر من \(7n+d\) يمكن تقسيمها إلى كتل كاملة من الشكل \(7a,\dots,7a+6\) بالإضافة إلى كتلة أخيرة جزئية. ومن ذلك نحصل على
$$F(7n+d)=7F(n)+21n-6+d\,f(n)+P(d),$$
حيث
$$P(d)=\sum_{x=0}^{d-1}(6-x)=\frac{d(13-d)}{2}.$$
ويظهر الحد \(-6\) فقط بسبب الحالة الاستثنائية \(f(0)=0\)؛ فلو لم تكن هذه الحالة موجودة لكانت مساهمة كل كتلة كاملة ذات شكل موحد تمامًا.
لأي \(n>0\)، نستخدم متجه الحالة الموسَّع
$$\mathbf{v}(n)=\begin{pmatrix}1\\ n-1\\ F(n)\\ f(n)\\ 1\end{pmatrix}.$$
إضافة رقم \(d\in\{0,\dots,6\}\) تعني الانتقال \(n\mapsto 7n+d\)، وبالتالي
$$\mathbf{v}(7n+d)=M_d\,\mathbf{v}(n),$$
مع
$$M_d=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 6 & 7 & 0 & 0 & d\\ 15 & 21 & 7 & d & P(d)\\ 0 & 0 & 0 & 1 & 6-d\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \pmod{M}.$$
وهذه هي المصفوفات نفسها التي تستخدمها تطبيقات C++ وPython وJava.
بما أن \(11\mid 7^{10}-1\)، فإن الكسر \(\frac{1}{11}\) يملك تمثيلًا دوريًا صرفًا في الأساس \(7\)، ونحصل خصوصًا على
$$\frac{7^{10}-1}{11}=(431162355)_7.$$
وعندما \(k=10t\)، يكون
$$\frac{7^k-1}{11}=\frac{7^{10}-1}{11}\left(1+7^{10}+7^{20}+\cdots+7^{10(t-1)}\right).$$
ولهذا فإن أرقامه في الأساس \(7\) تتكون من الكتلة 4311623550 مكررة \(t-1\) مرة، ثم الذيل 431162355. ولأن جميع هذه الأعداد تبدأ بالرقم \(4\)، تبدأ الحلول مباشرة من الحالة
$$\mathbf{v}(4)=\begin{pmatrix}1\\ 3\\ 12\\ 2\\ 1\end{pmatrix},$$
التي تحتوي مسبقًا على \(4-1\) و\(F(4)=12\) و\(f(4)=2\).
من الفحوص المحلية المفيدة أن نلحق الرقم \(3\) بالبادئة \(4\)، فنحصل على \(43_7=31\). وباستخدام \(F(4)=12\) و\(f(4)=2\) و\(P(3)=15\) نجد
$$F(31)=7\cdot 12+21\cdot 4-6+3\cdot 2+15=183.$$
إذن تعيد العلاقة التراكمية فعلًا القيمة \(\sum_{m=1}^{31} g(m)=183\). أما أول هدف غير بسيط فهو \(k=10\)، حيث يكون الحد الأعلى هو \((431162355)_7\). وإذا بدأنا من \(\mathbf{v}(4)\) وقرأنا الذيل المتبقي 31162355، نحصل على
$$H(10)=690409338 \pmod{M},$$
وهو نفس مقدار التحقق الموجود في التنفيذ.
التنفيذات الثلاثة تستخدم الفكرة نفسها. فهي تبني أولًا المصفوفات السبع \(M_0,\dots,M_6\) للأرقام في الأساس \(7\)، مع إجراء كل العمليات بترديد \(M\). بعد ذلك تُحسب مسبقًا تحولات السلاسل الرقمية الثابتة القليلة التي تظهر في تمثيل \(\frac{7^k-1}{11}\): ذيل قصير للحالة \(k=10\)، وكتلة ابتدائية حدّية، وكتلة تكرارية طولها 10 أرقام، وكتلة ختامية.
إذا كان \(k=10\)، فيكفي تطبيق الذيل القصير مرة واحدة على الحالة الابتدائية \(\mathbf{v}(4)\). وإذا كان \(k=10t\ge 20\)، فيُطبَّق أولًا التحول الابتدائي، ثم تُرفع الكتلة التكرارية إلى القوة \(t-2\) بواسطة الرفع الثنائي للأس، ثم يُطبَّق التحول الختامي. المركبة الثالثة من الحالة النهائية هي \(F\!\left(\frac{7^k-1}{11}\right)\)، أي القيمة المطلوبة \(H(k)\).
بما أن أبعاد المصفوفات ثابتة وتساوي \(5\)، فإن تكلفة الضرب المصفوفي الواحد ثابتة من الناحية التقاربية. الجزء الوحيد الذي ينمو مع الإدخال هو رفع الكتلة المتكررة إلى القوة \(t-2\)، حيث \(t=k/10\). وباستخدام الرفع الثنائي للأس نحصل على زمن كلي \(O(\log t)=O(\log k)\) وذاكرة إضافية \(O(1)\).