The problem asks for the largest total number of integers in \(1,\dots,N\) that can be arranged into pairwise non-overlapping local \(123\)-blocks. Every positive integer has a unique representation
$$n=m\,2^a3^b,\qquad \gcd(m,6)=1,$$
so the search splits into independent components indexed by the part \(m\) that is coprime to \(6\). Inside one component, only \(2^a3^b\)-smooth multipliers matter, and the final answer is the sum of the optimal local contributions.
Write \(A(N)\) for the required optimum. The fast solution has two layers: first solve one component exactly, then sum those component values over all possible \(m\).
Fix \(m\) with \(\gcd(m,6)=1\) and let
$$L=\left\lfloor\frac{N}{m}\right\rfloor.$$
Every integer in \(1,\dots,N\) whose \(6\)-free part is \(m\) can be written uniquely as \(m s\) with
$$\mathcal{S}(L)=\{2^a3^b\le L: a,b\ge 0\}.$$
Different values of \(m\) never mix, so the global optimum is a sum of independent component optima:
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}} G\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right),$$
where \(G(L)\) denotes the best contribution of one component with smooth bound \(L\).
For a smooth base \(s\in \mathcal{S}(L)\), the local block is
$$B_L(s)=\{s,2s,3s\}\cap [1,L].$$
After multiplying by \(m\), this becomes \(\{ms,2ms,3ms\}\cap [1,N]\). Its size is
$$|B_L(s)|=1+\mathbf{1}_{2s\le L}+\mathbf{1}_{3s\le L}.$$
So inside one component we want a collection of smooth bases whose blocks do not overlap, maximizing the total weight contributed by those block sizes.
Two local blocks \(B_L(s)\) and \(B_L(t)\) overlap exactly when
$$i s=j t\quad \text{for some } i,j\in\{1,2,3\}.$$
For distinct \(s\) and \(t\), this is equivalent to
$$\frac{t}{s}\in \left\{2,3,\frac{3}{2},\frac{1}{2},\frac{1}{3},\frac{2}{3}\right\}.$$
If we write \(s=2^a3^b\), these six ratios become the six neighbor moves
$$ (a,b)\leftrightarrow(a\pm 1,b),\qquad (a,b)\leftrightarrow(a,b\pm 1),\qquad (a,b)\leftrightarrow(a+1,b-1),\qquad (a,b)\leftrightarrow(a-1,b+1). $$
Thus \(G(L)\) is a maximum-weight independent-set value on the triangular lattice formed by the exponent pairs \((a,b)\) with \(2^a3^b\le L\).
The key structural fact used by the implementations is that this graph optimization has a simple exact value:
$$G(L)=|\mathcal{S}(L)|-|\mathcal{E}\cap [1,L]|,$$
where the exceptional smooth numbers are
$$\mathcal{E}=\{6,24,54\}\cup \{384\cdot 8^t:t\ge 0\}\cup \{243\cdot 27^t:t\ge 0\}.$$
So every \(2^a3^b\)-smooth number normally contributes one unit to the optimum, and only the explicit exceptional values subtract one unit. All three implementations are based on this identity.
Substituting the component formula into the outer sum gives
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}}\left(|\mathcal{S}(\lfloor N/m\rfloor)|-|\mathcal{E}\cap [1,\lfloor N/m\rfloor]|\right).$$
This already removes the hard combinatorial search. The remaining work is purely arithmetic: count smooth numbers, count exceptional smooth numbers, and aggregate them over the quotient values \(\lfloor N/m\rfloor\).
List the smooth numbers in increasing order. Between two consecutive smooth breakpoints, neither \(|\mathcal{S}(L)|\) nor \(|\mathcal{E}\cap [1,L]|\) changes, because every exceptional number is itself smooth. Hence \(G(L)\) is constant on each interval \([L,R]\), where \(L\) is a smooth number and \(R\) is the next smooth number minus \(1\), or \(R=N\) for the final interval.
For such an interval, the condition
$$L\le \left\lfloor\frac{N}{m}\right\rfloor\le R$$
is equivalent to
$$m_{\mathrm{low}}=\left\lfloor\frac{N}{R+1}\right\rfloor+1,\qquad m_{\mathrm{high}}=\left\lfloor\frac{N}{L}\right\rfloor.$$
The count of integers up to \(x\) that are coprime to \(6\) is
$$C(x)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{x}{6}\right\rfloor.$$
Therefore one quotient interval contributes
$$G(L)\left(C(m_{\mathrm{high}})-C(m_{\mathrm{low}}-1)\right).$$
The integers up to \(20\) that are \(2^a3^b\)-smooth are
$$1,2,3,4,6,8,9,12,16,18,$$
so \(|\mathcal{S}(20)|=10\). At this scale the only exceptional value is \(6\), so
$$G(20)=10-1=9.$$
The integers \(m\le 20\) with \(\gcd(m,6)=1\) are
$$1,5,7,11,13,17,19.$$
The corresponding quotient values are
$$\left\lfloor\frac{20}{1}\right\rfloor=20,\quad \left\lfloor\frac{20}{5}\right\rfloor=4,\quad \left\lfloor\frac{20}{7}\right\rfloor=2,\quad \left\lfloor\frac{20}{11}\right\rfloor=\left\lfloor\frac{20}{13}\right\rfloor=\left\lfloor\frac{20}{17}\right\rfloor=\left\lfloor\frac{20}{19}\right\rfloor=1.$$
Since \(G(4)=4\), \(G(2)=2\), and \(G(1)=1\), we get
$$A(20)=9+4+2+1+1+1+1=19,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations never build the conflict graph explicitly. Instead they first generate all \(2^a3^b\)-smooth numbers up to \(N\), sort them, and remove duplicates. They also generate the exceptional subset up to the same limit.
Next, they scan the smooth list once in increasing order. At each smooth breakpoint they update the current component value \(G(L)\): ordinary smooth numbers increase it by one, while exceptional smooth numbers leave it unchanged because they represent the one-unit loss encoded by the closed form.
Finally, the implementation walks through consecutive breakpoint intervals \([L,R]\), converts each interval into the matching range of \(m\)-values, counts how many of those \(m\) are coprime to \(6\) with the inclusion-exclusion formula for \(C(x)\), and adds the resulting block contribution. Python gets arbitrary-precision arithmetic automatically, while the compiled implementations use a wider accumulator for the final sum.
Let \(S(N)=|\mathcal{S}(N)|\). Since \(2^a3^b\le N\) implies \(0\le a\le \lfloor \log_2 N\rfloor\) and \(0\le b\le \lfloor \log_3 N\rfloor\), we have \(S(N)=O((\log N)^2)\). Generating and sorting the smooth list costs \(O(S(N)\log S(N))\), the exceptional list has only \(O(\log N)\) terms, and the final sweep over the breakpoint intervals is \(O(S(N))\). Memory usage is \(O(S(N))=O((\log N)^2)\).
Gesucht ist die maximale Gesamtzahl von ganzen Zahlen in \(1,\dots,N\), die sich in paarweise disjunkte lokale \(123\)-Blöcke zerlegen lassen. Jede positive Zahl besitzt die eindeutige Darstellung
$$n=m\,2^a3^b,\qquad \gcd(m,6)=1,$$
weshalb das Problem in unabhängige Komponenten zerfällt, die durch den zu \(6\) teilerfremden Anteil \(m\) bestimmt werden. Innerhalb einer Komponente spielen nur \(2^a3^b\)-glatte Multiplikatoren eine Rolle, und die Gesamtlösung ist die Summe der optimalen lokalen Beiträge.
Bezeichne das gesuchte Optimum mit \(A(N)\). Die schnelle Lösung arbeitet in zwei Schritten: zuerst wird eine einzelne Komponente exakt gelöst, danach werden diese Komponentenwerte über alle möglichen \(m\) aufsummiert.
Fixiere \(m\) mit \(\gcd(m,6)=1\) und setze
$$L=\left\lfloor\frac{N}{m}\right\rfloor.$$
Jede Zahl in \(1,\dots,N\) mit diesem \(6\)-freien Anteil hat eindeutig die Form \(m s\) mit
$$\mathcal{S}(L)=\{2^a3^b\le L: a,b\ge 0\}.$$
Verschiedene Werte von \(m\) überlappen nicht. Daher gilt
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}} G\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right),$$
wobei \(G(L)\) den optimalen Beitrag einer einzelnen Komponente mit Schranke \(L\) bezeichnet.
Für eine glatte Basis \(s\in \mathcal{S}(L)\) definieren wir den lokalen Block
$$B_L(s)=\{s,2s,3s\}\cap [1,L].$$
Nach Multiplikation mit \(m\) entsteht daraus \(\{ms,2ms,3ms\}\cap [1,N]\). Seine Größe ist
$$|B_L(s)|=1+\mathbf{1}_{2s\le L}+\mathbf{1}_{3s\le L}.$$
Innerhalb einer Komponente suchen wir also eine Menge glatter Basen, deren Blöcke sich nicht überschneiden und deren Gesamtgewicht maximal ist.
Zwei Blöcke \(B_L(s)\) und \(B_L(t)\) schneiden sich genau dann, wenn
$$i s=j t\quad \text{für gewisse } i,j\in\{1,2,3\}$$
gilt. Für verschiedene \(s\) und \(t\) ist das äquivalent zu
$$\frac{t}{s}\in \left\{2,3,\frac{3}{2},\frac{1}{2},\frac{1}{3},\frac{2}{3}\right\}.$$
Schreibt man \(s=2^a3^b\), so entsprechen diese sechs Verhältnisse den sechs Nachbarbewegungen
$$ (a,b)\leftrightarrow(a\pm 1,b),\qquad (a,b)\leftrightarrow(a,b\pm 1),\qquad (a,b)\leftrightarrow(a+1,b-1),\qquad (a,b)\leftrightarrow(a-1,b+1). $$
Damit ist \(G(L)\) der Wert eines Maximum-Weight-Independent-Set-Problems auf dem Dreiecksgitter der Exponentenpaare \((a,b)\) mit \(2^a3^b\le L\).
Der zentrale Struktursatz der Implementierungen lautet, dass dieser Graphenwert exakt durch
$$G(L)=|\mathcal{S}(L)|-|\mathcal{E}\cap [1,L]|$$
gegeben ist, wobei die Ausnahmezahlen
$$\mathcal{E}=\{6,24,54\}\cup \{384\cdot 8^t:t\ge 0\}\cup \{243\cdot 27^t:t\ge 0\}$$
sind. Fast jede glatte Zahl trägt also genau eine Einheit bei; nur die expliziten Ausnahmezahlen reduzieren das Optimum jeweils um eins.
Einsetzen der Komponentenformel liefert
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}}\left(|\mathcal{S}(\lfloor N/m\rfloor)|-|\mathcal{E}\cap [1,\lfloor N/m\rfloor]|\right).$$
Damit verschwindet die schwere kombinatorische Suche. Übrig bleibt reine Arithmetik: glatte Zahlen zählen, Ausnahmen zählen und die Werte über die Quotienten \(\lfloor N/m\rfloor\) aufsummieren.
Ordne die glatten Zahlen aufsteigend. Zwischen zwei aufeinanderfolgenden glatten Grenzwerten ändern sich weder \(|\mathcal{S}(L)|\) noch \(|\mathcal{E}\cap [1,L]|\), denn jede Ausnahmezahl ist selbst glatt. Also ist \(G(L)\) auf jedem Intervall \([L,R]\) konstant, wobei \(L\) glatt ist und \(R\) die nächste glatte Zahl minus \(1\) oder im letzten Block \(N\) ist.
Die Bedingung
$$L\le \left\lfloor\frac{N}{m}\right\rfloor\le R$$
ist äquivalent zu
$$m_{\mathrm{low}}=\left\lfloor\frac{N}{R+1}\right\rfloor+1,\qquad m_{\mathrm{high}}=\left\lfloor\frac{N}{L}\right\rfloor.$$
Die Anzahl der Zahlen bis \(x\), die zu \(6\) teilerfremd sind, ist
$$C(x)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{x}{6}\right\rfloor.$$
Somit trägt ein Quotientenblock genau
$$G(L)\left(C(m_{\mathrm{high}})-C(m_{\mathrm{low}}-1)\right)$$
zur Gesamtsumme bei.
Die \(2^a3^b\)-glatten Zahlen bis \(20\) sind
$$1,2,3,4,6,8,9,12,16,18,$$
also \(|\mathcal{S}(20)|=10\). In diesem Bereich ist nur \(6\) eine Ausnahme, daher
$$G(20)=10-1=9.$$
Die Zahlen \(m\le 20\) mit \(\gcd(m,6)=1\) sind
$$1,5,7,11,13,17,19.$$
Die zugehörigen Quotienten lauten
$$\left\lfloor\frac{20}{1}\right\rfloor=20,\quad \left\lfloor\frac{20}{5}\right\rfloor=4,\quad \left\lfloor\frac{20}{7}\right\rfloor=2,\quad \left\lfloor\frac{20}{11}\right\rfloor=\left\lfloor\frac{20}{13}\right\rfloor=\left\lfloor\frac{20}{17}\right\rfloor=\left\lfloor\frac{20}{19}\right\rfloor=1.$$
Mit \(G(4)=4\), \(G(2)=2\) und \(G(1)=1\) folgt
$$A(20)=9+4+2+1+1+1+1=19,$$
genau der Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen konstruieren den Konfliktgraphen nie explizit. Stattdessen erzeugen sie zunächst alle \(2^a3^b\)-glatten Zahlen bis \(N\), sortieren sie und entfernen Duplikate. Zusätzlich wird die Ausnahmemenge bis zur gleichen Grenze erzeugt.
Danach wird die glatte Liste einmal von links nach rechts durchlaufen. An jedem glatten Grenzwert wird der aktuelle Komponentenwert \(G(L)\) aktualisiert: gewöhnliche glatte Zahlen erhöhen ihn um eins, Ausnahmezahlen nicht, weil sie genau den einen verlorenen Beitrag der geschlossenen Formel darstellen.
Anschließend verarbeitet die Implementierung die aufeinanderfolgenden Intervalle \([L,R]\), übersetzt jedes Intervall in den passenden Bereich von \(m\)-Werten, zählt mit der Inklusions-Exklusions-Formel für \(C(x)\) die zu \(6\) teilerfremden Werte und addiert den Blockbeitrag. Python verwendet automatisch beliebig große Ganzzahlen; die kompilierten Implementierungen benutzen für die Endsumme einen breiteren Akkumulator.
Sei \(S(N)=|\mathcal{S}(N)|\). Aus \(2^a3^b\le N\) folgen \(0\le a\le \lfloor \log_2 N\rfloor\) und \(0\le b\le \lfloor \log_3 N\rfloor\), also \(S(N)=O((\log N)^2)\). Das Erzeugen und Sortieren der glatten Liste kostet \(O(S(N)\log S(N))\), die Ausnahmeliste enthält nur \(O(\log N)\) Terme, und der abschließende Durchlauf über die Quotientenblöcke kostet \(O(S(N))\). Der Speicherbedarf ist \(O(S(N))=O((\log N)^2)\).
Problem, \(1,\dots,N\) aralığındaki tamsayılardan birbirleriyle çakışmayan yerel \(123\)-bloklara yerleştirilebilen en büyük toplam eleman sayısını ister. Her pozitif tamsayı
$$n=m\,2^a3^b,\qquad \gcd(m,6)=1$$
biçiminde tekil yazılabildiği için arama, \(6\) ile aralarında asal çekirdek \(m\) tarafından indekslenen bağımsız bileşenlere ayrılır. Bir bileşenin içinde yalnızca \(2^a3^b\)-smooth çarpanlar önemlidir ve nihai cevap bu yerel optimumların toplamıdır.
Aranan optimumu \(A(N)\) ile gösterelim. Hızlı çözüm iki katmanlıdır: önce tek bir bileşenin değeri tam olarak bulunur, sonra bu değerler tüm uygun \(m\) değerleri üzerinde toplanır.
\(\gcd(m,6)=1\) olan sabit bir \(m\) seçelim ve
$$L=\left\lfloor\frac{N}{m}\right\rfloor$$
tanımını yapalım. \(6\)-serbest kısmı \(m\) olan her sayı, \(1,\dots,N\) içinde tekil olarak \(m s\) biçimindedir; burada
$$\mathcal{S}(L)=\{2^a3^b\le L: a,b\ge 0\}.$$
Farklı \(m\) değerleri birbirine karışmadığından
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}} G\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
olur. Burada \(G(L)\), smooth sınırı \(L\) olan tek bir bileşenin en iyi katkısıdır.
\(\mathcal{S}(L)\) içindeki bir smooth taban \(s\) için yerel blok
$$B_L(s)=\{s,2s,3s\}\cap [1,L]$$
olsun. Bu blok, dışarıda \(m\) ile çarpılınca \(\{ms,2ms,3ms\}\cap [1,N]\) olur. Blok büyüklüğü
$$|B_L(s)|=1+\mathbf{1}_{2s\le L}+\mathbf{1}_{3s\le L}$$
şeklindedir. Dolayısıyla bir bileşen içinde, blokları örtüşmeyen smooth tabanları seçip toplam ağırlığı en büyük yapmak isteriz.
İki blok \(B_L(s)\) ve \(B_L(t)\), ancak ve ancak
$$i s=j t\quad \text{bazı } i,j\in\{1,2,3\} \text{ için}$$
olduğunda kesişir. \(s\ne t\) için bu,
$$\frac{t}{s}\in \left\{2,3,\frac{3}{2},\frac{1}{2},\frac{1}{3},\frac{2}{3}\right\}$$
demektir. \(s=2^a3^b\) yazarsak bu altı oran, üs düzleminde şu altı komşuluğa karşılık gelir:
$$ (a,b)\leftrightarrow(a\pm 1,b),\qquad (a,b)\leftrightarrow(a,b\pm 1),\qquad (a,b)\leftrightarrow(a+1,b-1),\qquad (a,b)\leftrightarrow(a-1,b+1). $$
Yani \(G(L)\), \(2^a3^b\le L\) koşulunu sağlayan üs çiftleri üzerinde kurulu üçgensel kafeste bir maksimum ağırlıklı bağımsız küme problemidir.
Uygulamanın dayandığı temel yapısal gerçek, bu grafik optimizasyonunun tam olarak
$$G(L)=|\mathcal{S}(L)|-|\mathcal{E}\cap [1,L]|$$
değerine eşit olmasıdır. Burada istisna kümesi
$$\mathcal{E}=\{6,24,54\}\cup \{384\cdot 8^t:t\ge 0\}\cup \{243\cdot 27^t:t\ge 0\}$$
şeklindedir. Başka bir deyişle, neredeyse her smooth sayı optimuma bir birim ekler; yalnızca açıkça verilen istisna değerleri birer birim eksiltir.
Bileşen formülü dış toplama yazılınca
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}}\left(|\mathcal{S}(\lfloor N/m\rfloor)|-|\mathcal{E}\cap [1,\lfloor N/m\rfloor]|\right)$$
elde edilir. Böylece zor kombinatoryal arama tamamen ortadan kalkar; geriye smooth sayı saymak, istisnaları saymak ve bunları \(\lfloor N/m\rfloor\) değerleri üzerinden toplamak kalır.
Smooth sayıları artan sırayla dizelim. Ardışık iki smooth eşik arasında ne \(|\mathcal{S}(L)|\) ne de \(|\mathcal{E}\cap [1,L]|\) değişir; çünkü her istisna sayı da smooth'tur. Bu nedenle \(G(L)\), \(L\) bir smooth sayı ve \(R\) bir sonraki smooth sayı eksi \(1\) ya da son blokta \(N\) olmak üzere her \([L,R]\) aralığında sabittir.
Şu koşul
$$L\le \left\lfloor\frac{N}{m}\right\rfloor\le R$$
şuna denktir:
$$m_{\mathrm{low}}=\left\lfloor\frac{N}{R+1}\right\rfloor+1,\qquad m_{\mathrm{high}}=\left\lfloor\frac{N}{L}\right\rfloor.$$
\(x\)'e kadar \(6\) ile aralarında asal sayıların sayısı
$$C(x)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{x}{6}\right\rfloor$$
olduğundan, bir bölüm aralığının katkısı
$$G(L)\left(C(m_{\mathrm{high}})-C(m_{\mathrm{low}}-1)\right)$$
olur.
\(20\)'ye kadar olan \(2^a3^b\)-smooth sayılar
$$1,2,3,4,6,8,9,12,16,18$$
olduğundan \(|\mathcal{S}(20)|=10\) elde edilir. Bu ölçekte tek istisna \(6\) olduğu için
$$G(20)=10-1=9.$$
\(20\)'ye kadar \(\gcd(m,6)=1\) şartını sağlayan değerler
$$1,5,7,11,13,17,19$$
şeklindedir. Bunların bölüm değerleri
$$\left\lfloor\frac{20}{1}\right\rfloor=20,\quad \left\lfloor\frac{20}{5}\right\rfloor=4,\quad \left\lfloor\frac{20}{7}\right\rfloor=2,\quad \left\lfloor\frac{20}{11}\right\rfloor=\left\lfloor\frac{20}{13}\right\rfloor=\left\lfloor\frac{20}{17}\right\rfloor=\left\lfloor\frac{20}{19}\right\rfloor=1.$$
\(G(4)=4\), \(G(2)=2\) ve \(G(1)=1\) olduğundan
$$A(20)=9+4+2+1+1+1+1=19$$
çıkar; bu da implementasyonlardaki kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları çatışma grafiğini açıkça kurmaz. Bunun yerine önce \(N\)'ye kadar tüm \(2^a3^b\)-smooth sayıları üretir, sıralar ve tekrarları siler. Aynı sınır altında istisna alt kümesi de ayrıca üretilir.
Ardından smooth liste soldan sağa tek geçişle taranır. Her smooth eşikte güncel bileşen değeri \(G(L)\) yenilenir: sıradan smooth sayılar değeri bir artırır, istisna smooth sayılar ise kapalı formdaki birim kaybı temsil ettikleri için artırmaz.
Son aşamada implementasyon, ardışık eşik aralıklarını \([L,R]\) biçiminde dolaşır; her aralığı uygun \(m\) aralığına çevirir, \(C(x)\) için dahil et-çıkar formülüyle \(6\) ile aralarında asal kaç değer olduğunu sayar ve blok katkısını ekler. Python doğal olarak büyük tamsayı kullanır; derlenen implementasyonlar ise nihai toplam için daha geniş bir biriktirici kullanır.
\(S(N)=|\mathcal{S}(N)|\) olsun. \(2^a3^b\le N\) eşitsizliği \(0\le a\le \lfloor\log_2 N\rfloor\) ve \(0\le b\le \lfloor\log_3 N\rfloor\) verdiği için \(S(N)=O((\log N)^2)\) olur. Smooth listeyi üretip sıralamak \(O(S(N)\log S(N))\), istisna listesi yalnızca \(O(\log N)\) terim, son tarama ise \(O(S(N))\) zaman alır. Bellek kullanımı \(O(S(N))=O((\log N)^2)\) düzeyindedir.
El problema pide el mayor número total de enteros en \(1,\dots,N\) que pueden organizarse en bloques locales \(123\) sin solapamientos entre sí. Todo entero positivo admite la descomposición única
$$n=m\,2^a3^b,\qquad \gcd(m,6)=1,$$
de modo que la búsqueda se divide en componentes independientes indexados por la parte \(m\) coprima con \(6\). Dentro de cada componente solo importan los multiplicadores \(2^a3^b\)-suaves, y la respuesta final es la suma de los mejores aportes locales.
Denotemos por \(A(N)\) el óptimo buscado. La solución rápida tiene dos niveles: resolver exactamente un componente y luego sumar ese valor sobre todos los posibles \(m\).
Fijemos un \(m\) con \(\gcd(m,6)=1\) y definamos
$$L=\left\lfloor\frac{N}{m}\right\rfloor.$$
Cada entero de \(1,\dots,N\) cuya parte libre de \(6\) sea \(m\) se escribe de forma única como \(m s\), con
$$\mathcal{S}(L)=\{2^a3^b\le L: a,b\ge 0\}.$$
Como distintos valores de \(m\) no se mezclan, obtenemos
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}} G\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right),$$
donde \(G(L)\) es la mejor contribución de un solo componente con cota \(L\).
Para una base suave \(s\in \mathcal{S}(L)\), el bloque local es
$$B_L(s)=\{s,2s,3s\}\cap [1,L].$$
Al multiplicar por \(m\), esto se transforma en \(\{ms,2ms,3ms\}\cap [1,N]\). Su tamaño es
$$|B_L(s)|=1+\mathbf{1}_{2s\le L}+\mathbf{1}_{3s\le L}.$$
Por lo tanto, dentro de un componente debemos escoger bases suaves cuyos bloques no se superpongan y cuya suma de pesos sea máxima.
Dos bloques \(B_L(s)\) y \(B_L(t)\) se intersecan exactamente cuando
$$i s=j t\quad \text{para algunos } i,j\in\{1,2,3\}.$$
Si \(s\ne t\), eso equivale a
$$\frac{t}{s}\in \left\{2,3,\frac{3}{2},\frac{1}{2},\frac{1}{3},\frac{2}{3}\right\}.$$
Escribiendo \(s=2^a3^b\), esos cocientes se convierten en los seis movimientos vecinos
$$ (a,b)\leftrightarrow(a\pm 1,b),\qquad (a,b)\leftrightarrow(a,b\pm 1),\qquad (a,b)\leftrightarrow(a+1,b-1),\qquad (a,b)\leftrightarrow(a-1,b+1). $$
Así, \(G(L)\) es un problema de conjunto independiente de peso máximo sobre la retícula triangular formada por los pares \((a,b)\) con \(2^a3^b\le L\).
El hecho estructural clave utilizado por las implementaciones es que este problema de grafo tiene el valor exacto
$$G(L)=|\mathcal{S}(L)|-|\mathcal{E}\cap [1,L]|,$$
donde el conjunto excepcional es
$$\mathcal{E}=\{6,24,54\}\cup \{384\cdot 8^t:t\ge 0\}\cup \{243\cdot 27^t:t\ge 0\}.$$
En consecuencia, casi todo número suave aporta una unidad al óptimo y solo los valores excepcionales explícitos restan una unidad.
Sustituyendo la fórmula del componente en la suma exterior se obtiene
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}}\left(|\mathcal{S}(\lfloor N/m\rfloor)|-|\mathcal{E}\cap [1,\lfloor N/m\rfloor]|\right).$$
Con esto desaparece la búsqueda combinatoria difícil. El resto es aritmética: contar suaves, contar excepciones suaves y agregar esos valores sobre los cocientes \(\lfloor N/m\rfloor\).
Ordenemos los números suaves de menor a mayor. Entre dos puntos de ruptura suaves consecutivos no cambia ni \(|\mathcal{S}(L)|\) ni \(|\mathcal{E}\cap [1,L]|\), porque toda excepción también es suave. Por tanto, \(G(L)\) es constante en cada intervalo \([L,R]\), donde \(L\) es un suave y \(R\) es el siguiente suave menos \(1\), o \(R=N\) en el último bloque.
La condición
$$L\le \left\lfloor\frac{N}{m}\right\rfloor\le R$$
equivale a
$$m_{\mathrm{low}}=\left\lfloor\frac{N}{R+1}\right\rfloor+1,\qquad m_{\mathrm{high}}=\left\lfloor\frac{N}{L}\right\rfloor.$$
El número de enteros hasta \(x\) coprimos con \(6\) es
$$C(x)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{x}{6}\right\rfloor.$$
Así, un intervalo de cocientes aporta
$$G(L)\left(C(m_{\mathrm{high}})-C(m_{\mathrm{low}}-1)\right).$$
Los números \(2^a3^b\)-suaves hasta \(20\) son
$$1,2,3,4,6,8,9,12,16,18,$$
por lo que \(|\mathcal{S}(20)|=10\). En esta escala el único valor excepcional es \(6\), de modo que
$$G(20)=10-1=9.$$
Los enteros \(m\le 20\) con \(\gcd(m,6)=1\) son
$$1,5,7,11,13,17,19.$$
Sus cocientes correspondientes son
$$\left\lfloor\frac{20}{1}\right\rfloor=20,\quad \left\lfloor\frac{20}{5}\right\rfloor=4,\quad \left\lfloor\frac{20}{7}\right\rfloor=2,\quad \left\lfloor\frac{20}{11}\right\rfloor=\left\lfloor\frac{20}{13}\right\rfloor=\left\lfloor\frac{20}{17}\right\rfloor=\left\lfloor\frac{20}{19}\right\rfloor=1.$$
Como \(G(4)=4\), \(G(2)=2\) y \(G(1)=1\), resulta
$$A(20)=9+4+2+1+1+1+1=19,$$
exactamente el valor de comprobación usado por las implementaciones.
Las implementaciones en C++, Python y Java nunca construyen el grafo de conflictos de forma explícita. Primero generan todos los números \(2^a3^b\)-suaves hasta \(N\), los ordenan y eliminan duplicados. Luego generan el subconjunto excepcional hasta el mismo límite.
Después recorren la lista de suaves una sola vez en orden creciente. En cada punto de ruptura suave actualizan el valor actual \(G(L)\): un suave ordinario lo incrementa en una unidad, mientras que un suave excepcional no lo hace porque ya representa la pérdida de una unidad descrita por la fórmula cerrada.
Por último, la implementación recorre los intervalos consecutivos \([L,R]\), traduce cada intervalo al rango correspondiente de valores \(m\), cuenta cuántos de esos \(m\) son coprimos con \(6\) mediante la fórmula de inclusión-exclusión para \(C(x)\) y suma la contribución del bloque. Python maneja enteros grandes de forma nativa, mientras que las versiones compiladas usan un acumulador más amplio para la suma final.
Sea \(S(N)=|\mathcal{S}(N)|\). De \(2^a3^b\le N\) se deduce \(0\le a\le \lfloor\log_2 N\rfloor\) y \(0\le b\le \lfloor\log_3 N\rfloor\), así que \(S(N)=O((\log N)^2)\). Generar y ordenar la lista de suaves cuesta \(O(S(N)\log S(N))\), la lista excepcional tiene solo \(O(\log N)\) términos y el barrido final sobre los intervalos cuesta \(O(S(N))\). La memoria total es \(O(S(N))=O((\log N)^2)\).
这道题要求在 \(1,\dots,N\) 中选出尽可能多的整数，使它们能够被组织成两两不重叠的局部 \(123\) 块。每个正整数都可以唯一写成
$$n=m\,2^a3^b,\qquad \gcd(m,6)=1,$$
因此整体优化会自动分裂成若干个互不干扰的分量，每个分量由与 \(6\) 互素的核心部分 \(m\) 决定。在单个分量内部，只需要研究不超过 \(\lfloor N/m\rfloor\) 的 \(2^a3^b\)-平滑因子，最后答案就是所有局部最优值的总和。
记所求最优值为 \(A(N)\)。快速解法的思路是：先把单个分量彻底算清楚，再把这个分量值对所有可能的 \(m\) 累加起来。
固定一个满足 \(\gcd(m,6)=1\) 的 \(m\)，并令
$$L=\left\lfloor\frac{N}{m}\right\rfloor.$$
那么，区间 \(1,\dots,N\) 中所有 \(6\)-自由部分等于 \(m\) 的整数，都能唯一写成 \(m s\) 的形式，其中
$$\mathcal{S}(L)=\{2^a3^b\le L: a,b\ge 0\}.$$
不同的 \(m\) 永远不会混在一起，所以全局最优值就是各个分量最优值的和：
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}} G\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
这里 \(G(L)\) 表示平滑上界为 \(L\) 时，单个分量能够贡献的最大值。
对任意 \(s\in\mathcal{S}(L)\)，定义局部块
$$B_L(s)=\{s,2s,3s\}\cap [1,L].$$
乘回外层的 \(m\) 之后，它对应的实际整数块就是 \(\{ms,2ms,3ms\}\cap [1,N]\)。这个块的大小为
$$|B_L(s)|=1+\mathbf{1}_{2s\le L}+\mathbf{1}_{3s\le L}.$$
于是，单个分量内部的问题就变成：选择若干个平滑基数 \(s\)，要求它们对应的块互不相交，并且总权重最大。
两个局部块 \(B_L(s)\) 与 \(B_L(t)\) 相交，当且仅当存在 \(i,j\in\{1,2,3\}\) 使得
$$i s=j t.$$
对不同的 \(s\) 与 \(t\)，这等价于
$$\frac{t}{s}\in \left\{2,3,\frac{3}{2},\frac{1}{2},\frac{1}{3},\frac{2}{3}\right\}.$$
如果把 \(s\) 写成 \(2^a3^b\)，那么上述六个比例正好对应指数平面上的六个相邻移动：
$$ (a,b)\leftrightarrow(a\pm 1,b),\qquad (a,b)\leftrightarrow(a,b\pm 1),\qquad (a,b)\leftrightarrow(a+1,b-1),\qquad (a,b)\leftrightarrow(a-1,b+1). $$
因此 \(G(L)\) 可以看成一个三角格点图上的最大权独立集问题，顶点正是满足 \(2^a3^b\le L\) 的指数对 \((a,b)\)。
所有实现真正利用的关键结论是：这个图优化值可以直接写成
$$G(L)=|\mathcal{S}(L)|-|\mathcal{E}\cap [1,L]|,$$
其中异常平滑数集合为
$$\mathcal{E}=\{6,24,54\}\cup \{384\cdot 8^t:t\ge 0\}\cup \{243\cdot 27^t:t\ge 0\}.$$
也就是说，几乎每个 \(2^a3^b\)-平滑数都会给最优值贡献 \(1\)，只有上面列出的显式异常值会各自减去 \(1\)。快速算法正是建立在这个精确恒等式之上。
把分量公式代回总和，可得
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}}\left(|\mathcal{S}(\lfloor N/m\rfloor)|-|\mathcal{E}\cap [1,\lfloor N/m\rfloor]|\right).$$
到这里，困难的组合优化已经被完全消去，剩下的只是算术计数问题：统计平滑数，统计异常平滑数，然后按 \(\lfloor N/m\rfloor\) 的取值进行汇总。
将所有平滑数按从小到大排序。由于每个异常数本身也是平滑数，所以在两个相邻平滑断点之间，\(|\mathcal{S}(L)|\) 和 \(|\mathcal{E}\cap [1,L]|\) 都不会变化，从而 \(G(L)\) 在整个区间 \([L,R]\) 上保持常数。这里 \(L\) 是一个平滑断点，\(R\) 是下一个平滑数减 \(1\)，最后一个区间则取 \(R=N\)。
条件
$$L\le \left\lfloor\frac{N}{m}\right\rfloor\le R$$
等价于
$$m_{\mathrm{low}}=\left\lfloor\frac{N}{R+1}\right\rfloor+1,\qquad m_{\mathrm{high}}=\left\lfloor\frac{N}{L}\right\rfloor.$$
不超过 \(x\) 且与 \(6\) 互素的整数个数由容斥给出：
$$C(x)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{x}{6}\right\rfloor.$$
因此一个整除分块区间的贡献就是
$$G(L)\left(C(m_{\mathrm{high}})-C(m_{\mathrm{low}}-1)\right).$$
不超过 \(20\) 的 \(2^a3^b\)-平滑数为
$$1,2,3,4,6,8,9,12,16,18,$$
所以 \(|\mathcal{S}(20)|=10\)。在这个范围内，唯一的异常值是 \(6\)，于是
$$G(20)=10-1=9.$$
满足 \(\gcd(m,6)=1\) 且 \(m\le 20\) 的整数为
$$1,5,7,11,13,17,19.$$
相应的商值为
$$\left\lfloor\frac{20}{1}\right\rfloor=20,\quad \left\lfloor\frac{20}{5}\right\rfloor=4,\quad \left\lfloor\frac{20}{7}\right\rfloor=2,\quad \left\lfloor\frac{20}{11}\right\rfloor=\left\lfloor\frac{20}{13}\right\rfloor=\left\lfloor\frac{20}{17}\right\rfloor=\left\lfloor\frac{20}{19}\right\rfloor=1.$$
又因为 \(G(4)=4\)、\(G(2)=2\)、\(G(1)=1\)，于是
$$A(20)=9+4+2+1+1+1+1=19,$$
这与实现中使用的校验值完全一致。
C++、Python 和 Java 实现都不会真的去构造那个局部冲突图。它们先生成所有不超过 \(N\) 的 \(2^a3^b\)-平滑数，排序后去重，再生成同一范围内的异常子集。
接着，程序对平滑数列表做一次线性扫描。在每个平滑断点处更新当前的分量值 \(G(L)\)：普通平滑数会让它增加 \(1\)，异常平滑数则不会增加，因为它们正对应闭式公式中的那一次扣减。
最后，程序遍历连续的断点区间 \([L,R]\)，把每个区间转成对应的 \(m\) 取值范围，用容斥公式 \(C(x)\) 计算其中与 \(6\) 互素的整数个数，再乘上该区间的常数分量值并累加。Python 天然支持大整数；编译型实现则为最终总和使用更宽的整数累加器。
记 \(S(N)=|\mathcal{S}(N)|\)。由 \(2^a3^b\le N\) 可知 \(0\le a\le \lfloor\log_2 N\rfloor\)、\(0\le b\le \lfloor\log_3 N\rfloor\)，因此 \(S(N)=O((\log N)^2)\)。生成并排序平滑数列表需要 \(O(S(N)\log S(N))\) 时间，异常列表只有 \(O(\log N)\) 项，最终扫描所有断点区间需要 \(O(S(N))\) 时间。空间复杂度为 \(O(S(N))=O((\log N)^2)\)。
Нужно найти наибольшее общее число целых из диапазона \(1,\dots,N\), которые можно разложить на попарно непересекающиеся локальные \(123\)-блоки. Каждый положительный целый имеет единственное представление
$$n=m\,2^a3^b,\qquad \gcd(m,6)=1,$$
поэтому задача распадается на независимые компоненты, индексируемые частью \(m\), взаимно простой с \(6\). Внутри одной компоненты важны только \(2^a3^b\)-гладкие множители, а окончательный ответ равен сумме оптимальных локальных вкладов.
Обозначим искомый оптимум через \(A(N)\). Быстрое решение устроено так: сначала точно считается одна компонента, затем это значение суммируется по всем допустимым \(m\).
Зафиксируем \(m\) с \(\gcd(m,6)=1\) и положим
$$L=\left\lfloor\frac{N}{m}\right\rfloor.$$
Любое число из \(1,\dots,N\), у которого \(6\)-свободная часть равна \(m\), единственным образом имеет вид \(m s\), где
$$\mathcal{S}(L)=\{2^a3^b\le L: a,b\ge 0\}.$$
Разные значения \(m\) не взаимодействуют, поэтому
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}} G\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right),$$
где \(G(L)\) обозначает оптимальный вклад одной компоненты с параметром \(L\).
Для гладкой базы \(s\in\mathcal{S}(L)\) локальный блок задаётся как
$$B_L(s)=\{s,2s,3s\}\cap [1,L].$$
После умножения на \(m\) это становится \(\{ms,2ms,3ms\}\cap [1,N]\). Размер блока равен
$$|B_L(s)|=1+\mathbf{1}_{2s\le L}+\mathbf{1}_{3s\le L}.$$
Значит, внутри компоненты нужно выбрать такие гладкие базы, чтобы соответствующие блоки не пересекались, а суммарный вес был максимален.
Два блока \(B_L(s)\) и \(B_L(t)\) пересекаются тогда и только тогда, когда
$$i s=j t\quad \text{для некоторых } i,j\in\{1,2,3\}.$$
Для различных \(s\) и \(t\) это эквивалентно условию
$$\frac{t}{s}\in \left\{2,3,\frac{3}{2},\frac{1}{2},\frac{1}{3},\frac{2}{3}\right\}.$$
Если записать \(s=2^a3^b\), то эти отношения превращаются в шесть соседних переходов
$$ (a,b)\leftrightarrow(a\pm 1,b),\qquad (a,b)\leftrightarrow(a,b\pm 1),\qquad (a,b)\leftrightarrow(a+1,b-1),\qquad (a,b)\leftrightarrow(a-1,b+1). $$
Следовательно, \(G(L)\) есть значение задачи о максимальном взвешенном независимом множестве на треугольной решётке, образованной парами показателей \((a,b)\) при \(2^a3^b\le L\).
Ключевой структурный факт, на котором основаны реализации, состоит в том, что этот графовый оптимум равен
$$G(L)=|\mathcal{S}(L)|-|\mathcal{E}\cap [1,L]|,$$
где множество исключений имеет вид
$$\mathcal{E}=\{6,24,54\}\cup \{384\cdot 8^t:t\ge 0\}\cup \{243\cdot 27^t:t\ge 0\}.$$
То есть почти каждое \(2^a3^b\)-гладкое число даёт один вклад, а только явно перечисленные исключения отнимают по одной единице.
Подставляя формулу компоненты во внешнюю сумму, получаем
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}}\left(|\mathcal{S}(\lfloor N/m\rfloor)|-|\mathcal{E}\cap [1,\lfloor N/m\rfloor]|\right).$$
Тем самым трудный комбинаторный поиск исчезает. Остаётся только считать гладкие числа, считать исключения среди них и суммировать значения по частным \(\lfloor N/m\rfloor\).
Упорядочим гладкие числа по возрастанию. Между двумя соседними гладкими границами не меняются ни \(|\mathcal{S}(L)|\), ни \(|\mathcal{E}\cap [1,L]|\), потому что каждое исключение само является гладким числом. Поэтому \(G(L)\) постоянно на каждом интервале \([L,R]\), где \(L\) является гладкой границей, а \(R\) равно следующему гладкому числу минус \(1\), либо \(R=N\) в последнем блоке.
Условие
$$L\le \left\lfloor\frac{N}{m}\right\rfloor\le R$$
равносильно формулам
$$m_{\mathrm{low}}=\left\lfloor\frac{N}{R+1}\right\rfloor+1,\qquad m_{\mathrm{high}}=\left\lfloor\frac{N}{L}\right\rfloor.$$
Количество целых чисел до \(x\), взаимно простых с \(6\), задаётся включением-исключением:
$$C(x)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{x}{6}\right\rfloor.$$
Значит, вклад одного интервального блока равен
$$G(L)\left(C(m_{\mathrm{high}})-C(m_{\mathrm{low}}-1)\right).$$
\(2^a3^b\)-гладкие числа до \(20\) таковы:
$$1,2,3,4,6,8,9,12,16,18,$$
поэтому \(|\mathcal{S}(20)|=10\). На этом масштабе единственное исключение равно \(6\), значит
$$G(20)=10-1=9.$$
Числа \(m\le 20\) с условием \(\gcd(m,6)=1\) равны
$$1,5,7,11,13,17,19.$$
Соответствующие частные имеют вид
$$\left\lfloor\frac{20}{1}\right\rfloor=20,\quad \left\lfloor\frac{20}{5}\right\rfloor=4,\quad \left\lfloor\frac{20}{7}\right\rfloor=2,\quad \left\lfloor\frac{20}{11}\right\rfloor=\left\lfloor\frac{20}{13}\right\rfloor=\left\lfloor\frac{20}{17}\right\rfloor=\left\lfloor\frac{20}{19}\right\rfloor=1.$$
Поскольку \(G(4)=4\), \(G(2)=2\) и \(G(1)=1\), получаем
$$A(20)=9+4+2+1+1+1+1=19,$$
что совпадает с контрольным значением, используемым в реализациях.
Реализации на C++, Python и Java не строят граф конфликтов явно. Сначала они перечисляют все \(2^a3^b\)-гладкие числа до \(N\), сортируют список и удаляют дубликаты. Затем до той же границы строится список исключений.
После этого список гладких чисел один раз просматривается слева направо. На каждой гладкой границе обновляется текущее значение \(G(L)\): обычное гладкое число увеличивает его на единицу, а исключение не увеличивает, поскольку именно оно соответствует вычитаемой единице в замкнутой формуле.
Далее программа проходит по последовательным интервалам \([L,R]\), переводит каждый такой интервал в соответствующий диапазон значений \(m\), считает количество чисел, взаимно простых с \(6\), с помощью формулы для \(C(x)\), и добавляет вклад блока. Python автоматически использует длинную арифметику, а компилируемые реализации применяют более широкий аккумулятор для итоговой суммы.
Пусть \(S(N)=|\mathcal{S}(N)|\). Из условия \(2^a3^b\le N\) следует \(0\le a\le \lfloor\log_2 N\rfloor\) и \(0\le b\le \lfloor\log_3 N\rfloor\), поэтому \(S(N)=O((\log N)^2)\). Построение и сортировка списка гладких чисел занимают \(O(S(N)\log S(N))\), список исключений содержит лишь \(O(\log N)\) элементов, а финальный проход по интервалам требует \(O(S(N))\) времени. Память равна \(O(S(N))=O((\log N)^2)\).
المطلوب هو إيجاد أكبر عدد كلي من الأعداد الصحيحة في المجال \(1,\dots,N\) يمكن تنظيمه على هيئة كتل محلية من النوع \(123\) بحيث لا تتداخل هذه الكتل فيما بينها. كل عدد صحيح موجب يملك تمثيلاً وحيدًا على الصورة
$$n=m\,2^a3^b,\qquad \gcd(m,6)=1,$$
ولذلك تنقسم المسألة تلقائيًا إلى مكوّنات مستقلة يحددها الجزء \(m\) غير القابل للقسمة على \(2\) أو \(3\). داخل كل مكوّن لا نحتاج إلا إلى دراسة العوامل الملساء من الشكل \(2^a3^b\)، والجواب النهائي هو مجموع القيم المثلى لهذه المكوّنات.
لنرمز إلى القيمة المثلى المطلوبة بالرمز \(A(N)\). الحل السريع يعمل على مستويين: نحسب أولًا قيمة مكوّن واحد بدقة، ثم نجمع هذه القيمة على جميع القيم الممكنة لـ \(m\).
ثبّت عددًا \(m\) يحقق \(\gcd(m,6)=1\)، وعرّف
$$L=\left\lfloor\frac{N}{m}\right\rfloor.$$
كل عدد في \(1,\dots,N\) يكون جزؤه الحر من \(6\) مساويًا لـ \(m\) يمكن كتابته بشكل وحيد على صورة \(m s\)، حيث
$$\mathcal{S}(L)=\{2^a3^b\le L: a,b\ge 0\}.$$
ولأن القيم المختلفة لـ \(m\) لا تختلط فيما بينها، نحصل على
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}} G\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right),$$
حيث تمثل \(G(L)\) أفضل مساهمة يمكن أن يحققها مكوّن واحد حدّه الأملس هو \(L\).
لكل أساس أملس \(s\in\mathcal{S}(L)\) نعرّف الكتلة المحلية
$$B_L(s)=\{s,2s,3s\}\cap [1,L].$$
وبعد الضرب في \(m\) تصبح الكتلة الفعلية \(\{ms,2ms,3ms\}\cap [1,N]\). وحجم هذه الكتلة هو
$$|B_L(s)|=1+\mathbf{1}_{2s\le L}+\mathbf{1}_{3s\le L}.$$
إذن داخل المكوّن نريد اختيار أسس ملساء بحيث تكون الكتل المقابلة لها غير متقاطعة، مع تعظيم مجموع الأوزان.
تتقاطع الكتلتان \(B_L(s)\) و\(B_L(t)\) إذا وفقط إذا وُجد \(i,j\in\{1,2,3\}\) بحيث
$$i s=j t.$$
وعندما يكون \(s\ne t\)، فهذا يكافئ الشرط
$$\frac{t}{s}\in \left\{2,3,\frac{3}{2},\frac{1}{2},\frac{1}{3},\frac{2}{3}\right\}.$$
إذا كتبنا \(s=2^a3^b\)، فإن هذه النسب الست تتحول إلى ست حركات تجاور على شبكة الأسس:
$$ (a,b)\leftrightarrow(a\pm 1,b),\qquad (a,b)\leftrightarrow(a,b\pm 1),\qquad (a,b)\leftrightarrow(a+1,b-1),\qquad (a,b)\leftrightarrow(a-1,b+1). $$
وبالتالي فإن \(G(L)\) هو قيمة مسألة أكبر مجموعة مستقلة ذات وزن أعظمي على الشبكة المثلثية المكوّنة من الأزواج \((a,b)\) التي تحقق \(2^a3^b\le L\).
الحقيقة البنيوية الأساسية التي تعتمد عليها جميع التطبيقات هي أن قيمة هذا التحسين البياني تُعطى مباشرةً بـ
$$G(L)=|\mathcal{S}(L)|-|\mathcal{E}\cap [1,L]|,$$
حيث إن مجموعة القيم الاستثنائية هي
$$\mathcal{E}=\{6,24,54\}\cup \{384\cdot 8^t:t\ge 0\}\cup \{243\cdot 27^t:t\ge 0\}.$$
هذا يعني أن كل عدد أملس من الشكل \(2^a3^b\) يضيف عادةً وحدة واحدة إلى الحل الأمثل، ولا تُطرح وحدة إلا عند القيم الاستثنائية المذكورة صراحةً.
بالتعويض عن قيمة المكوّن داخل المجموع الخارجي نحصل على
$$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}}\left(|\mathcal{S}(\lfloor N/m\rfloor)|-|\mathcal{E}\cap [1,\lfloor N/m\rfloor]|\right).$$
وبذلك تختفي عملية البحث التركيبي الثقيلة، ويتبقى فقط عدّ الأعداد الملساء، وعدّ الاستثناءات الملساء، ثم جمع هذه القيم على قيم القسمة الصحيحة \(\lfloor N/m\rfloor\).
رتّب الأعداد الملساء تصاعديًا. بين حدّين أملسين متتاليين لا تتغير لا \(|\mathcal{S}(L)|\) ولا \(|\mathcal{E}\cap [1,L]|\)، لأن كل عنصر استثنائي هو بدوره عدد أملس. لذلك تكون \(G(L)\) ثابتة على كل فترة \([L,R]\)، حيث إن \(L\) عدد أملس و\(R\) يساوي العدد الأملس التالي ناقص \(1\)، أو \(R=N\) في الفترة الأخيرة.
الشرط
$$L\le \left\lfloor\frac{N}{m}\right\rfloor\le R$$
يكافئ
$$m_{\mathrm{low}}=\left\lfloor\frac{N}{R+1}\right\rfloor+1,\qquad m_{\mathrm{high}}=\left\lfloor\frac{N}{L}\right\rfloor.$$
أما عدد الأعداد الصحيحة حتى \(x\) الموافقة أوليًا مع \(6\) فيُعطى بمبدأ الشمول والاستبعاد:
$$C(x)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{x}{6}\right\rfloor.$$
ومن ثم فإن مساهمة فترة واحدة هي
$$G(L)\left(C(m_{\mathrm{high}})-C(m_{\mathrm{low}}-1)\right).$$
الأعداد الملساء من الشكل \(2^a3^b\) التي لا تتجاوز \(20\) هي
$$1,2,3,4,6,8,9,12,16,18,$$
ومن ثم \(|\mathcal{S}(20)|=10\). وعلى هذا المدى لا يوجد استثناء إلا \(6\)، وبالتالي
$$G(20)=10-1=9.$$
أما القيم \(m\le 20\) التي تحقق \(\gcd(m,6)=1\) فهي
$$1,5,7,11,13,17,19.$$
وقيم القسمة المقابلة لها هي
$$\left\lfloor\frac{20}{1}\right\rfloor=20,\quad \left\lfloor\frac{20}{5}\right\rfloor=4,\quad \left\lfloor\frac{20}{7}\right\rfloor=2,\quad \left\lfloor\frac{20}{11}\right\rfloor=\left\lfloor\frac{20}{13}\right\rfloor=\left\lfloor\frac{20}{17}\right\rfloor=\left\lfloor\frac{20}{19}\right\rfloor=1.$$
وبما أن \(G(4)=4\) و\(G(2)=2\) و\(G(1)=1\)، نحصل على
$$A(20)=9+4+2+1+1+1+1=19,$$
وهو تمامًا مقدار التحقق المستخدم في التطبيقات.
تطبيقات C++ وPython وJava لا تبني رسم التعارض المحلي صراحةً. بدلاً من ذلك فهي تولّد أولًا جميع الأعداد الملساء من الشكل \(2^a3^b\) حتى \(N\)، ثم ترتبها وتحذف التكرارات، وبعد ذلك تولّد المجموعة الاستثنائية حتى الحد نفسه.
بعد ذلك تُمسح قائمة الأعداد الملساء مرة واحدة تصاعديًا. عند كل حد أملس يجري تحديث القيمة الحالية \(G(L)\): العدد الأملس العادي يزيدها بمقدار \(1\)، أما العدد الاستثنائي فلا يزيدها لأنه يمثل تحديدًا الوحدة المفقودة في الصيغة المغلقة.
وفي المرحلة الأخيرة يمر التنفيذ على الفترات المتتالية \([L,R]\)، ويحوّل كل فترة إلى مجال القيم الموافق لـ \(m\)، ثم يحسب عدد القيم الموافقة أوليًا مع \(6\) بواسطة الصيغة \(C(x)\)، ويضيف مساهمة تلك الفترة. Python تتعامل تلقائيًا مع الأعداد الصحيحة كبيرة الحجم، بينما تستخدم التطبيقات المترجمة مُجمِّعًا أوسع من أجل المجموع النهائي.
لنكتب \(S(N)=|\mathcal{S}(N)|\). من الشرط \(2^a3^b\le N\) نحصل على \(0\le a\le \lfloor\log_2 N\rfloor\) و\(0\le b\le \lfloor\log_3 N\rfloor\)، ولذلك \(S(N)=O((\log N)^2)\). توليد قائمة الأعداد الملساء وترتيبها يكلف \(O(S(N)\log S(N))\)، أما قائمة الاستثناءات فحجمها \(O(\log N)\) فقط، والمرور النهائي على الفترات يكلف \(O(S(N))\). الذاكرة المستعملة هي \(O(S(N))=O((\log N)^2)\).