For an odd prime \(p\), pair the numbers \(1,2,\dots,p-1\) into \(\frac{p-1}{2}\) disjoint pairs. Each pair \(\{a,b\}\) contributes the least positive residue of \(ab \bmod p\), and the goal is to minimize the total sum over all pairs. The implementations solve the large target prime by converting this pairing problem into a modular optimization problem inside \((\mathbb{Z}/p\mathbb{Z})^\times\), then reconstructing the corresponding witness integer.
Let \(n=\frac{p-1}{2}\). If a pairing produces pair residues \(r_1,\dots,r_n\in\{1,\dots,p-1\}\), then the total pairing cost is
$$S(p)=\min \sum_{i=1}^{n} r_i.$$
If the pairs are \(\{a_i,b_i\}\), then \(r_i\equiv a_i b_i \pmod p\). Because the pairing uses each nonzero residue exactly once, we get
$$\prod_{i=1}^{n} r_i \equiv \prod_{k=1}^{p-1} k \equiv -1 \pmod p,$$
where the last congruence is Wilson's theorem. So every admissible pairing yields a multiset of positive residues whose product is \(-1\) modulo \(p\).
Every pair contributes at least \(1\), so
$$\sum_{i=1}^{n} r_i = n + \sum_{i=1}^{n}(r_i-1).$$
The constant term \(n\) is unavoidable. The real optimization is the excess \(\sum (r_i-1)\).
If a residue \(c>1\) is composite, say \(c=uv\), then
$$c-1=(u-1)+(v-1)+(u-1)(v-1)\ge (u-1)+(v-1).$$
This is why prime factors are the natural atomic pieces: splitting a composite residue into smaller factors never increases the excess. The implementations therefore search for a witness of the form
$$W=\prod_q q^{e_q}\equiv -1 \pmod p,$$
with \(q\) prime and \(e_q\ge 0\), minimizing
$$E(p)=\sum_q e_q(q-1).$$
For the large target prime, this excess is tiny compared with \(n\), so the factorized search matches the pairing objective cleanly. The small-prime checks in the C++ implementation confirm the relation
$$S(p)=\frac{p-1}{2}+E(p).$$
Fix a current excess budget \(B\). Any prime with \(q-1>B\) cannot appear, so only primes \(q\le B+1\) matter. An exponent vector determines two values:
$$r=\prod_q q^{e_q}\bmod p,\qquad c=\sum_q e_q(q-1).$$
For each reachable residue \(r\), only the smallest cost \(c\) matters. Many exponent vectors can therefore be compressed into one best state per residue class.
Split the allowed primes into two groups. Enumerate all reachable residue-cost states on the left and on the right, always staying within the same budget \(B\). If the left side produces \(r_A\), then the right side must produce
$$r_B\equiv -r_A^{-1}\pmod p$$
so that \(r_A r_B\equiv -1\pmod p\). Because \(p\) is prime, every nonzero residue has an inverse. The cheapest compatible left-right combination gives the best excess under budget \(B\).
The implementations further speed up the merge step by computing many inverses in one batch, using prefix products and one Fermat-style inverse instead of inverting every left residue separately.
After the smallest feasible excess has been found, a second exact search recovers the exponents \(e_q\) that attain it. Their product
$$W=\prod_q q^{e_q}$$
is then built as an arbitrary-precision integer. This witness is what the implementations finally print for the large prime from the problem.
Here \(n=\frac{7-1}{2}=3\), and the target congruence is \(W\equiv -1\equiv 6 \pmod 7\).
The cheapest prime-factor witness is
$$W=2\cdot 3=6,$$
with excess
$$E(7)=(2-1)+(3-1)=3.$$
So the predicted minimum pairing cost is
$$S(7)=3+3=6.$$
An explicit pairing is
$$\{1,3\},\qquad \{2,4\},\qquad \{5,6\},$$
whose pair residues are \(3\), \(1\), and \(2\). Their sum is \(3+1+2=6\), and their product is \(3\cdot 1\cdot 2=6\equiv -1\pmod 7\), exactly as the theory predicts. The \(p=5\) checkpoint works the same way: \(W=4=2^2\), the excess is \(2\), and the optimal pairing sum is \(4\).
The C++, Python, and Java implementations start with a small excess budget and enlarge it gradually until a feasible witness appears. For each budget they generate all primes up to \(B+1\), split them into two groups, and recursively enumerate every exponent pattern whose weighted cost stays within the budget. Each side stores only the cheapest cost for each residue modulo \(p\).
After the two maps are built, the implementation searches for matching residues whose product is \(-1\) modulo \(p\). When the first successful budget is found, a second recursive pass reconstructs the exact exponents and multiplies the corresponding primes to obtain the final big-integer witness \(W\). The C++ implementation also checks small primes by exhaustive pairing search, confirming that the computed excess matches the true minimum pairing total after adding the baseline \(\frac{p-1}{2}\).
Let \(B^*\) be the minimal excess cost. For a given budget \(B\), sieving primes up to \(B+1\) costs \(O(B\log\log B)\). The dominant work is enumerating exponent vectors satisfying
$$\sum_q e_q(q-1)\le B.$$
If \(N_A(B)\) and \(N_B(B)\) are the numbers of states explored on the two sides, then one round costs
$$O\bigl(B\log\log B + N_A(B) + N_B(B)\bigr)$$
time. Memory usage is
$$O\bigl(M_A(B)+M_B(B)\bigr),$$
where \(M_A(B)\) and \(M_B(B)\) are the numbers of stored residues in the two hash maps. In practice the budget stays small, so the running time depends much more on the optimal excess than on the huge size of \(p\).
Für eine ungerade Primzahl \(p\) sollen die Zahlen \(1,2,\dots,p-1\) zu \(\frac{p-1}{2}\) disjunkten Paaren zusammengefasst werden. Jedes Paar \(\{a,b\}\) trägt den kleinsten positiven Rest von \(ab \bmod p\) bei, und die Gesamtsumme soll minimal werden. Die Implementierungen lösen die große Zielprimzahl, indem sie dieses Paarungsproblem in ein modulares Optimierungsproblem in \((\mathbb{Z}/p\mathbb{Z})^\times\) übersetzen und danach die zugehörige Zeugenzahl rekonstruieren.
Sei \(n=\frac{p-1}{2}\). Wenn eine Paarung die Paarreste \(r_1,\dots,r_n\in\{1,\dots,p-1\}\) erzeugt, dann ist die Zielfunktion
$$S(p)=\min \sum_{i=1}^{n} r_i.$$
Sind die Paare \(\{a_i,b_i\}\), so gilt \(r_i\equiv a_i b_i \pmod p\). Weil in der Paarung jeder von \(1\) bis \(p-1\) genau einmal vorkommt, folgt
$$\prod_{i=1}^{n} r_i \equiv \prod_{k=1}^{p-1} k \equiv -1 \pmod p,$$
wobei die letzte Kongruenz der Satz von Wilson ist. Jede zulässige Paarung erzeugt also eine Menge positiver Reste, deren Produkt modulo \(p\) gleich \(-1\) ist.
Jedes Paar trägt mindestens \(1\) bei, also
$$\sum_{i=1}^{n} r_i = n + \sum_{i=1}^{n}(r_i-1).$$
Der konstante Anteil \(n\) ist unvermeidbar. Optimiert werden muss nur der Überschuss \(\sum (r_i-1)\).
Ist ein Rest \(c>1\) zusammengesetzt, also \(c=uv\), dann gilt
$$c-1=(u-1)+(v-1)+(u-1)(v-1)\ge (u-1)+(v-1).$$
Darum sind Primfaktoren die natürlichen atomaren Bausteine: Das Aufspalten eines zusammengesetzten Restes in kleinere Faktoren vergrößert den Überschuss nie. Die Implementierungen suchen deshalb nach einer Zahl
$$W=\prod_q q^{e_q}\equiv -1 \pmod p,$$
wobei \(q\) prim und \(e_q\ge 0\) ist, und minimieren
$$E(p)=\sum_q e_q(q-1).$$
Für die große Zielprimzahl ist dieser Überschuss winzig im Vergleich zu \(n\), sodass die faktorisierte Suche sauber mit dem Paarungsziel übereinstimmt. Die Kleinprimzahl-Tests der C++-Implementierung bestätigen
$$S(p)=\frac{p-1}{2}+E(p).$$
Fixiere ein aktuelles Überschussbudget \(B\). Jede Primzahl mit \(q-1>B\) scheidet aus, also kommen nur Primzahlen \(q\le B+1\) in Frage. Ein Exponentenvektor bestimmt
$$r=\prod_q q^{e_q}\bmod p,\qquad c=\sum_q e_q(q-1).$$
Für jeden erreichbaren Rest \(r\) ist nur die kleinste Kostenhöhe \(c\) relevant. Viele Exponentenvektoren lassen sich dadurch zu genau einem besten Zustand pro Restklasse verdichten.
Die zulässigen Primzahlen werden in zwei Gruppen aufgeteilt. Auf beiden Seiten werden alle erreichbaren Zustände aus Rest und Kosten bis zum selben Budget \(B\) rekursiv aufgelistet. Erzeugt die linke Seite den Rest \(r_A\), dann muss die rechte Seite
$$r_B\equiv -r_A^{-1}\pmod p$$
liefern, damit \(r_A r_B\equiv -1\pmod p\) gilt. Da \(p\) prim ist, besitzt jeder von \(0\) verschiedene Rest ein Inverses. Die billigste kompatible Links-Rechts-Kombination liefert den besten Überschuss unter Budget \(B\).
Zusätzlich beschleunigen die Implementierungen das Zusammenführen, indem sie viele Inverse in einem Schwung berechnen: mit Präfixprodukten und genau einem Fermat-Inversen statt einer separaten Inversion für jeden linken Rest.
Sobald der kleinste zulässige Überschuss gefunden ist, rekonstruiert eine zweite exakte Suche die zugehörigen Exponenten \(e_q\). Deren Produkt
$$W=\prod_q q^{e_q}$$
wird dann als Ganzzahl beliebiger Größe aufgebaut. Genau diese Zeugenzahl geben die Implementierungen für die große Primzahl der Aufgabe aus.
Hier ist \(n=\frac{7-1}{2}=3\), und die Zielkongruenz lautet \(W\equiv -1\equiv 6 \pmod 7\).
Die billigste Primfaktor-Zeugenzahl ist
$$W=2\cdot 3=6,$$
mit dem Überschuss
$$E(7)=(2-1)+(3-1)=3.$$
Damit ergibt sich als vorhergesagte Minimalpaarungssumme
$$S(7)=3+3=6.$$
Eine explizite Paarung ist
$$\{1,3\},\qquad \{2,4\},\qquad \{5,6\},$$
deren Paarreste \(3\), \(1\) und \(2\) sind. Ihre Summe ist \(3+1+2=6\), und ihr Produkt ist \(3\cdot 1\cdot 2=6\equiv -1\pmod 7\), also genau wie von der Theorie vorhergesagt. Der Kontrollfall \(p=5\) funktioniert analog: \(W=4=2^2\), der Überschuss ist \(2\), und die optimale Paarungssumme ist \(4\).
Die C++-, Python- und Java-Implementierungen starten mit einem kleinen Überschussbudget und vergrößern es schrittweise, bis eine zulässige Zeugenzahl erscheint. Für jedes Budget erzeugen sie alle Primzahlen bis \(B+1\), teilen sie in zwei Gruppen und enumerieren rekursiv jedes Exponentenmuster, dessen gewichtete Kosten innerhalb des Budgets bleiben. Pro Seite wird für jeden Rest modulo \(p\) nur die billigste bekannte Kostenhöhe gespeichert.
Nachdem beide Tabellen aufgebaut sind, sucht die Implementierung nach passenden Resten, deren Produkt modulo \(p\) gleich \(-1\) ist. Beim ersten erfolgreichen Budget rekonstruiert ein zweiter rekursiver Durchlauf die exakten Exponenten und multipliziert die entsprechenden Primzahlen zur endgültigen Big-Integer-Zeugenzahl \(W\). Die C++-Implementierung prüft zusätzlich kleine Primzahlen per vollständiger Paarungssuche und bestätigt so, dass der berechnete Überschuss nach Addition des Basisanteils \(\frac{p-1}{2}\) genau die wahre Minimalpaarungssumme ergibt.
Sei \(B^*\) der minimale Überschuss. Für ein gegebenes Budget \(B\) kostet das Sieben der Primzahlen bis \(B+1\) \(O(B\log\log B)\). Der dominante Aufwand ist die Enumeration aller Exponentenvektoren mit
$$\sum_q e_q(q-1)\le B.$$
Wenn \(N_A(B)\) und \(N_B(B)\) die auf beiden Seiten erkundeten Zustände bezeichnen, kostet eine Runde
$$O\bigl(B\log\log B + N_A(B) + N_B(B)\bigr)$$
Zeit. Der Speicherverbrauch ist
$$O\bigl(M_A(B)+M_B(B)\bigr),$$
wobei \(M_A(B)\) und \(M_B(B)\) die Anzahl gespeicherter Reste in den beiden Hashtabellen sind. In der Praxis bleibt das Budget klein, daher hängt die Laufzeit viel stärker vom optimalen Überschuss als von der enormen Größe von \(p\) ab.
Tek bir tek asal sayı \(p\) için \(1,2,\dots,p-1\) sayıları \(\frac{p-1}{2}\) ayrık çifte bölünür. Her \(\{a,b\}\) çifti, \(ab \bmod p\) ifadesinin en küçük pozitif kalıntısını maliyet olarak üretir ve amaç toplam maliyeti en aza indirmektir. Uygulamalar, büyük hedef asal için bu eşleştirme problemini \((\mathbb{Z}/p\mathbb{Z})^\times\) içinde bir modüler optimizasyona dönüştürür ve sonra buna karşılık gelen tanık tamsayıyı yeniden kurar.
\(n=\frac{p-1}{2}\) olsun. Bir eşleştirme \(r_1,\dots,r_n\in\{1,\dots,p-1\}\) kalıntılarını üretiyorsa amaç fonksiyonu
$$S(p)=\min \sum_{i=1}^{n} r_i$$
şeklindedir.
Çiftler \(\{a_i,b_i\}\) ise \(r_i\equiv a_i b_i \pmod p\) olur. Eşleştirme \(1\) ile \(p-1\) arasındaki her sayıyı tam bir kez kullandığı için
$$\prod_{i=1}^{n} r_i \equiv \prod_{k=1}^{p-1} k \equiv -1 \pmod p$$
elde edilir; son eşitlik Wilson teoremidir. Yani her uygun eşleştirme, çarpımı mod \(p\) altında \(-1\) olan pozitif kalıntılardan oluşan bir çokluk verir.
Her çift en az \(1\) katkı yaptığı için
$$\sum_{i=1}^{n} r_i = n + \sum_{i=1}^{n}(r_i-1).$$
Sabit \(n\) terimi kaçınılmazdır. Gerçek optimizasyon \(\sum (r_i-1)\) fazlalığı üzerindedir.
Eğer \(c>1\) bileşikse ve \(c=uv\) yazılabiliyorsa,
$$c-1=(u-1)+(v-1)+(u-1)(v-1)\ge (u-1)+(v-1)$$
olur. Bu yüzden asal çarpanlar doğal atomik parçalar haline gelir: bileşik bir kalıntıyı daha küçük çarpanlara ayırmak fazlalığı artırmaz. Uygulamalar bu nedenle
$$W=\prod_q q^{e_q}\equiv -1 \pmod p$$
şeklinde, \(q\) asal ve \(e_q\ge 0\) olacak bir tanık arar ve
$$E(p)=\sum_q e_q(q-1)$$
değerini minimize eder. Büyük hedef asal için bu fazlalık \(n\)'e göre çok küçüktür; dolayısıyla çarpanlara ayrılmış arama ile eşleştirme amacı düzgün biçimde örtüşür. C++ uygulamasındaki küçük asal kontrolleri de
$$S(p)=\frac{p-1}{2}+E(p)$$
ilişkisini doğrular.
Geçerli bir fazlalık bütçesi \(B\) sabitlenirse \(q-1>B\) olan hiçbir asal kullanılamaz; dolayısıyla sadece \(q\le B+1\) asalları önemlidir. Bir üs vektörü iki bilgi üretir:
$$r=\prod_q q^{e_q}\bmod p,\qquad c=\sum_q e_q(q-1).$$
Her ulaşılabilir \(r\) için sadece en küçük maliyet \(c\) önem taşır. Böylece çok sayıda üs kombinasyonu, her kalıntı sınıfı için tek bir en iyi duruma sıkıştırılır.
İzin verilen asallar iki gruba ayrılır. Her iki tarafta da aynı bütçe \(B\) altında ulaşılabilen tüm kalıntı-maliyet durumları üretilir. Sol taraf \(r_A\) kalıntısını veriyorsa sağ tarafın
$$r_B\equiv -r_A^{-1}\pmod p$$
üretmesi gerekir; böylece \(r_A r_B\equiv -1\pmod p\) olur. \(p\) asal olduğu için sıfır olmayan her kalıntının tersi vardır. Uyumlu en ucuz sol-sağ birleşimi, bu bütçe altındaki en iyi fazlalığı verir.
Uygulamalar birleştirme aşamasını ayrıca hızlandırır: her sol kalıntı için ayrı ters almak yerine, önek çarpımları ve Fermat tabanlı tek bir ters alma işlemiyle çok sayıda tersi toplu hesaplar.
En küçük uygun fazlalık bulunduktan sonra ikinci bir tam arama, bu değeri veren üsleri \(e_q\) olarak geri çıkarır. Sonra
$$W=\prod_q q^{e_q}$$
çarpımı keyfi büyüklükte bir tamsayı olarak oluşturulur. Uygulamaların büyük asal için yazdırdığı sonuç tam olarak bu tanıktır.
Burada \(n=\frac{7-1}{2}=3\) ve hedef kongruens
$$W\equiv -1\equiv 6\pmod 7$$
şeklindedir. En ucuz asal-çarpan tanığı
$$W=2\cdot 3=6$$
olur ve fazlalık
$$E(7)=(2-1)+(3-1)=3$$
çıkar. Dolayısıyla beklenen en küçük eşleştirme toplamı
$$S(7)=3+3=6$$
olmalıdır. Bunu veren açık bir eşleştirme
$$\{1,3\},\qquad \{2,4\},\qquad \{5,6\}$$
şeklindedir. Bu çiftlerin kalıntıları sırasıyla \(3\), \(1\) ve \(2\) olur. Toplam \(3+1+2=6\) ve çarpım \(3\cdot 1\cdot 2=6\equiv -1\pmod 7\) olduğu için teori birebir doğrulanır. \(p=5\) kontrolü de benzerdir: \(W=4=2^2\), fazlalık \(2\), en iyi toplam ise \(4\) olur.
C++, Python ve Java uygulamaları küçük bir fazlalık bütçesiyle başlar ve uygun bir tanık bulana kadar bu bütçeyi adım adım artırır. Her bütçe için \(B+1\)'e kadar olan tüm asalları üretir, bunları iki gruba ayırır ve ağırlıklı maliyeti bütçeyi aşmayan tüm üs desenlerini özyineli olarak listeler. Her tarafta mod \(p\) altında aynı kalıntıya ulaşan seçeneklerden sadece en ucuzu tutulur.
İki tablo hazır olduğunda uygulama, çarpımları mod \(p\) altında \(-1\) veren eşleşen kalıntıları arar. İlk başarılı bütçede ikinci bir özyineli geçiş tam üsleri geri kurar ve ilgili asalları çarparak son büyük tamsayı tanık \(W\)'yi elde eder. C++ uygulaması ayrıca küçük asallarda tam eşleştirme araması yapar ve bulunan fazlalığın, \(\frac{p-1}{2}\) taban terimi eklendiğinde gerçek minimum eşleştirme toplamına eşit olduğunu doğrular.
\(B^*\) minimal fazlalık olsun. Verilen bir \(B\) bütçesi için \(B+1\)'e kadar asal elemek \(O(B\log\log B)\) zaman alır. Baskın maliyet,
$$\sum_q e_q(q-1)\le B$$
koşulunu sağlayan üs vektörlerini üretmektir. İki tarafta keşfedilen durum sayıları \(N_A(B)\) ve \(N_B(B)\) ise bir tur
$$O\bigl(B\log\log B + N_A(B) + N_B(B)\bigr)$$
zamanda çalışır. Bellek kullanımı ise
$$O\bigl(M_A(B)+M_B(B)\bigr)$$
şeklindedir; burada \(M_A(B)\) ve \(M_B(B)\), iki hash tablosunda saklanan kalıntı sayılarıdır. Pratikte bütçe küçük kaldığı için çalışma süresi devasa \(p\) boyutundan çok optimal fazlalığa bağlıdır.
Para un primo impar \(p\), hay que emparejar los números \(1,2,\dots,p-1\) en \(\frac{p-1}{2}\) pares disjuntos. Cada par \(\{a,b\}\) aporta el menor residuo positivo de \(ab \bmod p\), y el objetivo es minimizar la suma total. Las implementaciones resuelven el primo objetivo grande transformando este problema de emparejamiento en una optimización modular dentro de \((\mathbb{Z}/p\mathbb{Z})^\times\) y luego reconstruyen el entero testigo correspondiente.
Sea \(n=\frac{p-1}{2}\). Si un emparejamiento produce residuos \(r_1,\dots,r_n\in\{1,\dots,p-1\}\), la cantidad a minimizar es
$$S(p)=\min \sum_{i=1}^{n} r_i.$$
Si los pares son \(\{a_i,b_i\}\), entonces \(r_i\equiv a_i b_i \pmod p\). Como el emparejamiento usa cada residuo no nulo exactamente una vez, se obtiene
$$\prod_{i=1}^{n} r_i \equiv \prod_{k=1}^{p-1} k \equiv -1 \pmod p,$$
y la última congruencia es el teorema de Wilson. Así, todo emparejamiento admisible produce un multiconjunto de residuos positivos cuyo producto es \(-1\) módulo \(p\).
Cada par aporta al menos \(1\), por lo que
$$\sum_{i=1}^{n} r_i = n + \sum_{i=1}^{n}(r_i-1).$$
El término constante \(n\) es inevitable. La optimización real está en el exceso \(\sum (r_i-1)\).
Si un residuo \(c>1\) es compuesto, digamos \(c=uv\), entonces
$$c-1=(u-1)+(v-1)+(u-1)(v-1)\ge (u-1)+(v-1).$$
Por eso los factores primos son las piezas atómicas correctas: descomponer un residuo compuesto nunca aumenta el exceso. Las implementaciones buscan entonces un testigo de la forma
$$W=\prod_q q^{e_q}\equiv -1 \pmod p,$$
con \(q\) primo y \(e_q\ge 0\), minimizando
$$E(p)=\sum_q e_q(q-1).$$
Para el primo objetivo grande, este exceso es minúsculo frente a \(n\), de modo que la búsqueda factorizada coincide limpiamente con el objetivo del emparejamiento. Las comprobaciones con primos pequeños en la implementación en C++ confirman
$$S(p)=\frac{p-1}{2}+E(p).$$
Fijemos un presupuesto de exceso \(B\). Cualquier primo con \(q-1>B\) queda descartado, así que solo importan los primos \(q\le B+1\). Un vector de exponentes determina
$$r=\prod_q q^{e_q}\bmod p,\qquad c=\sum_q e_q(q-1).$$
Para cada residuo alcanzable \(r\), solo interesa el costo mínimo \(c\). Muchas elecciones de exponentes quedan así comprimidas en un único mejor estado por clase residual.
Los primos permitidos se dividen en dos grupos. A izquierda y derecha se enumeran todos los estados residuo-costo alcanzables bajo el mismo presupuesto \(B\). Si el lado izquierdo produce \(r_A\), el lado derecho debe producir
$$r_B\equiv -r_A^{-1}\pmod p$$
para que \(r_A r_B\equiv -1\pmod p\). Como \(p\) es primo, todo residuo no nulo tiene inverso. La combinación compatible más barata da el mejor exceso bajo el presupuesto \(B\).
Las implementaciones aceleran además la unión de ambos lados calculando muchos inversos en lote, con productos prefijo y una sola inversión basada en Fermat en vez de invertir cada residuo izquierdo por separado.
Una vez hallado el exceso factible mínimo, una segunda búsqueda exacta recupera los exponentes \(e_q\) que lo alcanzan. Su producto
$$W=\prod_q q^{e_q}$$
se construye después como entero de precisión arbitraria. Ese es el testigo que las implementaciones imprimen para el primo grande del problema.
Aquí \(n=\frac{7-1}{2}=3\), y la congruencia objetivo es \(W\equiv -1\equiv 6 \pmod 7\).
El testigo más barato por factores primos es
$$W=2\cdot 3=6,$$
con exceso
$$E(7)=(2-1)+(3-1)=3.$$
Por tanto, el costo mínimo predicho del emparejamiento es
$$S(7)=3+3=6.$$
Un emparejamiento explícito es
$$\{1,3\},\qquad \{2,4\},\qquad \{5,6\},$$
cuyos residuos de par son \(3\), \(1\) y \(2\). Su suma es \(3+1+2=6\), y su producto es \(3\cdot 1\cdot 2=6\equiv -1\pmod 7\), exactamente como predice la teoría. El caso \(p=5\) es análogo: \(W=4=2^2\), el exceso es \(2\) y la suma óptima vale \(4\).
Las implementaciones en C++, Python y Java empiezan con un presupuesto de exceso pequeño y lo aumentan gradualmente hasta que aparece un testigo factible. Para cada presupuesto generan todos los primos hasta \(B+1\), los dividen en dos grupos y enumeran recursivamente cada patrón de exponentes cuyo costo ponderado no supera el presupuesto. Cada lado guarda solo el costo más bajo para cada residuo módulo \(p\).
Después de construir ambos mapas, la implementación busca residuos compatibles cuyo producto sea \(-1\) módulo \(p\). Cuando encuentra el primer presupuesto exitoso, una segunda pasada recursiva reconstruye los exponentes exactos y multiplica los primos correspondientes para obtener el testigo final \(W\) como entero grande. La implementación en C++ también verifica primos pequeños mediante búsqueda exhaustiva de emparejamientos y confirma que el exceso calculado coincide con el verdadero mínimo después de sumar la base \(\frac{p-1}{2}\).
Sea \(B^*\) el exceso mínimo. Para un presupuesto \(B\), cribar los primos hasta \(B+1\) cuesta \(O(B\log\log B)\). El trabajo dominante es enumerar los vectores de exponentes que satisfacen
$$\sum_q e_q(q-1)\le B.$$
Si \(N_A(B)\) y \(N_B(B)\) son los números de estados explorados en ambos lados, una ronda cuesta
$$O\bigl(B\log\log B + N_A(B) + N_B(B)\bigr)$$
tiempo. El uso de memoria es
$$O\bigl(M_A(B)+M_B(B)\bigr),$$
donde \(M_A(B)\) y \(M_B(B)\) son los números de residuos almacenados en los dos mapas hash. En la práctica el presupuesto es pequeño, así que el tiempo de ejecución depende mucho más del exceso óptimo que del enorme tamaño de \(p\).
对一个奇素数 \(p\)，要把 \(1,2,\dots,p-1\) 划分成 \(\frac{p-1}{2}\) 个互不相交的配对。每个配对 \(\{a,b\}\) 的代价定义为 \(ab \bmod p\) 的最小正剩余，目标是让所有配对代价之和最小。实现并不是直接在所有配对上暴力搜索，而是把问题改写成 \((\mathbb{Z}/p\mathbb{Z})^\times\) 中的一个模约束优化问题，然后再恢复出对应的见证整数。
记 \(n=\frac{p-1}{2}\)。如果某个配对方案产生的配对剩余为 \(r_1,\dots,r_n\in\{1,\dots,p-1\}\)，那么目标值就是
$$S(p)=\min \sum_{i=1}^{n} r_i.$$
若配对为 \(\{a_i,b_i\}\)，则有 \(r_i\equiv a_i b_i \pmod p\)。因为 \(1\) 到 \(p-1\) 的每个非零剩余都恰好出现一次，所以
$$\prod_{i=1}^{n} r_i \equiv \prod_{k=1}^{p-1} k \equiv -1 \pmod p,$$
最后一步就是威尔逊定理。因此，每个可行配对都对应着一组正剩余，它们在模 \(p\) 下的乘积一定是 \(-1\)。
每个配对的代价至少是 \(1\)，因此
$$\sum_{i=1}^{n} r_i = n + \sum_{i=1}^{n}(r_i-1).$$
其中常数项 \(n\) 无法避免，真正需要优化的是超额部分 \(\sum (r_i-1)\)。
如果某个剩余 \(c>1\) 是合数，设 \(c=uv\)，则
$$c-1=(u-1)+(v-1)+(u-1)(v-1)\ge (u-1)+(v-1).$$
这说明质因子才是自然的“原子代价”：把一个合数剩余拆成更小的因子，不会让超额变大。于是实现实际上寻找的是
$$W=\prod_q q^{e_q}\equiv -1 \pmod p,$$
其中 \(q\) 为素数、\(e_q\ge 0\)，并最小化
$$E(p)=\sum_q e_q(q-1).$$
对于题目中的大素数，这个超额远小于 \(n\)，因此这种因子化搜索与原始配对目标可以自然对应。C++ 实现对若干小素数做了穷举配对校验，验证了
$$S(p)=\frac{p-1}{2}+E(p).$$
固定当前的超额预算 \(B\)。任何满足 \(q-1>B\) 的素数都不可能出现，因此只需要考虑 \(q\le B+1\) 的素数。一个指数向量会决定两个量：
$$r=\prod_q q^{e_q}\bmod p,\qquad c=\sum_q e_q(q-1).$$
对每个可达剩余 \(r\)，只保留最小代价 \(c\) 即可。这样，许多不同的指数选择都会被压缩成同一个最优状态。
把允许的素数拆成两组，分别枚举左右两边在预算 \(B\) 内所有可达的“剩余-代价”状态。如果左边得到的剩余是 \(r_A\)，那么右边必须得到
$$r_B\equiv -r_A^{-1}\pmod p$$
才能保证 \(r_A r_B\equiv -1\pmod p\)。由于 \(p\) 是素数，每个非零剩余都有逆元。于是左右两边代价之和最小的兼容组合，就是预算 \(B\) 下的最佳超额。
实现中还额外优化了合并步骤：它不是对左侧每个剩余单独求逆，而是借助前缀乘积和一次基于费马小定理的求逆，把许多逆元批量算出来。
找到最小可行超额后，再做一次精确搜索，恢复达到该值的各个指数 \(e_q\)。随后构造
$$W=\prod_q q^{e_q}$$
这个任意精度整数。对题目中的大素数，最终输出的就是这个见证。
此时 \(n=\frac{7-1}{2}=3\)，目标同余是
$$W\equiv -1\equiv 6\pmod 7.$$
最便宜的质因子见证为
$$W=2\cdot 3=6,$$
于是超额为
$$E(7)=(2-1)+(3-1)=3.$$
因此预测的最小配对总代价是
$$S(7)=3+3=6.$$
一个显式配对可以写成
$$\{1,3\},\qquad \{2,4\},\qquad \{5,6\},$$
对应的配对剩余分别是 \(3\)、\(1\)、\(2\)。它们的和是 \(3+1+2=6\)，乘积是 \(3\cdot 1\cdot 2=6\equiv -1\pmod 7\)，与上面的理论完全一致。\(p=5\) 的检查也类似：\(W=4=2^2\)，超额为 \(2\)，最优总代价是 \(4\)。
C++、Python 和 Java 的实现都先从一个较小的超额预算开始，若当前预算下找不到可行见证，就逐步扩大预算。对于每个预算，它们先生成所有不超过 \(B+1\) 的素数，再把这些素数分成两组，递归枚举所有满足加权代价不超过预算的指数模式。每一侧对模 \(p\) 的每个剩余只保留最便宜的代价。
当左右两张表都建立完成后，实现会查找乘积为 \(-1 \bmod p\) 的兼容剩余。一旦某个预算第一次成功，就再做一次递归回溯，恢复精确的指数，并把相应的素数相乘得到最终的大整数见证 \(W\)。C++ 实现还额外对若干小素数执行穷举配对搜索，从而确认计算出的超额在加上基线 \(\frac{p-1}{2}\) 后，恰好等于真实的最优配对总代价。
记最小超额为 \(B^*\)。对给定预算 \(B\)，筛出不超过 \(B+1\) 的素数需要 \(O(B\log\log B)\) 时间。主导成本来自于枚举所有满足
$$\sum_q e_q(q-1)\le B$$
的指数向量。若左右两边分别探索到的状态数为 \(N_A(B)\) 和 \(N_B(B)\)，那么一轮的时间复杂度是
$$O\bigl(B\log\log B + N_A(B) + N_B(B)\bigr).$$
内存复杂度为
$$O\bigl(M_A(B)+M_B(B)\bigr),$$
其中 \(M_A(B)\) 与 \(M_B(B)\) 是两张哈希表里实际存储的剩余个数。由于实践中的预算很小，运行时间更多取决于最优超额，而不是取决于 \(p\) 的巨大数值本身。
Для нечётного простого \(p\) нужно разбить числа \(1,2,\dots,p-1\) на \(\frac{p-1}{2}\) непересекающихся пар. Каждая пара \(\{a,b\}\) даёт вклад, равный наименьшему положительному остатку от \(ab \bmod p\), и требуется минимизировать суммарную стоимость. Реализации не перебирают сами паросочетания для большого целевого простого, а сводят задачу к модульной оптимизации в группе \((\mathbb{Z}/p\mathbb{Z})^\times\), после чего восстанавливают соответствующее целое-свидетель.
Пусть \(n=\frac{p-1}{2}\). Если некоторое разбиение даёт остатки пар \(r_1,\dots,r_n\in\{1,\dots,p-1\}\), то минимизируется величина
$$S(p)=\min \sum_{i=1}^{n} r_i.$$
Если пары равны \(\{a_i,b_i\}\), то \(r_i\equiv a_i b_i \pmod p\). Поскольку каждое ненулевое число по модулю \(p\) используется ровно один раз, получаем
$$\prod_{i=1}^{n} r_i \equiv \prod_{k=1}^{p-1} k \equiv -1 \pmod p,$$
где последняя конгруэнция есть теорема Вильсона. Значит, любое допустимое разбиение порождает мультимножество положительных остатков, произведение которых сравнимо с \(-1\) по модулю \(p\).
Каждая пара даёт вклад не меньше \(1\), поэтому
$$\sum_{i=1}^{n} r_i = n + \sum_{i=1}^{n}(r_i-1).$$
Постоянная часть \(n\) неизбежна. Оптимизировать нужно именно избыток \(\sum (r_i-1)\).
Если остаток \(c>1\) составной и \(c=uv\), то
$$c-1=(u-1)+(v-1)+(u-1)(v-1)\ge (u-1)+(v-1).$$
Отсюда видно, почему простые множители являются естественными атомами задачи: разложение составного остатка на меньшие множители не увеличивает избыток. Поэтому реализации ищут свидетель вида
$$W=\prod_q q^{e_q}\equiv -1 \pmod p,$$
где \(q\) простое, \(e_q\ge 0\), и минимизируют
$$E(p)=\sum_q e_q(q-1).$$
Для большого целевого простого этот избыток очень мал по сравнению с \(n\), поэтому факторизованный поиск естественно совпадает с исходной задачей о попарном разбиении. Проверки на малых простых в C++-реализации подтверждают формулу
$$S(p)=\frac{p-1}{2}+E(p).$$
Зафиксируем текущий бюджет избытка \(B\). Любое простое с \(q-1>B\) использовать нельзя, так что важны только простые \(q\le B+1\). Вектор показателей задаёт две величины:
$$r=\prod_q q^{e_q}\bmod p,\qquad c=\sum_q e_q(q-1).$$
Для каждого достижимого остатка \(r\) нужно хранить только минимальную стоимость \(c\). Тем самым множество разных наборов показателей сжимается до одного лучшего состояния на каждый остаток.
Допустимые простые разбиваются на две группы. Для левой и правой части перечисляются все достижимые состояния «остаток-стоимость» при том же бюджете \(B\). Если левая часть даёт остаток \(r_A\), то правая должна дать
$$r_B\equiv -r_A^{-1}\pmod p$$
чтобы выполнялось \(r_A r_B\equiv -1\pmod p\). Так как \(p\) простое, любой ненулевой остаток обратим. Самая дешёвая совместимая комбинация левой и правой частей даёт лучший избыток при бюджете \(B\).
На этапе слияния реализации используют дополнительное ускорение: множество обратных элементов вычисляется пакетно через префиксные произведения и одно обращение по малой теореме Ферма, а не по одному инверсному вычислению на каждый левый остаток.
Когда найден минимальный допустимый избыток, второй точный поиск восстанавливает показатели \(e_q\), которые его достигают. Затем строится произведение
$$W=\prod_q q^{e_q},$$
уже как целое произвольной точности. Именно это число-свидетель и выводят реализации для большого простого из условия.
Здесь \(n=\frac{7-1}{2}=3\), а целевая конгруэнция равна
$$W\equiv -1\equiv 6\pmod 7.$$
Самый дешёвый простой факторизационный свидетель:
$$W=2\cdot 3=6,$$
и его избыток равен
$$E(7)=(2-1)+(3-1)=3.$$
Следовательно, предсказанная минимальная стоимость разбиения равна
$$S(7)=3+3=6.$$
Явное разбиение можно взять таким:
$$\{1,3\},\qquad \{2,4\},\qquad \{5,6\}.$$
Остатки этих пар равны \(3\), \(1\) и \(2\). Их сумма \(3+1+2=6\), а произведение \(3\cdot 1\cdot 2=6\equiv -1\pmod 7\), то есть полностью совпадает с теорией. Проверка для \(p=5\) устроена аналогично: \(W=4=2^2\), избыток равен \(2\), а оптимальная сумма равна \(4\).
Реализации на C++, Python и Java начинают с небольшого бюджета избытка и постепенно увеличивают его, пока не появляется допустимый свидетель. Для каждого бюджета они строят все простые до \(B+1\), делят их на две группы и рекурсивно перечисляют все наборы показателей, чья взвешенная стоимость не превосходит бюджета. Для каждого остатка по модулю \(p\) на каждой стороне сохраняется только минимальная стоимость.
Когда обе таблицы готовы, реализация ищет совместимые остатки, произведение которых равно \(-1\) по модулю \(p\). При первом успешном бюджете второй рекурсивный проход восстанавливает точные показатели и перемножает соответствующие простые, получая окончательный большой свидетель \(W\). Кроме того, C++-реализация проверяет малые простые полным перебором паросочетаний и тем самым подтверждает, что найденный избыток после добавления базы \(\frac{p-1}{2}\) совпадает с истинным минимумом задачи.
Пусть \(B^*\) — минимальный избыток. Для фиксированного бюджета \(B\) просеивание простых до \(B+1\) стоит \(O(B\log\log B)\). Основная работа — перечисление всех векторов показателей, удовлетворяющих условию
$$\sum_q e_q(q-1)\le B.$$
Если \(N_A(B)\) и \(N_B(B)\) — числа состояний, исследованных на двух сторонах, то один раунд занимает
$$O\bigl(B\log\log B + N_A(B) + N_B(B)\bigr)$$
времени. Память имеет порядок
$$O\bigl(M_A(B)+M_B(B)\bigr),$$
где \(M_A(B)\) и \(M_B(B)\) — числа реально сохранённых остатков в двух хеш-таблицах. На практике бюджет мал, поэтому время работы зависит гораздо сильнее от оптимального избытка, чем от огромного значения \(p\).
لعدد أولي فردي \(p\)، نريد تقسيم الأعداد \(1,2,\dots,p-1\) إلى \(\frac{p-1}{2}\) أزواج متباينة. كل زوج \(\{a,b\}\) يضيف أصغر باقٍ موجب للقيمة \(ab \bmod p\)، والمطلوب هو تصغير المجموع الكلي. لا تعتمد التطبيقات على تعداد جميع الأزواج مباشرة عند العدد الأولي الكبير في المسألة، بل تحوّل المسألة إلى تحسين معياري داخل \((\mathbb{Z}/p\mathbb{Z})^\times\)، ثم تعيد بناء العدد الشاهد الموافق لهذا الحل.
لنكتب \(n=\frac{p-1}{2}\). إذا أعطى اقتران ما بواقي الأزواج \(r_1,\dots,r_n\in\{1,\dots,p-1\}\)، فإن الكمية المراد تصغيرها هي
$$S(p)=\min \sum_{i=1}^{n} r_i.$$
إذا كانت الأزواج هي \(\{a_i,b_i\}\)، فلدينا \(r_i\equiv a_i b_i \pmod p\). وبما أن كل باقٍ غير صفري يظهر مرة واحدة تماماً، فإن
$$\prod_{i=1}^{n} r_i \equiv \prod_{k=1}^{p-1} k \equiv -1 \pmod p,$$
والتطابق الأخير هو مبرهنة ويلسون. إذن أي اقتران مقبول يعطي مجموعة متعددة من البواقي الموجبة التي يكون حاصل ضربها مساوياً لـ \(-1\) بترديد \(p\).
كل زوج يضيف على الأقل \(1\)، لذلك
$$\sum_{i=1}^{n} r_i = n + \sum_{i=1}^{n}(r_i-1).$$
الجزء الثابت \(n\) لا يمكن تجنبه، ولذلك يصبح جوهر المسألة هو تصغير الزيادة \(\sum (r_i-1)\).
إذا كان باقٍ ما \(c>1\) عدداً مركباً، ولنقل \(c=uv\)، فحينئذ
$$c-1=(u-1)+(v-1)+(u-1)(v-1)\ge (u-1)+(v-1).$$
وهذا يوضح لماذا تكون العوامل الأولية هي اللبنات الطبيعية للمشكلة: تفكيك باقٍ مركب إلى عوامل أصغر لا يزيد الزيادة. لذلك تبحث التطبيقات عن شاهد من الشكل
$$W=\prod_q q^{e_q}\equiv -1 \pmod p,$$
حيث \(q\) أولي و\(e_q\ge 0\)، مع تصغير
$$E(p)=\sum_q e_q(q-1).$$
بالنسبة إلى العدد الأولي الكبير المستهدف، تكون هذه الزيادة صغيرة جداً مقارنةً بـ \(n\)، ولهذا يتطابق البحث العاملـي عملياً مع هدف الاقتران الأصلي. كما تؤكد فحوص الأعداد الأولية الصغيرة في تنفيذ ++C العلاقة
$$S(p)=\frac{p-1}{2}+E(p).$$
لنثبت ميزانية حالية للزيادة \(B\). أي عدد أولي يحقق \(q-1>B\) لا يمكن أن يظهر، لذا لا نحتاج إلا إلى الأعداد الأولية \(q\le B+1\). متجه الأسس يحدد قيمتين:
$$r=\prod_q q^{e_q}\bmod p,\qquad c=\sum_q e_q(q-1).$$
ولكل باقٍ قابل للوصول \(r\)، يكفي الاحتفاظ بأصغر تكلفة \(c\). وهكذا تُضغط اختيارات كثيرة للأسس في حالة مثلى واحدة لكل فئة بواقٍ.
تُقسم الأعداد الأولية المسموح بها إلى مجموعتين. ثم تُعد جميع حالات الباقي-التكلفة الممكنة في الجهتين تحت الميزانية نفسها \(B\). إذا أعطت الجهة اليسرى الباقي \(r_A\)، فلا بد أن تعطي الجهة اليمنى
$$r_B\equiv -r_A^{-1}\pmod p$$
حتى يتحقق \(r_A r_B\equiv -1\pmod p\). وبما أن \(p\) أولي، فلكل باقٍ غير صفري معكوس. أرخص توليفة متوافقة بين الجهتين تعطي أفضل زيادة تحت الميزانية \(B\).
وتُسرّع التطبيقات خطوة الدمج أيضاً بحساب عدد كبير من المعكوسات دفعة واحدة، عبر جداءات بادئة ومعكوس واحد مبني على مبرهنة فيرما الصغرى، بدلاً من حساب معكوس مستقل لكل باقٍ في الجهة اليسرى.
بعد العثور على أصغر زيادة ممكنة، يجري بحث ثانٍ دقيق لاستعادة الأسس \(e_q\) التي تحققها. ثم يُبنى العدد
$$W=\prod_q q^{e_q}$$
كعدد صحيح ذي دقة غير محدودة. وهذا هو الشاهد الذي تطبعه التطبيقات في النهاية للعدد الأولي الكبير في المسألة.
هنا لدينا \(n=\frac{7-1}{2}=3\)، ويصبح شرط التطابق
$$W\equiv -1\equiv 6\pmod 7.$$
أرخص شاهد أولي العوامل هو
$$W=2\cdot 3=6,$$
ومن ثم تكون الزيادة
$$E(7)=(2-1)+(3-1)=3.$$
إذن الكلفة الدنيا المتوقعة للازواج هي
$$S(7)=3+3=6.$$
ويمكن إعطاء اقتران صريح بالشكل
$$\{1,3\},\qquad \{2,4\},\qquad \{5,6\}.$$
بواقي هذه الأزواج هي \(3\) و\(1\) و\(2\). مجموعها \(3+1+2=6\)، وحاصل ضربها \(3\cdot 1\cdot 2=6\equiv -1\pmod 7\)، وهذا يطابق النظرية تماماً. وفحص \(p=5\) مشابه أيضاً: \(W=4=2^2\)، والزيادة \(2\)، والمجموع الأمثل هو \(4\).
تبدأ تطبيقات ++C وPython وJava بميزانية صغيرة للزيادة، ثم ترفعها تدريجياً إلى أن يظهر شاهد صالح. في كل ميزانية، تُولِّد جميع الأعداد الأولية حتى \(B+1\)، ثم تقسّمها إلى مجموعتين، وتعدّ كل أنماط الأسس التي تبقى كلفتها الموزونة ضمن الميزانية. وعلى كل جانب لا يُحفظ إلا أصغر ثمن معروف لكل باقٍ modulo \(p\).
بعد بناء الجدولين، تبحث التطبيقات عن بواقي متوافقة يكون حاصل ضربها \(-1\) modulo \(p\). وعند أول ميزانية ناجحة، تمرّ مرحلة استرجاع ثانية لإعادة بناء الأسس الدقيقة ثم ضرب الأعداد الأولية الموافقة للحصول على الشاهد الكبير \(W\). كما يقوم تنفيذ ++C بفحص أعداد أولية صغيرة عبر تعداد كامل للاقترانات، وبذلك يؤكد أن الزيادة المحسوبة تعطي بعد إضافة الحد الأساسي \(\frac{p-1}{2}\) أقل مجموع حقيقي لمسألة الأزواج.
لنرمز إلى أقل زيادة ممكنة بـ \(B^*\). بالنسبة إلى ميزانية \(B\)، فإن توليد الأعداد الأولية حتى \(B+1\) يكلف \(O(B\log\log B)\). أما العمل المسيطر فهو تعداد جميع متجهات الأسس التي تحقق
$$\sum_q e_q(q-1)\le B.$$
إذا كان \(N_A(B)\) و\(N_B(B)\) يمثلان عدد الحالات المستكشفة في الجهتين، فإن جولة واحدة تحتاج إلى
$$O\bigl(B\log\log B + N_A(B) + N_B(B)\bigr)$$
زمن. أما الذاكرة فهي من الرتبة
$$O\bigl(M_A(B)+M_B(B)\bigr),$$
حيث \(M_A(B)\) و\(M_B(B)\) هما عددا البواقي المخزنة فعلياً في جدولَي التجزئة. عملياً تبقى الميزانية صغيرة، ولذلك يعتمد زمن التنفيذ على الزيادة المثلى أكثر بكثير من اعتماده على القيمة الضخمة لـ \(p\).