Let \(\operatorname{Co}(n)\) denote the maximum possible sum of a subset \(A\subseteq\{1,2,\dots,n\}\) such that any two distinct chosen numbers are coprime:
$$\operatorname{Co}(n)=\max\left\{\sum_{x\in A}x : A\subseteq\{1,\dots,n\},\ \gcd(a,b)=1\ \forall a\ne b\in A\right\}.$$
The local C++, Python, and Java solutions all use the same structure: start from the best one-prime-per-slot baseline, then add only profitable replacements of one small-prime power and one large prime by a larger mixed value. Those replacements form a maximum-weight bipartite matching.
If two selected numbers were both divisible by the same prime \(p\), their gcd would be at least \(p\), so they could not be pairwise coprime. Therefore each prime may appear in at most one chosen number.
For a fixed prime \(p\le n\), the best number using only that prime is the largest prime power not exceeding \(n\):
$$P_p=\max\{p^k : k\ge 1,\ p^k\le n\}.$$
This gives the baseline set
$$B_0=\{1\}\cup\{P_p : p\in\mathbb{P},\ p\le n\},$$
Here \(\mathbb{P}\) denotes the set of prime numbers.
which is pairwise coprime because different members are powers of different primes. Its sum is
$$S_0=1+\sum_{p\le n}P_p,$$
where the sum runs over primes \(p\le n\).
Suppose a candidate number \(x\le n\) has distinct prime divisors in a set \(T\). Choosing \(x\) forbids us from keeping the baseline representatives \(P_r\) for \(r\in T\).
If \(P_r=r^k\), then \(r^{k+1}>n\), hence
$$P_r>\frac{n}{r}.$$
Therefore
$$\sum_{r\in T}P_r>n\sum_{r\in T}\frac{1}{r}.$$
If \(x\) has at least three distinct prime factors, the smallest possible reciprocal sum is
$$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}>1,$$
so \(\sum_{r\in T}P_r>n\ge x\). Such a number can never improve the baseline. This is why the implementations only search upgrades involving exactly two primes.
Split the primes at \(\lfloor\sqrt{n}\rfloor\): small primes satisfy \(p\le \sqrt{n}\), while large primes satisfy \(q>\sqrt{n}\).
Two large primes cannot appear in the same chosen number because then their product would exceed \(n\). Also, for a large prime \(q\), we have \(P_q=q\) since \(q^2>n\).
The local solver therefore encodes profitable mixed replacements as numbers of the form
$$M(p,q)=q\cdot \max\{p^a : a\ge 1,\ p^a q\le n\},\qquad p\le \sqrt{n}\lt q.$$
The helper highest_power_with_limit(p, n / q) computes the inner maximum. Replacing \(P_p\) and \(P_q\) by \(M(p,q)\) changes the sum by
$$w(p,q)=M(p,q)-P_p-P_q.$$
Only positive values of \(w(p,q)\) are useful, so only those become edges in the optimization graph.
Each small prime can be used in at most one mixed number, and each large prime can also be used at most once. That is exactly a matching constraint.
Create a bipartite graph with small primes on the left and large primes on the right. Add an edge \((p,q)\) with weight \(w(p,q)\) whenever \(w(p,q)>0\). The implementations add extra zero-weight dummy columns so that a small prime may remain unmatched and simply keep \(P_p\).
If \(\mathcal{M}\) is a matching, its total gain is
$$G(\mathcal{M})=\sum_{(p,q)\in \mathcal{M}}w(p,q).$$
The answer computed by the code is
$$\boxed{\operatorname{Co}(n)=S_0+\max_{\mathcal{M}}G(\mathcal{M}).}$$
The maximum is obtained with the Hungarian algorithm on a rectangular assignment matrix.
The baseline representatives are
$$1,\ 16,\ 27,\ 25,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,$$
so
$$S_0=188.$$
Here \(\lfloor\sqrt{30}\rfloor=5\), so the small primes are \(2,3,5\). The only positive gain edge is \((2,7)\):
$$M(2,7)=7\cdot 4=28,\qquad w(2,7)=28-16-7=5.$$
Hence
$$\operatorname{Co}(30)=188+5=193,$$
which matches the checkpoint embedded in the C++ program.
For \(n=100\), the baseline sum is \(S_0=1263\). Several small primes have multiple profitable partners, so a greedy choice is not enough. The maximum matching selected by the implementations uses
$$64+11\to 88,\qquad 25+19\to 95,\qquad 49+13\to 91,$$
with gains \(13\), \(51\), and \(29\). The total gain is \(93\), giving
$$\operatorname{Co}(100)=1263+93=1356.$$
The three solution files implement the same mathematics. They sieve primes up to \(n\), compute every \(P_p\) with max_prime_power_leq_n, sum the baseline, and split primes at \(\lfloor\sqrt{n}\rfloor\).
For each feasible pair \((p,q)\) with \(p\) small, \(q\) large, and \(pq\le n\), they evaluate the best mixed value \(M(p,q)\). Positive gains are written into a weight matrix of size
$$s\times(\ell+s),$$
where \(s\) is the number of small primes and \(\ell\) is the number of large primes. The extra \(s\) columns are the dummy unmatched choices. The function hungarian_max_weight_bipartite returns the maximum additional gain.
The C++ version exposes this pipeline through prepare_solver_data, build_gain_edges, and solve_co_optimized. It also parallelizes edge generation over the small-prime side and verifies the checkpoints \(\operatorname{Co}(10)=30\), \(\operatorname{Co}(30)=193\), and \(\operatorname{Co}(100)=1356\). The Python and Java versions follow the same matrix construction in a single thread.
Let \(s=\pi(\lfloor\sqrt{n}\rfloor)\) and \(\ell=\pi(n)-s\). The sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. Building the gain matrix costs \(O(E\log n)\), where \(E\) is the number of feasible pairs \((p,q)\) with \(p\le\sqrt{n}\lt q\) and \(pq\le n\); the logarithmic factor comes from multiplying \(p\) repeatedly up to the limit \(n/q\).
The Hungarian algorithm on an \(s\times(\ell+s)\) matrix costs \(O(s^2(\ell+s))\) time and \(O(s(\ell+s))\) memory. For the actual input \(n=200000\), we have \(s=\pi(447)=86\), so the matching stage is small compared with the full prime range.
Sei \(\operatorname{Co}(n)\) die maximal mögliche Summe einer Teilmenge \(A\subseteq\{1,2,\dots,n\}\), deren Elemente paarweise teilerfremd sind:
$$\operatorname{Co}(n)=\max\left\{\sum_{x\in A}x : A\subseteq\{1,\dots,n\},\ \gcd(a,b)=1\ \forall a\ne b\in A\right\}.$$
Die lokalen C++-, Python- und Java-Lösungen verwenden dieselbe Struktur: Zuerst wird eine Basis konstruiert, in der jede Primzahl genau einen Platz bekommt. Danach werden nur noch profitable Ersetzungen betrachtet, bei denen eine kleine Primzahlpotenz und eine große Primzahl durch einen größeren Mischwert ersetzt werden. Diese Verbesserungen bilden ein maximales gewichtetes bipartites Matching.
Wären zwei gewählte Zahlen beide durch dieselbe Primzahl \(p\) teilbar, dann wäre ihr ggT mindestens \(p\). Also darf jede Primzahl in der gesuchten Menge nur in genau einem ausgewählten Element vorkommen.
Für eine feste Primzahl \(p\le n\) ist die beste reine \(p\)-Wahl die größte Primzahlpotenz unterhalb von \(n\):
$$P_p=\max\{p^k : k\ge 1,\ p^k\le n\}.$$
Damit erhält man die Basis
$$B_0=\{1\}\cup\{P_p : p\in\mathbb{P},\ p\le n\},$$
Hier bezeichnet \(\mathbb{P}\) die Menge der Primzahlen.
und diese Menge ist paarweise teilerfremd, weil ihre nichttrivialen Elemente Potenzen verschiedener Primzahlen sind. Die Basissumme lautet
$$S_0=1+\sum_{p\le n}P_p,$$
wobei über alle Primzahlen \(p\le n\) summiert wird.
Sei \(x\le n\) eine Kandidatenzahl mit den verschiedenen Primteilern aus einer Menge \(T\). Wenn man \(x\) auswählt, kann man die Basisvertreter \(P_r\) für \(r\in T\) nicht gleichzeitig behalten.
Ist \(P_r=r^k\), so gilt \(r^{k+1}>n\), also
$$P_r>\frac{n}{r}.$$
Daraus folgt
$$\sum_{r\in T}P_r>n\sum_{r\in T}\frac{1}{r}.$$
Hat \(x\) mindestens drei verschiedene Primteiler, dann ist die kleinste mögliche Kehrwertsumme
$$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}>1,$$
also \(\sum_{r\in T}P_r>n\ge x\). Solche Zahlen können die Basiskonstruktion nie verbessern. Deshalb untersucht die Implementierung nur Ersetzungen mit genau zwei Primzahlen.
Die Primzahlen werden bei \(\lfloor\sqrt{n}\rfloor\) getrennt: Kleine Primzahlen erfüllen \(p\le \sqrt{n}\), große Primzahlen erfüllen \(q>\sqrt{n}\).
Zwei große Primzahlen können nicht gemeinsam in einer Zahl \(\le n\) vorkommen, denn ihr Produkt wäre bereits größer als \(n\). Für eine große Primzahl \(q\) ist außerdem \(P_q=q\), da \(q^2>n\).
Der lokale Solver kodiert profitable Mischkandidaten daher als Zahlen der Form
$$M(p,q)=q\cdot \max\{p^a : a\ge 1,\ p^a q\le n\},\qquad p\le \sqrt{n}\lt q.$$
Das innere Maximum wird im Code durch highest_power_with_limit(p, n / q) berechnet. Ersetzt man \(P_p\) und \(P_q\) durch \(M(p,q)\), so ändert sich die Summe um
$$w(p,q)=M(p,q)-P_p-P_q.$$
Nur positive Werte von \(w(p,q)\) werden als Kanten übernommen.
Eine kleine Primzahl darf höchstens in einer Mischzahl auftauchen, und eine große Primzahl ebenfalls nur einmal. Genau das ist eine Matching-Bedingung.
Man bildet also einen bipartiten Graphen: links die kleinen Primzahlen, rechts die großen Primzahlen. Für jedes profitable Paar \((p,q)\) wird eine Kante mit Gewicht \(w(p,q)\) eingetragen. Zusätzlich fügt die Implementierung Nullspalten als Dummy-Wahlen ein, damit eine kleine Primzahl auch ungematcht bleiben und ihren Basiswert \(P_p\) behalten kann.
Ist \(\mathcal{M}\) ein Matching, dann ist sein Gesamtgewinn
$$G(\mathcal{M})=\sum_{(p,q)\in \mathcal{M}}w(p,q).$$
Damit berechnet das Programm
$$\boxed{\operatorname{Co}(n)=S_0+\max_{\mathcal{M}}G(\mathcal{M}).}$$
Das Maximum wird mit der ungarischen Methode auf einer rechteckigen Gewichtsmatrix bestimmt.
Die Basisvertreter sind
$$1,\ 16,\ 27,\ 25,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,$$
also
$$S_0=188.$$
Hier ist \(\lfloor\sqrt{30}\rfloor=5\), also sind \(2,3,5\) die kleinen Primzahlen. Die einzige positive Kante ist \((2,7)\):
$$M(2,7)=7\cdot 4=28,\qquad w(2,7)=28-16-7=5.$$
Folglich
$$\operatorname{Co}(30)=188+5=193,$$
genau wie im C++-Checkpoint.
Für \(n=100\) ist die Basissumme \(S_0=1263\). Mehrere kleine Primzahlen haben mehrere profitable Partner, daher reicht eine lokale Greedy-Wahl nicht. Das optimale Matching der Implementierungen wählt
$$64+11\to 88,\qquad 25+19\to 95,\qquad 49+13\to 91,$$
mit Gewinnen \(13\), \(51\) und \(29\). Insgesamt ergibt das \(93\), also
$$\operatorname{Co}(100)=1263+93=1356.$$
Alle drei Lösungsdateien setzen dieselbe Mathematik um. Zunächst werden alle Primzahlen bis \(n\) gesiebt, dann jedes \(P_p\) mit max_prime_power_leq_n berechnet, die Basissumme aufaddiert und die Primzahlen bei \(\lfloor\sqrt{n}\rfloor\) getrennt.
Für jedes zulässige Paar \((p,q)\) mit kleinem \(p\), großem \(q\) und \(pq\le n\) wird der beste Mischwert \(M(p,q)\) berechnet. Positive Gewinne landen in einer Gewichtsmatrix der Größe
$$s\times(\ell+s),$$
wobei \(s\) die Anzahl kleiner Primzahlen und \(\ell\) die Anzahl großer Primzahlen ist. Die zusätzlichen \(s\) Spalten stehen für die Dummy-Entscheidungen ohne Ersetzung. Die Funktion hungarian_max_weight_bipartite liefert den maximalen Zusatzgewinn.
Die C++-Version organisiert den Ablauf über prepare_solver_data, build_gain_edges und solve_co_optimized. Sie parallelisiert außerdem den Kantenaufbau und prüft vor der Standardrechnung die Kontrollwerte \(\operatorname{Co}(10)=30\), \(\operatorname{Co}(30)=193\) und \(\operatorname{Co}(100)=1356\). Python und Java folgen derselben Logik ohne Multithreading.
Seien \(s=\pi(\lfloor\sqrt{n}\rfloor)\) und \(\ell=\pi(n)-s\). Das Primzahlsieb benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Der Aufbau der Gewinnmatrix kostet \(O(E\log n)\), wobei \(E\) die Zahl der zulässigen Paare \((p,q)\) mit \(p\le\sqrt{n}\lt q\) und \(pq\le n\) ist; der logarithmische Faktor entsteht durch wiederholtes Multiplizieren von \(p\) bis zur Grenze \(n/q\).
Die ungarische Methode auf einer \(s\times(\ell+s)\)-Matrix benötigt \(O(s^2(\ell+s))\) Zeit und \(O(s(\ell+s))\) Speicher. Für den eigentlichen Eingabewert \(n=200000\) gilt \(s=\pi(447)=86\); daher bleibt die Matching-Phase in der Praxis klein.
\(\operatorname{Co}(n)\), \(\{1,2,\dots,n\}\) içinden seçilen ve her iki farklı elemanı aralarında asal olan bir alt kümenin ulaşabileceği en büyük toplam olsun:
$$\operatorname{Co}(n)=\max\left\{\sum_{x\in A}x : A\subseteq\{1,\dots,n\},\ \gcd(a,b)=1\ \forall a\ne b\in A\right\}.$$
Depodaki C++, Python ve Java çözümleri aynı fikri uygular: önce her asal için en iyi tek-asal temsilcilerden oluşan bir taban kuruluyor, sonra bir küçük asal kuvveti ile bir büyük asalın yerini alan daha karlı karma değerler aranıyor. Bu karlı hamleler, maksimum ağırlıklı iki parçalı eşleştirme problemine dönüşüyor.
Seçilen iki sayı aynı asal \(p\) ile bölünebilseydi, EBOB'ları en az \(p\) olurdu. Bu yüzden herhangi bir asal, seçili alt kümede en fazla bir sayının içinde görünebilir.
Belirli bir \(p\le n\) asalı için yalnızca bu asalı kullanan en iyi seçim, \(n\)'i aşmayan en büyük asal kuvvettir:
$$P_p=\max\{p^k : k\ge 1,\ p^k\le n\}.$$
Böylece başlangıç kümesi
$$B_0=\{1\}\cup\{P_p : p\in\mathbb{P},\ p\le n\}$$
Burada \(\mathbb{P}\), asal sayıların kümesini gösterir.
elde edilir. Farklı elemanlar farklı asalların kuvvetleri olduğundan bu küme ikişer ikişer aralarında asaldır. Toplamı da
$$S_0=1+\sum_{p\le n}P_p$$
şeklindedir; toplam tüm \(p\le n\) asalları üzerindedir.
\(x\le n\) olsun ve farklı asal bölenleri \(T\) kümesini oluştursun. Eğer \(x\) seçilirse, \(T\) içindeki asallar için tabandaki \(P_r\) değerleri aynı anda seçilemez.
\(P_r=r^k\) ise \(r^{k+1}>n\) olur; dolayısıyla
$$P_r>\frac{n}{r}.$$
Bundan
$$\sum_{r\in T}P_r>n\sum_{r\in T}\frac{1}{r}$$
çıkar. Eğer \(x\) en az üç farklı asal içeriyorsa mümkün olan en küçük ters toplam
$$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}>1$$
olur; bu da \(\sum_{r\in T}P_r>n\ge x\) demektir. Yani üç veya daha fazla farklı asal içeren bir sayı tabanı iyileştiremez. Bu nedenle kod yalnızca iki asallı yükseltmeleri araştırır.
Asalları \(\lfloor\sqrt{n}\rfloor\) noktasında ikiye ayıralım: Küçük asallar \(p\le \sqrt{n}\), büyük asallar ise \(q>\sqrt{n}\) koşulunu sağlar.
İki büyük asal aynı sayıda bulunamaz; çünkü çarpımları doğrudan \(n\)'i aşar. Ayrıca büyük bir \(q\) için \(q^2>n\) olduğundan \(P_q=q\) olur.
Yerel çözümler bu yüzden karlı karışık adayları şu biçimde kurar:
$$M(p,q)=q\cdot \max\{p^a : a\ge 1,\ p^a q\le n\},\qquad p\le \sqrt{n}\lt q.$$
İçteki maksimum kodda highest_power_with_limit(p, n / q) ile hesaplanır. \(P_p\) ve \(P_q\) yerine \(M(p,q)\) seçildiğinde toplam değişimi
$$w(p,q)=M(p,q)-P_p-P_q$$
olur. Yalnızca pozitif \(w(p,q)\) değerleri kenar olarak tutulur.
Bir küçük asal en fazla bir karma sayıda kullanılabilir; bir büyük asal da en fazla bir kez kullanılabilir. Bu tam olarak eşleştirme kısıtıdır.
Sol tarafta küçük asallar, sağ tarafta büyük asallar olan iki parçalı bir grafik kurulur. Her karlı \((p,q)\) çifti için ağırlığı \(w(p,q)\) olan bir kenar eklenir. Ayrıca küçük asalların hiç eşleşmeden kalıp \(P_p\) değerini koruması için sıfır ağırlıklı sahte sütunlar eklenir.
Bir eşleştirmenin toplam kazancı
$$G(\mathcal{M})=\sum_{(p,q)\in \mathcal{M}}w(p,q)$$
olursa, kodun hesapladığı sonuç
$$\boxed{\operatorname{Co}(n)=S_0+\max_{\mathcal{M}}G(\mathcal{M}).}$$
Bu maksimum, dikdörtgen ağırlık matrisi üzerinde Hungarian algoritması ile bulunur.
Taban temsilcileri şunlardır:
$$1,\ 16,\ 27,\ 25,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,$$
dolayısıyla
$$S_0=188.$$
Burada \(\lfloor\sqrt{30}\rfloor=5\) olduğundan küçük asallar \(2,3,5\)'tir. Tek pozitif kenar \((2,7)\) olur:
$$M(2,7)=7\cdot 4=28,\qquad w(2,7)=28-16-7=5.$$
Sonuç olarak
$$\operatorname{Co}(30)=188+5=193$$
elde edilir; bu da C++ dosyasındaki kontrol değeriyle aynıdır.
\(n=100\) için taban toplamı \(S_0=1263\)'tür. Birden fazla küçük asalın birden fazla karlı ortağı bulunduğundan, yerel olarak en iyi görünen seçimi yapmak yeterli değildir. Uygulamanın bulduğu en iyi eşleştirme
$$64+11\to 88,\qquad 25+19\to 95,\qquad 49+13\to 91$$
hamlelerini seçer. Kazançlar sırasıyla \(13\), \(51\) ve \(29\) olduğundan toplam ek kazanç \(93\) ve sonuç
$$\operatorname{Co}(100)=1263+93=1356$$
olur.
Üç çözüm dosyası da aynı matematiği uygular. Önce \(n\)'e kadar asallar elenir, ardından her \(P_p\) değeri max_prime_power_leq_n ile bulunur, taban toplamı hesaplanır ve asallar \(\lfloor\sqrt{n}\rfloor\) noktasında iki gruba ayrılır.
Küçük bir \(p\), büyük bir \(q\) ve \(pq\le n\) şartını sağlayan her çift için en iyi karışık değer \(M(p,q)\) hesaplanır. Pozitif kazançlar
$$s\times(\ell+s)$$
boyutlu bir ağırlık matrisine yazılır; burada \(s\) küçük asal sayısı, \(\ell\) ise büyük asal sayısıdır. Fazladan gelen \(s\) sütun, sahte eşleşme seçeneklerini temsil eder. hungarian_max_weight_bipartite fonksiyonu maksimum ek kazancı döndürür.
C++ sürümü bu hattı prepare_solver_data, build_gain_edges ve solve_co_optimized fonksiyonlarıyla kurar. Kenar üretimi küçük asal tarafında paralelleştirilir ve varsayılan çözümden önce \(\operatorname{Co}(10)=30\), \(\operatorname{Co}(30)=193\) ve \(\operatorname{Co}(100)=1356\) kontrol edilir. Python ve Java aynı matrisi tek iş parçacığıyla kurar.
\(s=\pi(\lfloor\sqrt{n}\rfloor)\) ve \(\ell=\pi(n)-s\) olsun. Asal eleği \(O(n\log\log n)\) zaman ve \(O(n)\) bellek kullanır. Kazanç matrisinin oluşturulması, \(p\le\sqrt{n}\lt q\) ve \(pq\le n\) koşullarını sağlayan \(E\) adet çift için \(O(E\log n)\) zaman alır; logaritmik çarpan, \(p\)'nin \(n/q\) sınırına kadar tekrar tekrar çarpılmasından gelir.
Hungarian algoritması \(s\times(\ell+s)\) boyutlu matris üzerinde \(O(s^2(\ell+s))\) zamanda ve \(O(s(\ell+s))\) bellekte çalışır. Gerçek girdi olan \(n=200000\) için \(s=\pi(447)=86\) olduğundan eşleştirme aşaması uygulamada oldukça küçüktür.
Sea \(\operatorname{Co}(n)\) la suma máxima que puede alcanzar un subconjunto \(A\subseteq\{1,2,\dots,n\}\) cuyos elementos sean coprimos por pares:
$$\operatorname{Co}(n)=\max\left\{\sum_{x\in A}x : A\subseteq\{1,\dots,n\},\ \gcd(a,b)=1\ \forall a\ne b\in A\right\}.$$
Las implementaciones locales en C++, Python y Java siguen la misma idea: primero construyen una base en la que cada primo ocupa su propio lugar, y después buscan sustituciones rentables donde una potencia de primo pequeño y un primo grande se reemplazan por un número mixto mayor. Esas sustituciones se optimizan como un matching bipartito de peso máximo.
Si dos números elegidos fueran divisibles por el mismo primo \(p\), su gcd sería al menos \(p\). Por tanto, en un conjunto coprimo por pares cada primo puede aparecer como factor en, a lo sumo, un elemento seleccionado.
Para un primo fijo \(p\le n\), la mejor elección que usa únicamente ese primo es la mayor potencia de \(p\) que no supera a \(n\):
$$P_p=\max\{p^k : k\ge 1,\ p^k\le n\}.$$
Con ello aparece la base
$$B_0=\{1\}\cup\{P_p : p\in\mathbb{P},\ p\le n\},$$
Aquí \(\mathbb{P}\) representa el conjunto de los números primos.
que es válida porque sus elementos no triviales son potencias de primos distintos. Su suma vale
$$S_0=1+\sum_{p\le n}P_p,$$
sumando sobre todos los primos \(p\le n\).
Sea \(x\le n\) un candidato cuyos divisores primos distintos formen el conjunto \(T\). Si elegimos \(x\), ya no podemos mantener simultáneamente los representantes de base \(P_r\) para \(r\in T\).
Si \(P_r=r^k\), entonces \(r^{k+1}>n\), y por tanto
$$P_r>\frac{n}{r}.$$
Luego
$$\sum_{r\in T}P_r>n\sum_{r\in T}\frac{1}{r}.$$
Si \(x\) tiene al menos tres factores primos distintos, la menor suma recíproca posible es
$$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}>1,$$
así que \(\sum_{r\in T}P_r>n\ge x\). Un número con tres o más primos distintos nunca mejora la base. Por eso el código solo estudia mejoras con exactamente dos primos.
Se divide en el umbral \(\lfloor\sqrt{n}\rfloor\): los primos pequeños cumplen \(p\le \sqrt{n}\) y los grandes cumplen \(q>\sqrt{n}\).
Dos primos grandes no pueden coexistir en un número \(\le n\), porque su producto ya sería mayor que \(n\). Además, para un primo grande \(q\), se cumple \(P_q=q\) ya que \(q^2>n\).
Por ello, el solver local codifica las mejoras rentables como números mixtos de la forma
$$M(p,q)=q\cdot \max\{p^a : a\ge 1,\ p^a q\le n\},\qquad p\le \sqrt{n}\lt q.$$
El máximo interno lo calcula la rutina highest_power_with_limit(p, n / q). Reemplazar \(P_p\) y \(P_q\) por \(M(p,q)\) cambia la suma en
$$w(p,q)=M(p,q)-P_p-P_q.$$
Solo se conservan los valores positivos de \(w(p,q)\).
Cada primo pequeño puede participar en, como mucho, una mejora, y cada primo grande también puede usarse una sola vez. Esa es exactamente la restricción de un matching.
Se construye un grafo bipartito con los primos pequeños a la izquierda y los grandes a la derecha. Para cada par rentable \((p,q)\), se añade una arista de peso \(w(p,q)\). Las implementaciones añaden además columnas ficticias de peso cero para representar la opción de no emparejar un primo pequeño y conservar simplemente \(P_p\).
Si \(\mathcal{M}\) es un matching, su ganancia total es
$$G(\mathcal{M})=\sum_{(p,q)\in \mathcal{M}}w(p,q).$$
La fórmula que implementa el programa es
$$\boxed{\operatorname{Co}(n)=S_0+\max_{\mathcal{M}}G(\mathcal{M}).}$$
Ese máximo se calcula con el algoritmo húngaro sobre una matriz de asignación rectangular.
Los representantes de base son
$$1,\ 16,\ 27,\ 25,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,$$
de modo que
$$S_0=188.$$
Aquí \(\lfloor\sqrt{30}\rfloor=5\), así que los primos pequeños son \(2,3,5\). La única arista positiva es \((2,7)\):
$$M(2,7)=7\cdot 4=28,\qquad w(2,7)=28-16-7=5.$$
Por tanto
$$\operatorname{Co}(30)=188+5=193,$$
exactamente el valor de control usado en C++.
Para \(n=100\), la base suma \(S_0=1263\). Varias filas tienen más de un socio rentable, así que una elección codiciosa no basta. El matching óptimo de las implementaciones selecciona
$$64+11\to 88,\qquad 25+19\to 95,\qquad 49+13\to 91,$$
con ganancias \(13\), \(51\) y \(29\). La mejora total es \(93\), luego
$$\operatorname{Co}(100)=1263+93=1356.$$
Los tres ficheros de solución implementan exactamente esta matemática. Primero generan todos los primos hasta \(n\), calculan cada \(P_p\) con max_prime_power_leq_n, acumulan la base y separan primos pequeños y grandes en \(\lfloor\sqrt{n}\rfloor\).
Para cada par factible \((p,q)\) con \(p\) pequeño, \(q\) grande y \(pq\le n\), evalúan el mejor valor mixto \(M(p,q)\). Las ganancias positivas se escriben en una matriz de pesos de tamaño
$$s\times(\ell+s),$$
donde \(s\) es el número de primos pequeños y \(\ell\) el número de primos grandes. Las \(s\) columnas extra representan las decisiones ficticias de dejar una fila sin emparejar. La función hungarian_max_weight_bipartite devuelve la mejora máxima.
La versión en C++ organiza este flujo con prepare_solver_data, build_gain_edges y solve_co_optimized. Además paraleliza la construcción de aristas y comprueba los hitos \(\operatorname{Co}(10)=30\), \(\operatorname{Co}(30)=193\) y \(\operatorname{Co}(100)=1356\). Python y Java usan la misma construcción de matriz en un solo hilo.
Sean \(s=\pi(\lfloor\sqrt{n}\rfloor)\) y \(\ell=\pi(n)-s\). La criba cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Construir la matriz de ganancias cuesta \(O(E\log n)\), donde \(E\) es el número de pares factibles \((p,q)\) con \(p\le\sqrt{n}\lt q\) y \(pq\le n\); el factor logarítmico proviene de multiplicar repetidamente \(p\) hasta alcanzar el límite \(n/q\).
El algoritmo húngaro sobre una matriz \(s\times(\ell+s)\) cuesta \(O(s^2(\ell+s))\) tiempo y \(O(s(\ell+s))\) memoria. Para la entrada real \(n=200000\), se tiene \(s=\pi(447)=86\), así que la fase de matching es pequeña en la práctica.
记 \(\operatorname{Co}(n)\) 为从集合 \(\{1,2,\dots,n\}\) 中选出一个子集 \(A\) 时能够得到的最大元素和，并要求任意两个不同元素都互素：
$$\operatorname{Co}(n)=\max\left\{\sum_{x\in A}x : A\subseteq\{1,\dots,n\},\ \gcd(a,b)=1\ \forall a\ne b\in A\right\}.$$
仓库里的 C++、Python 和 Java 解法使用同一套结构。先建立“每个素数只占一个位置”的基线，再寻找那些真正有收益的替换：用一个由小素数幂和大素数组成的混合数，替换原来的一个小素数幂与一个大素数。这些替换最终变成一个最大权二分匹配问题。
如果两个被选中的数都含有同一个素因子 \(p\)，那么它们的 gcd 至少是 \(p\)，就不可能两两互素。因此，每个素数至多只能在一个被选中的数里出现。
对于固定素数 \(p\le n\)，只使用这个素数时最好的代表值就是不超过 \(n\) 的最大素数幂：
$$P_p=\max\{p^k : k\ge 1,\ p^k\le n\}.$$
于是得到基线集合
$$B_0=\{1\}\cup\{P_p : p\in\mathbb{P},\ p\le n\},$$
这里的 \(\mathbb{P}\) 表示所有素数构成的集合。
它显然满足两两互素，因为其中非平凡元素都是不同素数的幂。基线总和为
$$S_0=1+\sum_{p\le n}P_p,$$
这里求和遍历所有不超过 \(n\) 的素数。
设 \(x\le n\) 的不同素因子集合为 \(T\)。一旦选择了 \(x\)，集合 \(T\) 中各素数对应的基线代表 \(P_r\) 就不能同时保留。
如果 \(P_r=r^k\)，则有 \(r^{k+1}>n\)，因此
$$P_r>\frac{n}{r}.$$
于是
$$\sum_{r\in T}P_r>n\sum_{r\in T}\frac{1}{r}.$$
当 \(x\) 含有至少三个不同素因子时，最小的倒数和也有
$$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}>1,$$
从而 \(\sum_{r\in T}P_r>n\ge x\)。这说明含有三个或更多不同素因子的数不可能比基线更优，所以程序只搜索两素数结构的改进。
把素数按 \(\lfloor\sqrt{n}\rfloor\) 分成两类：满足 \(p\le \sqrt{n}\) 的记为小素数，满足 \(q>\sqrt{n}\) 的记为大素数。
两个大素数不可能同时出现在一个不超过 \(n\) 的数里，因为它们的乘积已经超过 \(n\)。并且对于大素数 \(q\)，由于 \(q^2>n\)，基线代表就是 \(P_q=q\)。
因此，本仓库里的解法把有收益的候选项编码成
$$M(p,q)=q\cdot \max\{p^a : a\ge 1,\ p^a q\le n\},\qquad p\le \sqrt{n}\lt q.$$
代码中的 highest_power_with_limit(p, n / q) 正是在计算这个内部最大值。若用 \(M(p,q)\) 替换 \(P_p\) 与 \(P_q\)，增益就是
$$w(p,q)=M(p,q)-P_p-P_q.$$
只有正增益边才值得保留。
每个小素数最多参与一次混合替换，每个大素数也最多使用一次，这正是匹配约束。
于是构造一个二分图：左边是小素数，右边是大素数。若某对 \((p,q)\) 有正增益，就连一条权值为 \(w(p,q)\) 的边。实现里还额外加入若干权值为 \(0\) 的虚拟列，表示某个小素数不参与替换，直接保留原来的 \(P_p\)。
若 \(\mathcal{M}\) 为一个匹配，则总增益为
$$G(\mathcal{M})=\sum_{(p,q)\in \mathcal{M}}w(p,q).$$
程序最终计算的是
$$\boxed{\operatorname{Co}(n)=S_0+\max_{\mathcal{M}}G(\mathcal{M}).}$$
其中最大值由 Hungarian 算法在一个长方形权矩阵上求出。
基线代表是
$$1,\ 16,\ 27,\ 25,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,$$
所以
$$S_0=188.$$
此时 \(\lfloor\sqrt{30}\rfloor=5\)，小素数为 \(2,3,5\)。唯一的正增益边是 \((2,7)\)：
$$M(2,7)=7\cdot 4=28,\qquad w(2,7)=28-16-7=5.$$
因此
$$\operatorname{Co}(30)=188+5=193,$$
这正好对应 C++ 代码中的检查点。
当 \(n=100\) 时，基线和为 \(S_0=1263\)。若只做局部最优选择，很容易冲突，因为同一个小素数可能对应多个有收益的大素数。实现中求得的最大权匹配选择了
$$64+11\to 88,\qquad 25+19\to 95,\qquad 49+13\to 91,$$
对应增益分别为 \(13\)、\(51\)、\(29\)，总增益为 \(93\)，所以
$$\operatorname{Co}(100)=1263+93=1356.$$
三个解法文件实现的是同一套数学。它们先筛出不超过 \(n\) 的所有素数，再用 max_prime_power_leq_n 计算每个 \(P_p\)，累加基线总和，然后在 \(\lfloor\sqrt{n}\rfloor\) 处分成小素数和大素数两部分。
对每个满足 \(p\) 为小素数、\(q\) 为大素数且 \(pq\le n\) 的候选对，程序都会计算最优的混合值 \(M(p,q)\)。所有正增益会写入一个大小为
$$s\times(\ell+s)$$
的矩阵，其中 \(s\) 是小素数个数，\(\ell\) 是大素数个数。额外的 \(s\) 列就是“不匹配”的虚拟选择。随后由 hungarian_max_weight_bipartite 返回最大附加收益。
C++ 版本通过 prepare_solver_data、build_gain_edges 和 solve_co_optimized 组织整个流程，并把边构造分块并行化。它还会先验证 \(\operatorname{Co}(10)=30\)、\(\operatorname{Co}(30)=193\) 和 \(\operatorname{Co}(100)=1356\)。Python 与 Java 版本则以单线程方式实现相同的矩阵逻辑。
记 \(s=\pi(\lfloor\sqrt{n}\rfloor)\)，\(\ell=\pi(n)-s\)。筛法需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。构造增益矩阵需要 \(O(E\log n)\) 时间，其中 \(E\) 是满足 \(p\le\sqrt{n}\lt q\) 且 \(pq\le n\) 的可行对数；对数因子来自不断把 \(p\) 乘到上界 \(n/q\) 的过程。
Hungarian 算法处理 \(s\times(\ell+s)\) 矩阵时，时间复杂度为 \(O(s^2(\ell+s))\)，空间复杂度为 \(O(s(\ell+s))\)。对真实输入 \(n=200000\) 而言，\(s=\pi(447)=86\)，所以匹配部分相当小，运行上是可接受的。
Обозначим через \(\operatorname{Co}(n)\) максимальную сумму подмножества \(A\subseteq\{1,2,\dots,n\}\), в котором любые два различных элемента взаимно просты:
$$\operatorname{Co}(n)=\max\left\{\sum_{x\in A}x : A\subseteq\{1,\dots,n\},\ \gcd(a,b)=1\ \forall a\ne b\in A\right\}.$$
Локальные решения на C++, Python и Java используют одну и ту же идею. Сначала строится базовый набор, где каждой простой соответствует лучший одно-простой представитель. Затем рассматриваются только выгодные замены, в которых степень маленького простого и одно большое простое заменяются большим смешанным числом. Эти замены образуют задачу о максимальном взвешенном паросочетании в двудольном графе.
Если два выбранных числа делятся на одно и то же простое \(p\), то их gcd не меньше \(p\). Значит, в попарно взаимно простом наборе каждое простое число может встречаться как множитель не более чем у одного выбранного элемента.
Для фиксированного простого \(p\le n\) лучший кандидат, использующий только это простое, равен наибольшей степени \(p\), не превосходящей \(n\):
$$P_p=\max\{p^k : k\ge 1,\ p^k\le n\}.$$
Так возникает базовый набор
$$B_0=\{1\}\cup\{P_p : p\in\mathbb{P},\ p\le n\},$$
Здесь \(\mathbb{P}\) обозначает множество простых чисел.
который действительно попарно взаимно прост, потому что его нетривиальные элементы являются степенями разных простых. Его сумма равна
$$S_0=1+\sum_{p\le n}P_p,$$
где суммирование идёт по всем простым \(p\le n\).
Пусть число \(x\le n\) имеет множество различных простых делителей \(T\). Если выбрать \(x\), то базовые представители \(P_r\) для \(r\in T\) уже нельзя оставлять одновременно.
Если \(P_r=r^k\), то \(r^{k+1}>n\), а значит
$$P_r>\frac{n}{r}.$$
Следовательно,
$$\sum_{r\in T}P_r>n\sum_{r\in T}\frac{1}{r}.$$
Если у \(x\) как минимум три различных простых делителя, то минимально возможная сумма обратных равна
$$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}>1,$$
поэтому \(\sum_{r\in T}P_r>n\ge x\). Такие числа никогда не улучшают базовую конструкцию. Поэтому код ищет только улучшения, использующие ровно два простых.
Разделим простые по порогу \(\lfloor\sqrt{n}\rfloor\): малые простые удовлетворяют \(p\le \sqrt{n}\), а большие - \(q>\sqrt{n}\).
Два больших простых не могут входить в одно число \(\le n\), потому что их произведение уже больше \(n\). Кроме того, для большого простого \(q\) выполняется \(P_q=q\), так как \(q^2>n\).
Поэтому локальный solver кодирует выгодные смешанные кандидаты числами вида
$$M(p,q)=q\cdot \max\{p^a : a\ge 1,\ p^a q\le n\},\qquad p\le \sqrt{n}\lt q.$$
Внутренний максимум в коде вычисляет функция highest_power_with_limit(p, n / q). Если заменить \(P_p\) и \(P_q\) на \(M(p,q)\), приращение суммы равно
$$w(p,q)=M(p,q)-P_p-P_q.$$
В граф попадают только положительные значения \(w(p,q)\).
Каждое малое простое может участвовать не более чем в одной смешанной замене, и каждое большое простое тоже используется не более одного раза. Это и есть ограничение паросочетания.
Строится двудольный граф: слева малые простые, справа большие. Для каждой выгодной пары \((p,q)\) добавляется ребро веса \(w(p,q)\). Реализация также добавляет нулевые фиктивные столбцы, чтобы малое простое можно было оставить без пары и сохранить его базовое значение \(P_p\).
Если \(\mathcal{M}\) - паросочетание, то его общий выигрыш равен
$$G(\mathcal{M})=\sum_{(p,q)\in \mathcal{M}}w(p,q).$$
Итоговая формула программы имеет вид
$$\boxed{\operatorname{Co}(n)=S_0+\max_{\mathcal{M}}G(\mathcal{M}).}$$
Максимум находится венгерским алгоритмом на прямоугольной матрице весов.
Базовые представители таковы:
$$1,\ 16,\ 27,\ 25,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,$$
поэтому
$$S_0=188.$$
Здесь \(\lfloor\sqrt{30}\rfloor=5\), то есть малыми простыми являются \(2,3,5\). Единственное положительное ребро - \((2,7)\):
$$M(2,7)=7\cdot 4=28,\qquad w(2,7)=28-16-7=5.$$
Следовательно,
$$\operatorname{Co}(30)=188+5=193,$$
что совпадает с проверочным значением в C++-файле.
При \(n=100\) базовая сумма равна \(S_0=1263\). У нескольких малых простых имеется по несколько выгодных партнёров, поэтому жадный выбор не гарантирует оптимума. Максимальное паросочетание, которое находят реализации, выбирает
$$64+11\to 88,\qquad 25+19\to 95,\qquad 49+13\to 91,$$
с выигрышами \(13\), \(51\) и \(29\). Общий прирост равен \(93\), значит
$$\operatorname{Co}(100)=1263+93=1356.$$
Все три файла решения реализуют одну и ту же математику. Сначала просеиваются все простые до \(n\), затем с помощью max_prime_power_leq_n вычисляются значения \(P_p\), суммируется базовый ответ и выполняется разбиение простых по порогу \(\lfloor\sqrt{n}\rfloor\).
Для каждой допустимой пары \((p,q)\), где \(p\) малое, \(q\) большое и \(pq\le n\), вычисляется лучший смешанный кандидат \(M(p,q)\). Положительные выигрыши записываются в матрицу весов размера
$$s\times(\ell+s),$$
где \(s\) - число малых простых, а \(\ell\) - число больших. Дополнительные \(s\) столбцов соответствуют фиктивному выбору “оставить как есть”. Функция hungarian_max_weight_bipartite возвращает максимальный добавочный выигрыш.
В C++ эта схема оформлена через prepare_solver_data, build_gain_edges и solve_co_optimized. Построение рёбер распараллелено по малым простым, а перед основной задачей проверяются контрольные значения \(\operatorname{Co}(10)=30\), \(\operatorname{Co}(30)=193\) и \(\operatorname{Co}(100)=1356\). Python и Java повторяют ту же логику в однопоточном виде.
Пусть \(s=\pi(\lfloor\sqrt{n}\rfloor)\), \(\ell=\pi(n)-s\). Решето работает за \(O(n\log\log n)\) времени и требует \(O(n)\) памяти. Построение матрицы выигрышей занимает \(O(E\log n)\), где \(E\) - число допустимых пар \((p,q)\) с \(p\le\sqrt{n}\lt q\) и \(pq\le n\); логарифмический множитель возникает из-за последовательного умножения \(p\) до границы \(n/q\).
Венгерский алгоритм на матрице \(s\times(\ell+s)\) работает за \(O(s^2(\ell+s))\) и использует \(O(s(\ell+s))\) памяти. Для реального входа \(n=200000\) имеем \(s=\pi(447)=86\), поэтому стадия matching остаётся небольшой.
لنعرّف \(\operatorname{Co}(n)\) على أنه أكبر مجموع ممكن لمجموعة جزئية \(A\subseteq\{1,2,\dots,n\}\) بحيث يكون كل عنصرين مختلفين فيها أوليين نسبيًا:
$$\operatorname{Co}(n)=\max\left\{\sum_{x\in A}x : A\subseteq\{1,\dots,n\},\ \gcd(a,b)=1\ \forall a\ne b\in A\right\}.$$
الحلول المحلية في C++ وPython وJava تستخدم البنية نفسها. تبدأ بخط أساس يضع لكل عدد أولي أفضل ممثل يعتمد عليه وحده، ثم تبحث فقط عن الاستبدالات المربحة التي تستبدل قوةً لعدد أولي صغيرًا مع عدد أولي كبير بعدد مختلط أكبر. هذه الاستبدالات تتحول إلى مسألة مطابقة ثنائية ذات وزن أعظمي.
إذا كان عددان مختاران يقبلان القسمة على الأولي نفسه \(p\)، فسيكون القاسم المشترك الأكبر بينهما على الأقل \(p\)، وهذا يناقض شرط التباين الأولي الزوجي. لذلك لا يجوز أن يظهر أي أولي إلا في عنصر مختار واحد على الأكثر.
بالنسبة إلى أولي ثابت \(p\le n\)، فإن أفضل عدد يستخدم هذا الأولي وحده هو أكبر قوة له لا تتجاوز \(n\):
$$P_p=\max\{p^k : k\ge 1,\ p^k\le n\}.$$
ومن هنا نحصل على مجموعة الأساس
$$B_0=\{1\}\cup\{P_p : p\in\mathbb{P},\ p\le n\},$$
وترمز \(\mathbb{P}\) هنا إلى مجموعة الأعداد الأولية.
وهي مجموعة صالحة لأن عناصرها غير التافهة هي قوى لأوليّات مختلفة. مجموع هذا الأساس هو
$$S_0=1+\sum_{p\le n}P_p,$$
حيث يجري الجمع على جميع الأعداد الأولية التي لا تتجاوز \(n\).
افترض أن \(x\le n\) له مجموعة من القواسم الأولية المختلفة \(T\). اختيار \(x\) يعني أننا لا نستطيع الإبقاء في الوقت نفسه على ممثلات الأساس \(P_r\) لكل \(r\in T\).
إذا كان \(P_r=r^k\)، فإن \(r^{k+1}>n\)، ومن ثم
$$P_r>\frac{n}{r}.$$
وبالتالي
$$\sum_{r\in T}P_r>n\sum_{r\in T}\frac{1}{r}.$$
إذا كان \(x\) يحتوي على ثلاثة عوامل أولية مختلفة أو أكثر، فإن أصغر مجموع ممكن للمقلوبات هو
$$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}>1,$$
ولذلك نحصل على \(\sum_{r\in T}P_r>n\ge x\). أي أن عددًا فيه ثلاثة أوليات مختلفة أو أكثر لا يمكن أن يحسّن خط الأساس. لهذا السبب تبحث الشيفرة فقط في التحسينات التي تستخدم أوليين بالضبط.
نقسم الأوليات عند \(\lfloor\sqrt{n}\rfloor\): الأوليات الصغيرة تحقق \(p\le \sqrt{n}\)، أما الأوليات الكبيرة فتحقق \(q>\sqrt{n}\).
لا يمكن لعددين أوليين كبيرين أن يجتمعا في عدد واحد لا يتجاوز \(n\)، لأن حاصل ضربهما يتجاوز \(n\) مباشرة. كذلك إذا كان \(q\) أوليًا كبيرًا فإن \(P_q=q\) لأن \(q^2>n\).
لذلك تشفّر الحلول المحلية الاستبدالات المربحة بأعداد من الشكل
$$M(p,q)=q\cdot \max\{p^a : a\ge 1,\ p^a q\le n\},\qquad p\le \sqrt{n}\lt q.$$
الحد الأقصى الداخلي تحسبه الدالة highest_power_with_limit(p, n / q). وإذا استبدلنا \(P_p\) و\(P_q\) بالعدد \(M(p,q)\) فإن مقدار الربح يساوي
$$w(p,q)=M(p,q)-P_p-P_q.$$
ولا يحتفظ البرنامج إلا بالقيم الموجبة من \(w(p,q)\).
كل أولي صغير يمكن أن يشارك في استبدال مختلط واحد على الأكثر، وكل أولي كبير يمكن أن يُستخدم مرة واحدة فقط أيضًا. هذا هو بالضبط قيد المطابقة.
نبني رسمًا ثنائيًا: في الجهة اليسرى الأوليات الصغيرة، وفي الجهة اليمنى الأوليات الكبيرة. ولكل زوج مربح \((p,q)\) نضيف حافة وزنها \(w(p,q)\). كما تضيف الحلول أعمدة وهمية ذات وزن صفري حتى يمكن ترك أولي صغير بلا مطابقة، وبذلك يحتفظ بقيمة الأساس \(P_p\).
إذا كانت \(\mathcal{M}\) مطابقة، فإن الربح الكلي هو
$$G(\mathcal{M})=\sum_{(p,q)\in \mathcal{M}}w(p,q).$$
وعليه فالقيمة التي تحسبها الشيفرة هي
$$\boxed{\operatorname{Co}(n)=S_0+\max_{\mathcal{M}}G(\mathcal{M}).}$$
ويُحسب هذا الحد الأقصى بخوارزمية Hungarian على مصفوفة إسناد مستطيلة.
ممثلات الأساس هي
$$1,\ 16,\ 27,\ 25,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,$$
ومن ثم
$$S_0=188.$$
هنا \(\lfloor\sqrt{30}\rfloor=5\)، لذا فالأوليات الصغيرة هي \(2,3,5\). الحافة الموجبة الوحيدة هي \((2,7)\):
$$M(2,7)=7\cdot 4=28,\qquad w(2,7)=28-16-7=5.$$
إذًا
$$\operatorname{Co}(30)=188+5=193,$$
وهو نفس مقدار التحقق الموجود في برنامج C++.
عندما \(n=100\) يكون مجموع الأساس \(S_0=1263\). لبعض الأوليات الصغيرة أكثر من شريك مربح، لذلك لا تكفي قاعدة جشعة بسيطة. المطابقة المثلى التي تعثر عليها الحلول تختار
$$64+11\to 88,\qquad 25+19\to 95,\qquad 49+13\to 91,$$
وبذلك تكون الأرباح \(13\) و\(51\) و\(29\)، أي ربحًا كليًا قدره \(93\)، ومن ثم
$$\operatorname{Co}(100)=1263+93=1356.$$
الملفات الثلاثة تطبق الرياضيات نفسها. تبدأ بغربلة جميع الأوليات حتى \(n\)، ثم تحسب كل قيمة \(P_p\) بواسطة max_prime_power_leq_n، وتجمع مجموع الأساس، ثم تفصل بين الأوليات الصغيرة والكبيرة عند \(\lfloor\sqrt{n}\rfloor\).
لكل زوج ممكن \((p,q)\) حيث \(p\) صغير و\(q\) كبير و\(pq\le n\)، تُحسب أفضل قيمة مختلطة \(M(p,q)\). ثم تُكتب الأرباح الموجبة في مصفوفة أوزان حجمها
$$s\times(\ell+s),$$
حيث \(s\) هو عدد الأوليات الصغيرة و\(\ell\) هو عدد الأوليات الكبيرة. الأعمدة الإضافية وعددها \(s\) تمثل اختيارات “عدم المطابقة”. بعد ذلك تُرجع الدالة hungarian_max_weight_bipartite أكبر ربح إضافي.
في نسخة C++ يُنظَّم هذا المسار عبر prepare_solver_data وbuild_gain_edges وsolve_co_optimized. كما يجري بناء الحواف على نحو متوازٍ، وتُفحَص قيم التحقق \(\operatorname{Co}(10)=30\) و\(\operatorname{Co}(30)=193\) و\(\operatorname{Co}(100)=1356\) قبل حل الحالة الافتراضية. أما نسختا Python وJava فتستخدمان البناء نفسه لكن بخيط واحد.
لنكتب \(s=\pi(\lfloor\sqrt{n}\rfloor)\) و\(\ell=\pi(n)-s\). الغربلة تكلف \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. أما بناء مصفوفة الأرباح فيكلف \(O(E\log n)\)، حيث \(E\) هو عدد الأزواج الممكنة \((p,q)\) التي تحقق \(p\le\sqrt{n}\lt q\) و\(pq\le n\)؛ والعامل اللوغاريتمي ناتج عن تكرار ضرب \(p\) حتى الحد \(n/q\).
خوارزمية Hungarian على مصفوفة \(s\times(\ell+s)\) تعمل بزمن \(O(s^2(\ell+s))\) وذاكرة \(O(s(\ell+s))\). بالنسبة إلى الإدخال الحقيقي \(n=200000\) نجد أن \(s=\pi(447)=86\)، ولذلك تبقى مرحلة المطابقة صغيرة عمليًا.