Let
$$T_n=\frac{n(n+1)}{2},\qquad D_n=d(T_n),$$
where \(d(m)\) is the number of positive divisors of \(m\). For a given \(N\), we must count all triples of indices
$$1\le i \lt j \lt k\le N$$
such that
$$D_i \gt D_j \gt D_k.$$
In other words, after converting each triangular number \(T_n\) into its divisor count \(D_n\), the task is to count strictly decreasing subsequences of length three. The implementation targets \(N=60{,}000{,}000\) and returns the result modulo \(10^{18}\), so both the divisor-count computation and the triple counting must be highly optimized.
Consecutive integers are coprime:
$$\gcd(n,n+1)=1.$$
Also, exactly one of \(n\) and \(n+1\) is even. Therefore we can remove the factor \(2\) before applying the divisor function:
$$T_n=\begin{cases} \frac{n}{2}(n+1), & n \text{ even},\\[2mm] n\frac{n+1}{2}, & n \text{ odd}. \end{cases}$$
In both cases the two factors are coprime, so the divisor function is multiplicative:
$$d(ab)=d(a)d(b)\qquad \text{when } \gcd(a,b)=1.$$
Hence
$$D_n=d(T_n)=\begin{cases} d\!\left(\frac{n}{2}\right)d(n+1), & n \text{ even},\\[2mm] d(n)d\!\left(\frac{n+1}{2}\right), & n \text{ odd}. \end{cases}$$
This identity is the core simplification used by every implementation. For example, \(T_7=28=4\cdot 7\), so
$$D_7=d(4)d(7)=3\cdot 2=6,$$
which matches the explicit checkpoint in the C++ solver.
Because the formula above only needs \(d(x)\) for integers up to \(N+1\), the program first precomputes the divisor-count table once. The arrays in build_tau store:
\(lp[i]\): the smallest prime dividing \(i\),
\(cnt[i]\): the exponent of \(lp[i]\) inside \(i\),
\(d(i)\): the divisor count itself.
If
$$i=m p^e,\qquad p\nmid m,$$
then
$$d(i)=d(m)(e+1).$$
When the sieve extends \(i\) to \(x=i p\), there are two cases:
$$d(x)=\begin{cases} d(i)\cdot 2, & p\ne lp[i],\\[2mm] d(i)\cdot \dfrac{e+2}{e+1}, & p=lp[i]. \end{cases}$$
The second formula is exactly what the source code writes as
$$d(x)=\frac{d(i)}{cnt[i]+1}\,(cnt[x]+1).$$
This produces all values up to \(N+1\) in linear total work, after which each \(D_n\) can be evaluated in constant time from the parity split above.
Now consider the sequence
$$D_1,D_2,\dots,D_N.$$
We want the number of triples \(i \lt j \lt k\) with strict decrease. This is a dynamic-programming problem over values rather than over explicit triples.
For each processed position, maintain:
\(C(r)\): how many earlier indices have divisor-count rank \(r\),
\(P(r)\): how many decreasing pairs \((i,j)\) seen so far end with rank \(r\).
The code does not need coordinate compression. It first scans all \(D_n\) to find
$$M=\max_{1\le n\le N} D_n,$$
then uses the direct 1-based rank
$$r=D_n+1.$$
That is why the Fenwick trees are sized as max_d + 2 in both C++ and Java.
Suppose the current position is \(k\) and its rank is \(r\). Every earlier value larger than \(D_k\) creates a new decreasing pair ending at \(k\), so
$$\text{greater\_left}(k)=\sum_{t=r+1}^{M+1} C(t).$$
Similarly, every earlier decreasing pair whose second value is still larger than \(D_k\) can be extended to a triple ending at \(k\), so
$$\text{triples\_ending\_here}(k)=\sum_{t=r+1}^{M+1} P(t).$$
After computing those two quantities, the update rules are
$$P(r)\leftarrow P(r)+\text{greater\_left}(k),$$
$$C(r)\leftarrow C(r)+1.$$
A Fenwick tree gives each suffix sum and each point update in \(O(\log M)\). Two such trees are enough: one for single elements and one for decreasing pairs.
The first twenty values are
$$\left(D_1,\dots,D_{20}\right)=\left(1,2,4,4,4,4,6,9,6,4,8,8,4,8,16,8,6,6,8,16\right).$$
Because the inequalities are strict, equal values never contribute. For instance, \((8,9,10)\) is valid because
$$D_8=9,\qquad D_9=6,\qquad D_{10}=4,$$
and \((15,16,17)\) is valid because
$$16 \gt 8 \gt 6.$$
The total number of valid triples up to \(20\) is
$$14,$$
which is exactly the checkpoint count_triples_mod(20) == 14 in the C++ source.
The C++ implementation is the reference solver. It builds tau up to kTargetN + 1, verifies the checkpoints d_triangle(7)=6, Tr(20)=14, Tr(100)=5772, and Tr(1000)=11174776, then performs two passes over \(1,\dots,N\): the first finds max_d, and the second performs the Fenwick-based dynamic programming.
The Java version mirrors the same mathematics, but stores every \(D_n\) in an array dtArr during the first pass so that the second pass does not recompute them. The Python file is intentionally thin: it compiles and runs the C++ solver, then parses the produced answer. So the mathematical logic is shared across all three languages, with C++ providing the canonical implementation details.
Let \(N\) be the target limit and let \(M=\max_{1\le n\le N} D_n\). The divisor-count sieve runs in \(O(N)\) time and uses \(O(N)\) memory for the sieve arrays. The triple-counting phase performs two Fenwick queries and two Fenwick updates per index, so it costs \(O(N\log M)\) time and \(O(M)\) memory for the trees. Overall, the algorithm is dominated by
$$O(N)+O(N\log M)=O(N\log M)$$
time, with \(O(N)+O(M)\) memory. In practice \(M\) is far smaller than \(N\), which is why this approach is feasible for \(N=60{,}000{,}000\).
Sei
$$T_n=\frac{n(n+1)}{2},\qquad D_n=d(T_n),$$
wobei \(d(m)\) die Anzahl der positiven Teiler von \(m\) bezeichnet. Gesucht ist die Anzahl aller Indextripel
$$1\le i \lt j \lt k\le N$$
mit
$$D_i \gt D_j \gt D_k.$$
Nach der Umformung der Dreieckszahlen in ihre Teileranzahlen wird das Problem also zu einer Zählung streng fallender Teilfolgen der Länge drei. Für das echte Ziel \(N=60{,}000{,}000\) ist eine naive Enumeration ausgeschlossen; sowohl die Berechnung der \(D_n\) als auch die Tripelzählung müssen fast linear sein.
Für aufeinanderfolgende Zahlen gilt
$$\gcd(n,n+1)=1.$$
Außerdem ist genau eine von ihnen gerade. Daher kann man den Faktor \(2\) vorab entfernen:
$$T_n=\begin{cases} \frac{n}{2}(n+1), & n \text{ gerade},\\[2mm] n\frac{n+1}{2}, & n \text{ ungerade}. \end{cases}$$
In beiden Fällen sind die beiden Faktoren teilerfremd, also ist die Teilerfunktion multiplikativ:
$$d(ab)=d(a)d(b)\qquad \text{falls } \gcd(a,b)=1.$$
Damit folgt unmittelbar
$$D_n=d(T_n)=\begin{cases} d\!\left(\frac{n}{2}\right)d(n+1), & n \text{ gerade},\\[2mm] d(n)d\!\left(\frac{n+1}{2}\right), & n \text{ ungerade}. \end{cases}$$
Genau diese Formel verwenden C++, Java und Python. Für \(n=7\) ist \(T_7=28=4\cdot 7\), also
$$D_7=d(4)d(7)=3\cdot 2=6,$$
was dem ersten Kontrollwert der C++-Datei entspricht.
Da die Formel nur Werte \(d(x)\) bis \(N+1\) benötigt, berechnet das Programm zunächst eine komplette Tabelle. In build_tau stehen:
\(lp[i]\): der kleinste Primteiler von \(i\),
\(cnt[i]\): der Exponent dieses Primteilers in \(i\),
\(d(i)\): die Teileranzahl.
Schreibt man
$$i=m p^e,\qquad p\nmid m,$$
so gilt
$$d(i)=d(m)(e+1).$$
Beim Übergang zu \(x=i p\) ergeben sich genau die beiden Fälle aus dem Quelltext:
$$d(x)=\begin{cases} d(i)\cdot 2, & p\ne lp[i],\\[2mm] d(i)\cdot \dfrac{e+2}{e+1}, & p=lp[i]. \end{cases}$$
Die zweite Formel erscheint im Code als
$$d(x)=\frac{d(i)}{cnt[i]+1}\,(cnt[x]+1).$$
So entsteht die gesamte Tabelle bis \(N+1\) in linearer Gesamtzeit, und jedes \(D_n\) lässt sich danach in \(O(1)\) berechnen.
Nun betrachten wir die Folge
$$D_1,D_2,\dots,D_N.$$
Gesucht ist die Anzahl der Tripel \(i \lt j \lt k\) mit strenger Abnahme. Statt explizit Tripel zu durchsuchen, zählt das Programm dynamisch nach Werten.
Für bereits verarbeitete Positionen speichern wir:
\(C(r)\): Anzahl früherer Indizes mit Rang \(r\),
\(P(r)\): Anzahl bereits entstandener fallender Paare \((i,j)\), deren zweiter Wert Rang \(r\) hat.
Eine eigentliche Koordinatenkompression ist nicht nötig. Zunächst wird
$$M=\max_{1\le n\le N} D_n$$
bestimmt, und dann der direkte 1-basierte Rang
$$r=D_n+1$$
verwendet. Deshalb haben die Fenwick-Bäume in C++ und Java die Größe max_d + 2.
Sei \(k\) die aktuelle Position und \(r\) ihr Rang. Jede frühere Zahl, die größer als \(D_k\) ist, liefert ein neues fallendes Paar mit Ende \(k\):
$$\text{greater\_left}(k)=\sum_{t=r+1}^{M+1} C(t).$$
Ebenso kann jedes frühere fallende Paar, dessen zweiter Wert noch größer als \(D_k\) ist, zu einem gültigen Tripel erweitert werden:
$$\text{triples\_ending\_here}(k)=\sum_{t=r+1}^{M+1} P(t).$$
Danach werden die Tabellen aktualisiert:
$$P(r)\leftarrow P(r)+\text{greater\_left}(k),$$
$$C(r)\leftarrow C(r)+1.$$
Fenwick-Bäume liefern diese Suffixsummen und Punktupdates in \(O(\log M)\). Mehr als zwei Bäume braucht man nicht.
Die ersten zwanzig Werte lauten
$$\left(D_1,\dots,D_{20}\right)=\left(1,2,4,4,4,4,6,9,6,4,8,8,4,8,16,8,6,6,8,16\right).$$
Wegen der strengen Ungleichungen zählen gleiche Werte nie. Das Tripel \((8,9,10)\) ist gültig, denn
$$D_8=9,\qquad D_9=6,\qquad D_{10}=4,$$
und \((15,16,17)\) ist gültig, weil
$$16 \gt 8 \gt 6.$$
Insgesamt gibt es bis \(20\) genau
$$14$$
gültige Tripel, genau wie im Checkpoint count_triples_mod(20) == 14.
Die C++-Datei ist die Referenzimplementierung. Sie baut zunächst tau bis kTargetN + 1 auf, prüft die Kontrollwerte d_triangle(7)=6, Tr(20)=14, Tr(100)=5772 und Tr(1000)=11174776, bestimmt in einem ersten Durchlauf max_d und führt im zweiten Durchlauf das Fenwick-DP aus.
Die Java-Version verwendet dieselbe Mathematik, speichert aber alle \(D_n\) im Array dtArr, damit sie im zweiten Durchlauf nicht neu berechnet werden müssen. Die Python-Datei implementiert den Algorithmus nicht separat, sondern kompiliert und startet die C++-Lösung und extrahiert deren Ausgabe. Inhaltlich gibt also C++ die maßgebliche Logik vor.
Sei \(M=\max_{1\le n\le N} D_n\). Das lineare Sieb für die Teilerfunktion kostet \(O(N)\) Zeit und \(O(N)\) Speicher. Die Zählphase führt pro Index zwei Fenwick-Abfragen und zwei Updates aus und benötigt daher \(O(N\log M)\) Zeit bei \(O(M)\) zusätzlichem Speicher für die Bäume. Insgesamt ergibt sich
$$O(N)+O(N\log M)=O(N\log M)$$
Zeit sowie \(O(N)+O(M)\) Speicher. Da \(M\) in der Praxis viel kleiner als \(N\) ist, skaliert dieses Verfahren gut genug bis \(N=60{,}000{,}000\).
Şöyle tanımlayalım:
$$T_n=\frac{n(n+1)}{2},\qquad D_n=d(T_n),$$
burada \(d(m)\), \(m\) sayısının pozitif bölen sayısıdır. Amaç,
$$1\le i \lt j \lt k\le N$$
koşulunu sağlayan ve aynı zamanda
$$D_i \gt D_j \gt D_k$$
eşitsizliklerini veren tüm indis üçlülerini saymaktır. Yani üçgensel sayı dizisini önce bölen sayıları dizisine dönüştürüyor, sonra bu yeni dizi içindeki uzunluğu 3 olan sıkı azalan alt dizileri sayıyoruz. Gerçek hedef \(N=60{,}000{,}000\) olduğu için hem \(D_n\) değerlerini üretmek hem de üçlüleri saymak çok verimli olmak zorundadır.
Ardışık iki sayı için
$$\gcd(n,n+1)=1$$
olur. Ayrıca bu iki sayıdan tam biri çifttir. Bu yüzden önce \(2\) çarpanını ayırabiliriz:
$$T_n=\begin{cases} \frac{n}{2}(n+1), & n \text{ çift},\\[2mm] n\frac{n+1}{2}, & n \text{ tek}. \end{cases}$$
Her iki durumda da iki çarpan aralarında asal olduğundan bölen sayısı fonksiyonu çarpımsaldır:
$$d(ab)=d(a)d(b)\qquad \text{eğer } \gcd(a,b)=1.$$
Dolayısıyla
$$D_n=d(T_n)=\begin{cases} d\!\left(\frac{n}{2}\right)d(n+1), & n \text{ çift},\\[2mm] d(n)d\!\left(\frac{n+1}{2}\right), & n \text{ tek}. \end{cases}$$
Tüm çözümlerin dayandığı temel formül budur. Örneğin \(T_7=28=4\cdot 7\) olduğu için
$$D_7=d(4)d(7)=3\cdot 2=6,$$
ve bu da C++ dosyasındaki açık kontrol ile aynıdır.
Yukarıdaki formül yalnızca \(N+1\)'e kadar olan sayılar için \(d(x)\) istediğinden, program önce bu tabloyu tek seferde üretir. build_tau fonksiyonundaki diziler şunları tutar:
\(lp[i]\): \(i\)'yi bölen en küçük asal,
\(cnt[i]\): bu asalın \(i\) içindeki üssü,
\(d(i)\): bölen sayısı.
Eğer
$$i=m p^e,\qquad p\nmid m,$$
ise
$$d(i)=d(m)(e+1)$$
olur. Sieve adımında \(x=i p\) yazıldığında kaynak koddaki iki durum tam olarak şudur:
$$d(x)=\begin{cases} d(i)\cdot 2, & p\ne lp[i],\\[2mm] d(i)\cdot \dfrac{e+2}{e+1}, & p=lp[i]. \end{cases}$$
İkinci satır, C++ ve Java kodunda
$$d(x)=\frac{d(i)}{cnt[i]+1}\,(cnt[x]+1)$$
şeklinde uygulanır. Böylece \(N+1\)'e kadar tüm değerler toplamda lineer zamanda bulunur ve her \(D_n\) sabit zamanda hesaplanır.
Artık şu diziye bakıyoruz:
$$D_1,D_2,\dots,D_N.$$
İstenen şey, bu dizi içinde uzunluğu 3 olan tüm sıkı azalan alt dizilerin sayısıdır. Bunu açıkça tüm üçlüleri deneyerek değil, değer bazlı dinamik programlama ile sayıyoruz.
İşlenmiş kısım için şu iki yapıyı tutalım:
\(C(r)\): değeri rütbe \(r\) olan önceki eleman sayısı,
\(P(r)\): ikinci elemanı rütbe \(r\) olan azalan ikili sayısı.
Burada ayrıca bir koordinat sıkıştırması yapılmaz. Kod önce
$$M=\max_{1\le n\le N} D_n$$
değerini bulur, sonra doğrudan
$$r=D_n+1$$
rütbesini kullanır. Fenwick ağaçlarının boyutu bu yüzden max_d + 2 olur.
Güncel konum \(k\), rütbe de \(r\) olsun. \(D_k\)'den büyük olan her önceki değer, \(k\)'de biten yeni bir azalan ikili üretir:
$$\text{greater\_left}(k)=\sum_{t=r+1}^{M+1} C(t).$$
Aynı şekilde, ikinci elemanı hâlâ \(D_k\)'den büyük olan her eski azalan ikili yeni bir üçlüye uzatılabilir:
$$\text{triples\_ending\_here}(k)=\sum_{t=r+1}^{M+1} P(t).$$
Bunlar hesaplandıktan sonra güncellemeler şöyledir:
$$P(r)\leftarrow P(r)+\text{greater\_left}(k),$$
$$C(r)\leftarrow C(r)+1.$$
Fenwick ağacı, bu sonek toplamlarını ve nokta güncellemelerini \(O(\log M)\) zamanda verir. İki ağaç yeterlidir: biri tekli sayılar için, diğeri azalan ikililer için.
İlk yirmi değer şöyledir:
$$\left(D_1,\dots,D_{20}\right)=\left(1,2,4,4,4,4,6,9,6,4,8,8,4,8,16,8,6,6,8,16\right).$$
Eşit değerler sıkı azalma sağlamadığı için hiç katkı vermez. Mesela \((8,9,10)\) üçlüsü geçerlidir; çünkü
$$D_8=9,\qquad D_9=6,\qquad D_{10}=4.$$
Aynı şekilde \((15,16,17)\) de geçerlidir, çünkü
$$16 \gt 8 \gt 6.$$
\(20\)'ye kadar toplam geçerli üçlü sayısı
$$14$$
olur; bu da C++ içindeki count_triples_mod(20) == 14 kontrolüyle aynıdır.
C++ dosyası referans çözümdür. Önce tau tablosunu kTargetN + 1'e kadar kurar, ardından d_triangle(7)=6, Tr(20)=14, Tr(100)=5772 ve Tr(1000)=11174776 kontrol noktalarını doğrular. Sonra ilk turda max_d bulunur, ikinci turda ise Fenwick tabanlı dinamik programlama uygulanır.
Java sürümü aynı matematiği kullanır, fakat ikinci turda tekrar hesap yapmamak için tüm \(D_n\) değerlerini dtArr dizisinde tutar. Python dosyası bağımsız bir algoritma yazmaz; C++ çözümünü derler, çalıştırır ve çıktıyı ayrıştırır. Bu nedenle uygulama ayrıntılarının gerçek kaynağı C++ sürümüdür.
\(M=\max_{1\le n\le N} D_n\) olsun. Bölen sayısı sieve'ı \(O(N)\) zaman ve \(O(N)\) bellek kullanır. Sayım aşamasında her indis için iki Fenwick sorgusu ve iki güncelleme yapıldığı için süre \(O(N\log M)\), ağaç belleği ise \(O(M)\) olur. Toplam karmaşıklık
$$O(N)+O(N\log M)=O(N\log M)$$
zaman ve \(O(N)+O(M)\) bellektir. Pratikte \(M\), \(N\)'den çok daha küçük kaldığı için yöntem \(N=60{,}000{,}000\) için yeterince hızlıdır.
Definimos
$$T_n=\frac{n(n+1)}{2},\qquad D_n=d(T_n),$$
donde \(d(m)\) es la cantidad de divisores positivos de \(m\). Debemos contar todas las ternas de índices
$$1\le i \lt j \lt k\le N$$
que cumplen
$$D_i \gt D_j \gt D_k.$$
Es decir, primero transformamos cada número triangular en su número de divisores y luego contamos las subsecuencias estrictamente decrecientes de longitud tres. Como el programa objetivo trabaja con \(N=60{,}000{,}000\) y devuelve el resultado módulo \(10^{18}\), el método tiene que evitar tanto la factorización repetida como la enumeración explícita de ternas.
Dos enteros consecutivos son coprimos:
$$\gcd(n,n+1)=1.$$
Además, exactamente uno de ellos es par. Por eso podemos separar primero el factor \(2\):
$$T_n=\begin{cases} \frac{n}{2}(n+1), & n \text{ par},\\[2mm] n\frac{n+1}{2}, & n \text{ impar}. \end{cases}$$
En ambos casos los dos factores restantes son coprimos, así que la función divisor es multiplicativa:
$$d(ab)=d(a)d(b)\qquad \text{si } \gcd(a,b)=1.$$
Por tanto
$$D_n=d(T_n)=\begin{cases} d\!\left(\frac{n}{2}\right)d(n+1), & n \text{ par},\\[2mm] d(n)d\!\left(\frac{n+1}{2}\right), & n \text{ impar}. \end{cases}$$
Esta es la identidad central de las tres soluciones. Por ejemplo, \(T_7=28=4\cdot 7\), luego
$$D_7=d(4)d(7)=3\cdot 2=6,$$
que coincide con el primer checkpoint del código C++.
Como la fórmula anterior solo necesita \(d(x)\) hasta \(N+1\), el programa precalcula esa tabla una sola vez. La rutina build_tau usa:
\(lp[i]\): el menor primo que divide a \(i\),
\(cnt[i]\): el exponente de ese primo en \(i\),
\(d(i)\): el número de divisores.
Si
$$i=m p^e,\qquad p\nmid m,$$
entonces
$$d(i)=d(m)(e+1).$$
Al extender \(i\) hacia \(x=i p\), aparecen exactamente dos casos:
$$d(x)=\begin{cases} d(i)\cdot 2, & p\ne lp[i],\\[2mm] d(i)\cdot \dfrac{e+2}{e+1}, & p=lp[i]. \end{cases}$$
La segunda línea es la expresión implementada como
$$d(x)=\frac{d(i)}{cnt[i]+1}\,(cnt[x]+1).$$
Así se obtienen todos los valores hasta \(N+1\) en tiempo lineal total, y luego cada \(D_n\) se evalúa en tiempo constante.
Ahora miramos la secuencia
$$D_1,D_2,\dots,D_N.$$
Lo que buscamos es el número de ternas \(i \lt j \lt k\) con descenso estricto. En lugar de probar cada terna, el algoritmo hace programación dinámica sobre los valores ya vistos.
Para la parte procesada mantenemos:
\(C(r)\): cuántos índices anteriores tienen rango \(r\),
\(P(r)\): cuántos pares decrecientes \((i,j)\) terminan con rango \(r\).
El código no comprime valores distintos. Primero calcula
$$M=\max_{1\le n\le N} D_n,$$
y después usa el rango directo
$$r=D_n+1.$$
Por eso los árboles Fenwick tienen tamaño max_d + 2.
Si el índice actual es \(k\) y su rango es \(r\), cada valor previo mayor que \(D_k\) forma un nuevo par decreciente terminado en \(k\):
$$\text{greater\_left}(k)=\sum_{t=r+1}^{M+1} C(t).$$
Del mismo modo, cada par decreciente previo cuyo segundo valor siga siendo mayor que \(D_k\) produce una nueva terna terminada en \(k\):
$$\text{triples\_ending\_here}(k)=\sum_{t=r+1}^{M+1} P(t).$$
Luego se actualiza
$$P(r)\leftarrow P(r)+\text{greater\_left}(k),$$
$$C(r)\leftarrow C(r)+1.$$
Un Fenwick permite hacer cada suma de sufijo y cada actualización puntual en \(O(\log M)\). Con dos árboles basta.
Los veinte primeros valores son
$$\left(D_1,\dots,D_{20}\right)=\left(1,2,4,4,4,4,6,9,6,4,8,8,4,8,16,8,6,6,8,16\right).$$
Como la desigualdad es estricta, los empates no cuentan. La terna \((8,9,10)\) es válida porque
$$D_8=9,\qquad D_9=6,\qquad D_{10}=4,$$
y \((15,16,17)\) también es válida porque
$$16 \gt 8 \gt 6.$$
El total hasta \(20\) es
$$14,$$
exactamente el valor verificado por count_triples_mod(20) en la implementación de referencia.
La versión en C++ es la implementación principal. Primero construye tau hasta kTargetN + 1, valida los checkpoints d_triangle(7)=6, Tr(20)=14, Tr(100)=5772 y Tr(1000)=11174776, hace una pasada para hallar max_d y una segunda pasada para ejecutar la DP con Fenwick.
La versión Java sigue exactamente la misma matemática, pero guarda todos los valores \(D_n\) en el arreglo dtArr durante la primera pasada para no recalcularlos después. El archivo Python no reimplementa el algoritmo: compila y ejecuta la solución C++ y luego analiza la salida. Por eso, los detalles algorítmicos reales vienen de C++ y Java, mientras que Python funciona como puente.
Sea \(M=\max_{1\le n\le N} D_n\). La criba lineal para la función divisor cuesta \(O(N)\) tiempo y \(O(N)\) memoria. La fase de conteo realiza dos consultas y dos actualizaciones Fenwick por índice, de modo que requiere \(O(N\log M)\) tiempo y \(O(M)\) memoria adicional para los árboles. En conjunto, la complejidad es
$$O(N)+O(N\log M)=O(N\log M)$$
en tiempo, con \(O(N)+O(M)\) memoria. Como \(M\) es mucho menor que \(N\) en la práctica, el método escala bien hasta \(60{,}000{,}000\).
定义
$$T_n=\frac{n(n+1)}{2},\qquad D_n=d(T_n),$$
其中 \(d(m)\) 表示 \(m\) 的正因子个数。题目要求统计所有满足
$$1\le i \lt j \lt k\le N$$
且
$$D_i \gt D_j \gt D_k$$
的三元组个数。也就是说，先把三角数序列变成因子个数序列，再统计其中长度为 3 的严格下降子序列。由于实现目标是 \(N=60{,}000{,}000\)，并且最终结果按 \(10^{18}\) 取模，所以既不能逐个分解每个三角数，也不能显式枚举所有三元组。
连续两个整数互素：
$$\gcd(n,n+1)=1.$$
并且 \(n\) 与 \(n+1\) 中恰好有一个是偶数，因此可以先把因子 \(2\) 拿掉：
$$T_n=\begin{cases} \frac{n}{2}(n+1), & n \text{ 为偶数},\\[2mm] n\frac{n+1}{2}, & n \text{ 为奇数}. \end{cases}$$
这两种写法中的两个因子都互素，所以因子函数满足乘法性：
$$d(ab)=d(a)d(b)\qquad \text{当 } \gcd(a,b)=1.$$
于是
$$D_n=d(T_n)=\begin{cases} d\!\left(\frac{n}{2}\right)d(n+1), & n \text{ 为偶数},\\[2mm] d(n)d\!\left(\frac{n+1}{2}\right), & n \text{ 为奇数}. \end{cases}$$
这就是三份代码共同使用的核心公式。例如 \(T_7=28=4\cdot 7\)，因此
$$D_7=d(4)d(7)=3\cdot 2=6,$$
正好对应 C++ 程序中的显式检查点。
因为上面的公式只需要 \(x\le N+1\) 的因子个数，所以程序先整体预处理这张表。build_tau 中的数组含义是：
\(lp[i]\)：\(i\) 的最小质因子，
\(cnt[i]\)：这个最小质因子在 \(i\) 中的指数，
\(d(i)\)：\(i\) 的因子个数。
若
$$i=m p^e,\qquad p\nmid m,$$
则有
$$d(i)=d(m)(e+1).$$
当筛法把 \(i\) 扩展成 \(x=i p\) 时，恰好分成两种情况：
$$d(x)=\begin{cases} d(i)\cdot 2, & p\ne lp[i],\\[2mm] d(i)\cdot \dfrac{e+2}{e+1}, & p=lp[i]. \end{cases}$$
第二种情况在源码里写成
$$d(x)=\frac{d(i)}{cnt[i]+1}\,(cnt[x]+1).$$
这样就能用线性总工作量求出全部 \(d(x)\)，之后每个 \(D_n\) 都可以 \(O(1)\) 计算。
接下来考虑序列
$$D_1,D_2,\dots,D_N.$$
我们要统计的是所有满足 \(i \lt j \lt k\) 且数值严格下降的三元组。与其直接枚举三元组，不如按“已经处理过的值”做动态规划。
对已经扫描过的位置，维护两个量：
\(C(r)\)：值的排名为 \(r\) 的元素出现了多少次，
\(P(r)\)：所有严格下降二元组 \((i,j)\) 中，第二个值排名为 \(r\) 的个数。
这里并不需要离散化映射表。程序先求出
$$M=\max_{1\le n\le N} D_n,$$
然后直接使用 1 基排名
$$r=D_n+1.$$
这也是 C++ 和 Java 都把 Fenwick 树大小设成 max_d + 2 的原因。
设当前处理到位置 \(k\)，其排名为 \(r\)。所有比 \(D_k\) 大的历史值都会形成一个新的下降二元组，因此
$$\text{greater\_left}(k)=\sum_{t=r+1}^{M+1} C(t).$$
同理，所有第二项仍然大于 \(D_k\) 的历史下降二元组，都能再接上当前值形成一个合法三元组，因此
$$\text{triples\_ending\_here}(k)=\sum_{t=r+1}^{M+1} P(t).$$
然后执行更新
$$P(r)\leftarrow P(r)+\text{greater\_left}(k),$$
$$C(r)\leftarrow C(r)+1.$$
Fenwick 树可以在 \(O(\log M)\) 时间内完成这些后缀和查询与单点更新，所以两棵树就足够了。
前二十项为
$$\left(D_1,\dots,D_{20}\right)=\left(1,2,4,4,4,4,6,9,6,4,8,8,4,8,16,8,6,6,8,16\right).$$
由于必须严格下降，相等的值不会产生贡献。例如三元组 \((8,9,10)\) 有效，因为
$$D_8=9,\qquad D_9=6,\qquad D_{10}=4.$$
\((15,16,17)\) 也有效，因为
$$16 \gt 8 \gt 6.$$
当 \(N=20\) 时，合法三元组总数正好是
$$14,$$
这与 C++ 程序中的 count_triples_mod(20) == 14 完全一致。
C++ 文件是基准实现。它先构建到 kTargetN + 1 的 tau 表，再检查 d_triangle(7)=6、Tr(20)=14、Tr(100)=5772 和 Tr(1000)=11174776 这几个校验点。之后第一遍扫描求出 max_d，第二遍扫描用两棵 Fenwick 树执行动态规划。
Java 版本采用同样的数学思路，但会在第一遍中把全部 \(D_n\) 存入 dtArr，避免第二遍重新计算。Python 文件则故意保持很薄，只负责编译并调用 C++ 程序，再解析输出结果。因此真正的算法细节以 C++ 和 Java 为准，Python 只是桥接层。
记 \(M=\max_{1\le n\le N} D_n\)。因子个数的线性筛需要 \(O(N)\) 时间和 \(O(N)\) 内存。主计数阶段对每个位置做两次 Fenwick 查询和两次更新，所以需要 \(O(N\log M)\) 时间，Fenwick 树额外占用 \(O(M)\) 内存。总复杂度为
$$O(N)+O(N\log M)=O(N\log M),$$
总空间为 \(O(N)+O(M)\)。由于实践中 \(M\) 远小于 \(N\)，该方法才能处理 \(N=60{,}000{,}000\) 这样的规模。
Определим
$$T_n=\frac{n(n+1)}{2},\qquad D_n=d(T_n),$$
где \(d(m)\) обозначает число положительных делителей числа \(m\). Нужно посчитать количество троек индексов
$$1\le i \lt j \lt k\le N$$
таких, что
$$D_i \gt D_j \gt D_k.$$
Иными словами, мы переводим последовательность треугольных чисел в последовательность чисел делителей и затем считаем все строго убывающие подпоследовательности длины три. Для целевого значения \(N=60{,}000{,}000\) прямой перебор невозможен, поэтому решение должно быстро считать и сами \(D_n\), и число троек.
Для соседних чисел всегда верно
$$\gcd(n,n+1)=1.$$
Кроме того, ровно одно из чисел \(n\) и \(n+1\) чётно, поэтому фактор \(2\) удобно вынести заранее:
$$T_n=\begin{cases} \frac{n}{2}(n+1), & n \text{ чётное},\\[2mm] n\frac{n+1}{2}, & n \text{ нечётное}. \end{cases}$$
В обоих случаях оставшиеся множители взаимно просты, а функция числа делителей мультипликативна:
$$d(ab)=d(a)d(b)\qquad \text{если } \gcd(a,b)=1.$$
Следовательно,
$$D_n=d(T_n)=\begin{cases} d\!\left(\frac{n}{2}\right)d(n+1), & n \text{ чётное},\\[2mm] d(n)d\!\left(\frac{n+1}{2}\right), & n \text{ нечётное}. \end{cases}$$
Это ключевая формула всей реализации. Например, \(T_7=28=4\cdot 7\), поэтому
$$D_7=d(4)d(7)=3\cdot 2=6,$$
что в точности совпадает с первой проверкой в C++-коде.
Так как формула выше требует только значения \(d(x)\) для \(x\le N+1\), программа сначала строит всю таблицу за один проход. В функции build_tau используются массивы:
\(lp[i]\): минимальный простой делитель \(i\),
\(cnt[i]\): показатель степени этого простого делителя в \(i\),
\(d(i)\): число делителей.
Если
$$i=m p^e,\qquad p\nmid m,$$
то
$$d(i)=d(m)(e+1).$$
При переходе к \(x=i p\) возникают два случая, полностью совпадающие с исходниками:
$$d(x)=\begin{cases} d(i)\cdot 2, & p\ne lp[i],\\[2mm] d(i)\cdot \dfrac{e+2}{e+1}, & p=lp[i]. \end{cases}$$
Вторая формула в коде записана как
$$d(x)=\frac{d(i)}{cnt[i]+1}\,(cnt[x]+1).$$
Так строится вся таблица до \(N+1\) за линейное суммарное время, после чего каждый \(D_n\) считается за \(O(1)\).
Рассмотрим последовательность
$$D_1,D_2,\dots,D_N.$$
Нужно подсчитать количество троек \(i \lt j \lt k\) со строгим убыванием значений. Вместо явного перебора троек программа делает динамику по уже встреченным значениям.
Поддерживаются два объекта:
\(C(r)\): сколько ранее встречалось значений ранга \(r\),
\(P(r)\): сколько уже существует убывающих пар \((i,j)\), оканчивающихся рангом \(r\).
Координатное сжатие не требуется. Сначала находится
$$M=\max_{1\le n\le N} D_n,$$
а затем используется прямой ранг
$$r=D_n+1.$$
Именно поэтому в C++ и Java размер деревьев Фенвика равен max_d + 2.
Пусть текущая позиция равна \(k\), а её ранг равен \(r\). Любое предыдущее значение, большее чем \(D_k\), образует новую убывающую пару с концом в \(k\):
$$\text{greater\_left}(k)=\sum_{t=r+1}^{M+1} C(t).$$
Точно так же любая уже существующая убывающая пара, чей второй элемент всё ещё больше \(D_k\), продолжаетcя до допустимой тройки:
$$\text{triples\_ending\_here}(k)=\sum_{t=r+1}^{M+1} P(t).$$
После этого выполняются обновления
$$P(r)\leftarrow P(r)+\text{greater\_left}(k),$$
$$C(r)\leftarrow C(r)+1.$$
Дерево Фенвика вычисляет такие суффиксные суммы и точечные обновления за \(O(\log M)\), поэтому достаточно двух деревьев.
Первые двадцать значений имеют вид
$$\left(D_1,\dots,D_{20}\right)=\left(1,2,4,4,4,4,6,9,6,4,8,8,4,8,16,8,6,6,8,16\right).$$
Так как неравенства строгие, равные значения не подходят. Например, тройка \((8,9,10)\) допустима, потому что
$$D_8=9,\qquad D_9=6,\qquad D_{10}=4.$$
Тройка \((15,16,17)\) тоже допустима, так как
$$16 \gt 8 \gt 6.$$
Общее число допустимых троек при \(N=20\) равно
$$14,$$
и это в точности совпадает с проверкой count_triples_mod(20) == 14 в C++-реализации.
C++-файл является эталонной реализацией. Сначала строится массив tau до kTargetN + 1, затем проверяются контрольные значения d_triangle(7)=6, Tr(20)=14, Tr(100)=5772 и Tr(1000)=11174776. После этого первый проход находит max_d, а второй выполняет динамику на двух деревьях Фенвика.
Версия на Java использует ту же математику, но сохраняет все значения \(D_n\) в массиве dtArr, чтобы не вычислять их повторно во втором проходе. Python-версия специально сделана тонкой: она компилирует и запускает C++-решение, а затем разбирает его вывод. Поэтому фактическая логика алгоритма берётся именно из C++ и Java.
Обозначим \(M=\max_{1\le n\le N} D_n\). Линейное сито для функции числа делителей требует \(O(N)\) времени и \(O(N)\) памяти. Основная фаза подсчёта делает по две Fenwick-операции запроса и обновления на каждый индекс, то есть работает за \(O(N\log M)\) и использует \(O(M)\) дополнительной памяти для деревьев. Итого имеем
$$O(N)+O(N\log M)=O(N\log M)$$
по времени и \(O(N)+O(M)\) по памяти. На практике \(M\) существенно меньше \(N\), поэтому этот метод подходит для \(N=60{,}000{,}000\).
نعرّف
$$T_n=\frac{n(n+1)}{2},\qquad D_n=d(T_n),$$
حيث \(d(m)\) هي دالة عدد القواسم الموجبة للعدد \(m\). المطلوب هو عدّ جميع ثلاثيات الفهارس
$$1\le i \lt j \lt k\le N$$
التي تحقق
$$D_i \gt D_j \gt D_k.$$
بصياغة أخرى: نحوّل الأعداد المثلثية إلى سلسلة أعداد القواسم الخاصة بها، ثم نعدّ جميع المتتاليات الفرعية الهابطة هبوطًا صارمًا بطول 3. وبما أن التنفيذ يستهدف \(N=60{,}000{,}000\) ويعيد الناتج modulo \(10^{18}\)، فلا يمكن الاعتماد على التحليل الأولي المتكرر أو على التعداد الصريح لكل ثلاثية.
لدينا دائمًا
$$\gcd(n,n+1)=1.$$
كما أن واحدًا فقط من \(n\) و\(n+1\) يكون زوجيًا، لذلك يمكن فصل العامل \(2\) أولًا:
$$T_n=\begin{cases} \frac{n}{2}(n+1), & 2\mid n,\\[2mm] n\frac{n+1}{2}, & 2\nmid n. \end{cases}$$
في كلتا الحالتين يكون العاملان الباقيان متباينين نسبيًا، ولذلك تكون دالة القواسم مضاعِفة:
$$\gcd(a,b)=1 \implies d(ab)=d(a)d(b).$$
ومن ثم نحصل على
$$D_n=d(T_n)=\begin{cases} d\!\left(\frac{n}{2}\right)d(n+1), & 2\mid n,\\[2mm] d(n)d\!\left(\frac{n+1}{2}\right), & 2\nmid n. \end{cases}$$
هذه هي الصيغة الأساسية المشتركة بين جميع الملفات. فعلى سبيل المثال \(T_7=28=4\cdot 7\)، ولذلك
$$D_7=d(4)d(7)=3\cdot 2=6,$$
وهو نفس checkpoint المذكور صراحةً في حل ++C.
لأن الصيغة السابقة تحتاج فقط إلى \(d(x)\) للأعداد حتى \(N+1\)، يبدأ البرنامج ببناء جدول كامل مرة واحدة. في الدالة build_tau نجد:
\(lp[i]\): أصغر عامل أولي يقسم \(i\)،
\(cnt[i]\): أس هذا العامل الأولي داخل \(i\)،
\(d(i)\): عدد القواسم.
إذا كتبنا
$$i=m p^e,\qquad p\nmid m,$$
فعندئذ
$$d(i)=d(m)(e+1).$$
وعندما يمدّ الغربال \(i\) إلى \(x=i p\)، تظهر حالتان فقط:
$$d(x)=\begin{cases} d(i)\cdot 2, & p\ne lp[i],\\[2mm] d(i)\cdot \dfrac{e+2}{e+1}, & p=lp[i]. \end{cases}$$
والحالة الثانية هي نفسها المكتوبة في المصدر بالشكل
$$d(x)=\frac{d(i)}{cnt[i]+1}\,(cnt[x]+1).$$
بهذه الطريقة نحصل على جميع قيم \(d(x)\) حتى \(N+1\) بكلفة كلية خطية، وبعدها يصبح حساب كل \(D_n\) بزمن ثابت.
الآن ننظر إلى السلسلة
$$D_1,D_2,\dots,D_N.$$
المطلوب هو عدد الثلاثيات \(i \lt j \lt k\) ذات الهبوط الصارم. بدلًا من تجربة كل ثلاثية مباشرة، يستخدم البرنامج برمجة ديناميكية مبنية على القيم التي ظهرت حتى الآن.
نحافظ على بنيتين:
\(C(r)\): عدد العناصر السابقة ذات الرتبة \(r\)،
\(P(r)\): عدد الأزواج الهابطة \((i,j)\) التي ينتهي عنصرها الثاني عند الرتبة \(r\).
ولا حاجة هنا إلى ضغط إحداثيات منفصل. إذ يحسب البرنامج أولًا
$$M=\max_{1\le n\le N} D_n,$$
ثم يستخدم الرتبة المباشرة
$$r=D_n+1.$$
ولهذا السبب يكون حجم شجرتي Fenwick في ++C وJava مساويًا لـ max_d + 2.
لنفترض أن الموضع الحالي هو \(k\) ورتبته \(r\). كل قيمة سابقة أكبر من \(D_k\) تنتج زوجًا هابطًا جديدًا ينتهي عند \(k\)، ولذلك
$$\text{greater\_left}(k)=\sum_{t=r+1}^{M+1} C(t).$$
وبالمثل، كل زوج هابط سابق ما زالت قيمته الثانية أكبر من \(D_k\) يمكن تمديده إلى ثلاثية صحيحة تنتهي عند \(k\)، لذلك
$$\text{triples\_ending\_here}(k)=\sum_{t=r+1}^{M+1} P(t).$$
بعد ذلك تُحدَّث البنيتان كما يلي:
$$P(r)\leftarrow P(r)+\text{greater\_left}(k),$$
$$C(r)\leftarrow C(r)+1.$$
شجرة Fenwick تعطي هذه المجاميع اللاحقة وتحديثات النقاط بزمن \(O(\log M)\)، ولذلك تكفي شجرتان فقط.
أول عشرين قيمة هي
$$\left(D_1,\dots,D_{20}\right)=\left(1,2,4,4,4,4,6,9,6,4,8,8,4,8,16,8,6,6,8,16\right).$$
وبما أن عدم المساواة صارم، فإن القيم المتساوية لا تضيف شيئًا. على سبيل المثال، الثلاثية \((8,9,10)\) صالحة لأن
$$D_8=9,\qquad D_9=6,\qquad D_{10}=4.$$
والثلاثية \((15,16,17)\) صالحة أيضًا لأن
$$16 \gt 8 \gt 6.$$
أما العدد الكلي للثلاثيات الصحيحة حتى \(20\) فهو
$$14,$$
وهو نفس القيمة التي يتحقق منها السطر count_triples_mod(20) == 14 في ملف ++C.
ملف ++C هو التنفيذ المرجعي. يبدأ ببناء مصفوفة tau حتى kTargetN + 1، ثم يفحص القيم المرجعية d_triangle(7)=6 وTr(20)=14 وTr(100)=5772 وTr(1000)=11174776. بعد ذلك يقوم بمرور أول لإيجاد max_d، ثم بمرور ثانٍ لتنفيذ البرمجة الديناميكية باستخدام شجرتي Fenwick.
نسخة Java تطبق الفكرة الرياضية نفسها، لكنها تخزّن جميع قيم \(D_n\) في المصفوفة dtArr أثناء المرور الأول كي لا تعيد حسابها في المرور الثاني. أما ملف Python فهو طبقة ربط فقط: يترجم حل ++C ويشغله ثم يقرأ الناتج. لذلك فإن التفاصيل التنفيذية الحقيقية موجودة في ++C وJava، بينما Python يكتفي بالتغليف.
لنكتب \(M=\max_{1\le n\le N} D_n\). الغربال الخطي الخاص بدالة القواسم يعمل بزمن \(O(N)\) وبذاكرة \(O(N)\). أما مرحلة العدّ فتجري استعلامين وتحديثين على Fenwick لكل موضع، ومن ثم تحتاج إلى \(O(N\log M)\) زمنًا و\(O(M)\) ذاكرة إضافية للشجرتين. وبالتالي يكون التعقيد الكلي
$$O(N)+O(N\log M)=O(N\log M)$$
زمنًا، مع ذاكرة \(O(N)+O(M)\). وبما أن \(M\) أصغر بكثير من \(N\) عمليًا، فإن هذه الخطة قابلة للتطبيق حتى عند \(N=60{,}000{,}000\).