Let \(\tau(n)\) denote the number of positive divisors of \(n\). For fixed integers \(u\) and \(k\), define
$$M_n=\max_{n \le j \le n+k-1}\tau(j),\qquad S(u,k)=\sum_{n=1}^{u-k+1} M_n.$$
So each length-\(k\) interval contributes the largest divisor count appearing inside that interval, and the task is to add those maxima over all consecutive intervals from \(1\) up to \(u\). A naive method would recompute each maximum independently and would be far too slow for the full input size, so the solution splits the problem into two linear passes.
If
$$n=\prod_{r=1}^{t} p_r^{a_r},$$
then every divisor of \(n\) is obtained by choosing an exponent \(b_r\) with \(0 \le b_r \le a_r\) for each prime \(p_r\). Hence
$$\tau(n)=\prod_{r=1}^{t}(a_r+1).$$
This multiplicative formula is the starting point for the sieve. Instead of factoring each integer from scratch, the implementation builds all values \(\tau(1),\tau(2),\dots,\tau(u)\) incrementally.
Suppose \(n=p^a m\) with \(p \nmid m\). Then
$$\tau(n)=(a+1)\tau(m).$$
Multiplying by a prime gives two cases.
$$\tau(np)= \begin{cases} 2\tau(n), & p \nmid n,\\ \tau(n)\dfrac{a+2}{a+1}, & n=p^a m,\ p \nmid m. \end{cases}$$
The first case adds a new prime factor of exponent \(1\); the second increases the exponent of an existing prime factor from \(a\) to \(a+1\). The implementations maintain, for each integer, its smallest prime factor and the exponent of that smallest prime factor. That information is exactly what is needed to apply the recurrence in constant time when the next composite number is generated.
The sieve is linear because every composite number is produced once, in its canonical decomposition as a previous integer multiplied by a prime chosen under the smallest-prime-factor rule. As a result, the full divisor-count table up to \(u\) is built in \(O(u)\) time.
Once the table \(\tau(1),\dots,\tau(u)\) is available, the problem becomes a standard fixed-window maximum problem. While scanning integers from left to right, it is convenient to index windows by their right endpoint:
$$W_i=[\,i-k+1,\ i\,],\qquad i=k,k+1,\dots,u.$$
The contribution of window \(W_i\) is
$$\max_{j \in W_i}\tau(j).$$
This is the same set of windows as in the original definition, only written by ending position instead of starting position.
The key data structure is a deque of candidate indices. It satisfies two invariants at all times:
1. indices in the deque are increasing from front to back;
2. divisor counts are strictly decreasing from front to back.
When a new index \(i\) arrives, all trailing indices \(q\) with \(\tau(q)\le \tau(i)\) are removed before \(i\) is appended. Then any front index \(q \le i-k\) is removed because it has left the current window.
After these two clean-up steps, the front of the deque is the index of the maximum divisor count in the current window, so its \(\tau\)-value is added to the answer.
Assume \(q<i\) and \(\tau(q)\le \tau(i)\). From the moment \(i\) is inserted onward, any future window that still contains \(q\) also contains \(i\), because \(i\) is newer and therefore expires no earlier than \(q\). Since \(i\) has divisor count at least as large, \(q\) can never again be the unique best candidate for a maximum. So deleting \(q\) is always safe.
This domination argument is the whole reason the deque stays short and efficient: each index is inserted once, deleted at most once from the back, and deleted at most once from the front.
For \(u=10\) and \(k=3\), the divisor counts are
$$\tau(1),\tau(2),\dots,\tau(10)=1,2,2,3,2,4,2,4,3,4.$$
The window maxima are therefore
$$2,3,3,4,4,4,4,4,$$
so
$$S(10,3)=2+3+3+4+4+4+4+4=28.$$
The same mechanism scales to the full input because the expensive part is no longer the window search; it is just a single amortized-constant-time deque update per index.
The C++, Python, and Java implementations all follow the same two-stage pipeline. First they build the divisor-count table up to \(u\) using the linear sieve recurrence above. Second they scan that table once with a monotone deque and accumulate the maximum value of each length-\(k\) window.
The optimized method is validated on a published checkpoint,
$$S(1000,10)=17176,$$
and one implementation also compares a smaller test case against a brute-force window scan to confirm that the optimized and naive methods agree.
The divisor-count sieve runs in \(O(u)\) time. The deque scan is also \(O(u)\) because each index enters the deque once and leaves it at most once. Therefore the overall running time is
$$O(u).$$
The memory usage is \(O(u)\) for the divisor-count and sieve tables, plus \(O(k)\) for the deque. The asymptotic memory bound is therefore
$$O(u).$$
Sei \(\tau(n)\) die Anzahl der positiven Teiler von \(n\). Für feste ganze Zahlen \(u\) und \(k\) definieren wir
$$M_n=\max_{n \le j \le n+k-1}\tau(j),\qquad S(u,k)=\sum_{n=1}^{u-k+1} M_n.$$
Jedes Fenster der Länge \(k\) liefert also genau die größte Teileranzahl innerhalb dieses Fensters, und alle diese Maxima werden addiert. Eine direkte Berechnung jedes Fensters wäre viel zu langsam, deshalb zerfällt die Lösung in zwei lineare Schritte: erst alle \(\tau\)-Werte bis \(u\) erzeugen, dann die Fenstermaxima effizient aufsummieren.
Hat \(n\) die Primfaktorzerlegung
$$n=\prod_{r=1}^{t} p_r^{a_r},$$
dann entsteht jeder Teiler durch die Wahl von Exponenten \(b_r\) mit \(0 \le b_r \le a_r\). Daher gilt
$$\tau(n)=\prod_{r=1}^{t}(a_r+1).$$
Diese multiplikative Struktur wird im Sieb ausgenutzt. Man faktorisiert also nicht jede Zahl separat, sondern baut die gesamte Tabelle \(\tau(1),\tau(2),\dots,\tau(u)\) sukzessive auf.
Schreibe \(n=p^a m\) mit \(p \nmid m\). Dann ist
$$\tau(n)=(a+1)\tau(m).$$
Beim Multiplizieren mit einer Primzahl entstehen genau zwei Fälle:
$$\tau(np)= \begin{cases} 2\tau(n), & p \nmid n,\\ \tau(n)\dfrac{a+2}{a+1}, & n=p^a m,\ p \nmid m. \end{cases}$$
Im ersten Fall kommt ein neuer Primfaktor mit Exponent \(1\) hinzu, im zweiten Fall wird nur der vorhandene Exponent von \(a\) auf \(a+1\) erhöht. Die Implementierungen speichern deshalb zu jeder Zahl den kleinsten Primfaktor und den Exponenten dieses Primfaktors. Damit lässt sich der neue \(\tau\)-Wert sofort in \(O(1)\) berechnen.
Das Sieb ist linear, weil jede zusammengesetzte Zahl genau einmal erzeugt wird. Dadurch kostet die Konstruktion der gesamten Teileranzahl-Tabelle bis \(u\) nur \(O(u)\) Zeit.
Ist die Tabelle \(\tau(1),\dots,\tau(u)\) bekannt, bleibt nur noch ein Standardproblem für feste Fensterlänge. Während man von links nach rechts läuft, beschreibt man das aktuelle Fenster bequem über seinen rechten Rand:
$$W_i=[\,i-k+1,\ i\,],\qquad i=k,k+1,\dots,u.$$
Der jeweilige Beitrag ist
$$\max_{j \in W_i}\tau(j).$$
Das sind genau dieselben Fenster wie in der ursprünglichen Definition von \(S(u,k)\), nur anders indiziert.
Die Lösung hält eine Deque mit Kandidatenindizes. Dabei gelten stets zwei Invarianten:
1. Die Indizes steigen von vorne nach hinten streng an.
2. Die zugehörigen \(\tau\)-Werte fallen von vorne nach hinten streng ab.
Kommt ein neuer Index \(i\), so werden zunächst alle hinteren Indizes \(q\) mit \(\tau(q)\le \tau(i)\) entfernt. Danach wird \(i\) angehängt. Anschließend werden vorne alle Indizes \(q \le i-k\) entfernt, weil sie nicht mehr im aktuellen Fenster liegen.
Danach steht am Kopf der Deque immer der Index mit der größten Teileranzahl im aktuellen Fenster.
Seien \(q<i\) und \(\tau(q)\le \tau(i)\). Ab dem Zeitpunkt, an dem \(i\) eingefügt wird, enthält jedes zukünftige Fenster, das \(q\) noch enthält, auch \(i\). Außerdem ist \(i\) mindestens so gut wie \(q\), weil sein \(\tau\)-Wert nicht kleiner ist und sein Index später aus dem Fenster fällt. Also kann \(q\) nie wieder das beste Maximum liefern und darf endgültig entfernt werden.
Genau deshalb ist die Gesamtkostenanalyse linear: Jeder Index wird höchstens einmal hinten entfernt und höchstens einmal vorne entfernt.
Für \(u=10\) und \(k=3\) sind die Teileranzahlen
$$\tau(1),\tau(2),\dots,\tau(10)=1,2,2,3,2,4,2,4,3,4.$$
Die Fenstermaxima lauten
$$2,3,3,4,4,4,4,4,$$
also
$$S(10,3)=2+3+3+4+4+4+4+4=28.$$
Dasselbe Prinzip funktioniert für große Eingaben unverändert, weil pro Zahl nur eine konstante Zahl von Deque-Operationen anfällt.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Zweiphasen-Strategie. Zuerst wird die Tabelle der Teileranzahlen bis \(u\) mit dem linearen Sieb aufgebaut. Danach wird diese Tabelle genau einmal mit einer monotonen Deque durchlaufen, und das jeweilige Fenstermmaximum wird zur Summe addiert.
Als Kontrollwert wird
$$S(1000,10)=17176$$
verifiziert. Zusätzlich vergleicht eine Implementierung einen kleineren Testfall mit einer direkten Brute-Force-Berechnung, um die Optimierung abzusichern.
Das lineare Sieb benötigt \(O(u)\) Zeit. Der Deque-Durchlauf ist ebenfalls \(O(u)\), weil jeder Index nur einmal eingefügt und höchstens einmal entfernt wird. Insgesamt ergibt sich also
$$O(u)$$
Zeit. Für die Teileranzahl-Tabelle und die Hilfsinformationen des Siebs werden \(O(u)\) Speicherplätze benötigt; die Deque selbst braucht höchstens \(O(k)\). Asymptotisch dominiert damit
$$O(u).$$
\(\tau(n)\), \(n\) sayısının pozitif bölen sayısı olsun. Sabit \(u\) ve \(k\) için
$$M_n=\max_{n \le j \le n+k-1}\tau(j),\qquad S(u,k)=\sum_{n=1}^{u-k+1} M_n$$
tanımlanır. Yani uzunluğu \(k\) olan her ardışık aralık için içindeki en büyük bölen sayısını alır, sonra bu maksimumları toplarız. Her pencereyi bağımsız olarak taramak büyük girdi için çok yavaştır; bu yüzden çözüm iki doğrusal adıma ayrılır.
Eğer
$$n=\prod_{r=1}^{t} p_r^{a_r}$$
ise, \(n\)'nin her böleni her asal için \(0 \le b_r \le a_r\) olacak şekilde bir üs seçilerek elde edilir. Dolayısıyla
$$\tau(n)=\prod_{r=1}^{t}(a_r+1).$$
Lineer elekte kullanılan temel fikir budur. Her sayıyı ayrı ayrı çarpanlara ayırmak yerine \(\tau(1),\tau(2),\dots,\tau(u)\) tablosu artımlı biçimde üretilir.
\(n=p^a m\) ve \(p \nmid m\) olsun. O zaman
$$\tau(n)=(a+1)\tau(m).$$
Bir asal ile çarpınca iki durum vardır:
$$\tau(np)= \begin{cases} 2\tau(n), & p \nmid n,\\ \tau(n)\dfrac{a+2}{a+1}, & n=p^a m,\ p \nmid m. \end{cases}$$
İlk durumda yeni bir asal çarpan eklenir ve üs \(1\) olur. İkinci durumda var olan aynı asalın üssü \(a\)'dan \(a+1\)'e çıkar. Bu nedenle uygulama her sayı için en küçük asal çarpanı ve bu asalın üstünü tutar; böylece yeni \(\tau\) değeri sabit zamanda güncellenir.
Her bileşik sayı tam bir kez üretildiği için bu yöntem gerçekten lineerdir ve tüm bölen sayısı tablosu \(O(u)\) zamanda elde edilir.
\(\tau(1),\dots,\tau(u)\) hazır olduktan sonra geriye sabit uzunluklu pencere maksimumu problemi kalır. Sağ uçtan indekslemek uygundur:
$$W_i=[\,i-k+1,\ i\,],\qquad i=k,k+1,\dots,u.$$
Her pencerenin katkısı
$$\max_{j \in W_i}\tau(j)$$
olur. Bu, başlangıç indeksine göre yazılmış özgün tanımla tamamen aynı pencerelerdir.
Çözüm aday indeksleri bir deque içinde tutar. Her an iki değişmez sağlanır:
1. İndeksler önden arkaya artar.
2. Karşılık gelen \(\tau\) değerleri önden arkaya sıkı biçimde azalır.
Yeni \(i\) geldiğinde, önce arkadaki ve \(\tau(q)\le \tau(i)\) koşulunu sağlayan tüm indeksler silinir. Sonra \(i\) eklenir. Ardından \(q \le i-k\) olan ön elemanlar çıkarılır; çünkü artık pencerenin dışındadırlar.
Bu işlemlerden sonra deque'nin başı mevcut pencerenin maksimumunu verir.
\(q<i\) ve \(\tau(q)\le \tau(i)\) olsun. \(i\) eklendikten sonra \(q\)'yu içeren her gelecek pencere, daha yeni olduğu için \(i\)'yi de içerir. Ayrıca \(i\)'nin bölen sayısı daha küçük değildir ve pencereden daha geç çıkar. Bu yüzden \(q\), gelecekte hiçbir pencerede en iyi aday olamaz. Kalıcı olarak silinmesi güvenlidir.
Bu baskılama argümanı, her indeksin en fazla bir kez arkadan ve en fazla bir kez önden silinmesini garanti eder; dolayısıyla toplam deque maliyeti doğrusaldır.
\(u=10\) ve \(k=3\) için bölen sayıları
$$\tau(1),\tau(2),\dots,\tau(10)=1,2,2,3,2,4,2,4,3,4.$$
Pencere maksimumları ise
$$2,3,3,4,4,4,4,4$$
olur. Dolayısıyla
$$S(10,3)=2+3+3+4+4+4+4+4=28.$$
Büyük girdi için de aynı yöntem çalışır; çünkü her adımda yalnızca amortize sabit sayıda deque işlemi yapılır.
C++, Python ve Java uygulamalarının hepsi aynı iki aşamalı yapıyı kullanır. Önce lineer elek ile \(1\)'den \(u\)'ya kadar tüm bölen sayıları hesaplanır. Sonra bu tablo üzerinde tek geçişlik bir monotonik deque taraması yapılır ve her uzunluk-\(k\) pencerenin maksimumu toplama eklenir.
Doğrulama için
$$S(1000,10)=17176$$
kontrol edilir. Ayrıca bir uygulama, daha küçük bir örnekte sonucu kaba kuvvet yaklaşımıyla karşılaştırarak optimize yöntemi sınar.
Lineer elek \(O(u)\) zamanda çalışır. Deque taraması da \(O(u)\)'dur; çünkü her indeks yalnızca bir kez eklenir ve en fazla bir kez silinir. Toplam çalışma süresi
$$O(u)$$
olur. Bellek kullanımı bölen sayısı ve elek tabloları için \(O(u)\), deque için en fazla \(O(k)\)'dir. Asimptotik olarak baskın terim
$$O(u)$$
bellektir.
Sea \(\tau(n)\) el número de divisores positivos de \(n\). Para enteros fijos \(u\) y \(k\), definimos
$$M_n=\max_{n \le j \le n+k-1}\tau(j),\qquad S(u,k)=\sum_{n=1}^{u-k+1} M_n.$$
Cada bloque consecutivo de longitud \(k\) aporta el mayor valor de \(\tau\) que aparece dentro de ese bloque, y el problema pide sumar todos esos máximos. Recalcular el máximo en cada ventana de forma independiente sería demasiado costoso, así que la solución se divide en dos pasadas lineales.
Si
$$n=\prod_{r=1}^{t} p_r^{a_r},$$
entonces cualquier divisor de \(n\) se obtiene eligiendo para cada primo un exponente \(b_r\) con \(0 \le b_r \le a_r\). Por lo tanto,
$$\tau(n)=\prod_{r=1}^{t}(a_r+1).$$
Esta identidad multiplicativa permite construir la tabla completa \(\tau(1),\tau(2),\dots,\tau(u)\) sin factorizar cada entero desde cero.
Escribamos \(n=p^a m\) con \(p \nmid m\). Entonces
$$\tau(n)=(a+1)\tau(m).$$
Al multiplicar por un primo aparecen exactamente dos casos:
$$\tau(np)= \begin{cases} 2\tau(n), & p \nmid n,\\ \tau(n)\dfrac{a+2}{a+1}, & n=p^a m,\ p \nmid m. \end{cases}$$
En el primer caso aparece un nuevo factor primo con exponente \(1\). En el segundo, solo aumenta en uno el exponente del primo ya presente. Las implementaciones guardan el menor factor primo y el exponente correspondiente para cada entero, de modo que la actualización de \(\tau\) sea inmediata.
La criba es lineal porque cada compuesto se genera una sola vez. Así, toda la tabla de números de divisores hasta \(u\) se obtiene en \(O(u)\).
Una vez conocida la tabla \(\tau(1),\dots,\tau(u)\), el resto del trabajo consiste en máximos sobre ventanas de longitud fija. Es cómodo describir cada ventana por su extremo derecho:
$$W_i=[\,i-k+1,\ i\,],\qquad i=k,k+1,\dots,u.$$
La contribución de esa ventana es
$$\max_{j \in W_i}\tau(j).$$
Esto representa exactamente las mismas ventanas que la definición original de \(S(u,k)\).
Se mantiene una deque de índices candidatos con dos propiedades permanentes:
1. los índices aumentan de izquierda a derecha;
2. los valores de \(\tau\) disminuyen estrictamente de izquierda a derecha.
Cuando llega un nuevo índice \(i\), se eliminan por detrás todos los índices \(q\) con \(\tau(q)\le \tau(i)\). Después se inserta \(i\). Por último, se eliminan por delante los índices \(q \le i-k\), porque ya salieron de la ventana actual.
Tras estas operaciones, el frente de la deque contiene el máximo de la ventana actual.
Supongamos que \(q<i\) y \(\tau(q)\le \tau(i)\). Desde que \(i\) entra en la deque, cualquier ventana futura que todavía contenga a \(q\) también contendrá a \(i\), ya que \(i\) es más reciente y expirará no antes que \(q\). Como además \(\tau(i)\) no es menor, \(q\) ya no puede volver a ser el mejor candidato. Por eso puede eliminarse para siempre.
Ese argumento garantiza que cada índice se inserta una sola vez y se elimina a lo sumo una vez por cada extremo de la deque, lo que mantiene el coste total lineal.
Para \(u=10\) y \(k=3\), los valores son
$$\tau(1),\tau(2),\dots,\tau(10)=1,2,2,3,2,4,2,4,3,4.$$
Los máximos de las ventanas son
$$2,3,3,4,4,4,4,4,$$
y por tanto
$$S(10,3)=2+3+3+4+4+4+4+4=28.$$
La misma idea funciona para el caso grande porque en cada paso solo se hace un número amortizado constante de operaciones sobre la deque.
Las implementaciones en C++, Python y Java siguen exactamente las mismas dos etapas. Primero calculan todos los valores \(\tau(1),\dots,\tau(u)\) mediante la criba lineal. Después recorren esa tabla una sola vez con una deque monótona y van acumulando el máximo de cada ventana de longitud \(k\).
El método optimizado se comprueba con el valor
$$S(1000,10)=17176,$$
y una de las implementaciones también contrasta un caso más pequeño con una exploración por fuerza bruta.
La criba de divisores requiere \(O(u)\) tiempo. El recorrido con deque también cuesta \(O(u)\), porque cada índice entra una vez y sale como mucho una vez. En consecuencia, el tiempo total es
$$O(u).$$
La memoria usada es \(O(u)\) para las tablas de la criba y \(O(k)\) para la deque, así que el término dominante vuelve a ser
$$O(u).$$
记 \(\tau(n)\) 为 \(n\) 的正约数个数。对固定整数 \(u\) 与 \(k\)，定义
$$M_n=\max_{n \le j \le n+k-1}\tau(j),\qquad S(u,k)=\sum_{n=1}^{u-k+1} M_n.$$
也就是说，对每个长度为 \(k\) 的连续区间，取其中最大的约数个数，再把所有这些最大值相加。若对每个区间都重新扫描一次，总代价会过高，因此实现把问题拆成两个线性阶段。
若
$$n=\prod_{r=1}^{t} p_r^{a_r},$$
那么 \(n\) 的任一约数都由每个质因子的指数选择 \(0 \le b_r \le a_r\) 决定，因此
$$\tau(n)=\prod_{r=1}^{t}(a_r+1).$$
这就是筛法的数学基础。与其对每个整数单独分解质因数，不如一次性构造 \(\tau(1),\tau(2),\dots,\tau(u)\) 的整张表。
设 \(n=p^a m\)，且 \(p \nmid m\)。则有
$$\tau(n)=(a+1)\tau(m).$$
当再乘上一个质数时，只有两种情况：
$$\tau(np)= \begin{cases} 2\tau(n), & p \nmid n,\\ \tau(n)\dfrac{a+2}{a+1}, & n=p^a m,\ p \nmid m. \end{cases}$$
第一种情况表示加入了一个新的质因子，其指数为 \(1\)。第二种情况表示原有同一质因子的指数从 \(a\) 增加到 \(a+1\)。实现会为每个整数保存其最小质因子以及该最小质因子的指数，于是新的 \(\tau\) 值可以在常数时间内更新。
由于每个合数只会按照唯一方式被生成一次，这个筛法的总时间是 \(O(u)\)。
在得到 \(\tau(1),\dots,\tau(u)\) 之后，剩下的问题就是固定长度窗口的最大值。用窗口右端点来编号最方便：
$$W_i=[\,i-k+1,\ i\,],\qquad i=k,k+1,\dots,u.$$
该窗口对答案的贡献是
$$\max_{j \in W_i}\tau(j).$$
这与原始定义中的所有窗口完全相同，只是换了一种索引方式。
算法维护一个候选下标的双端队列，并始终保持两条性质：
1. 下标从队首到队尾严格递增；
2. 对应的 \(\tau\) 值从队首到队尾严格递减。
处理新下标 \(i\) 时，先删除队尾所有满足 \(\tau(q)\le \tau(i)\) 的下标 \(q\)，再把 \(i\) 加入队尾。随后删除队首所有 \(q \le i-k\) 的下标，因为它们已经离开当前窗口。
完成这两步后，队首下标对应的就是当前窗口中的最大约数个数。
若 \(q<i\) 且 \(\tau(q)\le \tau(i)\)，那么从 \(i\) 入队开始，任何仍然包含 \(q\) 的未来窗口也一定包含 \(i\)，因为 \(i\) 更新、过期更晚。同时 \(i\) 的约数个数又不小于 \(q\)。因此 \(q\) 不可能再成为任何未来窗口中的最佳候选，可以永久删除。
这正是线性复杂度的原因：每个下标只会入队一次，至多从队尾弹出一次，再至多从队首弹出一次。
取 \(u=10\)、\(k=3\)。这时
$$\tau(1),\tau(2),\dots,\tau(10)=1,2,2,3,2,4,2,4,3,4.$$
各个窗口的最大值为
$$2,3,3,4,4,4,4,4,$$
因此
$$S(10,3)=2+3+3+4+4+4+4+4=28.$$
在大规模输入中，算法仍然有效，因为每个位置只触发常数次摊还 deque 操作。
C++、Python 和 Java 实现都遵循同样的两阶段结构。第一阶段用线性筛计算 \(1\) 到 \(u\) 的全部约数个数。第二阶段对这张表做一次单调队列扫描，把每个长度为 \(k\) 的窗口最大值累计到最终答案中。
实现会先验证检查点
$$S(1000,10)=17176,$$
其中一个实现还会把较小输入与朴素暴力扫描进行比较，以确认优化方法无误。
线性筛耗时 \(O(u)\)。单调队列扫描同样是 \(O(u)\)，因为每个下标最多进入和离开队列各一次。所以总时间复杂度为
$$O(u).$$
空间方面，筛表与约数个数表占用 \(O(u)\)，双端队列最多占用 \(O(k)\)，因此主导项仍然是
$$O(u).$$
Пусть \(\tau(n)\) обозначает число положительных делителей числа \(n\). Для фиксированных \(u\) и \(k\) вводятся величины
$$M_n=\max_{n \le j \le n+k-1}\tau(j),\qquad S(u,k)=\sum_{n=1}^{u-k+1} M_n.$$
То есть для каждого подряд идущего отрезка длины \(k\) нужно взять максимальное число делителей среди его элементов, а затем просуммировать такие максимумы по всем окнам. Если искать максимум в каждом окне отдельно, получится слишком медленно, поэтому решение состоит из двух линейных этапов.
Если
$$n=\prod_{r=1}^{t} p_r^{a_r},$$
то любой делитель числа \(n\) определяется выбором показателей \(b_r\), где \(0 \le b_r \le a_r\). Поэтому
$$\tau(n)=\prod_{r=1}^{t}(a_r+1).$$
Именно эта мультипликативная формула лежит в основе построения таблицы \(\tau(1),\tau(2),\dots,\tau(u)\) без отдельной факторизации каждого числа.
Пусть \(n=p^a m\) и \(p \nmid m\). Тогда
$$\tau(n)=(a+1)\tau(m).$$
После умножения на простое число возникают два случая:
$$\tau(np)= \begin{cases} 2\tau(n), & p \nmid n,\\ \tau(n)\dfrac{a+2}{a+1}, & n=p^a m,\ p \nmid m. \end{cases}$$
В первом случае появляется новый простой множитель степени \(1\). Во втором случае степень уже существующего простого множителя увеличивается с \(a\) до \(a+1\). Поэтому реализации хранят для каждого числа его наименьший простой делитель и степень этого делителя; этого достаточно, чтобы обновлять \(\tau\) за \(O(1)\).
Каждое составное число порождается ровно один раз, поэтому построение всей таблицы до \(u\) работает за \(O(u)\).
Когда значения \(\tau(1),\dots,\tau(u)\) уже известны, остаётся задача о максимуме на окне фиксированной длины. Удобно индексировать окно его правой границей:
$$W_i=[\,i-k+1,\ i\,],\qquad i=k,k+1,\dots,u.$$
Вклад такого окна равен
$$\max_{j \in W_i}\tau(j).$$
Это те же самые окна, что и в исходном определении \(S(u,k)\), только записанные по-другому.
Используется дека индексов-кандидатов. Для неё постоянно поддерживаются два инварианта:
1. индексы возрастают от головы к хвосту;
2. соответствующие значения \(\tau\) строго убывают.
При обработке нового индекса \(i\) из хвоста удаляются все индексы \(q\) с \(\tau(q)\le \tau(i)\), затем \(i\) добавляется в хвост. После этого из головы удаляются все \(q \le i-k\), потому что они уже вышли из текущего окна.
После двух очисток в голове деки стоит индекс максимума для текущего окна.
Пусть \(q<i\) и \(\tau(q)\le \tau(i)\). Начиная с момента вставки \(i\), любое будущее окно, которое ещё содержит \(q\), обязательно содержит и \(i\), потому что \(i\) новее и выпадет из окна не раньше. При этом значение \(\tau(i)\) не меньше. Значит, \(q\) уже никогда не станет лучшим кандидатом на максимум и может быть удалён окончательно.
Именно этот аргумент обеспечивает линейную сложность: каждый индекс добавляется один раз и удаляется не более одного раза с каждого конца деки.
Для \(u=10\) и \(k=3\) имеем
$$\tau(1),\tau(2),\dots,\tau(10)=1,2,2,3,2,4,2,4,3,4.$$
Максимумы по окнам равны
$$2,3,3,4,4,4,4,4,$$
поэтому
$$S(10,3)=2+3+3+4+4+4+4+4=28.$$
На больших входных данных работает тот же принцип: на каждый индекс приходится лишь константное амортизированное число операций с декой.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала они строят таблицу числа делителей до \(u\) с помощью линейного решета. Затем эта таблица один раз просматривается монотонной декой, и максимум каждого окна длины \(k\) добавляется к ответу.
Оптимизированный метод проверяется по контрольному значению
$$S(1000,10)=17176,$$
а одна из реализаций дополнительно сравнивает меньший тест с прямым перебором окон.
Линейное решето требует \(O(u)\) времени. Проход с декой также работает за \(O(u)\), поскольку каждый индекс входит в деку один раз и выходит не более одного раза. Следовательно, общая временная сложность равна
$$O(u).$$
По памяти требуется \(O(u)\) для таблиц решета и значений \(\tau\), а сама дека занимает не более \(O(k)\). Асимптотически доминирует
$$O(u).$$
لتكن \(\tau(n)\) دالة عدد القواسم الموجبة للعدد \(n\). عند تثبيت العددين \(u\) و\(k\)، نعرّف
$$M_n=\max_{n \le j \le n+k-1}\tau(j),\qquad S(u,k)=\sum_{n=1}^{u-k+1} M_n.$$
أي إن كل نافذة متتالية طولها \(k\) تساهم بأكبر قيمة لعدد القواسم داخلها، ثم نجمع هذه القيم على جميع النوافذ. الفحص المباشر لكل نافذة على حدة سيكون بطيئًا جدًا، لذلك يعتمد الحل على مرحلتين خطيتين.
إذا كان
$$n=\prod_{r=1}^{t} p_r^{a_r},$$
فإن أي قاسم لـ \(n\) ينتج من اختيار أسّ \(b_r\) بحيث \(0 \le b_r \le a_r\) لكل عامل أولي. ومن ثم
$$\tau(n)=\prod_{r=1}^{t}(a_r+1).$$
هذه الصيغة الضربية هي أساس طريقة الغربال. بدلًا من تحليل كل عدد على حدة، تُبنى القيم \(\tau(1),\tau(2),\dots,\tau(u)\) كلها تدريجيًا.
اكتب \(n=p^a m\) حيث \(p \nmid m\). عندئذ
$$\tau(n)=(a+1)\tau(m).$$
وعند ضرب \(n\) في عدد أولي تظهر حالتان فقط:
$$\tau(np)= \begin{cases} 2\tau(n), & p \nmid n,\\ \tau(n)\dfrac{a+2}{a+1}, & n=p^a m,\ p \nmid m. \end{cases}$$
في الحالة الأولى نضيف عاملًا أوليًا جديدًا أسّه \(1\). وفي الحالة الثانية نزداد في أسّ العامل الأولي الموجود أصلًا من \(a\) إلى \(a+1\). لذلك تحفظ التطبيقات أصغر عامل أولي لكل عدد، وكذلك أسّه، حتى يمكن تحديث \(\tau\) بزمن ثابت.
يبقى الغربال خطيًا لأن كل عدد مركب يُولَّد مرة واحدة فقط وفق قاعدة أصغر عامل أولي، وبالتالي تُبنى الجدول كاملة حتى \(u\) في زمن \(O(u)\).
بعد حساب \(\tau(1),\dots,\tau(u)\)، تصبح المسألة مسألة أعظم قيمة في نافذة ثابتة الطول. من الملائم توصيف النافذة بحدّها الأيمن:
$$W_i=[\,i-k+1,\ i\,],\qquad i=k,k+1,\dots,u.$$
ومساهمة هذه النافذة هي
$$\max_{j \in W_i}\tau(j).$$
وهذه هي النوافذ نفسها الواردة في تعريف \(S(u,k)\)، لكن بصياغة مختلفة.
يُحافَظ على deque من الفهارس المرشحة مع خاصيتين دائمتيْن:
1. الفهارس مرتبة تصاعديًا من المقدمة إلى المؤخرة.
2. قيم \(\tau\) المقابلة لها مرتبة تنازليًا ترتيبًا صارمًا.
عند وصول الفهرس الجديد \(i\)، نحذف من الخلف كل فهرس \(q\) يحقق \(\tau(q)\le \tau(i)\)، ثم نضيف \(i\). وبعد ذلك نحذف من الأمام كل فهرس \(q \le i-k\) لأنه خرج من النافذة الحالية.
بعد هاتين العمليتين يكون عنصر المقدمة هو الفهرس الذي يعطي أكبر عدد قواسم داخل النافذة الحالية.
إذا كان \(q<i\) و\(\tau(q)\le \tau(i)\)، فكل نافذة مستقبلية ما زالت تحتوي \(q\) ستحتوي أيضًا \(i\)، لأن \(i\) أحدث وسيغادر النافذة بعد \(q\) أو معه. وبما أن قيمة \(\tau(i)\) ليست أصغر، فلن يعود \(q\) أفضل مرشح لأي أعظمية مستقبلية. لذا يمكن حذفه نهائيًا بأمان.
هذا البرهان هو سبب الكلفة الخطية: كل فهرس يدخل deque مرة واحدة، ويخرج منها من الخلف مرة على الأكثر، ومن الأمام مرة على الأكثر.
عند \(u=10\) و\(k=3\) نحصل على
$$\tau(1),\tau(2),\dots,\tau(10)=1,2,2,3,2,4,2,4,3,4.$$
وأعظميات النوافذ هي
$$2,3,3,4,4,4,4,4,$$
ومن ثم
$$S(10,3)=2+3+3+4+4+4+4+4=28.$$
ويعمل الأسلوب نفسه على المدخلات الكبيرة لأن كل خطوة تحتاج إلى عدد ثابت وسطيًا من عمليات deque.
تتبع تطبيقات C++ وPython وJava البنية نفسها. في المرحلة الأولى تُبنى قيم عدد القواسم حتى \(u\) باستعمال الغربال الخطي. وفي المرحلة الثانية تُمرَّر هذه القيم مرة واحدة عبر deque أحادية الرتابة، ويُضاف أكبر عنصر في كل نافذة طولها \(k\) إلى المجموع النهائي.
ويجري التحقق من صحة الطريقة بالقيمة
$$S(1000,10)=17176,$$
كما أن أحد التطبيقات يقارن حالة أصغر مع مسح مباشر بالقوة الغاشمة للتأكد من التطابق.
يعمل غربال عدد القواسم في زمن \(O(u)\). كما أن المرور بالـ deque يكلّف \(O(u)\) أيضًا لأن كل فهرس يُدرج مرة ويُزال مرة على الأكثر. لذلك يكون التعقيد الزمني الكلي
$$O(u).$$
أما الذاكرة فهي \(O(u)\) لجداول الغربال وقيم \(\tau\)، إضافة إلى \(O(k)\) للـ deque. وبالتالي يبقى الحد الغالب هو
$$O(u).$$