We study partitions of an integer \(n\) into terms of the form \(2^a3^b\) with \(a,b \ge 0\), under the extra restriction that no chosen term may divide any other chosen term. If \(P(n)\) denotes the number of such valid partitions, the target is
$$\sum_{\substack{q \lt 10^6 \\ q\text{ prime} \\ P(q)=1}} q.$$
Let \(L = 10^6 - 1\). The solution does not test all partitions of all integers up to \(L\). Instead, it converts the validity rule into a strict order constraint on the exponent pairs \((a,b)\).
Every allowed part has the form \(2^a3^b\). For each fixed exponent \(a\), define the row
$$R_a = \{2^a3^b \le L : b \ge 0\}.$$
The code stores these rows as rows[a][b], so row \(a\) is the increasing list
$$2^a,\;2^a3,\;2^a3^2,\;\dots.$$
This already compresses the search space into a small rectangular grid of exponent pairs instead of all integers below \(L\).
For two admissible terms \(x = 2^{a_1}3^{b_1}\) and \(y = 2^{a_2}3^{b_2}\), unique prime factorization gives
$$x \mid y \iff a_1 \le a_2 \text{ and } b_1 \le b_2.$$
So a valid partition is exactly a finite set of lattice points \((a,b)\) that forms an antichain in the product order on exponent pairs.
This has two immediate consequences:
First, a valid partition can contain at most one term from any fixed row \(a\), because inside one row the smaller \(b\)-index always divides the larger one.
Second, if rows are processed in increasing \(a\), then the chosen \(b\)-indices must be strictly decreasing. Indeed, if \(a_1 < a_2\) and \(b_1 \le b_2\), then \(2^{a_1}3^{b_1}\mid 2^{a_2}3^{b_2}\), which is forbidden.
After this reduction, the counting problem becomes a row-by-row depth-first search. The state
$$\mathrm{DFS}(i, j_{\max}, s)$$
means that rows \(0,1,\dots,i-1\) have already been processed, the current partial sum is \(s\), and every future chosen column index \(j\) must satisfy \(j < j_{\max}\). This invariant encodes the strict decrease of the \(3\)-exponents.
From a state \((i,j_{\max},s)\), the code has exactly two kinds of transitions:
Skip row \(i\):
$$\mathrm{DFS}(i+1, j_{\max}, s).$$
Choose the \(j\)-th term of row \(i\), where \(0 \le j < \min(j_{\max}, |R_i|)\) and \(s + 2^i3^j \le L\):
$$\mathrm{DFS}(i+1, j, s + 2^i3^j).$$
The parameter j_limit in the source is exactly this \(j_{\max}\).
Every valid partition has a unique description when its terms are ordered by increasing \(a\). In each row we either take nothing or choose exactly one column index \(b\). Therefore each valid partition corresponds to one unique DFS path.
Conversely, every DFS leaf represents a set of terms with strictly decreasing \(b\)-indices, hence no term can divide another. Therefore the leaf update
$$P(s) \leftarrow P(s) + 1$$
records the exact number of valid partitions of \(s\), not an approximation.
The code checkpoints match the examples from the statement. For 11, the two valid partitions are
$$11 = 2 + 9 = 2^1 3^0 + 2^0 3^2,$$
$$11 = 8 + 3 = 2^3 3^0 + 2^0 3^1,$$
so \(P(11)=2\).
For 17, the partition \(17 = 8 + 9\) is valid, but \(17 = 2 + 6 + 9\) is invalid because \(2 \mid 6\), and \(17 = 16 + 1\) is invalid because \(1 \mid 16\). Hence
$$P(17)=1.$$
Once the array \(P(s)\) has been filled for all \(s \le L\), the rest is straightforward. A sieve of Eratosthenes marks the primes, and the code returns
$$\sum_{\substack{q \lt 10^6 \\ q\text{ prime} \\ P(q)=1}} q.$$
The published sample
$$\sum_{\substack{q \lt 100 \\ q\text{ prime} \\ P(q)=1}} q = 233$$
is used as a correctness checkpoint.
build_terms(limit) constructs the rows \(R_a\). Then partition_counts(limit) runs the DFS described above and fills count[s] with the exact value \(P(s)\). Finally solve(prime_limit) computes a prime sieve and sums precisely those primes \(q\) for which count[q] == 1. The C++, Python, and Java implementations are the same algorithm in three syntaxes.
The count array and prime sieve require \(O(L)\) memory. The recursion depth is \(O(\log_2 L)\), because there is one DFS level per power of 2. The row table itself is tiny, of size only \(O(\log L \cdot \log L)\).
The running time is output-sensitive: the DFS does not examine all subsets of all admissible terms, but only row-compatible selections with strictly decreasing \(b\)-indices, while also pruning any branch whose partial sum already exceeds \(L\). In practice, the cost is governed by the number of reachable valid states, which is far smaller than a naive subset search.
Wir betrachten Zerlegungen einer Zahl \(n\) in Terme der Form \(2^a3^b\) mit \(a,b \ge 0\), unter der Zusatzbedingung, dass kein gewählter Term einen anderen gewählten Term teilen darf. Bezeichnet \(P(n)\) die Anzahl solcher gültigen Zerlegungen, so ist gesucht
$$\sum_{\substack{q \lt 10^6 \\ q\text{ prim} \\ P(q)=1}} q.$$
Sei \(L = 10^6 - 1\). Der Code durchsucht nicht alle Partitionen aller Zahlen bis \(L\), sondern übersetzt die Gültigkeitsbedingung in eine strenge Ordnungsbedingung auf den Exponentenpaaren \((a,b)\).
Jeder erlaubte Summand hat die Form \(2^a3^b\). Für festes \(a\) definieren wir die Zeile
$$R_a = \{2^a3^b \le L : b \ge 0\}.$$
Im Code werden diese Zeilen als rows[a][b] gespeichert; Zeile \(a\) ist also die wachsende Liste
$$2^a,\;2^a3,\;2^a3^2,\;\dots.$$
Damit wird der Suchraum bereits auf ein kleines Gitter von Exponentenpaaren reduziert, statt alle ganzen Zahlen bis \(L\) zu betrachten.
Für zwei zulässige Terme \(x = 2^{a_1}3^{b_1}\) und \(y = 2^{a_2}3^{b_2}\) folgt aus der eindeutigen Primfaktorzerlegung:
$$x \mid y \iff a_1 \le a_2 \text{ und } b_1 \le b_2.$$
Eine gültige Zerlegung ist also genau eine endliche Menge von Gitterpunkten \((a,b)\), die eine Antikette in der Produktordnung bilden.
Daraus ergeben sich zwei unmittelbare Folgerungen:
Erstens kann eine gültige Zerlegung aus jeder festen Zeile \(a\) höchstens einen Term enthalten, denn innerhalb derselben Zeile teilt der kleinere \(b\)-Index immer den größeren.
Zweitens müssen die gewählten \(b\)-Indizes streng fallen, wenn man die Zeilen in wachsendem \(a\) durchläuft. Denn aus \(a_1 < a_2\) und \(b_1 \le b_2\) würde \(2^{a_1}3^{b_1}\mid 2^{a_2}3^{b_2}\) folgen, was verboten ist.
Nach dieser Reduktion wird das Zählproblem zu einer zeilenweisen Tiefensuche. Der Zustand
$$\mathrm{DFS}(i, j_{\max}, s)$$
bedeutet: Die Zeilen \(0,1,\dots,i-1\) sind bereits verarbeitet, die aktuelle Teilsumme ist \(s\), und jeder künftig gewählte Spaltenindex \(j\) muss \(j < j_{\max}\) erfüllen. Diese Invariante kodiert das strenge Fallen der \(3\)-Exponenten.
Aus einem Zustand \((i,j_{\max},s)\) gibt es genau zwei Arten von Übergängen:
Zeile \(i\) überspringen:
$$\mathrm{DFS}(i+1, j_{\max}, s).$$
Den \(j\)-ten Term aus Zeile \(i\) wählen, wobei \(0 \le j < \min(j_{\max}, |R_i|)\) und \(s + 2^i3^j \le L\):
$$\mathrm{DFS}(i+1, j, s + 2^i3^j).$$
Genau diese Schranke wird im Quellcode durch j_limit weitergereicht.
Jede gültige Zerlegung besitzt eine eindeutige Darstellung, wenn ihre Terme nach wachsendem \(a\) geordnet werden. In jeder Zeile wird entweder nichts gewählt oder genau ein Spaltenindex \(b\). Daher entspricht jeder gültigen Zerlegung genau ein DFS-Pfad.
Umgekehrt steht jedes DFS-Blatt für eine Menge von Termen mit streng fallenden \(b\)-Indizes; damit kann kein Term einen anderen teilen. Das Blatt-Update
$$P(s) \leftarrow P(s) + 1$$
liefert also die exakte Anzahl gültiger Zerlegungen von \(s\).
Die Prüfpunkte im Code stimmen mit den Beispielen der Aufgabe überein. Für 11 gibt es genau die zwei gültigen Zerlegungen
$$11 = 2 + 9 = 2^1 3^0 + 2^0 3^2,$$
$$11 = 8 + 3 = 2^3 3^0 + 2^0 3^1,$$
also \(P(11)=2\).
Für 17 ist \(17 = 8 + 9\) gültig, aber \(17 = 2 + 6 + 9\) ist ungültig, weil \(2 \mid 6\), und \(17 = 16 + 1\) ist ungültig, weil \(1 \mid 16\). Daher gilt
$$P(17)=1.$$
Sobald das Array \(P(s)\) für alle \(s \le L\) gefüllt ist, bleibt nur noch ein Primzahlfilter. Ein Sieb des Eratosthenes markiert die Primzahlen, und der Code berechnet
$$\sum_{\substack{q \lt 10^6 \\ q\text{ prim} \\ P(q)=1}} q.$$
Als Korrektheitskontrolle dient das veröffentlichte Beispiel
$$\sum_{\substack{q \lt 100 \\ q\text{ prim} \\ P(q)=1}} q = 233.$$
build_terms(limit) baut die Zeilen \(R_a\) auf. Danach führt partition_counts(limit) die beschriebene DFS aus und füllt count[s] mit dem exakten Wert \(P(s)\). Schließlich berechnet solve(prime_limit) ein Primzahlsieb und summiert genau die Primzahlen \(q\) mit count[q] == 1. Die Versionen in C++, Python und Java implementieren denselben mathematischen Ablauf.
Zählarray und Primzahlsieb benötigen \(O(L)\) Speicher. Die Rekursionstiefe ist \(O(\log_2 L)\), weil es pro Zweierpotenz genau eine DFS-Ebene gibt. Die Zeilentabelle selbst ist mit \(O(\log L \cdot \log L)\) sehr klein.
Die Laufzeit ist ausgabesensitiv: Die DFS betrachtet nicht alle Teilmengen aller zulässigen Terme, sondern nur zeilenkompatible Auswahlen mit streng fallenden \(b\)-Indizes, und sie schneidet jeden Zweig ab, dessen Teilsumme \(L\) bereits überschreitet. Praktisch wird die Laufzeit daher von der Zahl tatsächlich erreichbarer gültiger Zustände bestimmt und ist viel kleiner als eine naive Teilmengensuche.
\(n\) sayısının, \(a,b \ge 0\) olmak üzere \(2^a3^b\) biçimindeki terimlerle yapılan partition'larını inceliyoruz. Ek koşul şudur: seçilen hiçbir terim başka bir seçili terimi bölemez. Bu geçerli partition sayısını \(P(n)\) ile gösterirsek aranan değer
$$\sum_{\substack{q \lt 10^6 \\ q\text{ asal} \\ P(q)=1}} q$$
toplamıdır.
\(L = 10^6 - 1\) olsun. Çözüm, \(L\)'ye kadar tüm sayıların tüm partition'larını denemez; bunun yerine geçerlilik koşulunu üs çiftleri \((a,b)\) üzerinde katı bir sıralama kısıtına dönüştürür.
Her izinli parça \(2^a3^b\) biçimindedir. Sabit bir \(a\) için şu satırı tanımlayalım:
$$R_a = \{2^a3^b \le L : b \ge 0\}.$$
Kod bunları rows[a][b] şeklinde tutar; yani \(a\). satır artan sırayla
$$2^a,\;2^a3,\;2^a3^2,\;\dots$$
değerlerinden oluşur. Böylece arama uzayı, \(L\)'nin altındaki tüm tamsayılar yerine küçük bir üsler ızgarasına sıkıştırılmış olur.
\(x = 2^{a_1}3^{b_1}\) ve \(y = 2^{a_2}3^{b_2}\) için benzersiz asal çarpanlara ayırma doğrudan şunu verir:
$$x \mid y \iff a_1 \le a_2 \text{ ve } b_1 \le b_2.$$
Dolayısıyla geçerli bir partition, üs çiftleri düzleminde ürün sıralamasına göre bir antizincire karşılık gelir.
Bundan iki önemli sonuç çıkar:
Birincisi, sabit bir \(a\) satırından en fazla bir terim seçilebilir; çünkü aynı satırda küçük \(b\) indeksli terim büyük \(b\) indeksli terimi her zaman böler.
İkincisi, satırları artan \(a\) sırasıyla gezersek seçilen \(b\) indeksleri mutlaka sıkı biçimde azalmalıdır. Çünkü \(a_1 < a_2\) ve \(b_1 \le b_2\) ise \(2^{a_1}3^{b_1}\mid 2^{a_2}3^{b_2}\) olur ve bu yasaktır.
Bu indirgemeden sonra sayım problemi satır satır ilerleyen bir derinlik-öncelikli aramaya dönüşür. Durum
$$\mathrm{DFS}(i, j_{\max}, s)$$
şu anlama gelir: \(0,1,\dots,i-1\) satırları işlenmiştir, mevcut kısmi toplam \(s\)'dir ve bundan sonra seçilecek her sütun indeksi \(j\) için \(j < j_{\max}\) olmalıdır. Bu invariant, \(3\) üslerinin sıkı biçimde azalmasını kodlar.
\((i,j_{\max},s)\) durumundan tam olarak iki tür geçiş vardır:
\(i\). satırı atlamak:
$$\mathrm{DFS}(i+1, j_{\max}, s).$$
\(i\). satırdaki \(j\). terimi seçmek; burada \(0 \le j < \min(j_{\max}, |R_i|)\) ve \(s + 2^i3^j \le L\):
$$\mathrm{DFS}(i+1, j, s + 2^i3^j).$$
Kaynak koddaki j_limit değişkeni tam olarak bu \(j_{\max}\) sınırıdır.
Her geçerli partition, terimleri artan \(a\) sırasına göre yazıldığında tek bir temsile sahiptir. Her satırda ya hiçbir şey seçilmez ya da tam bir sütun indeksi \(b\) seçilir; dolayısıyla her geçerli partition tek bir DFS yoluna karşılık gelir.
Tersine, her DFS yaprağı sıkı biçimde azalan \(b\) indekslerine sahip bir terim kümesi üretir; bu nedenle seçilen hiçbir terim başka bir seçili terimi bölemez. Yaprakta yapılan
$$P(s) \leftarrow P(s) + 1$$
güncellemesi bu yüzden sezgisel değil, tam matematiksel sayımdır.
Koddaki checkpoint'ler, problem metnindeki örneklerle birebir uyuşur. 11 için iki geçerli partition vardır:
$$11 = 2 + 9 = 2^1 3^0 + 2^0 3^2,$$
$$11 = 8 + 3 = 2^3 3^0 + 2^0 3^1,$$
dolayısıyla \(P(11)=2\).
17 için \(17 = 8 + 9\) geçerlidir; ancak \(17 = 2 + 6 + 9\) geçersizdir çünkü \(2 \mid 6\), ayrıca \(17 = 16 + 1\) de geçersizdir çünkü \(1 \mid 16\). O halde
$$P(17)=1.$$
\(P(s)\) dizisi tüm \(s \le L\) için doldurulduktan sonra geriye yalnızca asal süzmesi kalır. Eratosthenes eleği asalları işaretler ve kod
$$\sum_{\substack{q \lt 10^6 \\ q\text{ asal} \\ P(q)=1}} q$$
değerini hesaplar. Yayınlanan örnek
$$\sum_{\substack{q \lt 100 \\ q\text{ asal} \\ P(q)=1}} q = 233$$
doğrulama amacıyla checkpoint olarak kullanılır.
build_terms(limit) fonksiyonu \(R_a\) satırlarını kurar. Ardından partition_counts(limit) yukarıdaki DFS'i çalıştırır ve count[s] dizisini tam \(P(s)\) değeriyle doldurur. Son olarak solve(prime_limit) bir asal eleği üretir ve yalnızca count[q] == 1 olan asal \(q\) değerlerini toplar. C++, Python ve Java sürümleri aynı matematiksel hattın üç ayrı sözdizimidir.
Sayım dizisi ve asal eleği \(O(L)\) bellek kullanır. Özyineleme derinliği \(O(\log_2 L)\)'dir; çünkü her \(2\) kuvveti için en fazla bir DFS seviyesi vardır. Satır tablosunun kendisi ise yalnızca \(O(\log L \cdot \log L)\) boyutundadır.
Çalışma süresi çıktı-duyarlıdır: DFS, tüm uygun terimlerin bütün alt kümelerini değil, yalnızca satırla uyumlu ve \(b\) indeksleri sıkı biçimde azalan seçimleri gezer; ayrıca kısmi toplamı \(L\)'yi aşan her dal erken kesilir. Bu yüzden pratik maliyet, erişilebilen geçerli durumların sayısına bağlıdır ve naif bir alt küme taramasından çok daha küçüktür.
Consideramos particiones de un entero \(n\) en términos de la forma \(2^a3^b\) con \(a,b \ge 0\), bajo la restricción adicional de que ningún término elegido puede dividir a otro término elegido. Si \(P(n)\) denota el número de tales particiones válidas, el objetivo es
$$\sum_{\substack{q \lt 10^6 \\ q\text{ primo} \\ P(q)=1}} q.$$
Sea \(L = 10^6 - 1\). La solución no prueba todas las particiones de todos los enteros hasta \(L\); transforma la condición de validez en una restricción de orden estricta sobre los pares de exponentes \((a,b)\).
Cada sumando permitido tiene la forma \(2^a3^b\). Para un \(a\) fijo definimos la fila
$$R_a = \{2^a3^b \le L : b \ge 0\}.$$
El código guarda estas filas como rows[a][b]; por tanto, la fila \(a\) es la lista creciente
$$2^a,\;2^a3,\;2^a3^2,\;\dots.$$
Con ello el espacio de búsqueda queda comprimido en una pequeña rejilla de pares de exponentes en lugar de todos los enteros menores que \(L\).
Para dos términos admisibles \(x = 2^{a_1}3^{b_1}\) y \(y = 2^{a_2}3^{b_2}\), la factorización prima única implica
$$x \mid y \iff a_1 \le a_2 \text{ y } b_1 \le b_2.$$
Así, una partición válida es exactamente un conjunto finito de puntos \((a,b)\) que forma una anticadena en el orden producto.
De aquí se obtienen dos consecuencias inmediatas:
Primero, una partición válida no puede contener más de un término de una misma fila \(a\), porque dentro de la misma fila el término con menor índice \(b\) siempre divide al de mayor índice.
Segundo, si recorremos las filas en orden creciente de \(a\), los índices \(b\) elegidos deben decrecer estrictamente. En efecto, si \(a_1 < a_2\) y \(b_1 \le b_2\), entonces \(2^{a_1}3^{b_1}\mid 2^{a_2}3^{b_2}\), lo cual está prohibido.
Tras esta reducción, el conteo se convierte en una búsqueda en profundidad fila por fila. El estado
$$\mathrm{DFS}(i, j_{\max}, s)$$
significa que las filas \(0,1,\dots,i-1\) ya fueron procesadas, la suma parcial actual es \(s\), y todo índice futuro \(j\) debe satisfacer \(j < j_{\max}\). Este invariante codifica el decrecimiento estricto de los exponentes de 3.
Desde un estado \((i,j_{\max},s)\) el código tiene exactamente dos tipos de transición:
Omitir la fila \(i\):
$$\mathrm{DFS}(i+1, j_{\max}, s).$$
Elegir el término \(j\)-ésimo de la fila \(i\), donde \(0 \le j < \min(j_{\max}, |R_i|)\) y \(s + 2^i3^j \le L\):
$$\mathrm{DFS}(i+1, j, s + 2^i3^j).$$
La variable j_limit del código fuente es exactamente este \(j_{\max}\).
Toda partición válida tiene una representación única cuando sus términos se ordenan por \(a\) creciente. En cada fila o no se toma nada o se elige exactamente un índice \(b\). Por ello cada partición válida corresponde a un único camino DFS.
Recíprocamente, cada hoja del DFS produce un conjunto de términos con índices \(b\) estrictamente decrecientes; por tanto, ningún término puede dividir a otro. La actualización terminal
$$P(s) \leftarrow P(s) + 1$$
registra entonces el número exacto de particiones válidas de \(s\).
Los checkpoints del código coinciden con los ejemplos del enunciado. Para 11 existen exactamente dos particiones válidas:
$$11 = 2 + 9 = 2^1 3^0 + 2^0 3^2,$$
$$11 = 8 + 3 = 2^3 3^0 + 2^0 3^1,$$
por lo tanto \(P(11)=2\).
Para 17, \(17 = 8 + 9\) es válida, pero \(17 = 2 + 6 + 9\) es inválida porque \(2 \mid 6\), y \(17 = 16 + 1\) también es inválida porque \(1 \mid 16\). Así pues,
$$P(17)=1.$$
Una vez calculado \(P(s)\) para todo \(s \le L\), el resto es aritmética elemental. Una criba de Eratóstenes marca los primos y el código devuelve
$$\sum_{\substack{q \lt 10^6 \\ q\text{ primo} \\ P(q)=1}} q.$$
El ejemplo publicado
$$\sum_{\substack{q \lt 100 \\ q\text{ primo} \\ P(q)=1}} q = 233$$
se usa como verificación de corrección.
build_terms(limit) construye las filas \(R_a\). Luego partition_counts(limit) ejecuta el DFS anterior y llena count[s] con el valor exacto \(P(s)\). Por último, solve(prime_limit) calcula una criba de primos y suma exactamente aquellos primos \(q\) para los que count[q] == 1. Las versiones en C++, Python y Java implementan la misma tubería matemática.
El arreglo de conteos y la criba de primos requieren memoria \(O(L)\). La profundidad de la recursión es \(O(\log_2 L)\), porque hay un nivel DFS por cada potencia de 2. La tabla de filas es muy pequeña: solo \(O(\log L \cdot \log L)\).
El tiempo de ejecución es sensible a la salida: el DFS no recorre todos los subconjuntos de todos los términos admisibles, sino solo selecciones compatibles por filas y con índices \(b\) estrictamente decrecientes, además de podar toda rama cuya suma parcial ya supera \(L\). En la práctica, el costo está gobernado por el número de estados válidos alcanzables, muy inferior al de una búsqueda ingenua sobre subconjuntos.
我们考虑把整数 \(n\) 拆分为若干项 \(2^a3^b\)（其中 \(a,b \ge 0\)）之和，并要求任意两个被选中的项之间都不存在“一个整除另一个”的关系。记这样的有效划分个数为 \(P(n)\)，则目标是
$$\sum_{\substack{q \lt 10^6 \\ q\text{为素数} \\ P(q)=1}} q.$$
设 \(L = 10^6 - 1\)。程序并不是枚举所有不超过 \(L\) 的整数的所有划分，而是先把“合法性条件”改写成指数对 \((a,b)\) 上的严格顺序约束。
每个允许的部件都形如 \(2^a3^b\)。对固定的 \(a\)，定义一行
$$R_a = \{2^a3^b \le L : b \ge 0\}.$$
代码把这些行存成 rows[a][b]，因此第 \(a\) 行就是递增序列
$$2^a,\;2^a3,\;2^a3^2,\;\dots.$$
这样一来，搜索空间被压缩成一个很小的指数网格，而不是 \(L\) 以下的所有整数。
对两个可选项 \(x = 2^{a_1}3^{b_1}\) 与 \(y = 2^{a_2}3^{b_2}\)，由唯一分解可直接得到
$$x \mid y \iff a_1 \le a_2 \text{ 且 } b_1 \le b_2.$$
因此，一个有效划分恰好对应于指数平面上的一个反链。
这立刻推出两个关键事实：
第一，同一行 \(a\) 中至多只能选一个元素，因为同一行里较小的 \(b\) 总会整除较大的 \(b\)。
第二，如果按 \(a\) 递增的顺序处理各行，那么被选中的 \(b\) 下标必须严格递减。否则若 \(a_1 < a_2\) 且 \(b_1 \le b_2\)，就会有 \(2^{a_1}3^{b_1}\mid 2^{a_2}3^{b_2}\)，与题意冲突。
经过上述化简，计数问题变成逐行进行的深度优先搜索。状态
$$\mathrm{DFS}(i, j_{\max}, s)$$
表示：第 \(0,1,\dots,i-1\) 行已经处理完，当前部分和为 \(s\)，今后所有被选中的列下标 \(j\) 都必须满足 \(j < j_{\max}\)。这个不变量正是“3 的指数严格递减”的编码。
从状态 \((i,j_{\max},s)\) 出发，代码只有两类转移：
跳过第 \(i\) 行：
$$\mathrm{DFS}(i+1, j_{\max}, s).$$
选择第 \(i\) 行的第 \(j\) 项，其中 \(0 \le j < \min(j_{\max}, |R_i|)\) 且 \(s + 2^i3^j \le L\)：
$$\mathrm{DFS}(i+1, j, s + 2^i3^j).$$
源码中的 j_limit 就是这个 \(j_{\max}\)。
任意一个有效划分，只要按 \(a\) 从小到大排列，其表示就是唯一的。每一行要么不选，要么只选唯一一个列下标 \(b\)，因此它对应唯一的一条 DFS 路径。
反过来，每个 DFS 叶子产生的都是 \(b\) 下标严格递减的一组项，所以任意两项之间都不可能存在整除关系。于是叶子处的更新
$$P(s) \leftarrow P(s) + 1$$
给出的正是 \(s\) 的有效划分精确个数。
代码中的检查点与题目示例完全一致。对 11，有且仅有两种有效划分：
$$11 = 2 + 9 = 2^1 3^0 + 2^0 3^2,$$
$$11 = 8 + 3 = 2^3 3^0 + 2^0 3^1,$$
因此 \(P(11)=2\)。
对 17，\(17 = 8 + 9\) 是有效的；但 \(17 = 2 + 6 + 9\) 无效，因为 \(2 \mid 6\)；\(17 = 16 + 1\) 也无效，因为 \(1 \mid 16\)。所以
$$P(17)=1.$$
当 \(P(s)\) 对所有 \(s \le L\) 都算出以后，剩下的只是筛素数。程序用埃拉托斯特尼筛标记素数，并计算
$$\sum_{\substack{q \lt 10^6 \\ q\text{为素数} \\ P(q)=1}} q.$$
题目给出的样例
$$\sum_{\substack{q \lt 100 \\ q\text{为素数} \\ P(q)=1}} q = 233$$
被用作正确性检查。
build_terms(limit) 构造各行 \(R_a\)。然后 partition_counts(limit) 执行上述 DFS，把 count[s] 填成精确的 \(P(s)\)。最后 solve(prime_limit) 计算素数筛，并把所有满足 count[q] == 1 的素数 \(q\) 相加。C++、Python 和 Java 版本只是同一算法的三种语法实现。
计数数组和素数筛都需要 \(O(L)\) 空间。递归深度是 \(O(\log_2 L)\)，因为每个 2 的幂对应一层 DFS。行表本身非常小，仅为 \(O(\log L \cdot \log L)\) 规模。
运行时间是输出敏感的：DFS 并不会遍历所有可选项的全部子集，而只会遍历“按行兼容且 \(b\) 下标严格递减”的选择，同时任何部分和已经超过 \(L\) 的分支都会立刻剪枝。因此实际成本由可达的有效状态数决定，远小于朴素的子集暴力搜索。
Рассматриваются разбиения числа \(n\) на слагаемые вида \(2^a3^b\), где \(a,b \ge 0\), при дополнительном условии: ни одно выбранное слагаемое не должно делить другое выбранное слагаемое. Если \(P(n)\) обозначает число таких корректных разбиений, то требуется вычислить
$$\sum_{\substack{q \lt 10^6 \\ q\text{ простое} \\ P(q)=1}} q.$$
Положим \(L = 10^6 - 1\). Решение не перебирает все разбиения всех чисел до \(L\); вместо этого оно переводит условие корректности в строгий порядок на парах показателей \((a,b)\).
Каждая допустимая часть имеет вид \(2^a3^b\). Для фиксированного \(a\) введём строку
$$R_a = \{2^a3^b \le L : b \ge 0\}.$$
В программе эти строки хранятся как rows[a][b]; значит, строка \(a\) есть возрастающий список
$$2^a,\;2^a3,\;2^a3^2,\;\dots.$$
Тем самым пространство поиска сжимается до небольшой решётки показателей, а не всех целых чисел меньше \(L\).
Для двух допустимых слагаемых \(x = 2^{a_1}3^{b_1}\) и \(y = 2^{a_2}3^{b_2}\) из единственности разложения на простые множители следует
$$x \mid y \iff a_1 \le a_2 \text{ и } b_1 \le b_2.$$
Следовательно, корректное разбиение есть в точности конечное множество точек \((a,b)\), образующее антицепь в произведённом порядке.
Отсюда немедленно следуют два ключевых факта:
Во-первых, из одной фиксированной строки \(a\) можно взять не более одного слагаемого, потому что внутри строки элемент с меньшим \(b\) всегда делит элемент с большим \(b\).
Во-вторых, если обрабатывать строки в порядке возрастания \(a\), то выбранные индексы \(b\) должны строго убывать. Иначе из \(a_1 < a_2\) и \(b_1 \le b_2\) следовало бы \(2^{a_1}3^{b_1}\mid 2^{a_2}3^{b_2}\), что запрещено.
После этого сведения задача подсчёта превращается в поиск в глубину по строкам. Состояние
$$\mathrm{DFS}(i, j_{\max}, s)$$
означает, что строки \(0,1,\dots,i-1\) уже обработаны, текущая частичная сумма равна \(s\), а любой будущий выбранный индекс \(j\) обязан удовлетворять условию \(j < j_{\max}\). Этот инвариант кодирует строгое убывание показателей степени тройки.
Из состояния \((i,j_{\max},s)\) есть ровно два типа переходов:
Пропустить строку \(i\):
$$\mathrm{DFS}(i+1, j_{\max}, s).$$
Выбрать \(j\)-й элемент из строки \(i\), где \(0 \le j < \min(j_{\max}, |R_i|)\) и \(s + 2^i3^j \le L\):
$$\mathrm{DFS}(i+1, j, s + 2^i3^j).$$
Именно эту верхнюю границу в исходнике хранит переменная j_limit.
У любого корректного разбиения есть единственное представление, если упорядочить его слагаемые по возрастанию \(a\). В каждой строке либо ничего не выбирается, либо выбирается ровно один индекс \(b\); значит, каждому корректному разбиению соответствует единственный путь DFS.
Обратно, каждый лист DFS задаёт набор слагаемых со строго убывающими индексами \(b\), а значит, никакое из них не делит другое. Поэтому обновление
$$P(s) \leftarrow P(s) + 1$$
даёт точное число корректных разбиений суммы \(s\).
Контрольные точки в коде совпадают с примерами из условия. Для 11 существуют ровно два корректных разбиения:
$$11 = 2 + 9 = 2^1 3^0 + 2^0 3^2,$$
$$11 = 8 + 3 = 2^3 3^0 + 2^0 3^1,$$
следовательно, \(P(11)=2\).
Для 17 разбиение \(17 = 8 + 9\) корректно, но \(17 = 2 + 6 + 9\) некорректно, так как \(2 \mid 6\), а \(17 = 16 + 1\) некорректно, так как \(1 \mid 16\). Значит,
$$P(17)=1.$$
После того как массив \(P(s)\) заполнен для всех \(s \le L\), остаётся только отфильтровать простые числа. Решето Эратосфена отмечает простые, и программа вычисляет
$$\sum_{\substack{q \lt 10^6 \\ q\text{ простое} \\ P(q)=1}} q.$$
Опубликованный пример
$$\sum_{\substack{q \lt 100 \\ q\text{ простое} \\ P(q)=1}} q = 233$$
используется как проверка корректности.
build_terms(limit) строит строки \(R_a\). Затем partition_counts(limit) выполняет описанный DFS и заполняет массив count[s] точным значением \(P(s)\). Наконец, solve(prime_limit) строит решето простых и суммирует именно те простые \(q\), для которых count[q] == 1. Версии на C++, Python и Java реализуют один и тот же алгоритм.
Массив подсчёта и решето простых требуют \(O(L)\) памяти. Глубина рекурсии равна \(O(\log_2 L)\), поскольку на каждую степень двойки приходится один уровень DFS. Таблица строк сама по себе очень мала: всего \(O(\log L \cdot \log L)\).
Время работы чувствительно к числу достижимых состояний: DFS не перебирает все подмножества всех допустимых слагаемых, а рассматривает только совместимые по строкам выборы со строго убывающими индексами \(b\), одновременно отсеивая ветви, у которых частичная сумма уже превысила \(L\). Поэтому практическая стоимость существенно меньше наивного перебора всех подмножеств.
ننظر إلى تمثيلات العدد \(n\) كمجموع حدود من الشكل \(2^a3^b\) حيث \(a,b \ge 0\)، مع شرط إضافي هو أن أي حد مختار لا يجوز أن يقسم حدًا مختارًا آخر. إذا رمزنا بعدد هذه التقسيمات الصحيحة بـ \(P(n)\)، فالمطلوب هو حساب
$$\sum_{\substack{q \lt 10^6 \\ q\text{ أولي} \\ P(q)=1}} q.$$
لنضع \(L = 10^6 - 1\). الحل لا يجرّب جميع تقسيمات جميع الأعداد حتى \(L\)، بل يحوّل شرط الصحة إلى قيد ترتيب صارم على أزواج الأسس \((a,b)\).
كل جزء مسموح له الصورة \(2^a3^b\). ولكل \(a\) ثابت نعرّف الصف
$$R_a = \{2^a3^b \le L : b \ge 0\}.$$
يخزن الكود هذه الصفوف على هيئة rows[a][b]، ولذلك يكون الصف \(a\) هو القائمة المتزايدة
$$2^a,\;2^a3,\;2^a3^2,\;\dots.$$
وبهذا يُضغط فضاء البحث إلى شبكة صغيرة من أزواج الأسس بدلًا من جميع الأعداد الصحيحة الأصغر من \(L\).
إذا كان \(x = 2^{a_1}3^{b_1}\) و\(y = 2^{a_2}3^{b_2}\)، فإن التحليل الأولي الفريد يعطي مباشرة
$$x \mid y \iff a_1 \le a_2 \text{ و } b_1 \le b_2.$$
إذن التقسيم الصحيح يطابق تمامًا مجموعة من نقاط الشبكة \((a,b)\) تشكل سلسلة مضادة في ترتيب الجداء.
ومن ذلك نحصل فورًا على نتيجتين أساسيتين:
أولًا، لا يمكن أن يحتوي تقسيم صحيح على أكثر من حد واحد من الصف نفسه \(a\)، لأن الحد ذو \(b\) الأصغر داخل الصف نفسه يقسم الحد ذو \(b\) الأكبر دائمًا.
ثانيًا، إذا عالجنا الصفوف بترتيب \(a\) المتزايد، فيجب أن تكون مؤشرات \(b\) المختارة متناقصة تناقصًا صارمًا. ذلك لأن \(a_1 < a_2\) مع \(b_1 \le b_2\) يؤدي إلى \(2^{a_1}3^{b_1}\mid 2^{a_2}3^{b_2}\)، وهذا ممنوع.
بعد هذا الاختزال، تتحول مهمة العد إلى بحث عمقي سطرًا بعد سطر. الحالة
$$\mathrm{DFS}(i, j_{\max}, s)$$
تعني أن الصفوف \(0,1,\dots,i-1\) قد عولجت بالفعل، وأن المجموع الجزئي الحالي هو \(s\)، وأن أي مؤشر عمود مستقبلي \(j\) يجب أن يحقق \(j < j_{\max}\). هذا الثابت يشفّر التناقص الصارم في أسس العدد 3.
ومن الحالة \((i,j_{\max},s)\) يوجد نوعان فقط من الانتقالات:
تجاوز الصف \(i\):
$$\mathrm{DFS}(i+1, j_{\max}, s).$$
اختيار الحد رقم \(j\) من الصف \(i\)، حيث \(0 \le j < \min(j_{\max}, |R_i|)\) و\(s + 2^i3^j \le L\):
$$\mathrm{DFS}(i+1, j, s + 2^i3^j).$$
المتغير j_limit في المصدر هو بالضبط هذا الحد \(j_{\max}\).
لكل تقسيم صحيح تمثيل وحيد إذا رتبنا حدوده بحسب \(a\) تصاعديًا. ففي كل صف إما ألا نختار شيئًا أو نختار مؤشرًا واحدًا فقط \(b\)، ولذلك يقابل كل تقسيم صحيح مسار DFS واحدًا لا غير.
وبالعكس، كل ورقة في DFS تعطي مجموعة حدود ذات مؤشرات \(b\) متناقصة تناقصًا صارمًا، وبالتالي لا يمكن لأي حد منها أن يقسم حدًا آخر. لذلك فإن التحديث النهائي
$$P(s) \leftarrow P(s) + 1$$
يعطي العدد الدقيق للتقسيمات الصحيحة للمجموع \(s\).
نقاط التحقق في الكود تطابق أمثلة نص المسألة. بالنسبة إلى 11 يوجد تقسيمان صحيحان فقط:
$$11 = 2 + 9 = 2^1 3^0 + 2^0 3^2,$$
$$11 = 8 + 3 = 2^3 3^0 + 2^0 3^1,$$
إذن \(P(11)=2\).
أما 17 فالتقسيم \(17 = 8 + 9\) صحيح، لكن \(17 = 2 + 6 + 9\) غير صحيح لأن \(2 \mid 6\)، وكذلك \(17 = 16 + 1\) غير صحيح لأن \(1 \mid 16\). ومن ثم
$$P(17)=1.$$
بعد حساب \(P(s)\) لكل \(s \le L\)، يبقى فقط ترشيح الأعداد الأولية. يستخدم البرنامج منخل إراتوستينس، ثم يحسب
$$\sum_{\substack{q \lt 10^6 \\ q\text{ أولي} \\ P(q)=1}} q.$$
كما تُستخدم العينة المنشورة
$$\sum_{\substack{q \lt 100 \\ q\text{ أولي} \\ P(q)=1}} q = 233$$
بوصفها نقطة تحقق للصحة.
تقوم الدالة build_terms(limit) ببناء الصفوف \(R_a\). ثم تنفّذ partition_counts(limit) عملية DFS السابقة وتملأ المصفوفة count[s] بالقيمة الدقيقة \(P(s)\). وأخيرًا تحسب solve(prime_limit) منخلًا للأعداد الأولية وتجمع فقط تلك القيم الأولية \(q\) التي تحقق count[q] == 1. نسخ C++ وPython وJava تطبق الخوارزمية الرياضية نفسها.
مصفوفة العد ومنخل الأعداد الأولية يحتاجان إلى ذاكرة \(O(L)\). وعمق الاستدعاء التعاودي هو \(O(\log_2 L)\)، لأن هناك مستوى DFS واحدًا لكل قوة من قوى 2. أما جدول الصفوف نفسه فصغير جدًا، وحجمه \(O(\log L \cdot \log L)\) فقط.
زمن التنفيذ يعتمد على عدد الحالات القابلة للوصول: فالـ DFS لا يمر على جميع المجموعات الجزئية لكل الحدود المسموح بها، بل يزور فقط الاختيارات المتوافقة صفّيًا والتي تمتلك مؤشرات \(b\) متناقصة تناقصًا صارمًا، مع قص أي فرع يتجاوز مجموعه الجزئي \(L\). لذلك تكون الكلفة العملية أصغر كثيرًا من بحث ساذج على جميع المجموعات الجزئية.