Let \(f(n)\) be the smallest positive integer such that
$$\gcd(f(n),m)\gt 1$$
for every positive integer \(m\le n\) whose last decimal digit is \(3\). The goal is to compute
$$L(n)=\ln f(n)$$
for \(n=10^6\), rounded to 6 decimal places. The C++, Python, and Java implementations work with logarithms because minimizing a product of primes is equivalent to minimizing the sum of their logarithms.
Define the target set
$$\mathcal{S}_n=\left\{m\in\mathbb{Z}_{\ge 1}: m\le n,\ m\equiv 3 \pmod{10}\right\}.$$
We want the cheapest set of primes whose union of divisibility covers every element of \(\mathcal{S}_n\).
If a prime \(p\) already divides the candidate integer, replacing \(p^k\) by \(p\) for any \(k\ge 2\) keeps the condition \(\gcd(f(n),m)\gt 1\) unchanged and only makes the number smaller. Therefore the optimal \(f(n)\) is squarefree.
So we only need to choose a set of primes \(\mathcal{T}\) and minimize
$$L(n)=\min_{\mathcal{T}} \sum_{p\in\mathcal{T}} \ln p,$$
subject to the requirement that every \(m\in\mathcal{S}_n\) is divisible by at least one prime in \(\mathcal{T}\).
Numbers ending in \(3\) are never divisible by \(2\) or \(5\), so those primes are irrelevant. Now split the remaining primes by their residue modulo \(10\):
$$\mathcal{P}_3=\left\{p\le n: p \text{ prime and } p\equiv 3 \pmod{10}\right\},$$
$$\mathcal{P}_7=\left\{p\le n: p \text{ prime and } p\equiv 7 \pmod{10}\right\},\qquad \mathcal{P}_9=\left\{p\le n: p \text{ prime and } p\equiv 9 \pmod{10}\right\}.$$
Primes congruent to \(1 \pmod{10}\) are never needed in an optimal answer. If \(q\equiv 1 \pmod{10}\) divides some \(m\in\mathcal{S}_n\), then \(m/q\) is still a positive integer ending in \(3\), and \(m/q\lt m\). Any selected prime that hits \(m/q\) also hits \(m\), so such numbers do not introduce a new obligation.
Every prime in \(\mathcal{P}_3\) is itself an element of \(\mathcal{S}_n\). Hence every feasible solution must contain all of them, contributing the unavoidable term
$$L_3=\sum_{p\in\mathcal{P}_3}\ln p.$$
After removing numbers that already contain a \(1 \pmod{10}\) prime factor or a mandatory \(3 \pmod{10}\) prime factor, any remaining target number is built only from primes in \(\mathcal{P}_7\cup\mathcal{P}_9\).
A product of such primes can end in \(3\) only if it contains at least one \(7 \pmod{10}\) prime. More precisely, if we count multiplicities, the number of \(7 \pmod{10}\) prime factors must be odd. That means every unresolved number contains either
$$\text{at least three primes from }\mathcal{P}_7,$$
or
$$\text{one prime from }\mathcal{P}_7 \text{ and at least one prime from }\mathcal{P}_9.$$
If \(a\in\mathcal{P}_7\) and \(a^3\le n\), then \(a^3\in\mathcal{S}_n\). Since \(a^3\) has no prime divisor other than \(a\), that prime is forced. Define
$$\mathcal{F}=\left\{a\in\mathcal{P}_7: a^3\le n\right\},\qquad L_F=\sum_{a\in\mathcal{F}}\ln a.$$
This also automatically covers every target containing at least three \(7 \pmod{10}\) prime factors: if \(a\le b\le c\) are three such factors of \(m\), then \(a^3\le abc\le m\le n\), so \(a\in\mathcal{F}\).
Once the forced set \(\mathcal{F}\) is included, the only unresolved cases are numbers containing a nonforced \(7 \pmod{10}\) prime and at least one \(9 \pmod{10}\) prime. Put
$$\mathcal{A}=\mathcal{P}_7\setminus\mathcal{F},\qquad \mathcal{B}=\mathcal{P}_9.$$
If \(a\in\mathcal{A}\), \(b\in\mathcal{B}\), and \(ab\le n\), then \(ab\equiv 3 \pmod{10}\), so \(ab\in\mathcal{S}_n\). Therefore any valid prime set must include at least one of \(a\) or \(b\).
Conversely, every unresolved target \(m\) contains some pair \(a\in\mathcal{A}\), \(b\in\mathcal{B}\) with \(ab\mid m\), hence \(ab\le m\le n\). Covering all such pairs is therefore equivalent to covering all remaining target numbers.
The optimization becomes
$$\min_{X\subseteq\mathcal{A},\,Y\subseteq\mathcal{B}} \left(\sum_{a\in X}\ln a+\sum_{b\in Y}\ln b\right),$$
subject to the rule that for every pair \((a,b)\) with \(ab\le n\), at least one endpoint is chosen.
Build a bipartite graph
$$G=(\mathcal{A},\mathcal{B},E),\qquad E=\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
Choosing primes from \(X\subseteq\mathcal{A}\) and \(Y\subseteq\mathcal{B}\) that hit every admissible pair is exactly a weighted vertex-cover problem on this graph, with weights \(\ln a\) and \(\ln b\).
The standard flow reduction applies:
$$s\to a \text{ has capacity } \ln a,\qquad b\to t \text{ has capacity } \ln b,$$
and every graph edge \(a\to b\) receives a very large capacity. Then the minimum \(s\)-\(t\) cut equals the minimum weighted vertex cover. Hence
$$L(n)=L_3+L_F+\operatorname{mincut}(G).$$
For \(n=800\), the forced \(7 \pmod{10}\) prime is only \(7\), because
$$7^3=343\le 800,\qquad 17^3=4913\gt 800.$$
Among nonforced \(7 \pmod{10}\) primes, the only ones that still form admissible products with a \(9 \pmod{10}\) prime are \(17\) and \(37\). On the \(9 \pmod{10}\) side, the relevant primes are \(19\) and \(29\). The valid edges are
$$17\cdot 19=323,\qquad 17\cdot 29=493,\qquad 37\cdot 19=703,$$
all of which are at most \(800\) and end in \(3\).
So the graph has edges
$$ (17,19),\qquad (17,29),\qquad (37,19). $$
The cheapest cover is \(\{17,19\}\): prime \(17\) covers two edges, prime \(19\) covers the third, and any cover using \(29\) or \(37\) has larger total logarithmic weight. Therefore the optimization stage contributes the factors \(7\), \(17\), and \(19\), and
$$f(800)=\left(\prod_{\substack{p\le 800\\ p\equiv 3 \pmod{10}}} p\right)\cdot 7\cdot 17\cdot 19.$$
The C++, Python, and Java implementations begin with a prime sieve up to \(n\). They partition the primes into the residue classes \(3\), \(7\), and \(9 \pmod{10}\), immediately add the logarithms of all mandatory \(3 \pmod{10}\) primes, and then add the logarithms of all forced \(7 \pmod{10}\) primes satisfying \(p^3\le n\).
Next, they construct only the useful part of the bipartite graph. For each nonforced \(7 \pmod{10}\) prime \(a\), every \(9 \pmod{10}\) prime \(b\le n/a\) creates one edge. Vertices that never appear in any edge are ignored, because they cannot affect the minimum cover.
A standard max-flow/min-cut routine is then run on the source-left-right-sink network. The cut value is added to the two mandatory logarithmic contributions, and the final result is rounded to six decimal places. The implementations also use the checkpoints
$$L(40)=6.799056,\qquad L(2800)=715.019337$$
as sanity checks for the construction.
The prime sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. Let
$$|E|=\#\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
Building the graph takes \(O(|\mathcal{A}|\log|\mathcal{B}|+|E|)\) time: each left-side prime first finds the cutoff point among the sorted right-side primes, then emits exactly its incident edges. The max-flow stage runs on a network with \(O(|\mathcal{A}|+|\mathcal{B}|)\) vertices and \(O(|E|)\) finite edges, so it dominates the remaining runtime. Overall memory usage after the sieve is \(O(|\mathcal{A}|+|\mathcal{B}|+|E|)\).
Sei \(f(n)\) die kleinste positive ganze Zahl mit der Eigenschaft, dass
$$\gcd(f(n),m)\gt 1$$
für jede positive ganze Zahl \(m\le n\) gilt, deren letzte Dezimalziffer \(3\) ist. Gesucht ist
$$L(n)=\ln f(n)$$
für \(n=10^6\), gerundet auf 6 Nachkommastellen. Die C++-, Python- und Java-Implementierungen arbeiten im Logarithmus, weil das Minimieren eines Primfaktorprodukts gleichbedeutend mit dem Minimieren der Summe der Logarithmen ist.
Wir definieren die Zielmenge
$$\mathcal{S}_n=\left\{m\in\mathbb{Z}_{\ge 1}: m\le n,\ m\equiv 3 \pmod{10}\right\}.$$
Gesucht ist also die billigste Primzahlmenge, die jede Zahl aus \(\mathcal{S}_n\) über mindestens einen gemeinsamen Primteiler trifft.
Wenn eine Primzahl \(p\) den Kandidaten schon teilt, dann ist eine höhere Potenz \(p^k\) mit \(k\ge 2\) nutzlos: Die Bedingung \(\gcd(f(n),m)\gt 1\) bleibt unverändert, das Produkt wird aber größer. Daher ist das optimale \(f(n)\) quadratfrei.
Wir müssen also nur eine Primzahlmenge \(\mathcal{T}\) wählen und
$$L(n)=\min_{\mathcal{T}} \sum_{p\in\mathcal{T}} \ln p$$
minimieren, unter der Nebenbedingung, dass jede Zahl \(m\in\mathcal{S}_n\) durch mindestens eine Primzahl aus \(\mathcal{T}\) teilbar ist.
Zahlen mit Endziffer \(3\) sind nie durch \(2\) oder \(5\) teilbar, also spielen diese Primzahlen keine Rolle. Nun zerlegen wir die übrigen Primzahlen nach ihrer Restklasse modulo \(10\):
$$\mathcal{P}_3=\left\{p\le n: p \text{ prim und } p\equiv 3 \pmod{10}\right\},$$
$$\mathcal{P}_7=\left\{p\le n: p \text{ prim und } p\equiv 7 \pmod{10}\right\},\qquad \mathcal{P}_9=\left\{p\le n: p \text{ prim und } p\equiv 9 \pmod{10}\right\}.$$
Primzahlen mit \(p\equiv 1 \pmod{10}\) werden in einer optimalen Lösung nie benötigt. Falls \(q\equiv 1 \pmod{10}\) eine Zahl \(m\in\mathcal{S}_n\) teilt, dann endet auch \(m/q\) auf \(3\) und ist kleiner als \(m\). Jede gewählte Primzahl, die \(m/q\) trifft, trifft automatisch auch \(m\). Solche Zahlen erzeugen also keinen neuen Zwang.
Jede Primzahl aus \(\mathcal{P}_3\) ist selbst ein Element von \(\mathcal{S}_n\). Deshalb muss jede zulässige Lösung alle diese Primzahlen enthalten. Ihr unvermeidbarer Beitrag ist
$$L_3=\sum_{p\in\mathcal{P}_3}\ln p.$$
Wenn man alle Zahlen entfernt, die bereits einen Primfaktor \(1 \pmod{10}\) oder einen obligatorischen Primfaktor \(3 \pmod{10}\) besitzen, bleiben nur noch Produkte aus Primzahlen der Mengen \(\mathcal{P}_7\) und \(\mathcal{P}_9\) übrig.
Ein solches Produkt kann nur dann auf \(3\) enden, wenn es mindestens eine Primzahl aus \(\mathcal{P}_7\) enthält. Genauer gesagt muss die Anzahl der Primfaktoren aus \(\mathcal{P}_7\), mit Vielfachheiten gezählt, ungerade sein. Jede noch offene Zielzahl enthält also entweder
$$\text{mindestens drei Primzahlen aus }\mathcal{P}_7,$$
oder
$$\text{eine Primzahl aus }\mathcal{P}_7 \text{ und mindestens eine aus }\mathcal{P}_9.$$
Gilt für \(a\in\mathcal{P}_7\) die Bedingung \(a^3\le n\), dann gehört \(a^3\) selbst zu \(\mathcal{S}_n\). Da \(a^3\) keinen anderen Primteiler als \(a\) hat, ist \(a\) erzwungen. Wir definieren
$$\mathcal{F}=\left\{a\in\mathcal{P}_7: a^3\le n\right\},\qquad L_F=\sum_{a\in\mathcal{F}}\ln a.$$
Damit sind zugleich alle Zielzahlen mit mindestens drei Primfaktoren aus \(\mathcal{P}_7\) automatisch abgedeckt: Für drei solcher Faktoren \(a\le b\le c\) gilt \(a^3\le abc\le m\le n\), also \(a\in\mathcal{F}\).
Nachdem \(\mathcal{F}\) aufgenommen wurde, bleiben nur Fälle übrig, die einen nicht erzwungenen Primfaktor \(7 \pmod{10}\) und mindestens einen Primfaktor \(9 \pmod{10}\) enthalten. Setze
$$\mathcal{A}=\mathcal{P}_7\setminus\mathcal{F},\qquad \mathcal{B}=\mathcal{P}_9.$$
Falls \(a\in\mathcal{A}\), \(b\in\mathcal{B}\) und \(ab\le n\), dann gilt \(ab\equiv 3 \pmod{10}\), also \(ab\in\mathcal{S}_n\). Jede gültige Lösung muss deshalb mindestens einen der beiden Endpunkte \(a\) oder \(b\) auswählen.
Umgekehrt enthält jede noch offene Zielzahl \(m\) ein Paar \(a\in\mathcal{A}\), \(b\in\mathcal{B}\) mit \(ab\mid m\), also insbesondere \(ab\le m\le n\). Es reicht daher genau, alle diese Paare zu treffen.
Damit erhalten wir das Optimierungsproblem
$$\min_{X\subseteq\mathcal{A},\,Y\subseteq\mathcal{B}} \left(\sum_{a\in X}\ln a+\sum_{b\in Y}\ln b\right),$$
wobei für jedes Paar \((a,b)\) mit \(ab\le n\) mindestens ein Endpunkt gewählt werden muss.
Wir bauen den bipartiten Graphen
$$G=(\mathcal{A},\mathcal{B},E),\qquad E=\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
Eine Auswahl \(X\subseteq\mathcal{A}\), \(Y\subseteq\mathcal{B}\), die jedes zulässige Paar trifft, ist genau ein gewichtetes Vertex Cover dieses Graphen mit Gewichten \(\ln a\) bzw. \(\ln b\).
Dann greift die Standardreduktion auf Min-Cut: Die Kante \(s\to a\) erhält Kapazität \(\ln a\), die Kante \(b\to t\) erhält Kapazität \(\ln b\), und jede Graphkante bekommt eine sehr große Kapazität. Der minimale \(s\)-\(t\)-Schnitt hat denselben Wert wie das billigste gewichtete Vertex Cover. Somit gilt
$$L(n)=L_3+L_F+\operatorname{mincut}(G).$$
Für \(n=800\) ist die einzige erzwungene Primzahl \(7 \pmod{10}\) gleich \(7\), denn
$$7^3=343\le 800,\qquad 17^3=4913\gt 800.$$
Unter den nicht erzwungenen Primzahlen \(7 \pmod{10}\) bilden nur \(17\) und \(37\) noch zulässige Produkte mit einer Primzahl \(9 \pmod{10}\). Auf der rechten Seite sind daher nur \(19\) und \(29\) relevant. Die gültigen Produkte lauten
$$17\cdot 19=323,\qquad 17\cdot 29=493,\qquad 37\cdot 19=703,$$
also die Graphkanten
$$ (17,19),\qquad (17,29),\qquad (37,19). $$
Die billigste Überdeckung ist \(\{17,19\}\): Die Primzahl \(17\) deckt zwei Kanten ab, \(19\) die dritte, und jede Lösung mit \(29\) oder \(37\) ist schwerer. Daher trägt die Optimierungsstufe die Faktoren \(7\), \(17\) und \(19\) bei, also
$$f(800)=\left(\prod_{\substack{p\le 800\\ p\equiv 3 \pmod{10}}} p\right)\cdot 7\cdot 17\cdot 19.$$
Die C++-, Python- und Java-Implementierungen beginnen mit einem Primzahlsieb bis \(n\). Anschließend teilen sie die Primzahlen in die Restklassen \(3\), \(7\) und \(9 \pmod{10}\) auf, addieren sofort die Logarithmen aller obligatorischen Primzahlen \(3 \pmod{10}\) und dann die Logarithmen aller erzwungenen Primzahlen \(7 \pmod{10}\) mit \(p^3\le n\).
Danach wird nur der tatsächlich benötigte Teil des bipartiten Graphen aufgebaut. Für jede nicht erzwungene Primzahl \(a\equiv 7 \pmod{10}\) erzeugt jede Primzahl \(b\equiv 9 \pmod{10}\) mit \(b\le n/a\) genau eine Kante. Knoten ohne inzidente Kante werden weggelassen, weil sie den optimalen Schnitt nicht beeinflussen können.
Auf dem so entstehenden Quelle-Links-Rechts-Senke-Netzwerk läuft dann ein Standardverfahren für Max-Flow beziehungsweise Min-Cut. Der Schnittwert wird zu den beiden unvermeidbaren Logarithmenbeiträgen addiert, und das Ergebnis wird auf sechs Nachkommastellen gerundet. Als zusätzliche Plausibilitätsprüfungen verwenden die Implementierungen die Werte
$$L(40)=6.799056,\qquad L(2800)=715.019337.$$
Das Primzahlsieb benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Sei
$$|E|=\#\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
Der Aufbau des Graphen kostet \(O(|\mathcal{A}|\log|\mathcal{B}|+|E|)\) Zeit: Für jede Primzahl links wird zuerst die Grenzposition in der sortierten rechten Liste gefunden, danach werden genau die tatsächlich vorhandenen Kanten erzeugt. Die Max-Flow-Stufe arbeitet auf einem Netzwerk mit \(O(|\mathcal{A}|+|\mathcal{B}|)\) Knoten und \(O(|E|)\) endlichen Kanten und dominiert damit den restlichen Aufwand. Nach dem Sieb liegt der Speicherbedarf insgesamt bei \(O(|\mathcal{A}|+|\mathcal{B}|+|E|)\).
\(f(n)\),
$$\gcd(f(n),m)\gt 1$$
koşulunu son basamağı \(3\) olan ve \(m\le n\) şartını sağlayan her pozitif tamsayı için sağlayan en küçük pozitif tamsayı olsun. İstenen büyüklük
$$L(n)=\ln f(n)$$
olup \(n=10^6\) için 6 ondalık basamağa yuvarlanır. C++, Python ve Java implementasyonları, asal çarpanların çarpımını küçültmek yerine logaritmalar toplamını küçültür.
Hedef kümesini
$$\mathcal{S}_n=\left\{m\in\mathbb{Z}_{\ge 1}: m\le n,\ m\equiv 3 \pmod{10}\right\}$$
olarak tanımlayalım. Amaç, bu kümedeki her sayıyla en az bir ortak asal bölen paylaşan en ucuz asal kümesini bulmaktır.
Eğer aday sayıda bir asal \(p\) zaten varsa, \(p^k\) biçiminde daha yüksek üsler kullanmak hiçbir yeni sayı yakalatmaz; \(\gcd(f(n),m)\gt 1\) koşulu değişmez, sadece sayı büyür. Bu yüzden en iyi çözüm karesiz olur.
Dolayısıyla yalnızca bir asal kümesi \(\mathcal{T}\) seçeriz ve
$$L(n)=\min_{\mathcal{T}} \sum_{p\in\mathcal{T}} \ln p$$
ifadesini küçültürüz. Yan koşul, her \(m\in\mathcal{S}_n\) sayısının \(\mathcal{T}\) içindeki en az bir asal tarafından bölünmesidir.
Sonu \(3\) ile biten sayılar \(2\) veya \(5\) ile bölünmez; bu yüzden bu asallar tamamen önemsizdir. Kalan asalları mod \(10\)'a göre ayıralım:
$$\mathcal{P}_3=\left\{p\le n: p \text{ asal ve } p\equiv 3 \pmod{10}\right\},$$
$$\mathcal{P}_7=\left\{p\le n: p \text{ asal ve } p\equiv 7 \pmod{10}\right\},\qquad \mathcal{P}_9=\left\{p\le n: p \text{ asal ve } p\equiv 9 \pmod{10}\right\}.$$
\(1 \pmod{10}\) sınıfındaki asallar optimal çözümde hiç gerekmez. Gerçekten, \(q\equiv 1 \pmod{10}\) bir asal \(m\in\mathcal{S}_n\)'yi bölüyorsa, \(m/q\) sayısı da yine \(3\) ile biter ve \(m/q\lt m\) olur. \(m/q\)'yu yakalayan herhangi bir seçilmiş asal zaten \(m\)'yi de yakalar. Dolayısıyla bu tür sayılar yeni bir zorunluluk getirmez.
\(\mathcal{P}_3\) içindeki her asal zaten \(\mathcal{S}_n\)'nin kendisinde bulunduğundan hepsi zorunludur. Kaçınılmaz katkı
$$L_3=\sum_{p\in\mathcal{P}_3}\ln p$$
şeklindedir.
\(1 \pmod{10}\) sınıfından bir asal çarpan taşıyan veya zaten zorunlu bir \(3 \pmod{10}\) asal içeren sayıları çıkardıktan sonra geriye sadece \(\mathcal{P}_7\cup\mathcal{P}_9\) içinden oluşan çarpımlar kalır.
Böyle bir çarpımın sonu ancak en az bir tane \(7 \pmod{10}\) asal varsa \(3\) olabilir. Daha net söylersek, çokluklarıyla sayıldığında \(7 \pmod{10}\) tipindeki asal çarpan sayısı tek olmalıdır. Bu yüzden çözümsüz kalan her hedef sayı ya
$$\text{en az üç tane } \mathcal{P}_7 \text{ asalı içerir},$$
ya da
$$\text{bir tane } \mathcal{P}_7 \text{ asalı ve en az bir tane } \mathcal{P}_9 \text{ asalı içerir}.$$
Eğer \(a\in\mathcal{P}_7\) ve \(a^3\le n\) ise, \(a^3\) sayısı doğrudan \(\mathcal{S}_n\) içindedir. \(a^3\)'ün tek asal böleni \(a\) olduğundan bu asal zorunludur. Şunu tanımlayalım:
$$\mathcal{F}=\left\{a\in\mathcal{P}_7: a^3\le n\right\},\qquad L_F=\sum_{a\in\mathcal{F}}\ln a.$$
Bu aynı zamanda üç veya daha fazla \(7 \pmod{10}\) tipi asal içeren bütün hedefleri de otomatik kapatır. Çünkü \(a\le b\le c\) olmak üzere üç böyle çarpan varsa, \(a^3\le abc\le m\le n\) olur ve dolayısıyla \(a\in\mathcal{F}\) çıkar.
\(\mathcal{F}\) eklendikten sonra çözülmemiş tek durumlar, zorunlu olmayan bir \(7 \pmod{10}\) asalı ile en az bir \(9 \pmod{10}\) asalı içeren sayılardır. Şimdi
$$\mathcal{A}=\mathcal{P}_7\setminus\mathcal{F},\qquad \mathcal{B}=\mathcal{P}_9$$
olsun. Eğer \(a\in\mathcal{A}\), \(b\in\mathcal{B}\) ve \(ab\le n\) ise, \(ab\equiv 3 \pmod{10}\) olduğundan \(ab\in\mathcal{S}_n\) olur. O halde geçerli herhangi bir çözümde \(a\) veya \(b\)'den en az biri seçilmelidir.
Tersine, çözülmemiş her hedef sayı \(m\), \(ab\mid m\) olacak şekilde bazı \(a\in\mathcal{A}\) ve \(b\in\mathcal{B}\) içerir; dolayısıyla \(ab\le m\le n\). Bu yüzden bütün bu çiftleri kapatmak, kalan tüm hedefleri kapatmakla tam olarak aynıdır.
Böylece optimizasyon problemi
$$\min_{X\subseteq\mathcal{A},\,Y\subseteq\mathcal{B}} \left(\sum_{a\in X}\ln a+\sum_{b\in Y}\ln b\right)$$
haline gelir; burada \(ab\le n\) olan her çift için en az bir uç nokta seçilmelidir.
Şu bipartit grafı kuralım:
$$G=(\mathcal{A},\mathcal{B},E),\qquad E=\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
\(X\subseteq\mathcal{A}\) ve \(Y\subseteq\mathcal{B}\) seçip her uygun çifti kapatma işi, tam olarak bu graf üzerinde ağırlıklı vertex-cover problemidir; ağırlıklar sırasıyla \(\ln a\) ve \(\ln b\)'dir.
Standart akış indirgemesi uygulanır: \(s\to a\) kapasitesi \(\ln a\), \(b\to t\) kapasitesi \(\ln b\), her graf kenarı için kapasite ise çok büyük bir sayı alınır. Böylece minimum \(s\)-\(t\) kesiti ile minimum ağırlıklı vertex cover aynı değeri verir. Sonuç olarak
$$L(n)=L_3+L_F+\operatorname{mincut}(G)$$
elde edilir.
\(n=800\) için zorunlu tek \(7 \pmod{10}\) asalı \(7\)'dir; çünkü
$$7^3=343\le 800,\qquad 17^3=4913\gt 800.$$
Zorunlu olmayan \(7 \pmod{10}\) asalları içinde yalnızca \(17\) ve \(37\), bir \(9 \pmod{10}\) asalıyla birlikte uygun çarpım oluşturur. Sağ tarafta ise yalnızca \(19\) ve \(29\) önemlidir. Geçerli çarpımlar
$$17\cdot 19=323,\qquad 17\cdot 29=493,\qquad 37\cdot 19=703$$
olduğu için grafın kenarları
$$ (17,19),\qquad (17,29),\qquad (37,19) $$
şeklindedir. En ucuz örtü \(\{17,19\}\) olur: \(17\) iki kenarı, \(19\) kalan kenarı kapatır; \(29\) veya \(37\) içeren her örtü daha pahalıdır. Dolayısıyla optimizasyon aşaması \(7\), \(17\) ve \(19\) çarpanlarını üretir ve
$$f(800)=\left(\prod_{\substack{p\le 800\\ p\equiv 3 \pmod{10}}} p\right)\cdot 7\cdot 17\cdot 19$$
olur.
C++, Python ve Java implementasyonları önce \(n\)'e kadar bütün asalları süzer. Ardından bunları \(3\), \(7\) ve \(9 \pmod{10}\) kalıntı sınıflarına ayırır; zorunlu \(3 \pmod{10}\) asallarının logaritmalarını hemen toplar, sonra da \(p^3\le n\) koşulunu sağlayan zorunlu \(7 \pmod{10}\) asallarını ekler.
Sonraki adımda yalnızca gerekli bipartit graf parçası kurulur. Zorunlu olmayan her \(a\equiv 7 \pmod{10}\) asalı için, \(b\le n/a\) şartını sağlayan her \(b\equiv 9 \pmod{10}\) asalı bir kenar üretir. Hiç kenara dokunmayan düğümler akış ağına alınmaz; çünkü optimum değeri değiştiremezler.
Daha sonra kaynak-sol-sağ-hedef ağı üzerinde standart bir max-flow/min-cut rutini çalıştırılır. Kesit değeri iki zorunlu logaritmik katkıyla toplanır ve sonuç altı ondalık basamağa yuvarlanır. Implementasyonlar ayrıca
$$L(40)=6.799056,\qquad L(2800)=715.019337$$
kontrollerini kullanarak kurulumun doğruluğunu sınar.
Asal süzgeci \(O(n\log\log n)\) zaman ve \(O(n)\) bellek kullanır. Şimdi
$$|E|=\#\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}$$
olsun. Grafı kurmak \(O(|\mathcal{A}|\log|\mathcal{B}|+|E|)\) zaman alır; çünkü soldaki her asal için önce sağdaki sıralı listede sınır nokta bulunur, sonra yalnızca gerçekten var olan kenarlar eklenir. Max-flow aşaması \(O(|\mathcal{A}|+|\mathcal{B}|)\) düğüm ve \(O(|E|)\) sonlu kenar içeren bir ağ üzerinde çalıştığından geri kalan sürenin baskın kısmını oluşturur. Süzgeç sonrası toplam bellek kullanımı \(O(|\mathcal{A}|+|\mathcal{B}|+|E|)\) seviyesindedir.
Sea \(f(n)\) el menor entero positivo tal que
$$\gcd(f(n),m)\gt 1$$
para todo entero positivo \(m\le n\) cuya última cifra decimal sea \(3\). Debemos calcular
$$L(n)=\ln f(n)$$
para \(n=10^6\), redondeado a 6 decimales. Las implementaciones en C++, Python y Java trabajan con logaritmos porque minimizar un producto de primos equivale a minimizar la suma de sus logaritmos.
Definimos el conjunto objetivo
$$\mathcal{S}_n=\left\{m\in\mathbb{Z}_{\ge 1}: m\le n,\ m\equiv 3 \pmod{10}\right\}.$$
El problema consiste en encontrar el conjunto de primos de peso total mínimo que cubra, por divisibilidad, a todos los elementos de \(\mathcal{S}_n\).
Si un primo \(p\) ya divide al candidato, sustituir \(p^k\) por \(p\) con \(k\ge 2\) no cambia la condición \(\gcd(f(n),m)\gt 1\), pero sí hace el número más pequeño. Por tanto, el \(f(n)\) óptimo es libre de cuadrados.
Solo tenemos que escoger un conjunto de primos \(\mathcal{T}\) y minimizar
$$L(n)=\min_{\mathcal{T}} \sum_{p\in\mathcal{T}} \ln p,$$
bajo la restricción de que cada \(m\in\mathcal{S}_n\) sea divisible por al menos un primo de \(\mathcal{T}\).
Los números que terminan en \(3\) nunca son divisibles por \(2\) ni por \(5\), así que esos primos se descartan por completo. Separaremos los demás primos según su residuo módulo \(10\):
$$\mathcal{P}_3=\left\{p\le n: p \text{ es primo y } p\equiv 3 \pmod{10}\right\},$$
$$\mathcal{P}_7=\left\{p\le n: p \text{ es primo y } p\equiv 7 \pmod{10}\right\},\qquad \mathcal{P}_9=\left\{p\le n: p \text{ es primo y } p\equiv 9 \pmod{10}\right\}.$$
Los primos congruentes con \(1 \pmod{10}\) nunca son necesarios en una solución óptima. Si \(q\equiv 1 \pmod{10}\) divide a cierto \(m\in\mathcal{S}_n\), entonces \(m/q\) sigue terminando en \(3\) y además es menor que \(m\). Cualquier primo seleccionado que cubra a \(m/q\) también cubre a \(m\), así que esos factores no generan una obligación nueva.
En cambio, cada primo de \(\mathcal{P}_3\) ya pertenece por sí mismo a \(\mathcal{S}_n\), de modo que todos son obligatorios. Su contribución inevitable es
$$L_3=\sum_{p\in\mathcal{P}_3}\ln p.$$
Después de eliminar los números que ya contienen un primo \(1 \pmod{10}\) o un primo obligatorio \(3 \pmod{10}\), cualquier objetivo restante está compuesto solo por primos de \(\mathcal{P}_7\cup\mathcal{P}_9\).
Un producto de ese tipo solo puede terminar en \(3\) si contiene al menos un primo \(7 \pmod{10}\). Más concretamente, contando multiplicidades, el número de factores \(7 \pmod{10}\) debe ser impar. Por eso todo número aún no cubierto contiene o bien
$$\text{al menos tres primos de }\mathcal{P}_7,$$
o bien
$$\text{un primo de }\mathcal{P}_7 \text{ y al menos un primo de }\mathcal{P}_9.$$
Si \(a\in\mathcal{P}_7\) satisface \(a^3\le n\), entonces \(a^3\in\mathcal{S}_n\). Como \(a^3\) no tiene ningún otro divisor primo aparte de \(a\), ese primo está forzado. Definimos
$$\mathcal{F}=\left\{a\in\mathcal{P}_7: a^3\le n\right\},\qquad L_F=\sum_{a\in\mathcal{F}}\ln a.$$
Esto además cubre automáticamente todos los objetivos con al menos tres primos de tipo \(7\): si \(a\le b\le c\) son tres de esos factores en \(m\), entonces \(a^3\le abc\le m\le n\), luego \(a\in\mathcal{F}\).
Una vez añadida la familia \(\mathcal{F}\), solo quedan sin resolver los números que contienen un primo no forzado \(7 \pmod{10}\) y al menos un primo \(9 \pmod{10}\). Sea
$$\mathcal{A}=\mathcal{P}_7\setminus\mathcal{F},\qquad \mathcal{B}=\mathcal{P}_9.$$
Si \(a\in\mathcal{A}\), \(b\in\mathcal{B}\) y \(ab\le n\), entonces \(ab\equiv 3 \pmod{10}\), así que \(ab\in\mathcal{S}_n\). Por lo tanto, cualquier solución válida debe elegir al menos uno de \(a\) o \(b\).
Recíprocamente, cada objetivo aún pendiente contiene un par \(a\in\mathcal{A}\), \(b\in\mathcal{B}\) con \(ab\mid m\), y por eso \(ab\le m\le n\). Cubrir todos esos pares equivale exactamente a cubrir todos los objetivos restantes.
La optimización queda así:
$$\min_{X\subseteq\mathcal{A},\,Y\subseteq\mathcal{B}} \left(\sum_{a\in X}\ln a+\sum_{b\in Y}\ln b\right),$$
sujeta a que todo par con \(ab\le n\) tenga al menos un extremo elegido.
Construimos el grafo bipartito
$$G=(\mathcal{A},\mathcal{B},E),\qquad E=\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
Elegir \(X\subseteq\mathcal{A}\) y \(Y\subseteq\mathcal{B}\) que cubran todos los pares admisibles es exactamente encontrar un vertex cover ponderado en ese grafo, con pesos \(\ln a\) y \(\ln b\).
La reducción estándar a flujo dice: conectar la fuente con cada \(a\) con capacidad \(\ln a\), conectar cada \(b\) con el sumidero con capacidad \(\ln b\), y dar una capacidad muy grande a cada arista del grafo. El valor del corte mínimo coincide entonces con el del cover ponderado mínimo. En consecuencia,
$$L(n)=L_3+L_F+\operatorname{mincut}(G).$$
Para \(n=800\), el único primo forzado de tipo \(7 \pmod{10}\) es \(7\), porque
$$7^3=343\le 800,\qquad 17^3=4913\gt 800.$$
Entre los primos \(7 \pmod{10}\) no forzados, solo \(17\) y \(37\) generan todavía productos admisibles con un primo \(9 \pmod{10}\). En la parte derecha solo intervienen \(19\) y \(29\). Los productos válidos son
$$17\cdot 19=323,\qquad 17\cdot 29=493,\qquad 37\cdot 19=703,$$
así que el grafo tiene las aristas
$$ (17,19),\qquad (17,29),\qquad (37,19). $$
El cover más barato es \(\{17,19\}\): \(17\) cubre dos aristas y \(19\) cubre la tercera, mientras que cualquier cover que use \(29\) o \(37\) pesa más. Por eso la etapa de optimización aporta los factores \(7\), \(17\) y \(19\), y
$$f(800)=\left(\prod_{\substack{p\le 800\\ p\equiv 3 \pmod{10}}} p\right)\cdot 7\cdot 17\cdot 19.$$
Las implementaciones en C++, Python y Java empiezan generando todos los primos hasta \(n\) con una criba. Después los separan en las clases residuales \(3\), \(7\) y \(9 \pmod{10}\), suman de inmediato los logaritmos de todos los primos obligatorios \(3 \pmod{10}\) y luego añaden los logaritmos de los primos forzados \(7 \pmod{10}\) que cumplen \(p^3\le n\).
A continuación construyen solo la parte útil del grafo bipartito. Para cada primo no forzado \(a\equiv 7 \pmod{10}\), todo primo \(b\equiv 9 \pmod{10}\) con \(b\le n/a\) genera una arista. Los vértices que no participan en ninguna arista se omiten porque no pueden alterar el cover óptimo.
Sobre la red fuente-izquierda-derecha-sumidero se ejecuta entonces un algoritmo estándar de max-flow/min-cut. El valor del corte se suma a las dos contribuciones logarítmicas obligatorias y el resultado final se redondea a seis decimales. Además, las implementaciones verifican la construcción con los puntos de control
$$L(40)=6.799056,\qquad L(2800)=715.019337.$$
La criba de primos cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Sea
$$|E|=\#\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
Construir el grafo requiere \(O(|\mathcal{A}|\log|\mathcal{B}|+|E|)\) tiempo: cada primo del lado izquierdo encuentra primero el punto de corte en la lista ordenada del lado derecho y luego emite exactamente sus aristas incidentes. La fase de max-flow trabaja sobre una red con \(O(|\mathcal{A}|+|\mathcal{B}|)\) vértices y \(O(|E|)\) aristas finitas, por lo que domina el resto del tiempo. Después de la criba, la memoria total es \(O(|\mathcal{A}|+|\mathcal{B}|+|E|)\).
设 \(f(n)\) 是满足下面条件的最小正整数：
$$\gcd(f(n),m)\gt 1$$
对每个不超过 \(n\)、且十进制末位是 \(3\) 的正整数 \(m\) 都成立。题目要求计算
$$L(n)=\ln f(n)$$
在 \(n=10^6\) 时的数值，并保留 6 位小数。C++、Python 和 Java 实现都把问题写成“选哪些素数最便宜”，再把乘积最小化改写为对数和最小化。
定义目标集合
$$\mathcal{S}_n=\left\{m\in\mathbb{Z}_{\ge 1}: m\le n,\ m\equiv 3 \pmod{10}\right\}.$$
我们要找的是一个素数集合，使得 \(\mathcal{S}_n\) 中每个数都至少含有集合中的一个素因子，而且该集合对应的总代价最小。
如果候选答案里已经含有素数 \(p\)，那么把 \(p^k\) 换回 \(p\)（其中 \(k\ge 2\)）并不会改变任何一个 \(\gcd(f(n),m)\gt 1\) 的判断，因为只要有一个共同素因子就够了；这样做只会让数更小。所以最优的 \(f(n)\) 一定是平方因子自由的。
于是我们只需要选择一个素数集合 \(\mathcal{T}\)，并最小化
$$L(n)=\min_{\mathcal{T}} \sum_{p\in\mathcal{T}} \ln p,$$
同时要求每个 \(m\in\mathcal{S}_n\) 都能被 \(\mathcal{T}\) 中至少一个素数整除。也就是说，问题已经变成了一个带权覆盖问题，权值就是 \(\ln p\)。
末位是 \(3\) 的整数不可能被 \(2\) 或 \(5\) 整除，所以这两个素数完全无关。把剩下的素数按模 \(10\) 的余数分成三类：
$$\mathcal{P}_3=\left\{p\le n: p \text{ 是素数且 } p\equiv 3 \pmod{10}\right\},$$
$$\mathcal{P}_7=\left\{p\le n: p \text{ 是素数且 } p\equiv 7 \pmod{10}\right\},\qquad \mathcal{P}_9=\left\{p\le n: p \text{ 是素数且 } p\equiv 9 \pmod{10}\right\}.$$
余数为 \(1\) 的素数在最优解里永远不需要出现。原因是：若 \(q\equiv 1 \pmod{10}\) 整除某个 \(m\in\mathcal{S}_n\)，那么 \(m/q\) 仍然以 \(3\) 结尾，而且更小。只要我们选到某个能覆盖 \(m/q\) 的素数，它同样会覆盖 \(m\)。所以带有 \(1 \pmod{10}\) 素因子的目标数并不会引入新的硬约束。
而 \(\mathcal{P}_3\) 中的每一个素数本身就是一个目标数，因为它自己就以 \(3\) 结尾并且不超过 \(n\)。因此这些素数全都必须被选中，它们带来的不可避免代价是
$$L_3=\sum_{p\in\mathcal{P}_3}\ln p.$$
去掉已经由 \(1 \pmod{10}\) 或 \(3 \pmod{10}\) 情况自动处理掉的目标之后，剩下的数只能由 \(\mathcal{P}_7\) 和 \(\mathcal{P}_9\) 里的素数组成。
现在看模 \(10\) 的乘法规律。只用 \(7\) 型和 \(9\) 型素数相乘，要得到末位 \(3\)，就必须至少出现一个 \(7 \pmod{10}\) 的素因子。更准确地说，按重数计算，\(7 \pmod{10}\) 这一类素因子的个数必须是奇数。因此每个还没有被自动覆盖的目标数，必然属于以下两种情况之一：
$$\text{它至少含有三个 } \mathcal{P}_7 \text{ 型素因子},$$
或者
$$\text{它含有一个 } \mathcal{P}_7 \text{ 型素因子和至少一个 } \mathcal{P}_9 \text{ 型素因子}.$$
如果某个 \(a\in\mathcal{P}_7\) 满足 \(a^3\le n\)，那么 \(a^3\) 本身就是一个合法目标数，而且它唯一的素因子就是 \(a\)。所以 \(a\) 一定得选，这是一类强制项。记
$$\mathcal{F}=\left\{a\in\mathcal{P}_7: a^3\le n\right\},\qquad L_F=\sum_{a\in\mathcal{F}}\ln a.$$
这一步还顺便解决了所有“至少有三个 \(7\) 型素因子”的情况。因为若 \(a\le b\le c\) 是其中三个这样的因子，那么 \(a^3\le abc\le m\le n\)，从而 \(a\in\mathcal{F}\)。也就是说，这类目标一定已经被最小的那个 \(7\) 型素因子覆盖了。
把强制集合 \(\mathcal{F}\) 全部加入之后，剩下还需要处理的目标数，只可能包含一个“非强制”的 \(7 \pmod{10}\) 素数以及至少一个 \(9 \pmod{10}\) 素数。令
$$\mathcal{A}=\mathcal{P}_7\setminus\mathcal{F},\qquad \mathcal{B}=\mathcal{P}_9.$$
若 \(a\in\mathcal{A}\)、\(b\in\mathcal{B}\)，并且 \(ab\le n\)，那么 \(ab\equiv 3 \pmod{10}\)，于是 \(ab\in\mathcal{S}_n\)。因此任何可行解都必须在 \(a\) 和 \(b\) 中至少选一个。
反过来，每一个剩余目标数 \(m\) 都至少包含这样一对 \(a\in\mathcal{A}\)、\(b\in\mathcal{B}\)，并满足 \(ab\mid m\)，从而 \(ab\le m\le n\)。所以“覆盖所有剩余目标数”和“覆盖所有满足 \(ab\le n\) 的这种素数对”是完全等价的。
于是剩下的问题变成
$$\min_{X\subseteq\mathcal{A},\,Y\subseteq\mathcal{B}} \left(\sum_{a\in X}\ln a+\sum_{b\in Y}\ln b\right),$$
其中每个满足 \(ab\le n\) 的素数对都要被至少一个端点命中。
构造二分图
$$G=(\mathcal{A},\mathcal{B},E),\qquad E=\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
从左侧选出 \(X\subseteq\mathcal{A}\)，从右侧选出 \(Y\subseteq\mathcal{B}\)，要求每条边至少被一个端点覆盖，这正是一个带权最小点覆盖问题；每个顶点的权值分别是 \(\ln a\) 或 \(\ln b\)。
接着使用标准的最小割建模：源点到左侧顶点的容量设为 \(\ln a\)，右侧顶点到汇点的容量设为 \(\ln b\)，原二分图中的每条边赋予一个足够大的容量。这样一来，最小 \(s\)-\(t\) 割的值就等于最小带权点覆盖的总代价。因此
$$L(n)=L_3+L_F+\operatorname{mincut}(G).$$
当 \(n=800\) 时，被立方强制选中的 \(7 \pmod{10}\) 素数只有 \(7\)，因为
$$7^3=343\le 800,\qquad 17^3=4913\gt 800.$$
在非强制的 \(7\) 型素数里，只有 \(17\) 和 \(37\) 还能和某个 \(9\) 型素数构成不超过 \(800\) 的合法乘积；右侧相关的 \(9\) 型素数只有 \(19\) 和 \(29\)。对应的合法乘积为
$$17\cdot 19=323,\qquad 17\cdot 29=493,\qquad 37\cdot 19=703,$$
所以图中的边就是
$$ (17,19),\qquad (17,29),\qquad (37,19). $$
最便宜的点覆盖是 \(\{17,19\}\)：顶点 \(17\) 覆盖了两条边，顶点 \(19\) 覆盖了剩下的一条，而任何包含 \(29\) 或 \(37\) 的方案总代价都更高。于是优化阶段最终额外选出 \(7\)、\(17\)、\(19\) 这三个素数，并得到
$$f(800)=\left(\prod_{\substack{p\le 800\\ p\equiv 3 \pmod{10}}} p\right)\cdot 7\cdot 17\cdot 19.$$
C++、Python 和 Java 实现都先用筛法生成不超过 \(n\) 的全部素数，然后按 \(3\)、\(7\)、\(9 \pmod{10}\) 分组。第一部分总代价直接加上所有必选的 \(3\) 型素数的对数；第二部分再加上所有满足 \(p^3\le n\) 的强制 \(7\) 型素数的对数。
接下来只构造真正有用的二分图。对每个非强制的 \(7\) 型素数 \(a\)，凡是满足 \(b\le n/a\) 的 \(9\) 型素数 \(b\) 都会生成一条边。没有任何关联边的顶点不会被放进流网络，因为它们不可能影响最优点覆盖。
最后，在源点-左部-右部-汇点组成的网络上运行标准的最大流/最小割算法。割值与前两部分的固定代价相加后，再保留 6 位小数输出。实现中还使用了两个校验点
$$L(40)=6.799056,\qquad L(2800)=715.019337$$
来确认图构造和求解流程是正确的。
筛素数需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。记
$$|E|=\#\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
构图时间是 \(O(|\mathcal{A}|\log|\mathcal{B}|+|E|)\)：每个左侧素数先在排好序的右侧素数表中找到截断位置，然后只生成自己真正相连的边。最大流阶段运行在一个拥有 \(O(|\mathcal{A}|+|\mathcal{B}|)\) 个顶点和 \(O(|E|)\) 条有限边的网络上，因此它主导了后续运行时间。去掉筛法本身之后，额外内存消耗为 \(O(|\mathcal{A}|+|\mathcal{B}|+|E|)\)。
Пусть \(f(n)\) обозначает наименьшее положительное целое число, для которого
$$\gcd(f(n),m)\gt 1$$
выполнено для каждого положительного целого \(m\le n\), оканчивающегося цифрой \(3\). Требуется вычислить
$$L(n)=\ln f(n)$$
при \(n=10^6\) и округлить результат до 6 знаков после запятой. Реализации на C++, Python и Java переходят к логарифмам, потому что минимизация произведения простых эквивалентна минимизации суммы их логарифмов.
Введем множество целей
$$\mathcal{S}_n=\left\{m\in\mathbb{Z}_{\ge 1}: m\le n,\ m\equiv 3 \pmod{10}\right\}.$$
Нужно найти самый дешевый набор простых чисел, который покрывает по делимости каждый элемент \(\mathcal{S}_n\).
Если простой множитель \(p\) уже входит в кандидат, то замена \(p^k\) на \(p\) при любом \(k\ge 2\) не меняет условие \(\gcd(f(n),m)\gt 1\): один общий простой множитель уже достаточен. При этом число становится только меньше. Значит, оптимальное \(f(n)\) всегда квадратно-свободно.
Поэтому мы выбираем лишь множество простых \(\mathcal{T}\) и минимизируем
$$L(n)=\min_{\mathcal{T}} \sum_{p\in\mathcal{T}} \ln p,$$
требуя, чтобы каждый \(m\in\mathcal{S}_n\) делился хотя бы на один простой из \(\mathcal{T}\).
Числа, оканчивающиеся на \(3\), не делятся на \(2\) и \(5\), так что эти простые сразу отпадают. Остальные простые разобьем по модулю \(10\):
$$\mathcal{P}_3=\left\{p\le n: p \text{ простое и } p\equiv 3 \pmod{10}\right\},$$
$$\mathcal{P}_7=\left\{p\le n: p \text{ простое и } p\equiv 7 \pmod{10}\right\},\qquad \mathcal{P}_9=\left\{p\le n: p \text{ простое и } p\equiv 9 \pmod{10}\right\}.$$
Простые \(q\equiv 1 \pmod{10}\) никогда не нужны в оптимальном ответе. Если такой \(q\) делит некоторое \(m\in\mathcal{S}_n\), то число \(m/q\) по-прежнему оканчивается на \(3\) и меньше самого \(m\). Любой выбранный простой, покрывающий \(m/q\), автоматически покрывает и \(m\). Значит, факторы вида \(1 \pmod{10}\) не добавляют новых обязательств.
Напротив, каждая простая из \(\mathcal{P}_3\) сама лежит в \(\mathcal{S}_n\). Поэтому все такие простые обязательны, и их неизбежный вклад равен
$$L_3=\sum_{p\in\mathcal{P}_3}\ln p.$$
После удаления чисел, уже обработанных за счет простых \(1 \pmod{10}\) или обязательных простых \(3 \pmod{10}\), остаются только произведения простых из \(\mathcal{P}_7\cup\mathcal{P}_9\).
Такое произведение может оканчиваться на \(3\) только если содержит хотя бы один простой множитель \(7 \pmod{10}\). Точнее, число простых множителей из \(\mathcal{P}_7\), с учетом кратностей, должно быть нечетным. Поэтому всякая еще не покрытая цель содержит либо
$$\text{не менее трех простых из }\mathcal{P}_7,$$
либо
$$\text{один простой из }\mathcal{P}_7 \text{ и хотя бы один из }\mathcal{P}_9.$$
Если \(a\in\mathcal{P}_7\) и \(a^3\le n\), то \(a^3\) само принадлежит \(\mathcal{S}_n\). Поскольку у \(a^3\) нет другого простого делителя, кроме \(a\), этот простой принудителен. Обозначим
$$\mathcal{F}=\left\{a\in\mathcal{P}_7: a^3\le n\right\},\qquad L_F=\sum_{a\in\mathcal{F}}\ln a.$$
Этим автоматически покрываются и все числа, содержащие не меньше трех простых факторов из \(\mathcal{P}_7\): если \(a\le b\le c\) являются тремя такими множителями числа \(m\), то \(a^3\le abc\le m\le n\), а значит \(a\in\mathcal{F}\).
После включения \(\mathcal{F}\) неразобранными остаются только числа, содержащие непринудительный простой \(7 \pmod{10}\) и хотя бы один простой \(9 \pmod{10}\). Положим
$$\mathcal{A}=\mathcal{P}_7\setminus\mathcal{F},\qquad \mathcal{B}=\mathcal{P}_9.$$
Если \(a\in\mathcal{A}\), \(b\in\mathcal{B}\) и \(ab\le n\), то \(ab\equiv 3 \pmod{10}\), следовательно \(ab\in\mathcal{S}_n\). Значит, любое допустимое решение должно выбрать хотя бы один из концов пары \(a\) или \(b\).
И наоборот, каждая оставшаяся цель \(m\) содержит пару \(a\in\mathcal{A}\), \(b\in\mathcal{B}\), для которой \(ab\mid m\), а потому \(ab\le m\le n\). Следовательно, покрыть все такие пары равносильно покрыть все оставшиеся целевые числа.
Остается задача
$$\min_{X\subseteq\mathcal{A},\,Y\subseteq\mathcal{B}} \left(\sum_{a\in X}\ln a+\sum_{b\in Y}\ln b\right),$$
где для каждой пары с \(ab\le n\) должен быть выбран хотя бы один конец.
Строим двудольный граф
$$G=(\mathcal{A},\mathcal{B},E),\qquad E=\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
Выбор множеств \(X\subseteq\mathcal{A}\) и \(Y\subseteq\mathcal{B}\), покрывающих все допустимые пары, в точности является задачей о минимальном взвешенном вершинном покрытии этого графа с весами \(\ln a\) и \(\ln b\).
Дальше используется стандартная редукция к минимальному разрезу: ребро из истока в вершину \(a\) получает пропускную способность \(\ln a\), ребро из вершины \(b\) в сток получает пропускную способность \(\ln b\), а каждое ребро двудольного графа снабжается очень большой емкостью. Тогда значение минимального \(s\)-\(t\)-разреза совпадает со стоимостью минимального взвешенного покрытия. Поэтому
$$L(n)=L_3+L_F+\operatorname{mincut}(G).$$
При \(n=800\) единственный принудительный простой вида \(7 \pmod{10}\) равен \(7\), поскольку
$$7^3=343\le 800,\qquad 17^3=4913\gt 800.$$
Среди непринудительных простых \(7 \pmod{10}\) допустимые произведения с простыми \(9 \pmod{10}\) образуют только вершины \(17\) и \(37\) слева, а также \(19\) и \(29\) справа. Имеем произведения
$$17\cdot 19=323,\qquad 17\cdot 29=493,\qquad 37\cdot 19=703,$$
то есть ребра
$$ (17,19),\qquad (17,29),\qquad (37,19). $$
Минимальное покрытие здесь равно \(\{17,19\}\): вершина \(17\) накрывает две дуги, вершина \(19\) накрывает третью, а любое решение с использованием \(29\) или \(37\) оказывается дороже. Значит, стадия оптимизации добавляет множители \(7\), \(17\) и \(19\), и получается
$$f(800)=\left(\prod_{\substack{p\le 800\\ p\equiv 3 \pmod{10}}} p\right)\cdot 7\cdot 17\cdot 19.$$
Реализации на C++, Python и Java сначала строят решето простых до \(n\). Затем простые разбиваются на классы \(3\), \(7\) и \(9 \pmod{10}\), сразу суммируются логарифмы обязательных простых \(3 \pmod{10}\), после чего добавляются логарифмы принудительных простых \(7 \pmod{10}\), удовлетворяющих \(p^3\le n\).
После этого строится только полезная часть двудольного графа. Для каждого непринудительного простого \(a\equiv 7 \pmod{10}\) каждая правая вершина \(b\equiv 9 \pmod{10}\) с условием \(b\le n/a\) создает одно ребро. Вершины, не входящие ни в одно ребро, просто отбрасываются, потому что они не могут повлиять на оптимальное покрытие.
Далее на сети исток-левая доля-правая доля-сток запускается стандартная процедура max-flow/min-cut. Значение разреза складывается с двумя обязательными логарифмическими вкладами, а итог округляется до шести знаков после запятой. В качестве проверок используются значения
$$L(40)=6.799056,\qquad L(2800)=715.019337.$$
Решето простых работает за \(O(n\log\log n)\) по времени и требует \(O(n)\) памяти. Пусть
$$|E|=\#\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
Построение графа занимает \(O(|\mathcal{A}|\log|\mathcal{B}|+|E|)\) времени: для каждой левой вершины сначала находится граница в отсортированном списке правых вершин, а затем добавляются ровно ее инцидентные ребра. Этап max-flow выполняется на сети с \(O(|\mathcal{A}|+|\mathcal{B}|)\) вершинами и \(O(|E|)\) конечными ребрами, поэтому именно он доминирует над остальной частью вычислений. После решета дополнительная память составляет \(O(|\mathcal{A}|+|\mathcal{B}|+|E|)\).
ليكن \(f(n)\) أصغر عدد صحيح موجب يحقق
$$\gcd(f(n),m)\gt 1$$
لكل عدد صحيح موجب \(m\le n\) ينتهي رقمه العشري الأخير بـ \(3\). المطلوب هو حساب
$$L(n)=\ln f(n)$$
عند \(n=10^6\)، مع التقريب إلى 6 منازل عشرية. تعتمد تطبيقات C++ وPython وJava على اللوغاريتمات لأن تصغير حاصل ضرب الأعداد الأولية يكافئ تصغير مجموع لوغاريتماتها.
لنعرّف مجموعة الأهداف
$$\mathcal{S}_n=\left\{m\in\mathbb{Z}_{\ge 1}: m\le n,\ m\equiv 3 \pmod{10}\right\}.$$
إذًا نحن نبحث عن أقل مجموعة من الأعداد الأولية كلفةً بحيث يقسم أحدها كل عنصر من عناصر \(\mathcal{S}_n\).
إذا كان العدد الأولي \(p\) موجودًا أصلًا في المرشح، فإن استبدال \(p^k\) بـ \(p\) لأي \(k\ge 2\) لا يغيّر شرط \(\gcd(f(n),m)\gt 1\)، لأن وجود عامل أولي مشترك واحد يكفي. لكنه يجعل العدد أصغر. لذلك يكون \(f(n)\) الأمثل خاليًا من المربعات.
وبالتالي لا نحتاج إلا إلى اختيار مجموعة أولية \(\mathcal{T}\) وتصغير
$$L(n)=\min_{\mathcal{T}} \sum_{p\in\mathcal{T}} \ln p,$$
مع اشتراط أن يكون كل \(m\in\mathcal{S}_n\) قابلًا للقسمة على عدد أولي واحد على الأقل من \(\mathcal{T}\).
الأعداد التي تنتهي بـ \(3\) لا تقبل القسمة على \(2\) ولا على \(5\)، لذلك لا دور لهذين العددين الأوليين. نقسم بقية الأعداد الأولية بحسب باقي القسمة على \(10\):
$$\mathcal{P}_3=\left\{p\le n: p \text{ أولي و } p\equiv 3 \pmod{10}\right\},$$
$$\mathcal{P}_7=\left\{p\le n: p \text{ أولي و } p\equiv 7 \pmod{10}\right\},\qquad \mathcal{P}_9=\left\{p\le n: p \text{ أولي و } p\equiv 9 \pmod{10}\right\}.$$
الأعداد الأولية الموافقة لـ \(1 \pmod{10}\) لا حاجة لها في الحل الأمثل. فإذا كان \(q\equiv 1 \pmod{10}\) يقسم عددًا ما \(m\in\mathcal{S}_n\)، فإن \(m/q\) يبقى منتهيًا بـ \(3\) ويكون أصغر من \(m\). وكل عدد أولي مختار يغطي \(m/q\) سيغطي \(m\) أيضًا. لذا فالعوامل من هذا النوع لا تضيف قيدًا جديدًا.
أما كل عدد أولي في \(\mathcal{P}_3\) فهو بحد ذاته عنصر من \(\mathcal{S}_n\)، ولذلك لا بد من اختياره. ومساهمته الإلزامية تساوي
$$L_3=\sum_{p\in\mathcal{P}_3}\ln p.$$
بعد حذف الأعداد التي تحتوي أصلًا على عامل أولي من النوع \(1 \pmod{10}\) أو على عامل أولي إلزامي من النوع \(3 \pmod{10}\)، لا يبقى إلا الأعداد المؤلفة من أوليات \(\mathcal{P}_7\cup\mathcal{P}_9\).
حتى ينتهي حاصل ضرب من هذا النوع بالرقم \(3\)، لا بد أن يحتوي على عدد أولي واحد على الأقل من \(\mathcal{P}_7\). وبتعبير أدق، يجب أن يكون عدد عوامل \(\mathcal{P}_7\) مع احتساب التكرار عددًا فرديًا. لذلك فإن كل هدف لم يُغطَّ بعد يحتوي إما على
$$\text{ثلاثة عوامل أولية على الأقل من }\mathcal{P}_7,$$
أو على
$$\text{عامل أولي واحد من }\mathcal{P}_7 \text{ ومعه عامل واحد على الأقل من }\mathcal{P}_9.$$
إذا كان \(a\in\mathcal{P}_7\) ويحقق \(a^3\le n\)، فإن \(a^3\) نفسه عنصر من \(\mathcal{S}_n\)، ولا يملك عاملًا أوليًا غير \(a\). لذا يصبح \(a\) عنصرًا مفروضًا. نعرّف
$$\mathcal{F}=\left\{a\in\mathcal{P}_7: a^3\le n\right\},\qquad L_F=\sum_{a\in\mathcal{F}}\ln a.$$
وهذا يغطي تلقائيًا أيضًا كل هدف يحتوي على ثلاثة عوامل من \(\mathcal{P}_7\) أو أكثر. فإذا كانت \(a\le b\le c\) ثلاثة من هذه العوامل في عدد \(m\)، فإن \(a^3\le abc\le m\le n\)، ومن ثم \(a\in\mathcal{F}\).
بعد إدخال المجموعة المفروضة \(\mathcal{F}\)، لا تبقى إلا الحالات التي تحتوي على عدد أولي غير مفروض من النوع \(7 \pmod{10}\) وعلى عدد أولي واحد على الأقل من النوع \(9 \pmod{10}\). لنضع
$$\mathcal{A}=\mathcal{P}_7\setminus\mathcal{F},\qquad \mathcal{B}=\mathcal{P}_9.$$
إذا كان \(a\in\mathcal{A}\) و\(b\in\mathcal{B}\) ويحققان \(ab\le n\)، فإن \(ab\equiv 3 \pmod{10}\)، وبالتالي \(ab\in\mathcal{S}_n\). إذًا يجب على أي حل صالح أن يختار \(a\) أو \(b\) على الأقل.
وبالعكس، كل عدد باقٍ غير مغطى يحتوي على زوج من هذا النوع يحقق \(ab\mid m\)، ومن ثم \(ab\le m\le n\). لذلك فإن تغطية كل الأزواج الممكنة تكافئ تمامًا تغطية كل الأهداف المتبقية.
وعليه تصبح المسألة
$$\min_{X\subseteq\mathcal{A},\,Y\subseteq\mathcal{B}} \left(\sum_{a\in X}\ln a+\sum_{b\in Y}\ln b\right),$$
مع الشرط أن كل زوج يحقق \(ab\le n\) يجب أن يغطيه أحد طرفيه على الأقل.
نبني الرسم الثنائي
$$G=(\mathcal{A},\mathcal{B},E),\qquad E=\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
واختيار \(X\subseteq\mathcal{A}\) و\(Y\subseteq\mathcal{B}\) بحيث تُغطى كل الحواف هو بالضبط مسألة غطاء رؤوس موزون، حيث وزن الرأس \(a\) هو \(\ln a\) ووزن الرأس \(b\) هو \(\ln b\).
ثم نستخدم التحويل القياسي إلى أقل قطع: نعطي الحافة من المصدر إلى كل رأس أيسر سعة \(\ln a\)، والحافة من كل رأس أيمن إلى المصب سعة \(\ln b\)، وكل حافة من الرسم الثنائي سعة كبيرة جدًا. عندئذٍ تصبح قيمة أقل قطع \(s\)-\(t\) مساوية لقيمة أقل غطاء رؤوس موزون. ومن هنا نحصل على
$$L(n)=L_3+L_F+\operatorname{mincut}(G).$$
عندما \(n=800\)، يكون العدد الأولي المفروض الوحيد من النوع \(7 \pmod{10}\) هو \(7\)، لأن
$$7^3=343\le 800,\qquad 17^3=4913\gt 800.$$
ومن بين أوليات \(7 \pmod{10}\) غير المفروضة، لا يبقى في الرسم إلا \(17\) و\(37\). وعلى الجهة الأخرى لا تظهر إلا \(19\) و\(29\). أما الأزواج الصالحة فهي
$$17\cdot 19=323,\qquad 17\cdot 29=493,\qquad 37\cdot 19=703,$$
أي إن الحواف هي
$$ (17,19),\qquad (17,29),\qquad (37,19). $$
أرخص غطاء هو \(\{17,19\}\): فالعدد \(17\) يغطي حافتين، و\(19\) يغطي الحافة الثالثة، وأي غطاء يستخدم \(29\) أو \(37\) سيكون أعلى كلفة. لذلك تضيف مرحلة التحسين العوامل \(7\) و\(17\) و\(19\)، ويصبح
$$f(800)=\left(\prod_{\substack{p\le 800\\ p\equiv 3 \pmod{10}}} p\right)\cdot 7\cdot 17\cdot 19.$$
تبدأ تطبيقات C++ وPython وJava ببناء غربال للأعداد الأولية حتى \(n\). بعد ذلك تُقسم الأعداد الأولية إلى الفئات \(3\)، \(7\)، و\(9 \pmod{10}\)، ثم تُجمع مباشرة لوغاريتمات كل أولي إلزامي من النوع \(3 \pmod{10}\)، وبعدها لوغاريتمات كل أولي مفروض من النوع \(7 \pmod{10}\) يحقق \(p^3\le n\).
في المرحلة التالية لا يُبنى إلا الجزء المفيد من الرسم الثنائي. فلكل أولي غير مفروض \(a\equiv 7 \pmod{10}\)، يولِّد كل أولي \(b\equiv 9 \pmod{10}\) يحقق \(b\le n/a\) حافة واحدة. أما الرؤوس التي لا تشارك في أي حافة فتُهمل، لأنها لا تؤثر في الغطاء الأمثل.
ثم تُشغَّل خوارزمية قياسية للتدفق الأعظمي/القطع الأدنى على شبكة المصدر-اليسار-اليمين-المصب. وتُضاف قيمة القطع إلى المساهمتين الإلزاميتين السابقتين، ثم تُقرَّب النتيجة النهائية إلى ست منازل عشرية. كما تستعمل التطبيقات نقطتي فحص هما
$$L(40)=6.799056,\qquad L(2800)=715.019337$$
للتأكد من صحة بناء الرسم والحساب.
بناء غربال الأعداد الأولية يحتاج إلى \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. ولتكن
$$|E|=\#\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$$
بناء الرسم يكلف \(O(|\mathcal{A}|\log|\mathcal{B}|+|E|)\) من الزمن: إذ يجد كل رأس في الجهة اليسرى أولًا موضع الحد في القائمة المرتبة للجهة اليمنى، ثم ينشئ بالضبط الحواف المتصلة به. وبعد ذلك تعمل خوارزمية التدفق الأعظمي على شبكة فيها \(O(|\mathcal{A}|+|\mathcal{B}|)\) رأسًا و\(O(|E|)\) حوافًا منتهية السعة، ولذلك تكون هذه المرحلة هي الغالبة على بقية الزمن. أما الذاكرة الإضافية بعد الغربال فهي \(O(|\mathcal{A}|+|\mathcal{B}|+|E|)\).