For a given \(n\), define the stations
$$P_i=\left(2^i \bmod n,\ 3^i \bmod n\right),\qquad 0 \le i \le 2n.$$
An uphill path from \((0,0)\) to \((n,n)\) uses only right and up moves, so the stations visited by such a path must appear in an order whose coordinates never decrease. Let \(S(n)\) be the maximum number of stations that can be visited by one uphill path. The program evaluates
$$\sum_{k=1}^{30} S(k^5).$$
The implementation does not search over grid paths directly. Instead, it reduces the problem to a finite set of modular points and then solves an order problem on those points.
Write
$$n = 2^{\alpha} 3^{\beta} m,\qquad \gcd(m,6)=1.$$
Consider the \(x\)-coordinate \(x_i = 2^i \bmod n\). For every \(i \ge \alpha\), the factor \(2^{\alpha}\) already divides \(2^i\), so modulo \(2^{\alpha}\) the value is fixed at \(0\). On the coprime part \(n / 2^{\alpha}\), the base \(2\) is invertible, hence the remaining behavior is purely periodic with period
$$T_2 = \operatorname{ord}_{n / 2^{\alpha}}(2),$$
with the harmless convention \(T_2=1\) when \(n / 2^{\alpha}=1\). Thus the \(x\)-coordinate is eventually periodic after \(\alpha\) steps.
Exactly the same argument applies to the \(y\)-coordinate \(y_i = 3^i \bmod n\). After \(\beta\) steps it is periodic with period
$$T_3 = \operatorname{ord}_{n / 3^{\beta}}(3),$$
again taking \(T_3=1\) when the modulus equals \(1\).
Therefore the pair sequence \((x_i,y_i)\) is periodic from
$$p = \max(\alpha,\beta)$$
onward, with common period
$$T = \operatorname{lcm}(T_2,T_3).$$
Every station with index \(i \ge p+T\) repeats one already seen in the block \(p, p+1, \dots, p+T-1\). Since the original problem only uses indices \(0 \le i \le 2n\), it is enough to generate
$$M = \min(2n+1,\ p+T)$$
points and then discard duplicates.
After deduplication, sort the distinct stations lexicographically by \(x\) and then by \(y\):
$$Q_1,\dots,Q_r,\qquad Q_j=(x_j,y_j),\qquad x_1 \le x_2 \le \cdots \le x_r.$$
If an uphill path visits stations \(Q_{j_1}, Q_{j_2}, \dots, Q_{j_t}\), then necessarily
$$x_{j_1} \le x_{j_2} \le \cdots \le x_{j_t},\qquad y_{j_1} \le y_{j_2} \le \cdots \le y_{j_t}.$$
Because the list is already sorted by \(x\), the first condition is automatic when we take an increasing index subsequence. So the entire problem becomes
$$S(n)=\operatorname{LNDS}(y_1,y_2,\dots,y_r),$$
where \(\operatorname{LNDS}\) denotes the length of the longest nondecreasing subsequence.
The word nondecreasing matters. Equal \(x\)-coordinates are allowed because a path can move vertically between two stations, and equal \(y\)-coordinates are allowed because it can move horizontally. That is why the implementation uses the patience-sorting variant based on the first tail strictly greater than the new \(y\)-value.
For \(n=22=2\cdot 11\), we have \(\alpha=1\) and \(\beta=0\). Hence
$$T_2=\operatorname{ord}_{11}(2)=10,\qquad T_3=\operatorname{ord}_{22}(3)=5,$$
so
$$p=1,\qquad T=\operatorname{lcm}(10,5)=10,\qquad M=\min(45,11)=11.$$
Thus all relevant stations already occur among the first \(11\) indices. After sorting and removing repeats, the \(y\)-sequence is
$$1,3,9,15,5,1,1,5,15,9,3.$$
Its longest nondecreasing subsequence has length \(5\), so
$$S(22)=5.$$
This matches the checkpoint used by the implementation. The same program also verifies \(S(123)=14\) and \(S(10000)=48\).
The C++, Python, and Java implementations build a smallest-prime-factor table once up to \(30^5\). That table makes Euler's totient function and multiplicative orders fast to evaluate for every modulus \(n=k^5\).
For each \(k\in\{1,\dots,30\}\), the implementation forms \(n=k^5\), computes the preperiod length \(p\) and the common period \(T\), generates the first \(M\) stations, sorts and deduplicates them, and finally applies patience sorting with binary search to the \(y\)-coordinates. The Python entry point reuses the same compiled computation, while the Java version mirrors the same mathematics directly.
For one modulus \(n\), let \(M=\min(2n+1,p+T)\), and let \(r\le M\) be the number of distinct stations after deduplication. Generating the modular points costs \(O(M)\). Sorting the distinct points costs \(O(r\log r)\), and the longest-nondecreasing-subsequence step also costs \(O(r\log r)\). Therefore one evaluation of \(S(n)\) runs in
$$O(r\log r)$$
time and uses \(O(r)\) memory.
Across all \(k \le 30\), the one-time prime-factor sieve up to \(30^5\) is near-linear and uses \(O(30^5)\) memory. After that precomputation, the point ordering work dominates.
Für ein gegebenes \(n\) sind die Stationen definiert durch
$$P_i=\left(2^i \bmod n,\ 3^i \bmod n\right),\qquad 0 \le i \le 2n.$$
Ein Uphill-Pfad von \((0,0)\) nach \((n,n)\) darf sich nur nach rechts und oben bewegen. Daher können besuchte Stationen nur in einer Reihenfolge auftreten, in der beide Koordinaten niemals abnehmen. Sei \(S(n)\) die maximale Zahl von Stationen auf einem solchen Pfad. Gesucht ist
$$\sum_{k=1}^{30} S(k^5).$$
Die Implementierung durchsucht nicht alle Gitterwege. Stattdessen reduziert sie das Problem auf eine endliche Menge modularer Punkte und löst darauf ein Ordnungsproblem.
Schreibe
$$n = 2^{\alpha} 3^{\beta} m,\qquad \gcd(m,6)=1.$$
Für die \(x\)-Koordinate \(x_i = 2^i \bmod n\) gilt: Sobald \(i \ge \alpha\), ist \(2^i\) bereits durch \(2^{\alpha}\) teilbar, also ist der Wert modulo \(2^{\alpha}\) fest gleich \(0\). Auf dem teilerfremden Anteil \(n / 2^{\alpha}\) ist \(2\) invertierbar, also rein periodisch mit Periode
$$T_2 = \operatorname{ord}_{n / 2^{\alpha}}(2),$$
wobei im Sonderfall \(n / 2^{\alpha}=1\) die Konvention \(T_2=1\) verwendet wird. Die \(x\)-Folge ist also nach \(\alpha\) Schritten letztlich periodisch.
Dasselbe gilt für die \(y\)-Koordinate \(y_i = 3^i \bmod n\). Nach \(\beta\) Schritten ist sie periodisch mit
$$T_3 = \operatorname{ord}_{n / 3^{\beta}}(3),$$
und im trivialen Fall wieder \(T_3=1\).
Damit ist die Paarfolge \((x_i,y_i)\) ab
$$p = \max(\alpha,\beta)$$
periodisch, und zwar mit gemeinsamer Periode
$$T = \operatorname{lcm}(T_2,T_3).$$
Jede Station mit Index \(i \ge p+T\) wiederholt daher eine frühere Station aus dem Block \(p,\dots,p+T-1\). Da die Aufgabenstellung ohnehin nur \(0 \le i \le 2n\) betrachtet, genügt es,
$$M = \min(2n+1,\ p+T)$$
Punkte zu erzeugen und anschließend zu deduplizieren.
Nach dem Entfernen von Duplikaten werden die Stationen lexikographisch nach \(x\), dann nach \(y\), sortiert:
$$Q_1,\dots,Q_r,\qquad Q_j=(x_j,y_j),\qquad x_1 \le x_2 \le \cdots \le x_r.$$
Besucht ein Uphill-Pfad die Stationen \(Q_{j_1},Q_{j_2},\dots,Q_{j_t}\), dann muss gelten
$$x_{j_1} \le x_{j_2} \le \cdots \le x_{j_t},\qquad y_{j_1} \le y_{j_2} \le \cdots \le y_{j_t}.$$
Die erste Bedingung ist nach der Sortierung automatisch erfüllt. Damit reduziert sich alles auf die längste nicht fallende Teilfolge der \(y\)-Werte:
$$S(n)=\operatorname{LNDS}(y_1,y_2,\dots,y_r).$$
Die Gleichheit ist wichtig. Zwei Stationen dürfen denselben \(x\)-Wert haben, wenn man sich vertikal bewegt, oder denselben \(y\)-Wert bei horizontaler Bewegung. Deshalb verwendet die Implementierung die nicht fallende Variante der LIS mit binärer Suche nach dem ersten Schwanzwert, der strikt größer ist.
Für \(n=22=2\cdot 11\) ist \(\alpha=1\) und \(\beta=0\). Also
$$T_2=\operatorname{ord}_{11}(2)=10,\qquad T_3=\operatorname{ord}_{22}(3)=5,$$
damit
$$p=1,\qquad T=\operatorname{lcm}(10,5)=10,\qquad M=\min(45,11)=11.$$
Alle relevanten Stationen erscheinen also bereits unter den ersten \(11\) Indizes. Nach Sortierung und Deduplikation lautet die \(y\)-Folge
$$1,3,9,15,5,1,1,5,15,9,3.$$
Ihre längste nicht fallende Teilfolge hat Länge \(5\), also
$$S(22)=5.$$
Genau diesen Kontrollwert prüft die Implementierung. Zusätzlich werden \(S(123)=14\) und \(S(10000)=48\) validiert.
Die C++-, Python- und Java-Implementierungen bauen einmalig eine Tabelle kleinster Primfaktoren bis \(30^5\) auf. Damit lassen sich Eulers \(\varphi\)-Funktion und die benötigten multiplikativen Ordnungen für jedes \(n=k^5\) effizient bestimmen.
Für jedes \(k\in\{1,\dots,30\}\) bildet die Implementierung \(n=k^5\), berechnet Vorlauf \(p\) und Periode \(T\), erzeugt die ersten \(M\) Stationen, sortiert und dedupliziert sie und berechnet schließlich per Patience Sorting mit binärer Suche die Länge der LNDS der \(y\)-Koordinaten. Der Python-Einstieg verwendet dieselbe kompilierte Rechnung; die Java-Version setzt dieselbe Mathematik direkt um.
Für ein einzelnes \(n\) sei \(M=\min(2n+1,p+T)\), und \(r\le M\) sei die Zahl verschiedener Stationen nach der Deduplikation. Das Erzeugen der Punkte kostet \(O(M)\). Das Sortieren kostet \(O(r\log r)\), und auch der LNDS-Schritt kostet \(O(r\log r)\). Somit benötigt eine Auswertung von \(S(n)\)
$$O(r\log r)$$
Zeit und \(O(r)\) Speicher.
Über alle \(k \le 30\) hinweg ist das einmalige Primfaktorsieb bis \(30^5\) nahezu linear und verbraucht \(O(30^5)\) Speicher. Danach dominiert die Punktsortierung.
Verilen bir \(n\) için istasyonlar
$$P_i=\left(2^i \bmod n,\ 3^i \bmod n\right),\qquad 0 \le i \le 2n$$
olarak tanımlanır. \((0,0)\) noktasından \((n,n)\) noktasına giden bir uphill path sadece sağa ve yukarı hareket edebilir; bu yüzden ziyaret edilen istasyonların koordinatları seçilen sırada asla azalamaz. Bir böyle yolun ziyaret edebileceği en büyük istasyon sayısına \(S(n)\) diyelim. Programın hedefi
$$\sum_{k=1}^{30} S(k^5)$$
değerini hesaplamaktır.
Uygulama, grid üzerindeki tüm yolları denemez. Bunun yerine önce modüler nokta kümesini sonlu hale getirir, sonra da bu noktalar üzerinde bir sıralama problemi çözer.
Şöyle yazalım:
$$n = 2^{\alpha} 3^{\beta} m,\qquad \gcd(m,6)=1.$$
\(x_i = 2^i \bmod n\) için, \(i \ge \alpha\) olduğunda \(2^i\) artık \(2^{\alpha}\) ile tam bölünür; dolayısıyla \(2^{\alpha}\) modunda değer sürekli \(0\) olur. Geriye kalan \(n / 2^{\alpha}\) kısmında ise taban \(2\) ile modül aralarında asaldır; bu nedenle davranış tam periyodiktir ve periyot
$$T_2 = \operatorname{ord}_{n / 2^{\alpha}}(2)$$
olur. Eğer \(n / 2^{\alpha}=1\) ise uygulama güvenli biçimde \(T_2=1\) alır. Yani \(x\)-koordinatı \(\alpha\) adımdan sonra periyodiğe girer.
Aynı düşünce \(y_i = 3^i \bmod n\) için de geçerlidir. \(\beta\) adımdan sonra periyot
$$T_3 = \operatorname{ord}_{n / 3^{\beta}}(3)$$
olur; modül \(1\) ise yine \(T_3=1\) alınır.
Böylece çift dizi \((x_i,y_i)\),
$$p = \max(\alpha,\beta)$$
indeksinden itibaren ortak
$$T = \operatorname{lcm}(T_2,T_3)$$
periyoduna sahiptir. Yani \(i \ge p+T\) için gelen her istasyon, daha önce \(p,\dots,p+T-1\) aralığında zaten görülmüştür. Problem zaten yalnızca \(0 \le i \le 2n\) aralığını kullandığı için üretmemiz gereken aday sayısı
$$M = \min(2n+1,\ p+T)$$
olur; sonra tekrar eden noktalar silinir.
Tekrarlar kaldırıldıktan sonra istasyonlar önce \(x\), sonra \(y\) değerine göre sözlük sırasıyla dizilir:
$$Q_1,\dots,Q_r,\qquad Q_j=(x_j,y_j),\qquad x_1 \le x_2 \le \cdots \le x_r.$$
Bir uphill path bu listedeki \(Q_{j_1},Q_{j_2},\dots,Q_{j_t}\) istasyonlarını ziyaret ediyorsa mutlaka
$$x_{j_1} \le x_{j_2} \le \cdots \le x_{j_t},\qquad y_{j_1} \le y_{j_2} \le \cdots \le y_{j_t}$$
olmalıdır. Liste zaten \(x\)'e göre sıralı olduğundan ilk koşul otomatikleşir. Böylece problem sadece \(y\)-değerlerinin en uzun azalmayan alt dizisini bulmaya indirgenir:
$$S(n)=\operatorname{LNDS}(y_1,y_2,\dots,y_r).$$
Burada eşitlik önemlidir. Aynı \(x\)-değerine sahip iki istasyon arasında dikey hareket yapılabilir; aynı \(y\)-değerine sahip iki istasyon arasında ise yatay hareket yapılabilir. Bu nedenle uygulama, klasik sıkı LIS yerine azalmayan sürümü kullanır ve ikili aramada ilk daha büyük kuyruğu arar.
\(n=22=2\cdot 11\) için \(\alpha=1\), \(\beta=0\) olur. Dolayısıyla
$$T_2=\operatorname{ord}_{11}(2)=10,\qquad T_3=\operatorname{ord}_{22}(3)=5,$$
ve
$$p=1,\qquad T=\operatorname{lcm}(10,5)=10,\qquad M=\min(45,11)=11.$$
Yani tüm ilgili istasyonlar ilk \(11\) indeks içinde ortaya çıkar. Sıralama ve tekrar silmeden sonra \(y\)-dizisi
$$1,3,9,15,5,1,1,5,15,9,3$$
olur. En uzun azalmayan alt dizinin uzunluğu \(5\) olduğu için
$$S(22)=5.$$
Bu, uygulamadaki kontrol değeriyle aynıdır. Aynı kod \(S(123)=14\) ve \(S(10000)=48\) eşitliklerini de doğrular.
C++, Python ve Java uygulamaları önce \(30^5\)'e kadar en küçük asal bölen tablosu kurar. Bu tablo sayesinde Euler \(\varphi\) fonksiyonu ve her \(n=k^5\) için gereken çarpımsal mertebeler hızlıca bulunur.
Her \(k\in\{1,\dots,30\}\) için uygulama \(n=k^5\) değerini kurar, önfaz uzunluğu \(p\) ile ortak periyot \(T\)'yi hesaplar, ilk \(M\) istasyonu üretir, bunları sıralayıp tekrarları siler ve son olarak patience sorting ile \(y\)-koordinatlarının LNDS uzunluğunu bulur. Python giriş noktası aynı derlenmiş hesabı yeniden kullanır; Java sürümü ise aynı matematiği doğrudan uygular.
Tek bir \(n\) için \(M=\min(2n+1,p+T)\) ve deduplikasyondan sonra farklı istasyon sayısı \(r\le M\) olsun. Modüler noktaları üretmek \(O(M)\) zaman alır. Sıralama \(O(r\log r)\), LNDS adımı da \(O(r\log r)\) zaman ister. Bu nedenle bir \(S(n)\) hesabı
$$O(r\log r)$$
zamanda çalışır ve \(O(r)\) bellek kullanır.
Tüm \(k \le 30\) için tek seferlik asal bölen süzgeci \(30^5\)'e kadar yaklaşık lineer zamanda hazırlanır ve \(O(30^5)\) bellek kullanır. Sonrasında baskın maliyet nokta sıralamasıdır.
Para un \(n\) dado, las estaciones se definen por
$$P_i=\left(2^i \bmod n,\ 3^i \bmod n\right),\qquad 0 \le i \le 2n.$$
Un camino ascendente desde \((0,0)\) hasta \((n,n)\) solo puede moverse a la derecha y hacia arriba; por tanto, las estaciones visitadas deben aparecer en un orden cuyas coordenadas nunca disminuyan. Sea \(S(n)\) el número máximo de estaciones visitables por un solo camino de ese tipo. El objetivo final es
$$\sum_{k=1}^{30} S(k^5).$$
La implementación no busca todos los caminos del retículo. Primero convierte la familia de estaciones en un conjunto finito de puntos modulares y después resuelve un problema de orden sobre esos puntos.
Escribimos
$$n = 2^{\alpha} 3^{\beta} m,\qquad \gcd(m,6)=1.$$
Para la coordenada \(x_i = 2^i \bmod n\), cuando \(i \ge \alpha\) ya se cumple que \(2^i\) es múltiplo de \(2^{\alpha}\), así que el residuo módulo \(2^{\alpha}\) queda fijado en \(0\). En la parte coprima \(n / 2^{\alpha}\), la base \(2\) es invertible y por ello la sucesión restante es puramente periódica, con período
$$T_2 = \operatorname{ord}_{n / 2^{\alpha}}(2),$$
tomando \(T_2=1\) si \(n / 2^{\alpha}=1\). Por tanto, la coordenada \(x\) es eventualmente periódica a partir de \(\alpha\) pasos.
La misma idea vale para \(y_i = 3^i \bmod n\). Después de \(\beta\) pasos, la periodicidad es
$$T_3 = \operatorname{ord}_{n / 3^{\beta}}(3),$$
y otra vez se usa \(T_3=1\) cuando el módulo es \(1\).
Así, la sucesión de pares \((x_i,y_i)\) es periódica a partir de
$$p = \max(\alpha,\beta)$$
con período común
$$T = \operatorname{lcm}(T_2,T_3).$$
Toda estación con índice \(i \ge p+T\) repite una estación ya vista dentro del bloque \(p,\dots,p+T-1\). Como el problema original solo usa \(0 \le i \le 2n\), basta generar
$$M = \min(2n+1,\ p+T)$$
puntos y luego eliminar duplicados.
Tras quitar repeticiones, las estaciones distintas se ordenan lexicográficamente por \(x\) y después por \(y\):
$$Q_1,\dots,Q_r,\qquad Q_j=(x_j,y_j),\qquad x_1 \le x_2 \le \cdots \le x_r.$$
Si un camino ascendente visita \(Q_{j_1},Q_{j_2},\dots,Q_{j_t}\), necesariamente se cumple
$$x_{j_1} \le x_{j_2} \le \cdots \le x_{j_t},\qquad y_{j_1} \le y_{j_2} \le \cdots \le y_{j_t}.$$
La primera desigualdad queda garantizada por el orden lexicográfico. Por eso el problema entero se reduce a encontrar la longitud de la subsecuencia no decreciente más larga de los valores \(y\):
$$S(n)=\operatorname{LNDS}(y_1,y_2,\dots,y_r).$$
El detalle de “no decreciente” es esencial. Dos estaciones con el mismo \(x\) todavía pueden visitarse con movimientos verticales, y dos estaciones con el mismo \(y\) con movimientos horizontales. Por ello la implementación usa la variante de patience sorting basada en la primera cola estrictamente mayor que el nuevo valor.
Cuando \(n=22=2\cdot 11\), se tiene \(\alpha=1\) y \(\beta=0\). Entonces
$$T_2=\operatorname{ord}_{11}(2)=10,\qquad T_3=\operatorname{ord}_{22}(3)=5,$$
de modo que
$$p=1,\qquad T=\operatorname{lcm}(10,5)=10,\qquad M=\min(45,11)=11.$$
Así, todas las estaciones relevantes ya aparecen en los primeros \(11\) índices. Después de ordenar y deduplicar, la sucesión de \(y\) es
$$1,3,9,15,5,1,1,5,15,9,3.$$
Su subsecuencia no decreciente más larga tiene longitud \(5\), luego
$$S(22)=5.$$
Ese es exactamente uno de los puntos de control usados por la implementación. También se verifican \(S(123)=14\) y \(S(10000)=48\).
Las implementaciones en C++, Python y Java construyen una tabla de menor factor primo hasta \(30^5\). Esa precomputación permite evaluar con rapidez la función \(\varphi\) de Euler y los órdenes multiplicativos necesarios para cada módulo \(n=k^5\).
Para cada \(k\in\{1,\dots,30\}\), la implementación forma \(n=k^5\), calcula el prefijo no periódico \(p\) y el período común \(T\), genera las primeras \(M\) estaciones, las ordena, elimina repeticiones y finalmente aplica patience sorting con búsqueda binaria sobre las coordenadas \(y\). La entrada en Python reutiliza el mismo cálculo compilado, mientras que Java reproduce directamente la misma matemática.
Para un solo valor de \(n\), sea \(M=\min(2n+1,p+T)\), y sea \(r\le M\) el número de estaciones distintas tras deduplicar. Generar los puntos cuesta \(O(M)\). Ordenarlos cuesta \(O(r\log r)\), y el paso de LNDS también cuesta \(O(r\log r)\). En consecuencia, una evaluación de \(S(n)\) requiere
$$O(r\log r)$$
tiempo y \(O(r)\) memoria.
Sobre todos los \(k \le 30\), la criba inicial de factores primos hasta \(30^5\) es casi lineal y usa \(O(30^5)\) memoria. Después de eso, el trabajo dominante es el ordenamiento de puntos.
对给定的 \(n\)，车站定义为
$$P_i=\left(2^i \bmod n,\ 3^i \bmod n\right),\qquad 0 \le i \le 2n.$$
一条从 \((0,0)\) 到 \((n,n)\) 的 uphill path 只能向右或向上走，因此它经过的车站必须按照两个坐标都不下降的顺序出现。记 \(S(n)\) 为一条这样的路径最多能经过多少个车站。程序最终要求的是
$$\sum_{k=1}^{30} S(k^5).$$
实现并不直接枚举网格路径，而是先把车站序列压缩成一个有限的模点集合，再把问题转成这些点上的序关系问题。
写成
$$n = 2^{\alpha} 3^{\beta} m,\qquad \gcd(m,6)=1.$$
看 \(x_i = 2^i \bmod n\)。当 \(i \ge \alpha\) 时，\(2^i\) 已经含有足够多的 \(2\) 因子，所以模 \(2^{\alpha}\) 的部分恒为 \(0\)。而在互素部分 \(n / 2^{\alpha}\) 上，底数 \(2\) 可逆，因此剩余行为是纯周期的，周期为
$$T_2 = \operatorname{ord}_{n / 2^{\alpha}}(2),$$
若 \(n / 2^{\alpha}=1\)，实现中约定 \(T_2=1\)。这说明 \(x\) 坐标在 \(\alpha\) 步之后进入周期。
对 \(y_i = 3^i \bmod n\) 完全类似。经过 \(\beta\) 步后，其周期为
$$T_3 = \operatorname{ord}_{n / 3^{\beta}}(3),$$
若模数为 \(1\)，同样取 \(T_3=1\)。
因此点对序列 \((x_i,y_i)\) 从
$$p = \max(\alpha,\beta)$$
开始周期化，公共周期为
$$T = \operatorname{lcm}(T_2,T_3).$$
凡是 \(i \ge p+T\) 的车站，都会与区间 \(p,\dots,p+T-1\) 中某个更早的车站重复。原题本来只关心 \(0 \le i \le 2n\)，所以只需生成
$$M = \min(2n+1,\ p+T)$$
个候选点，再去重即可。
去重后，把所有不同车站按 \(x\) 再按 \(y\) 做字典序排序：
$$Q_1,\dots,Q_r,\qquad Q_j=(x_j,y_j),\qquad x_1 \le x_2 \le \cdots \le x_r.$$
如果一条 uphill path 访问了 \(Q_{j_1},Q_{j_2},\dots,Q_{j_t}\)，那么必有
$$x_{j_1} \le x_{j_2} \le \cdots \le x_{j_t},\qquad y_{j_1} \le y_{j_2} \le \cdots \le y_{j_t}.$$
由于排序后 \(x\) 已经天然不下降，问题就变成在 \(y\) 序列中寻找最长不下降子序列：
$$S(n)=\operatorname{LNDS}(y_1,y_2,\dots,y_r).$$
这里必须是“不下降”而不是“严格上升”。若两个车站 \(x\) 相同，路径仍可通过竖直移动依次经过；若 \(y\) 相同，也可通过水平移动依次经过。所以实现采用的是 patience sorting 的非严格版本，也就是二分查找第一个严格大于新 \(y\) 的尾值。
当 \(n=22=2\cdot 11\) 时，\(\alpha=1,\ \beta=0\)。于是
$$T_2=\operatorname{ord}_{11}(2)=10,\qquad T_3=\operatorname{ord}_{22}(3)=5,$$
从而
$$p=1,\qquad T=\operatorname{lcm}(10,5)=10,\qquad M=\min(45,11)=11.$$
也就是说，前 \(11\) 个索引已经包含了全部相关车站。排序并去重后，\(y\) 序列为
$$1,3,9,15,5,1,1,5,15,9,3.$$
它的最长不下降子序列长度为 \(5\)，因此
$$S(22)=5.$$
这正是实现中的检查点。程序还验证了 \(S(123)=14\) 与 \(S(10000)=48\)。
C++、Python 和 Java 实现都会先预处理到 \(30^5\) 为止的最小质因子表。借助这张表，可以快速计算 Euler \(\varphi\) 函数以及每个 \(n=k^5\) 所需的乘法阶。
对每个 \(k\in\{1,\dots,30\}\)，实现先构造 \(n=k^5\)，再求出前导长度 \(p\) 与公共周期 \(T\)，生成前 \(M\) 个车站，排序去重，最后对 \(y\) 坐标执行带二分的 patience sorting，得到 \(S(n)\)。Python 入口复用了同一套已编译计算；Java 则直接复现同样的数学流程。
对单个 \(n\)，令 \(M=\min(2n+1,p+T)\)，去重后不同车站数为 \(r\le M\)。生成点需要 \(O(M)\) 时间；排序需要 \(O(r\log r)\)；最长不下降子序列步骤也需要 \(O(r\log r)\)。因此一次 \(S(n)\) 计算的时间复杂度是
$$O(r\log r),$$
空间复杂度为 \(O(r)\)。
对全部 \(k \le 30\) 来说，预处理到 \(30^5\) 的质因子筛是近线性的，并占用 \(O(30^5)\) 内存。之后真正占主导的是点的排序与子序列计算。
Для заданного \(n\) станции определяются как
$$P_i=\left(2^i \bmod n,\ 3^i \bmod n\right),\qquad 0 \le i \le 2n.$$
Восходящий путь из \((0,0)\) в \((n,n)\) может идти только вправо и вверх, поэтому посещаемые станции должны идти в порядке, где обе координаты не убывают. Обозначим через \(S(n)\) максимальное число станций, которое может посетить один такой путь. Нужно вычислить
$$\sum_{k=1}^{30} S(k^5).$$
Реализация не перебирает пути по решетке напрямую. Сначала она сокращает задачу до конечного множества точек по модулю, а затем решает на этом множестве задачу о порядке.
Разложим
$$n = 2^{\alpha} 3^{\beta} m,\qquad \gcd(m,6)=1.$$
Рассмотрим \(x_i = 2^i \bmod n\). При \(i \ge \alpha\) число \(2^i\) уже делится на \(2^{\alpha}\), значит по модулю \(2^{\alpha}\) значение фиксируется в \(0\). На взаимно простой части \(n / 2^{\alpha}\) число \(2\) обратимо, поэтому остается чисто периодическое поведение с периодом
$$T_2 = \operatorname{ord}_{n / 2^{\alpha}}(2),$$
а в случае \(n / 2^{\alpha}=1\) реализация берет \(T_2=1\). Итак, \(x\)-координата становится периодической после \(\alpha\) шагов.
То же верно для \(y_i = 3^i \bmod n\). После \(\beta\) шагов ее период равен
$$T_3 = \operatorname{ord}_{n / 3^{\beta}}(3),$$
и при модуле \(1\) снова используется \(T_3=1\).
Следовательно, последовательность пар \((x_i,y_i)\) периодична начиная с
$$p = \max(\alpha,\beta)$$
с общим периодом
$$T = \operatorname{lcm}(T_2,T_3).$$
Любая станция с индексом \(i \ge p+T\) уже повторяет станцию из блока \(p,\dots,p+T-1\). Так как в исходной задаче рассматриваются только индексы \(0 \le i \le 2n\), достаточно сгенерировать
$$M = \min(2n+1,\ p+T)$$
точек, а затем удалить совпадения.
После удаления повторов все различные станции сортируются лексикографически по \(x\), затем по \(y\):
$$Q_1,\dots,Q_r,\qquad Q_j=(x_j,y_j),\qquad x_1 \le x_2 \le \cdots \le x_r.$$
Если восходящий путь проходит через станции \(Q_{j_1},Q_{j_2},\dots,Q_{j_t}\), то обязательно
$$x_{j_1} \le x_{j_2} \le \cdots \le x_{j_t},\qquad y_{j_1} \le y_{j_2} \le \cdots \le y_{j_t}.$$
Первая цепочка неравенств уже обеспечена сортировкой. Поэтому задача полностью сводится к длине наибольшей неубывающей подпоследовательности координат \(y\):
$$S(n)=\operatorname{LNDS}(y_1,y_2,\dots,y_r).$$
Именно неубывающей, а не строго возрастающей. Одинаковые \(x\) допустимы, потому что между такими станциями можно идти вертикально; одинаковые \(y\) допустимы благодаря горизонтальному движению. Поэтому реализация использует вариант patience sorting с поиском первого хвоста, строго большего нового значения.
При \(n=22=2\cdot 11\) имеем \(\alpha=1\) и \(\beta=0\). Тогда
$$T_2=\operatorname{ord}_{11}(2)=10,\qquad T_3=\operatorname{ord}_{22}(3)=5,$$
следовательно,
$$p=1,\qquad T=\operatorname{lcm}(10,5)=10,\qquad M=\min(45,11)=11.$$
Значит, все релевантные станции уже содержатся среди первых \(11\) индексов. После сортировки и удаления повторов последовательность \(y\) равна
$$1,3,9,15,5,1,1,5,15,9,3.$$
Длина ее наибольшей неубывающей подпоследовательности равна \(5\), поэтому
$$S(22)=5.$$
Это совпадает с контрольным значением в реализации. Аналогично проверяются \(S(123)=14\) и \(S(10000)=48\).
Реализации на C++, Python и Java один раз строят таблицу наименьших простых делителей до \(30^5\). Благодаря ей быстро вычисляются функция Эйлера \(\varphi\) и нужные мультипликативные порядки для каждого модуля \(n=k^5\).
Для каждого \(k\in\{1,\dots,30\}\) реализация формирует \(n=k^5\), находит длину предпериода \(p\) и общий период \(T\), генерирует первые \(M\) станций, сортирует их, удаляет повторы и затем применяет patience sorting с бинарным поиском к координатам \(y\). Python-вход переиспользует ту же компилируемую вычислительную часть, а Java повторяет ту же математику напрямую.
Для одного значения \(n\) обозначим через \(M=\min(2n+1,p+T)\) число сгенерированных кандидатов, а через \(r\le M\) число различных станций после удаления повторов. Генерация точек стоит \(O(M)\). Сортировка требует \(O(r\log r)\), и шаг LNDS тоже требует \(O(r\log r)\). Следовательно, одно вычисление \(S(n)\) работает за
$$O(r\log r)$$
по времени и использует \(O(r)\) памяти.
Для всех \(k \le 30\) предварительное решето простых множителей до \(30^5\) работает почти линейно и требует \(O(30^5)\) памяти. После этой подготовки основная стоимость приходится на сортировку точек и поиск подпоследовательности.
من أجل قيمة معطاة \(n\)، تُعرَّف المحطات بالصيغة
$$P_i=\left(2^i \bmod n,\ 3^i \bmod n\right),\qquad 0 \le i \le 2n.$$
المسار الصاعد من \((0,0)\) إلى \((n,n)\) لا يتحرك إلا إلى اليمين أو إلى الأعلى، ولذلك فلا يمكنه زيارة المحطات إلا بترتيب لا تنخفض فيه الإحداثيات. نرمز بـ \(S(n)\) إلى أكبر عدد من المحطات التي يمكن لمسار واحد من هذا النوع أن يمر بها. والكمية المطلوبة هي
$$\sum_{k=1}^{30} S(k^5).$$
التنفيذ لا يجرّب جميع المسارات على الشبكة مباشرة. بدلًا من ذلك، يحول المسألة أولًا إلى مجموعة منتهية من النقاط المعيارية، ثم يحل مسألة ترتيب على هذه النقاط.
نكتب
$$n = 2^{\alpha} 3^{\beta} m,\qquad \gcd(m,6)=1.$$
لننظر إلى الإحداثي \(x_i = 2^i \bmod n\). عندما يصبح \(i \ge \alpha\)، يكون \(2^i\) قابلًا للقسمة على \(2^{\alpha}\)، ولذلك تثبت قيمته modulo \(2^{\alpha}\) عند \(0\). أما على الجزء المتباين معه \(n / 2^{\alpha}\)، فإن العدد \(2\) قابل للعكس، ومن ثم يصبح السلوك دوريًا صرفًا بفترة
$$T_2 = \operatorname{ord}_{n / 2^{\alpha}}(2),$$
ومع الحالة الخاصة \(n / 2^{\alpha}=1\) تأخذ الخوارزمية convention بسيطة هي \(T_2=1\). إذن إحداثي \(x\) يصبح دوريًا بعد \(\alpha\) خطوة.
وينطبق البرهان نفسه على \(y_i = 3^i \bmod n\). فبعد \(\beta\) خطوة تكون فترته
$$T_3 = \operatorname{ord}_{n / 3^{\beta}}(3),$$
ومع modulus يساوي \(1\) نأخذ أيضًا \(T_3=1\).
إذًا تسلسل الأزواج \((x_i,y_i)\) يصبح دوريًا ابتداءً من
$$p = \max(\alpha,\beta)$$
وبفترة مشتركة مقدارها
$$T = \operatorname{lcm}(T_2,T_3).$$
وأي محطة ذات فهرس \(i \ge p+T\) لا تضيف نقطة جديدة، بل تكرر محطة ظهرت من قبل داخل المدى \(p,\dots,p+T-1\). وبما أن المسألة الأصلية لا تستخدم إلا \(0 \le i \le 2n\)، فيكفي توليد
$$M = \min(2n+1,\ p+T)$$
نقطة مرشحة ثم حذف المكرر منها.
بعد حذف التكرارات، تُرتَّب المحطات المميزة ترتيبًا معجميًا بحسب \(x\) ثم \(y\):
$$Q_1,\dots,Q_r,\qquad Q_j=(x_j,y_j),\qquad x_1 \le x_2 \le \cdots \le x_r.$$
إذا مر مسار صاعد بالمحطات \(Q_{j_1},Q_{j_2},\dots,Q_{j_t}\)، فلا بد أن يتحقق
$$x_{j_1} \le x_{j_2} \le \cdots \le x_{j_t},\qquad y_{j_1} \le y_{j_2} \le \cdots \le y_{j_t}.$$
وبما أن الترتيب بحسب \(x\) مضمون مسبقًا بعد الفرز، فإن المسألة كلها تختزل إلى إيجاد طول أطول متتالية جزئية غير متناقصة من قيم \(y\):
$$S(n)=\operatorname{LNDS}(y_1,y_2,\dots,y_r).$$
كونها غير متناقصة أمر مهم. فالمسار قد يمر بمحطتين لهما نفس \(x\) عبر حركة عمودية، أو نفس \(y\) عبر حركة أفقية. ولهذا تستخدم الخوارزمية نسخة patience sorting التي تبحث ثنائيًا عن أول ذيل أكبر strictly من القيمة الجديدة.
عندما يكون \(n=22=2\cdot 11\)، نحصل على \(\alpha=1\) و\(\beta=0\). وعندها
$$T_2=\operatorname{ord}_{11}(2)=10,\qquad T_3=\operatorname{ord}_{22}(3)=5,$$
ومن ثم
$$p=1,\qquad T=\operatorname{lcm}(10,5)=10,\qquad M=\min(45,11)=11.$$
أي أن جميع المحطات المهمة تظهر أصلًا ضمن أول \(11\) فهرسًا. وبعد الفرز وإزالة التكرار يصبح تسلسل \(y\)
$$1,3,9,15,5,1,1,5,15,9,3.$$
وطول أطول متتالية جزئية غير متناقصة فيه يساوي \(5\)، وبالتالي
$$S(22)=5.$$
وهذا يطابق قيمة التحقق المستخدمة في التنفيذ. كما يجري التحقق أيضًا من \(S(123)=14\) و\(S(10000)=48\).
تنشئ تطبيقات C++ وPython وJava جدولًا لأصغر عامل أولي حتى \(30^5\). وبذلك يصبح حساب دالة أويلر \(\varphi\) والرتب الضربية اللازمة لكل \(n=k^5\) سريعًا.
لكل \(k\in\{1,\dots,30\}\)، تُكوِّن الخوارزمية \(n=k^5\)، ثم تحسب طول المقدمة غير الدورية \(p\) والفترة المشتركة \(T\)، وتولد أول \(M\) محطة، وتفرزها، وتحذف التكرارات، ثم تطبق patience sorting مع بحث ثنائي على إحداثيات \(y\). مدخل Python يعيد استخدام الحساب المترجم نفسه، بينما تعيد Java تطبيق الرياضيات نفسها بصورة مباشرة.
لنفترض من أجل قيمة واحدة لـ \(n\) أن
$$M=\min(2n+1,p+T),$$
وأن عدد المحطات المختلفة بعد حذف التكرار هو \(r\le M\). توليد النقاط يكلف \(O(M)\). أما الفرز فيكلف \(O(r\log r)\)، وخطوة LNDS تكلف أيضًا \(O(r\log r)\). إذن حساب \(S(n)\) الواحد يعمل في
$$O(r\log r)$$
زمنًا ويستخدم \(O(r)\) ذاكرة.
وعبر جميع القيم \(k \le 30\)، فإن منخل العوامل الأولية حتى \(30^5\) ينجز مرة واحدة بزمن شبه خطي ويستهلك \(O(30^5)\) ذاكرة. وبعد هذه التهيئة، يصبح فرز النقاط هو الجزء الغالب في الكلفة.