The sequence is defined by
$$a_1=1,\qquad a_n\equiv \sum_{k=1}^{n-1}k\,a_k\pmod n\qquad(n\ge 2).$$
For given \(N\) and \(M\), we must count how many subarrays of
$$a_1,a_2,\dots,a_N$$
have sum divisible by \(M\). The final instance is
$$f(10^{12},10^6).$$
A direct \(O(N)\) pass is impossible, so the key is to expose the hidden periodic structure.
1) Prefix sums turn divisibility into equal residues.
Define prefix sums modulo \(M\):
$$P_t\equiv \sum_{i=1}^{t}a_i\pmod M,\qquad P_0=0.$$
Then for any \(0\le i \lt j\le N\),
$$\sum_{k=i+1}^{j}a_k\equiv 0\pmod M \iff P_i\equiv P_j\pmod M.$$
So if residue \(r\) appears \(c_r\) times among
$$P_0,P_1,\dots,P_N,$$
then it contributes
$$\binom{c_r}{2}$$
valid subarrays. Therefore
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
2) Introduce the weighted running sum.
Let
$$W_n=\sum_{k=1}^{n}k\,a_k.$$
Then the recurrence is simply
$$a_n=W_{n-1}\bmod n,\qquad W_n=W_{n-1}+n\,a_n.$$
This is exactly the pair of variables tracked in the C++ code.
3) The first terms reveal a 6-step block pattern.
The code checks the first ten values
$$1,1,0,3,0,3,5,4,1,9,$$
and if we continue a little further, the sequence groups naturally into blocks of length 6:
$$[1,1,0,3,0,3],$$
$$[5,4,1,9,1,6],$$
$$[9,7,2,15,2,9],\dots$$
This is not an accident. For every integer \(m\ge 0\), the exact formulas are
$$a_{6m+1}=4m+1,\qquad a_{6m+2}=3m+1,\qquad a_{6m+3}=m,$$
$$a_{6m+4}=6m+3,\qquad a_{6m+5}=m,\qquad a_{6m+6}=3m+3.$$
These identities can be proved by induction from the definition of \(W_n\), and they are the real reason the problem becomes tractable.
4) Why this implies a period of \(6M\).
Each formula above is affine in \(m\). Therefore, modulo \(M\), replacing \(m\) by \(m+M\) leaves every value unchanged. So
$$a_{n+6M}\equiv a_n\pmod M.$$
That gives periodicity of the term sequence modulo \(M\).
5) Why the prefix residues also repeat with period \(6M\).
We still need the prefix sums \(P_t\), not just the terms \(a_t\). For one full period, the block sum is
$$a_{6m+1}+\cdots+a_{6m+6}=18m+8.$$
Summing over \(m=0,1,\dots,M-1\) gives
$$\sum_{n=1}^{6M} a_n = \sum_{m=0}^{M-1}(18m+8)=M(9M-1),$$
which is divisible by \(M\). Therefore one whole period changes the prefix sum by
$$0\pmod M,$$
and hence the prefix-residue sequence \((P_t)\) itself has period \(6M\).
6) Histogram over one period plus a tail.
Write
$$N=q(6M)+t,\qquad 0\le t \lt 6M.$$
Let \(h_r\) be the number of times residue \(r\) appears in one full period of
$$P_0,P_1,\dots,P_{6M-1},$$
and let \(u_r\) be the number of appearances in the tail
$$P_0,P_1,\dots,P_t.$$
Then the total count of residue \(r\) among \(P_0,\dots,P_N\) is
$$c_r=q\,h_r+u_r.$$
Once these counts are known, the answer is just
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
7) Worked checkpoint.
The code checks
$$f(10,10)=4,$$
and also
$$f(10^4,10^3)=97158.$$
These are excellent sanity checks for both the sequence generator and the residue-histogram logic.
1) Simulate exactly one period of length \(6M\).
2) While simulating, record how often each prefix residue appears in the full period.
3) Also record the residue histogram for the first \(t=N\bmod 6M\) positions.
4) Combine the two histograms via \(c_r=q\,h_r+u_r\).
5) Sum \(\binom{c_r}{2}\) over all residues.
Only one period is simulated, so the running time is
$$O(M)$$
up to the constant factor 6, and the memory usage is
$$O(M).$$
The huge value of \(N\) never appears as a loop bound.
The checkpoints are
$$a_1,\dots,a_{10}=1,1,0,3,0,3,5,4,1,9,$$
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
For the target input, the final answer is
$$f(10^{12},10^6)=1966666166408794329.$$
Die Folge ist definiert durch
$$a_1=1,\qquad a_n\equiv \sum_{k=1}^{n-1}k\,a_k\pmod n\qquad(n\ge 2).$$
Gesucht ist die Anzahl der Teilintervalle von \(a_1,\dots,a_N\), deren Summe durch \(M\) teilbar ist. Der Zielwert ist
$$f(10^{12},10^6).$$
1) Praefixreste.
Setze
$$P_t\equiv \sum_{i=1}^{t}a_i\pmod M,\qquad P_0=0.$$
Dann gilt fuer \(0\le i \lt j\le N\):
$$\sum_{k=i+1}^{j}a_k\equiv 0\pmod M \iff P_i\equiv P_j\pmod M.$$
Wenn ein Rest \(r\) insgesamt \(c_r\)-mal vorkommt, traegt er
$$\binom{c_r}{2}$$
gueltige Intervalle bei. Also
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
2) Gewichtete Summe \(W_n\).
Mit
$$W_n=\sum_{k=1}^{n}k\,a_k$$
wird die Definition zu
$$a_n=W_{n-1}\bmod n,\qquad W_n=W_{n-1}+n\,a_n.$$
3) Exakte 6er-Blockformel.
Die ersten Terme sind
$$1,1,0,3,0,3,5,4,1,9,\dots$$
und tatsaechlich gilt fuer jedes \(m\ge 0\):
$$a_{6m+1}=4m+1,\qquad a_{6m+2}=3m+1,\qquad a_{6m+3}=m,$$
$$a_{6m+4}=6m+3,\qquad a_{6m+5}=m,\qquad a_{6m+6}=3m+3.$$
Damit ist die Folge modulo \(M\) periodisch mit Periode \(6M\).
4) Warum auch die Praefixreste Periode \(6M\) haben.
Die Summe eines Blocks ist
$$18m+8.$$
Ueber \(m=0,\dots,M-1\) ergibt eine ganze Periode
$$\sum_{n=1}^{6M}a_n=M(9M-1),$$
also \(0\pmod M\). Daher wiederholt sich nicht nur \(a_n\bmod M\), sondern auch die Folge der Praefixreste \(P_t\).
5) Vollperioden und Restsegment.
Schreibe
$$N=q(6M)+t,\qquad 0\le t\lt 6M.$$
Ist \(h_r\) die Haeufigkeit von Rest \(r\) in einer vollen Periode und \(u_r\) die Haeufigkeit im Restsegment, dann
$$c_r=q\,h_r+u_r.$$
Danach folgt sofort
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
6) Checkpoints.
Der Code prueft
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
1) Genau eine Periode der Laenge \(6M\) simulieren.
2) Histogramm der Praefixreste fuer die volle Periode sammeln.
3) Histogramm fuer den Tail \(t=N\bmod 6M\) sammeln.
4) Mit \(c_r=q\,h_r+u_r\) kombinieren.
5) \(\binom{c_r}{2}\) ueber alle Reste aufsummieren.
Es wird nur eine einzige Periode simuliert. Daher ist die Laufzeit
$$O(M)$$
und der Speicherverbrauch
$$O(M).$$
Geprueft werden die ersten zehn Werte
$$1,1,0,3,0,3,5,4,1,9,$$
sowie
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
Das Endergebnis lautet
$$f(10^{12},10^6)=1966666166408794329.$$
Dizi su sekilde tanimli:
$$a_1=1,\qquad a_n\equiv \sum_{k=1}^{n-1}k\,a_k\pmod n\qquad(n\ge 2).$$
Amac, \(a_1,\dots,a_N\) dizisi icindeki toplami \(M\)'ye tam bolunen alt araliklarin sayisini bulmak. Nihai hedef
$$f(10^{12},10^6)$$
degeridir.
1) Onek toplamlar alt aralik problemini cozer.
Su onek toplamlari tanimlayalim:
$$P_t\equiv \sum_{i=1}^{t}a_i\pmod M,\qquad P_0=0.$$
O zaman
$$\sum_{k=i+1}^{j}a_k\equiv 0\pmod M \iff P_i\equiv P_j\pmod M.$$
Yani bir kalanin frekansi \(c_r\) ise katkisi
$$\binom{c_r}{2}$$
olur. Dolayisiyla
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
2) Agirlikli kismi ayri takip et.
Su toplami tanimlayalim:
$$W_n=\sum_{k=1}^{n}k\,a_k.$$
O zaman dizi reküransi cok sade hale gelir:
$$a_n=W_{n-1}\bmod n,\qquad W_n=W_{n-1}+n\,a_n.$$
Kod da tam olarak bu iki buyuklugu tutuyor.
3) Dizi 6'li bloklarda kapali form tasir.
Ilk on terim
$$1,1,0,3,0,3,5,4,1,9$$
olarak gelir. Devamina bakinca 6'li blok yapisi gorulur ve gercekte her \(m\ge 0\) icin
$$a_{6m+1}=4m+1,\qquad a_{6m+2}=3m+1,\qquad a_{6m+3}=m,$$
$$a_{6m+4}=6m+3,\qquad a_{6m+5}=m,\qquad a_{6m+6}=3m+3$$
olur. Bu dogrudan periyot ispatinin cekirdegi.
4) Neden \(a_n \bmod M\) icin periyot \(6M\)?
Yukaridaki altili blok formullerinin her biri \(m\)'de lineerdir. Bu yuzden modulo \(M\), \(m\) yerine \(m+M\) koymak degeri degistirmez. Sonuc olarak
$$a_{n+6M}\equiv a_n\pmod M.$$
5) Neden onek modlari da \(6M\) periyotludur?
Tek bir 6'li blok toplamı
$$18m+8$$
eder. Tam bir periyotta, yani \(m=0,\dots,M-1\) icin toplam
$$\sum_{n=1}^{6M}a_n=\sum_{m=0}^{M-1}(18m+8)=M(9M-1)$$
olur ve bu da \(M\)'ye tam bolunur. Demek ki sadece terimler degil, onek kalani dizisi de ayni periyodu tekrarlar.
6) Tam periyot + kuyruk sayimi.
Su ayrimi yapalim:
$$N=q(6M)+t,\qquad 0\le t\lt 6M.$$
Bir tam periyotta kalan \(r\)'nin gorulme sayisina \(h_r\), kuyruğun ilk \(t\) adimindaki sayiya \(u_r\) diyelim. O halde toplam frekans
$$c_r=q\,h_r+u_r$$
olur ve cevap
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}$$
haline gelir.
7) Checkpoint'ler.
Kod once ilk 10 terimi dogrular:
$$1,1,0,3,0,3,5,4,1,9.$$
Ardindan
$$f(10,10)=4,\qquad f(10^4,10^3)=97158$$
kontrollerini yapar.
1) Yalnizca bir periyot, yani \(6M\) adim simule et.
2) Tam periyottaki onek-kalan histogramini topla.
3) Kuyruk \(t=N\bmod 6M\) icin ayrica histogram topla.
4) Her kalanin toplam frekansini \(c_r=q\,h_r+u_r\) ile kur.
5) Tum kalalar uzerinden \(\binom{c_r}{2}\) toplamini hesapla.
Sadece bir periyot simule edildigi icin zaman
$$O(M),$$
bellek ise
$$O(M)$$
olur. Devasa \(N\) hicbir yerde dongu siniri olarak kullanilmaz.
Checkpoint'ler:
$$a_1,\dots,a_{10}=1,1,0,3,0,3,5,4,1,9,$$
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
Nihai cevap
$$f(10^{12},10^6)=1966666166408794329$$
olarak bulunur.
La sucesion viene dada por
$$a_1=1,\qquad a_n\equiv \sum_{k=1}^{n-1}k\,a_k\pmod n\qquad(n\ge 2).$$
Hay que contar cuantos subintervalos de \(a_1,\dots,a_N\) tienen suma divisible por \(M\). El caso final es
$$f(10^{12},10^6).$$
1) Prefijos modulo \(M\).
Definimos
$$P_t\equiv \sum_{i=1}^{t}a_i\pmod M,\qquad P_0=0.$$
Entonces
$$\sum_{k=i+1}^{j}a_k\equiv 0\pmod M \iff P_i\equiv P_j\pmod M.$$
Si un residuo \(r\) aparece \(c_r\) veces, aporta
$$\binom{c_r}{2},$$
de modo que
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
2) La suma ponderada \(W_n\).
Sea
$$W_n=\sum_{k=1}^{n}k\,a_k.$$
La recurrencia se reescribe como
$$a_n=W_{n-1}\bmod n,\qquad W_n=W_{n-1}+n\,a_n.$$
3) Formula exacta por bloques de longitud 6.
Los primeros valores
$$1,1,0,3,0,3,5,4,1,9,\dots$$
sugieren la estructura correcta. En efecto, para todo \(m\ge 0\):
$$a_{6m+1}=4m+1,\qquad a_{6m+2}=3m+1,\qquad a_{6m+3}=m,$$
$$a_{6m+4}=6m+3,\qquad a_{6m+5}=m,\qquad a_{6m+6}=3m+3.$$
4) Periodo \(6M\).
Cada una de esas expresiones es lineal en \(m\). Por tanto, modulo \(M\), reemplazar \(m\) por \(m+M\) no cambia nada, y queda
$$a_{n+6M}\equiv a_n\pmod M.$$
5) Los prefijos tambien son periodicos.
La suma de un bloque es
$$18m+8.$$
En una vuelta completa,
$$\sum_{n=1}^{6M}a_n=\sum_{m=0}^{M-1}(18m+8)=M(9M-1),$$
que es divisible por \(M\). Asi, la sucesion de residuos prefijo \(P_t\) tambien tiene periodo \(6M\).
6) Ciclos completos y cola.
Escribimos
$$N=q(6M)+t,\qquad 0\le t\lt 6M.$$
Si \(h_r\) es la frecuencia del residuo \(r\) en un periodo completo y \(u_r\) la frecuencia en la cola, entonces
$$c_r=q\,h_r+u_r.$$
Con eso ya basta para calcular
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
7) Checkpoints.
El codigo comprueba
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
1) Simular exactamente un periodo de longitud \(6M\).
2) Construir el histograma de residuos prefijo en el periodo completo.
3) Construir el histograma en la cola de longitud \(t\).
4) Combinar mediante \(c_r=q\,h_r+u_r\).
5) Sumar \(\binom{c_r}{2}\) sobre todos los residuos.
Solo se simula un periodo, asi que el tiempo es
$$O(M)$$
y la memoria es
$$O(M).$$
El codigo valida
$$a_1,\dots,a_{10}=1,1,0,3,0,3,5,4,1,9,$$
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
El resultado final es
$$f(10^{12},10^6)=1966666166408794329.$$
数列满足
$$a_1=1,\qquad a_n\equiv \sum_{k=1}^{n-1}k\,a_k\pmod n\qquad(n\ge 2).$$
要求统计 \(a_1,\dots,a_N\) 中有多少个子区间的和能被 \(M\) 整除。最终目标是
$$f(10^{12},10^6).$$
1) 前缀模把问题变成“相同余数配对”。
定义
$$P_t\equiv \sum_{i=1}^{t}a_i\pmod M,\qquad P_0=0.$$
则
$$\sum_{k=i+1}^{j}a_k\equiv 0\pmod M \iff P_i\equiv P_j\pmod M.$$
如果某个余数 \(r\) 总共出现 \(c_r\) 次，就贡献
$$\binom{c_r}{2}$$
个合法子区间，因此
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
2) 引入加权前缀和 \(W_n\)。
令
$$W_n=\sum_{k=1}^{n}k\,a_k.$$
那么递推就变成
$$a_n=W_{n-1}\bmod n,\qquad W_n=W_{n-1}+n\,a_n.$$
3) 真正的关键是 6 项分块公式。
前几项
$$1,1,0,3,0,3,5,4,1,9,\dots$$
已经暗示出规律。事实上对任意 \(m\ge 0\)，都有
$$a_{6m+1}=4m+1,\qquad a_{6m+2}=3m+1,\qquad a_{6m+3}=m,$$
$$a_{6m+4}=6m+3,\qquad a_{6m+5}=m,\qquad a_{6m+6}=3m+3.$$
4) 因而 \(a_n\bmod M\) 的周期是 \(6M\)。
上面六个表达式全都是关于 \(m\) 的一次式，所以模 \(M\) 后，把 \(m\) 换成 \(m+M\) 不会改变结果，于是
$$a_{n+6M}\equiv a_n\pmod M.$$
5) 为什么前缀余数 \(P_t\) 也有同样周期。
一个 6 项块的总和是
$$18m+8.$$
把 \(m=0,1,\dots,M-1\) 累加，得到一整周期的总和
$$\sum_{n=1}^{6M}a_n=\sum_{m=0}^{M-1}(18m+8)=M(9M-1),$$
这显然被 \(M\) 整除。所以一整周期结束后，前缀和模 \(M\) 的净变化是 0，因此 \(P_t\) 本身也以 \(6M\) 为周期。
6) 完整周期直方图加尾部直方图。
写成
$$N=q(6M)+t,\qquad 0\le t\lt 6M.$$
设 \(h_r\) 是一个完整周期里余数 \(r\) 的出现次数，\(u_r\) 是尾部长度 \(t\) 内的出现次数，则
$$c_r=q\,h_r+u_r.$$
最后直接代入
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}$$
即可。
7) 校验点。
代码先验证前 10 项，再验证
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
1) 只模拟一个长度为 \(6M\) 的周期。
2) 统计完整周期中各前缀余数的频次。
3) 统计尾部 \(t=N\bmod 6M\) 中的频次。
4) 用 \(c_r=q\,h_r+u_r\) 合并。
5) 对所有余数求和 \(\binom{c_r}{2}\)。
由于只模拟一整个周期，时间复杂度是
$$O(M),$$
空间复杂度也是
$$O(M).$$
校验值为
$$a_1,\dots,a_{10}=1,1,0,3,0,3,5,4,1,9,$$
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
最终答案是
$$f(10^{12},10^6)=1966666166408794329.$$
Последовательность задаётся так:
$$a_1=1,\qquad a_n\equiv \sum_{k=1}^{n-1}k\,a_k\pmod n\qquad(n\ge 2).$$
Нужно посчитать число подотрезков последовательности \(a_1,\dots,a_N\), сумма которых кратна \(M\). Итоговый запрос:
$$f(10^{12},10^6).$$
1) Префиксные суммы по модулю.
Положим
$$P_t\equiv \sum_{i=1}^{t}a_i\pmod M,\qquad P_0=0.$$
Тогда
$$\sum_{k=i+1}^{j}a_k\equiv 0\pmod M \iff P_i\equiv P_j\pmod M.$$
Если остаток \(r\) встречается \(c_r\) раз, вклад равен
$$\binom{c_r}{2},$$
и потому
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
2) Взвешенная сумма \(W_n\).
Определим
$$W_n=\sum_{k=1}^{n}k\,a_k.$$
Тогда рекурсия переписывается как
$$a_n=W_{n-1}\bmod n,\qquad W_n=W_{n-1}+n\,a_n.$$
3) Точные формулы по блокам длины 6.
Первые члены
$$1,1,0,3,0,3,5,4,1,9,\dots$$
подсказывают структуру, и действительно для любого \(m\ge 0\):
$$a_{6m+1}=4m+1,\qquad a_{6m+2}=3m+1,\qquad a_{6m+3}=m,$$
$$a_{6m+4}=6m+3,\qquad a_{6m+5}=m,\qquad a_{6m+6}=3m+3.$$
4) Отсюда период \(6M\).
Все эти выражения линейны по \(m\). Значит, по модулю \(M\) замена \(m\mapsto m+M\) ничего не меняет, поэтому
$$a_{n+6M}\equiv a_n\pmod M.$$
5) Почему префиксные остатки тоже периодичны.
Сумма одного блока равна
$$18m+8.$$
За полный период получаем
$$\sum_{n=1}^{6M}a_n=\sum_{m=0}^{M-1}(18m+8)=M(9M-1),$$
то есть это \(0\pmod M\). Следовательно, последовательность префиксных остатков \(P_t\) тоже имеет период \(6M\).
6) Полные циклы и хвост.
Пишем
$$N=q(6M)+t,\qquad 0\le t\lt 6M.$$
Если \(h_r\) - число появлений остатка \(r\) в полном периоде, а \(u_r\) - в хвосте, то
$$c_r=q\,h_r+u_r.$$
После этого ответ сразу равен
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
7) Контрольные точки.
Код проверяет
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
1) Смоделировать ровно один период длины \(6M\).
2) Построить гистограмму префиксных остатков на полном периоде.
3) Построить гистограмму для хвоста длины \(t\).
4) Скомбинировать по формуле \(c_r=q\,h_r+u_r\).
5) Просуммировать \(\binom{c_r}{2}\) по всем остаткам.
Время равно
$$O(M),$$
память тоже
$$O(M).$$
Проверяются первые десять членов
$$1,1,0,3,0,3,5,4,1,9,$$
а также
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
Итоговый ответ:
$$f(10^{12},10^6)=1966666166408794329.$$
المتتالية معرفة بالعلاقة
$$a_1=1,\qquad a_n\equiv \sum_{k=1}^{n-1}k\,a_k\pmod n\qquad(n\ge 2).$$
ونريد عدّ المقاطع الفرعية من \(a_1,\dots,a_N\) التي يكون مجموعها قابلاً للقسمة على \(M\). الحالة النهائية هي
$$f(10^{12},10^6).$$
1) مجاميع البوادئ modulo \(M\).
نعرّف
$$P_t\equiv \sum_{i=1}^{t}a_i\pmod M,\qquad P_0=0.$$
وعندها
$$\sum_{k=i+1}^{j}a_k\equiv 0\pmod M \iff P_i\equiv P_j\pmod M.$$
إذا ظهر الباقي \(r\) عدد \(c_r\) من المرات، فمساهمته هي
$$\binom{c_r}{2}.$$
إذن
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
2) مجموع موزون مساعد.
لنكتب
$$W_n=\sum_{k=1}^{n}k\,a_k.$$
فتصبح العلاقة
$$a_n=W_{n-1}\bmod n,\qquad W_n=W_{n-1}+n\,a_n.$$
3) الصيغة الدقيقة على كتل طولها 6.
أول القيم هي
$$1,1,0,3,0,3,5,4,1,9,\dots$$
والنمط الحقيقي هو أنه لكل \(m\ge 0\):
$$a_{6m+1}=4m+1,\qquad a_{6m+2}=3m+1,\qquad a_{6m+3}=m,$$
$$a_{6m+4}=6m+3,\qquad a_{6m+5}=m,\qquad a_{6m+6}=3m+3.$$
4) ومن هنا تأتي دورية \(6M\).
كل صيغة من هذه الصيغ خطية في \(m\)، ولذلك modulo \(M\) لا يتغير شيء عند استبدال \(m\) بـ \(m+M\). بالتالي
$$a_{n+6M}\equiv a_n\pmod M.$$
5) لماذا بوادئ المجاميع دورية أيضًا.
مجموع كتلة واحدة يساوي
$$18m+8.$$
أما مجموع دورة كاملة فهو
$$\sum_{n=1}^{6M}a_n=\sum_{m=0}^{M-1}(18m+8)=M(9M-1),$$
وهو من مضاعفات \(M\). لذلك تتكرر متتالية البوادئ \(P_t\) نفسها كل \(6M\) خطوة.
6) دورة كاملة مع ذيل.
نكتب
$$N=q(6M)+t,\qquad 0\le t\lt 6M.$$
إذا كان \(h_r\) عدد مرات ظهور الباقي \(r\) في دورة كاملة، و\(u_r\) عدد مرات ظهوره في الذيل، فإن
$$c_r=q\,h_r+u_r.$$
ثم يصبح الجواب
$$f(N,M)=\sum_{r=0}^{M-1}\binom{c_r}{2}.$$
7) نقاط الفحص.
يفحص البرنامج
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
1) نحاكي دورة واحدة فقط بطول \(6M\).
2) نبني إحصاء بواقي البوادئ في الدورة الكاملة.
3) نبني إحصاء الذيل بطول \(t\).
4) نركّب التكرارات باستخدام \(c_r=q\,h_r+u_r\).
5) نجمع \(\binom{c_r}{2}\) على جميع البواقي.
بما أننا نحاكي دورة واحدة فقط، فالزمن هو
$$O(M),$$
والذاكرة هي
$$O(M).$$
يتحقق البرنامج من أول عشر قيم
$$1,1,0,3,0,3,5,4,1,9,$$
وكذلك من
$$f(10,10)=4,\qquad f(10^4,10^3)=97158.$$
أما النتيجة النهائية فهي
$$f(10^{12},10^6)=1966666166408794329.$$