We count sequences
$$x_1,x_2,\dots,x_n$$
such that
$$x_1=2,$$
$$x_{i-1}\lt x_i\qquad (2\le i\le n),$$
and for all \(1\le i,j\le n\),
$$(x_i)^j \lt (x_j+1)^i.$$
Let \(t(n)\) be the number of such sequences. We are given
$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891,$$
and we must find
$$t(10^{10})\pmod{10^9}.$$
1) The defining inequalities mean "take floors of powers of one real number".
Rewrite the condition
$$(x_i)^j \lt (x_j+1)^i$$
as
$$x_i^{1/i} \lt (x_j+1)^{1/j} \qquad \text{for all } i,j.$$
So the intervals
$$I_i=\bigl(x_i^{1/i},\ (x_i+1)^{1/i}\bigr)$$
all overlap. Therefore there exists a real number \(y\) belonging to every \(I_i\), and for that \(y\) we have
$$x_i \lt y^i \lt x_i+1,$$
hence
$$x_i=\lfloor y^i\rfloor.$$
Conversely, any \(y\in(2,3)\) defines a valid sequence by setting \(x_i=\lfloor y^i\rfloor\). The condition \(x_1=2\) is exactly \(2\le y \lt 3\), and because \(y\gt1\), the sequence is strictly increasing.
2) So \(t(n)\) is a boundary-counting problem on \(y\in[2,3)\).
As \(y\) moves through \([2,3)\), the sequence
$$\bigl(\lfloor y\rfloor,\lfloor y^2\rfloor,\dots,\lfloor y^n\rfloor\bigr)$$
changes only when some \(y^k\) crosses an integer. The change points are exactly the numbers
$$y=m^{1/k},\qquad 1\le k\le n,\qquad 2^k \lt m \lt 3^k.$$
Therefore \(t(n)\) equals
$$1+\text{(number of distinct boundary points in }(2,3)\text{ visible up to exponent }n).$$
3) Distinct roots are the real difficulty.
If we simply count all pairs \((m,k)\) with \(2^k \lt m \lt 3^k\), we overcount. For example, the same boundary might be representable both as \(m^{1/k}\) and as \(u^{1/d}\) if \(m\) is a perfect power.
To remove duplicates, define:
$$f(k)=3^k-2^k-1,$$
the number of integers strictly between \(2^k\) and \(3^k\), and
$$g(k)=\text{number of boundary points whose minimal exponent is exactly }k.$$
Every integer \(m\) counted by \(f(k)\) corresponds to a boundary whose minimal exponent divides \(k\). Hence
$$f(k)=\sum_{d\mid k} g(d).$$
4) Möbius inversion produces the primitive counts.
Applying Möbius inversion gives
$$g(k)=\sum_{d\mid k}\mu(d)\,f\!\left(\frac{k}{d}\right),$$
where \(\mu\) is the Möbius function.
Since each primitive boundary of degree \(k\) contributes exactly one new cut point once \(k\le n\), we have
$$t(n)=1+\sum_{k=1}^{n} g(k).$$
Substituting the inversion formula and swapping the order of summation yields
$$t(n)=1+\sum_{k=1}^{n} f(k)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right),$$
where
$$M(x)=\sum_{m\le x}\mu(m)$$
is the Mertens function.
This is exactly the formula implemented by the code, with
$$f(k)=3^k-2^k-1.$$
5) Worked example: why \(t(2)=5\).
For \(n=2\), only \(k=2\) contributes new boundaries, because
$$f(1)=3-2-1=0,\qquad f(2)=9-4-1=4.$$
The four boundary points are
$$\sqrt5,\ \sqrt6,\ \sqrt7,\ \sqrt8.$$
They split the interval \([2,3)\) into five parts, producing the five sequences
$$\{2,4\},\ \{2,5\},\ \{2,6\},\ \{2,7\},\ \{2,8\}.$$
So
$$t(2)=5,$$
exactly as stated.
6) Prefix sums of the coefficients.
The code needs many interval sums of
$$a_k=f(k)=3^k-2^k-1.$$
Define
$$A(m)=\sum_{k=1}^{m} a_k.$$
Using geometric-series formulas,
$$A(m)=\frac{3^{m+1}-3}{2}-(2^{m+1}-2)-m.$$
Therefore any block \([l,r]\) contributes
$$\sum_{k=l}^{r}a_k=A(r)-A(l-1).$$
Because the final modulus is \(10^9\), division by \(2\) is not invertible modulo \(10^9\). The implementation avoids trouble by first computing \(3^{m+1}\) modulo \(2\cdot10^9\), so the numerator is still even and can be safely halved.
7) Harmonic partition of the outer sum.
The quotient
$$q=\left\lfloor\frac{n}{k}\right\rfloor$$
is constant on long ranges \([l,r]\). So instead of summing one \(k\) at a time, we group all \(k\) in the same block:
$$\sum_{k=1}^{n} a_k\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right) =\sum_{\text{blocks }[l,r]} \bigl(A(r)-A(l-1)\bigr)\,M(q).$$
The number of such blocks is only about \(2\sqrt n\), not \(n\).
8) Fast computation of the Mertens function.
For small values, \(\mu\) and \(M\) are precomputed with a linear sieve. For large \(x\), the code uses the classical identity
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$
where each interval \([l,r]\) shares the same quotient \(\lfloor x/l\rfloor\). Memoization makes each large \(M(x)\) value get computed only once.
1) Use the combinatorial reformulation
$$t(n)=1+\sum_{k=1}^{n}(3^k-2^k-1)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
2) Precompute \(\mu\) and \(M\) up to about \(n^{2/3}\) with a linear sieve.
3) Compute large \(M(x)\) recursively with quotient grouping and memoization.
4) Group the outer sum into blocks of constant \(\lfloor n/k\rfloor\).
5) Use the closed form for \(A(m)\) to evaluate each block in \(O(1)\).
The sieve runs up to roughly \(n^{2/3}\). The outer harmonic decomposition has only
$$O(\sqrt n)$$
blocks. Combined with memoized Mertens queries, this is dramatically faster than summing \(10^{10}\) terms one by one.
The source validates
$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891.$$
For
$$n=10^{10},$$
the program outputs
$$268457129$$
modulo \(10^9\).
Gesucht ist die Anzahl spezieller Folgen \(x_1,\dots,x_n\) mit \(x_1=2\), strikt wachsend und der Bedingung
$$(x_i)^j \lt (x_j+1)^i.$$
Fuer \(n=10^{10}\) soll \(t(n)\bmod 10^9\) berechnet werden.
1) Die Folgen sind genau \(\lfloor y^i\rfloor\)-Folgen.
Die Ungleichung ist aequivalent zu
$$x_i^{1/i}\lt(x_j+1)^{1/j}\qquad\text{fuer alle }i,j.$$
Also schneiden sich die Intervalle
$$I_i=\bigl(x_i^{1/i},(x_i+1)^{1/i}\bigr),$$
und es existiert ein \(y\in[2,3)\) mit
$$x_i=\lfloor y^i\rfloor.$$
Umgekehrt liefert jedes \(y\in[2,3)\) genau eine gueltige Folge.
2) Grenzen entstehen bei Wurzeln ganzer Zahlen.
Die Folge aendert sich nur, wenn fuer ein \(k\le n\) der Wert \(y^k\) eine ganze Zahl kreuzt. Die Grenzpunkte sind also
$$y=m^{1/k},\qquad 2^k\lt m\lt 3^k.$$
Daher ist \(t(n)\) gleich \(1\) plus der Zahl der verschiedenen solchen Grenzpunkte.
3) Primitive Grade und Möbius-Inversion.
Setze
$$f(k)=3^k-2^k-1,$$
also die Zahl der ganzen Zahlen strikt zwischen \(2^k\) und \(3^k\), und
$$g(k)=\text{Zahl der Grenzpunkte mit minimalem Exponenten }k.$$
Dann gilt
$$f(k)=\sum_{d\mid k} g(d),$$
und per Möbius-Inversion
$$g(k)=\sum_{d\mid k}\mu(d)\,f(k/d).$$
Somit
$$t(n)=1+\sum_{k=1}^{n}g(k)=1+\sum_{k=1}^{n}f(k)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right),$$
wobei \(M\) die Mertens-Funktion ist.
4) Beispiel \(t(2)=5\).
Es gibt genau vier Grenzpunkte \(\sqrt5,\sqrt6,\sqrt7,\sqrt8\), also fuenf Intervalle in \([2,3)\). Das erzeugt die fuenf Folgen
$$\{2,4\},\{2,5\},\{2,6\},\{2,7\},\{2,8\}.$$
5) Prefixsummen der Koeffizienten.
Mit \(a_k=f(k)=3^k-2^k-1\) und
$$A(m)=\sum_{k=1}^{m}a_k$$
erhaelt man
$$A(m)=\frac{3^{m+1}-3}{2}-(2^{m+1}-2)-m.$$
Damit kann ein ganzer Block \([l,r]\) in \(O(1)\) summiert werden.
6) Harmonische Blockbildung und schnelle Mertens-Werte.
Der Quotient \(\lfloor n/k\rfloor\) ist auf Intervallen konstant. Dadurch reduziert sich die aeussere Summe auf etwa \(2\sqrt n\) Bloecke. Fuer grosse \(x\) wird
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right)$$
mit Quotienten-Gruppierung und Memoisierung benutzt.
1) Sieve fuer \(\mu\) und \(M\) bis etwa \(n^{2/3}\).
2) Rekursive, memoisierte Mertens-Funktion fuer grosse Argumente.
3) Aeussere Summe nach konstantem \(\lfloor n/k\rfloor\) blocken.
4) Blockgewicht mit \(A(r)-A(l-1)\) berechnen.
Vorberechnung bis etwa \(n^{2/3}\), danach nur \(O(\sqrt n)\) Blöcke plus memoiserte Mertens-Abfragen. Praktisch weit schneller als eine lineare Summe.
Der Code prueft
$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891.$$
Fuer \(n=10^{10}\) modulo \(10^9\) ist das Ergebnis
$$268457129.$$
Aranan \(x_1,\dots,x_n\) dizileri
$$x_1=2,$$
$$x_{i-1}\lt x_i,$$
ve her \(i,j\) icin
$$(x_i)^j \lt (x_j+1)^i$$
sartlarini sagliyor. \(t(n)\) bu dizilerin sayisi. Hedef,
$$t(10^{10})\bmod 10^9$$
degerini bulmak.
1) Dizi kosulu aslinda tek bir gercek sayinin kuvvet tabanina iner.
Verilen esitssizlik su anlama gelir:
$$x_i^{1/i}\lt(x_j+1)^{1/j}\qquad\text{tum }i,j\text{ icin}.$$
Yani
$$I_i=\bigl(x_i^{1/i},(x_i+1)^{1/i}\bigr)$$
araliklari ortak bir noktaya sahiptir. Bu ortak noktaya \(y\) dersek
$$x_i \lt y^i \lt x_i+1$$
ve dolayisiyla
$$x_i=\lfloor y^i\rfloor$$
olur. Tersine, \(y\in[2,3)\) icin \(\lfloor y^i\rfloor\) dizisi bu kosullari saglar. Demek ki problem, \([2,3)\) araligindaki \(y\) degerlerinin ayirdigi farkli floor-kuvvet oruntulerini saymaktan ibarettir.
2) Sinir noktalar nerede?
Dizi ancak bir \(y^k\) degeri tam sayi esigini gectiginde degisir. Bu nedenle sinir noktalar
$$y=m^{1/k},\qquad 1\le k\le n,\qquad 2^k \lt m \lt 3^k$$
seklindedir. O halde
$$t(n)=1+\text{(} [2,3)\text{ icindeki farkli sinir noktasi sayisi)}.$$
3) Ayni kokun birden cok kez sayilmasi Möbius inversiyonunu dogurur.
Su fonksiyonlari tanimlayalim:
$$f(k)=3^k-2^k-1,$$
yani \(2^k\) ile \(3^k\) arasindaki tam sayi sayisi,
ve
$$g(k)=\text{minimal ussu tam olarak }k\text{ olan sinir noktasi sayisi}.$$
Her \(m^{1/k}\) sinir noktasi, minimal ussu \(k\)'yi bolecek bir primitive koktan gelir. Bu yuzden
$$f(k)=\sum_{d\mid k} g(d).$$
Möbius inversiyonu ile
$$g(k)=\sum_{d\mid k}\mu(d)\,f(k/d)$$
elde edilir. Buradan
$$t(n)=1+\sum_{k=1}^{n}g(k)=1+\sum_{k=1}^{n}f(k)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$$
sonucuna variriz. Burada \(M(x)=\sum_{m\le x}\mu(m)\) Mertens fonksiyonudur.
4) Neden \(t(2)=5\)?
\(n=2\) icin yeni sinirler sadece
$$\sqrt5,\ \sqrt6,\ \sqrt7,\ \sqrt8$$
noktalaridir. Bunlar \([2,3)\) araligini bes parcaya boler ve bes farkli dizi uretir:
$$\{2,4\},\{2,5\},\{2,6\},\{2,7\},\{2,8\}.$$
5) Katsayi prefix toplamlari.
Kod
$$a_k=f(k)=3^k-2^k-1$$
katsayilarini kullanir. Prefix toplam
$$A(m)=\sum_{k=1}^{m}a_k$$
icin kapali form
$$A(m)=\frac{3^{m+1}-3}{2}-(2^{m+1}-2)-m$$
olur. Dolayisiyla herhangi bir \([l,r]\) araligindaki toplam
$$A(r)-A(l-1)$$
ile bulunur. Mod \(10^9\) altinda \(1/2\) terslenemedigi icin kod once \(3^{m+1}\)'i \(2\cdot10^9\) modunda hesaplayip daha sonra ikiye boler.
6) Harmonik bloklama.
Dis toplamda
$$q=\left\lfloor\frac{n}{k}\right\rfloor$$
degeri uzun araliklarda sabittir. Bu yuzden
$$\sum_{k=1}^{n} a_k\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$$
ifadesi, ayni \(q\)'yu paylasan bloklara ayrilir:
$$\sum_{\text{blok }[l,r]} \bigl(A(r)-A(l-1)\bigr)\,M(q).$$
Böylece terim sayisi \(n\)'den yaklasik \(2\sqrt n\)'ye duser.
7) Mertens fonksiyonunun hizli hesabi.
Kucuk degerler lineer elek ile onceden bulunur. Buyuk \(x\) icin ise
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right)$$
bagintisi, ayni bolum degerlerini gruplayarak ve memoization kullanilarak hesaplanir.
1) \(t(n)\)'i Möbius-Mertens formuna cevir.
2) Yaklasik \(n^{2/3}\) seviyesine kadar \(\mu\) ve \(M\) degerlerini elekle onhesapla.
3) Buyuk \(M(x)\) degerlerini recursive + memoized olarak bul.
4) Dis toplami \(\lfloor n/k\rfloor\) sabit bloklara ayir.
5) Her blok katkisini \(A(r)-A(l-1)\) ile hesapla.
Onhesap yaklasik \(n^{2/3}\) olcegindedir. Dis toplam sadece
$$O(\sqrt n)$$
blok icerir. Memoization sayesinde toplam maliyet, \(10^{10}\) terimi tek tek toplamaktan cok daha dusuktur.
Kaynak kod su degerleri dogrular:
$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891.$$
Son olarak
$$t(10^{10})\bmod 10^9=268457129$$
elde edilir.
Contamos sucesiones \(x_1,\dots,x_n\) con \(x_1=2\), estrictamente crecientes y tales que
$$(x_i)^j \lt (x_j+1)^i$$
para todo \(i,j\). Hay que hallar \(t(10^{10})\bmod 10^9\).
1) Toda sucesion valida es de la forma \(\lfloor y^i\rfloor\).
La desigualdad equivale a
$$x_i^{1/i}\lt(x_j+1)^{1/j}.$$
Por tanto, los intervalos
$$I_i=\bigl(x_i^{1/i},(x_i+1)^{1/i}\bigr)$$
tienen interseccion comun, y existe un \(y\in[2,3)\) tal que
$$x_i=\lfloor y^i\rfloor.$$
Reciprocamente, cualquier \(y\in[2,3)\) produce una sucesion valida.
2) Entonces \(t(n)\) cuenta puntos frontera en \([2,3)\).
La sucesion cambia solo cuando \(y^k\) cruza un entero. Los puntos frontera son
$$y=m^{1/k},\qquad 2^k\lt m\lt 3^k,\qquad 1\le k\le n.$$
3) Hay que eliminar duplicados entre potencias perfectas.
Definimos
$$f(k)=3^k-2^k-1,$$
y
$$g(k)=\text{numero de fronteras cuyo exponente minimo es }k.$$
Entonces
$$f(k)=\sum_{d\mid k}g(d).$$
Por inversion de Möbius:
$$g(k)=\sum_{d\mid k}\mu(d)\,f(k/d).$$
De aqui sigue
$$t(n)=1+\sum_{k=1}^{n}f(k)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right),$$
donde \(M\) es la funcion de Mertens.
4) Ejemplo \(t(2)=5\).
Las unicas fronteras son \(\sqrt5,\sqrt6,\sqrt7,\sqrt8\), que dividen \([2,3)\) en cinco intervalos y producen exactamente las cinco sucesiones del enunciado.
5) Sumas prefijo.
Con \(a_k=f(k)=3^k-2^k-1\),
$$A(m)=\sum_{k=1}^{m}a_k=\frac{3^{m+1}-3}{2}-(2^{m+1}-2)-m.$$
Asi, un bloque \([l,r]\) aporta \(A(r)-A(l-1)\).
6) Bloques armonicos y Mertens rapido.
Como \(\lfloor n/k\rfloor\) es constante en bloques, la suma exterior se reduce a unas \(2\sqrt n\) piezas. Los valores grandes de \(M(x)\) se calculan por recursion memoizada con agrupacion por cocientes iguales.
1) Reescribir \(t(n)\) con Möbius/Mertens.
2) Precalcular \(\mu\) y \(M\) hasta aprox. \(n^{2/3}\).
3) Calcular \(M(x)\) grande con recursion memoizada.
4) Agrupar la suma por bloques de \(\lfloor n/k\rfloor\) constante.
Tras el precalculo, la suma exterior tiene \(O(\sqrt n)\) bloques. En la practica es muy superior a una suma lineal hasta \(10^{10}\).
El codigo valida
$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891.$$
Finalmente,
$$t(10^{10})\bmod 10^9=268457129.$$
我们要统计满足
$$x_1=2,\qquad x_{i-1}\lt x_i,\qquad (x_i)^j\lt(x_j+1)^i$$
的长度为 \(n\) 的序列个数 \(t(n)\)，最后求
$$t(10^{10})\bmod 10^9.$$
1）序列条件等价于 \(x_i=\lfloor y^i\rfloor\)。
原不等式可改写为
$$x_i^{1/i}\lt(x_j+1)^{1/j}.$$
于是区间
$$I_i=\bigl(x_i^{1/i},(x_i+1)^{1/i}\bigr)$$
有公共交点，因此存在 \(y\in[2,3)\) 使得
$$x_i=\lfloor y^i\rfloor.$$
反过来，任意 \(y\in[2,3)\) 也都会给出一个合法序列。
2）因此 \(t(n)\) 就是在数边界点。
序列只会在某个 \(y^k\) 穿过整数时发生变化，所以边界点正是
$$y=m^{1/k},\qquad 2^k\lt m\lt 3^k,\qquad 1\le k\le n.$$
3）去重会导出 Möbius 反演。
定义
$$f(k)=3^k-2^k-1,$$
即 \(2^k\) 与 \(3^k\) 之间的整数个数；再定义
$$g(k)=\text{最小指数恰为 }k\text{ 的边界点个数}.$$
则有
$$f(k)=\sum_{d\mid k}g(d).$$
由 Möbius 反演，
$$g(k)=\sum_{d\mid k}\mu(d)\,f(k/d).$$
因此
$$t(n)=1+\sum_{k=1}^{n}f(k)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right),$$
其中 \(M\) 是 Mertens 函数。
4）为什么 \(t(2)=5\)。
边界点只有 \(\sqrt5,\sqrt6,\sqrt7,\sqrt8\)，它们把 \([2,3)\) 分成五段，所以得到题目里列出的五个长度为 2 的序列。
5）系数前缀和。
若 \(a_k=f(k)=3^k-2^k-1\)，那么
$$A(m)=\sum_{k=1}^{m}a_k=\frac{3^{m+1}-3}{2}-(2^{m+1}-2)-m.$$
因此任意区间 \([l,r]\) 的贡献都可写成 \(A(r)-A(l-1)\)。
6）调和分块与快速 Mertens。
因为 \(\lfloor n/k\rfloor\) 在大段区间上保持不变，外层求和只剩约 \(2\sqrt n\) 个块。大参数的 \(M(x)\) 用递推加记忆化求值。
1) 先把 \(t(n)\) 化为 Möbius-Mertens 加权和。
2) 线性筛预处理 \(\mu\) 与小范围 \(M\)。
3) 对大 \(M(x)\) 使用递归 + 记忆化。
4) 对外层求和做 \(\lfloor n/k\rfloor\) 分块。
预处理规模约为 \(n^{2/3}\)，外层只有 \(O(\sqrt n)\) 个块，因此远快于从 \(1\) 加到 \(10^{10}\) 的直接计算。
程序验证了
$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891.$$
最终得到
$$t(10^{10})\bmod 10^9=268457129.$$
Нужно посчитать число последовательностей \(x_1,\dots,x_n\) с \(x_1=2\), строгим возрастанием и условием
$$(x_i)^j\lt(x_j+1)^i,$$
а затем найти \(t(10^{10})\bmod 10^9\).
1) Эквивалентность формуле \(x_i=\lfloor y^i\rfloor\).
Условие равносильно
$$x_i^{1/i}\lt(x_j+1)^{1/j}.$$
Значит, интервалы
$$I_i=\bigl(x_i^{1/i},(x_i+1)^{1/i}\bigr)$$
имеют общую точку. Следовательно, существует \(y\in[2,3)\), для которого
$$x_i=\lfloor y^i\rfloor.$$
И наоборот, любое такое \(y\) задает допустимую последовательность.
2) Значит, \(t(n)\) считает точки разбиения по \(y\).
Последовательность меняется только тогда, когда некоторое \(y^k\) проходит через целое число. Поэтому границы имеют вид
$$y=m^{1/k},\qquad 2^k\lt m\lt 3^k.$$
3) Устранение повторов и инверсия Мёбиуса.
Положим
$$f(k)=3^k-2^k-1,$$
а
$$g(k)=\text{число границ с минимальным показателем }k.$$
Тогда
$$f(k)=\sum_{d\mid k}g(d),$$
и по инверсии Мёбиуса
$$g(k)=\sum_{d\mid k}\mu(d)\,f(k/d).$$
Отсюда
$$t(n)=1+\sum_{k=1}^{n}f(k)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right),$$
где \(M\) - функция Мертенса.
4) Пример \(t(2)=5\).
Границы: \(\sqrt5,\sqrt6,\sqrt7,\sqrt8\). Они делят \([2,3)\) на пять интервалов, что и дает пять последовательностей из условия.
5) Префиксные суммы коэффициентов.
Для \(a_k=f(k)\) имеем
$$A(m)=\sum_{k=1}^{m}a_k=\frac{3^{m+1}-3}{2}-(2^{m+1}-2)-m.$$
Это позволяет считать вклад блока \([l,r]\) как \(A(r)-A(l-1)\).
6) Гармоническая блокировка и быстрый Mertens.
Частное \(\lfloor n/k\rfloor\) постоянно на длинных интервалах, поэтому внешняя сумма разбивается всего на \(O(\sqrt n)\) блоков. Большие значения \(M(x)\) вычисляются рекурсивно с мемоизацией.
1) Переписать \(t(n)\) через Möbius/Mertens.
2) Предвычислить \(\mu\) и малые \(M\) линейным ситом.
3) Для больших \(M(x)\) использовать рекурсию и кеш.
4) Внешнюю сумму сгруппировать по одинаковому \(\lfloor n/k\rfloor\).
После предвычисления примерно до \(n^{2/3}\) остается лишь \(O(\sqrt n)\) блоков. На практике это намного быстрее лобового прохода до \(10^{10}\).
Код проверяет
$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891.$$
Итог:
$$t(10^{10})\bmod 10^9=268457129.$$
نعدّ المتتاليات \(x_1,\dots,x_n\) التي تحقق \(x_1=2\)، وتزايدًا صارمًا، وكذلك
$$(x_i)^j\lt(x_j+1)^i.$$
ثم نريد حساب
$$t(10^{10})\bmod 10^9.$$
1) الشرط كله يكافئ الصيغة \(x_i=\lfloor y^i\rfloor\).
الشرط يعادل
$$x_i^{1/i}\lt(x_j+1)^{1/j}.$$
إذن الفترات
$$I_i=\bigl(x_i^{1/i},(x_i+1)^{1/i}\bigr)$$
لها تقاطع مشترك، وبالتالي يوجد \(y\in[2,3)\) بحيث
$$x_i=\lfloor y^i\rfloor.$$
وبالعكس، كل \(y\in[2,3)\) يولد متتالية صالحة.
2) إذن \(t(n)\) هو في الحقيقة عدّ لنقاط الحدود.
تتغير المتتالية فقط عندما يمر \(y^k\) عبر عدد صحيح. لذلك تكون نقاط الحد من الشكل
$$y=m^{1/k},\qquad 2^k\lt m\lt 3^k.$$
3) إزالة التكرار تؤدي إلى انقلاب Möbius.
لنعرّف
$$f(k)=3^k-2^k-1,$$
و
$$g(k)=\text{عدد نقاط الحد التي أصغر أس لها هو }k.$$
عندئذ
$$f(k)=\sum_{d\mid k}g(d),$$
ومن ثم
$$g(k)=\sum_{d\mid k}\mu(d)\,f(k/d).$$
وبالتالي
$$t(n)=1+\sum_{k=1}^{n}f(k)\,M\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right),$$
حيث \(M\) هي دالة Mertens.
4) لماذا \(t(2)=5\)؟
نقاط الحد الوحيدة هي \(\sqrt5,\sqrt6,\sqrt7,\sqrt8\)، وهي تقسّم \([2,3)\) إلى خمس فترات، ومن ثم خمس متتاليات كما في نص المسألة.
5) مجاميع البوادئ للمعاملات.
إذا كان \(a_k=f(k)\)، فإن
$$A(m)=\sum_{k=1}^{m}a_k=\frac{3^{m+1}-3}{2}-(2^{m+1}-2)-m.$$
وهذا يسمح بحساب مساهمة أي كتلة \([l,r]\) على صورة \(A(r)-A(l-1)\).
6) التجميع التوافقي وحساب Mertens بسرعة.
بما أن \(\lfloor n/k\rfloor\) ثابت على فترات طويلة، فإن المجموع الخارجي ينخفض إلى نحو \(O(\sqrt n)\) كتل فقط. أما القيم الكبيرة لـ \(M(x)\) فتحسب تكراريًا مع التخزين.
1) إعادة كتابة \(t(n)\) بصيغة Möbius-Mertens.
2) غربلة خطية مسبقة لحساب \(\mu\) و\(M\) للقيم الصغيرة.
3) حساب \(M(x)\) الكبير بالتكرار مع التخزين.
4) جمع الحدود على كتل ثابتة القسمة \(\lfloor n/k\rfloor\).
بعد التحضير حتى نحو \(n^{2/3}\)، يبقى فقط \(O(\sqrt n)\) كتل. هذا أسرع عمليًا بكثير من جمع \(10^{10}\) حدًا مباشرة.
يتحقق البرنامج من
$$t(2)=5,\qquad t(5)=293,\qquad t(10)=86195,\qquad t(20)=5227991891.$$
والنتيجة النهائية هي
$$t(10^{10})\bmod 10^9=268457129.$$