Problem 995 looks like a question about divisibility of two sparse polynomials, but the useful object is not a polynomial expansion. For a prime \(p\), \(f_p(x)=1+x+\cdots+x^{p-1}\) is the cyclotomic polynomial \(\Phi_p(x)\). Therefore divisibility by \(f_p\) can be tested at a primitive \(p\)-th root of unity. This turns the problem into a question about how the divisor set of an integer \(s\) is distributed among residue classes modulo \(p\).
The main reduction is that \(f_p(x)\mid g_s(x)\) holds exactly when the positive divisors of \(s\) form a perfect tiling of \(\mathbb{F}_p^\times\) by residues. Consequently \(p\nmid s\), \(\tau(s)=p-1\), and each non-zero residue class modulo \(p\) must be hit exactly once by a divisor of \(s\). The implementation then searches for the numerically smallest such \(s\), not by enumerating divisors of candidate integers, but by building a subgroup chain inside the cyclic group \(\mathbb{F}_p^\times\).
The final product \(T(20000)\) is much too large to store. The program computes each \(\log_{10} S(p)\), sums those logarithms over all primes \(p\lt 20000\), and formats the final mantissa and exponent. Exact integer reconstruction is used only for small validation cases such as \(S(5)=8\), \(T(20)=1348422598656\), and the stated \(T(100)\) checkpoint.
For a prime \(p\) and a positive integer \(n\), the problem defines
$$f_p(x)=\sum_{i=0}^{p-1}x^i,\qquad g_n(x)=1+\sum_{d\mid n}x^d.$$
The term \(1\) in \(g_n\) is important: it is an extra constant term whose exponent is \(0\). The divisors \(d\mid n\) are positive divisors and contribute exponents \(d\). We seek the least positive integer \(s\) such that \(f_p(x)\mid g_s(x)\), denoted \(S(p)\).
Throughout the analysis, \(G=\mathbb{F}_p^\times\) denotes the multiplicative group of non-zero residues modulo \(p\). This group is cyclic of order \(p-1\). If \(g\) is a primitive root modulo \(p\), every non-zero residue has a unique representation \(g^e\), \(0\le e\lt p-1\); the exponent \(e\) is the discrete logarithm used by the code.
Let \(\zeta\ne 1\) be a primitive \(p\)-th root of unity. Since \(p\) is prime,
$$f_p(x)=1+x+\cdots+x^{p-1}=\Phi_p(x),$$
and \(\Phi_p(x)\) is the minimal polynomial of \(\zeta\) over \(\mathbb{Q}\). Therefore \(f_p(x)\mid g_s(x)\) if and only if \(g_s(\zeta)=0\).
Group the exponents of \(g_s\) by their residue classes modulo \(p\). Let \(c_r\) be the number of terms in \(g_s\) whose exponent is congruent to \(r\pmod p\). Then
$$g_s(\zeta)=\sum_{r=0}^{p-1}c_r\zeta^r.$$
The powers \(1,\zeta,\ldots,\zeta^{p-1}\) satisfy one rational linear relation, namely \(1+\zeta+\cdots+\zeta^{p-1}=0\), and all rational relations are multiples of it. Hence \(g_s(\zeta)=0\) is equivalent to
$$c_0=c_1=\cdots=c_{p-1}.$$
Thus the polynomial divisibility problem has become a balancing condition on residue-class counts. The coefficients of the polynomials themselves never need to be expanded.
First suppose \(p\mid s\), and write \(s=p^a u\), with \(a\ge 1\) and \(p\nmid u\). The divisors not divisible by \(p\) are exactly the divisors of \(u\), so all non-zero residue classes together receive \(\tau(u)\) contributions. If the common residue count is \(C\), then
$$\tau(u)=(p-1)C.$$
The zero residue class receives the extra constant term and every divisor containing at least one factor \(p\), so its count is \(1+a\tau(u)\). Equality of all \(c_r\) would require
$$C=1+a\tau(u)=1+a(p-1)C,$$
which is impossible for positive \(C\). Hence no valid minimal or non-minimal solution can have \(p\mid s\).
Now \(p\nmid s\). Every divisor of \(s\) is non-zero modulo \(p\), and the only contribution to residue class \(0\) is the separate constant term in \(g_s\). Therefore \(c_0=1\). Since all \(c_r\) must be equal, every non-zero class must also occur exactly once. The divisibility condition is therefore equivalent to the bijection
$$\{d:d\mid s\}\longrightarrow \mathbb{F}_p^\times,\qquad d\longmapsto d\bmod p.$$
In particular, the number of divisors must be
$$\tau(s)=p-1.$$
Write the unknown integer in prime-power form
$$s=\prod_{j=1}^k q_j^{a_j},\qquad q_j\ne p,$$
and define the divisor-box lengths \(\ell_j=a_j+1\). Since \(\tau(s)=\prod_j(a_j+1)\), the lengths must satisfy
$$\prod_{j=1}^k \ell_j=p-1.$$
Choosing a factor \(q_j^{a_j}\) adds the finite progression \(1,q_j,q_j^2,\ldots,q_j^{\ell_j-1}\) to the divisor box. Modulo \(p\), these progressions should multiply together without collisions and eventually cover the whole cyclic group \(G\). The implementation uses the canonical subgroup-chain formulation of this condition: after some steps the already constructed residues are the unique subgroup \(H\le G\) of size \(h\mid p-1\).
Assume the current subgroup has size \(h\). The quotient group \(G/H\) has order
$$Q={p-1\over h}.$$
A new prime residue \(q\) may be used with length \(\ell\mid Q\) precisely when the coset \(qH\) has order \(\ell\) in \(G/H\). Then the cosets
$$H,\;qH,\;q^2H,\;\ldots,\;q^{\ell-1}H$$
are distinct, and multiplying the old subgroup by \(1,q,\ldots,q^{\ell-1}\) gives the unique subgroup of size \(h\ell\). This is exactly the no-collision condition needed by the divisor tiling.
Using a primitive root \(g\), write \(q\equiv g^e\pmod p\). In the quotient of order \(Q\), the order of \(qH\) is
$$\operatorname{ord}_{G/H}(qH)={Q\over \gcd(e,Q)}.$$
Therefore the transition condition used in the solver is
$$\operatorname{ord}_{G/H}(qH)=\ell \quad\Longleftrightarrow\quad \gcd(e,Q)={Q\over \ell}.$$
The value of \(s\) should be minimal as an integer. If a transition uses a prime \(q\) with length \(\ell\), then it contributes the factor \(q^{\ell-1}\) to \(s\). The code minimizes logarithms, so the transition weight is
$$w(\ell,q)=(\ell-1)\log_{10}q.$$
For a fixed state \(h\) and a fixed length \(\ell\), the future state depends only on \(h\ell\), not on the path by which \(h\) was reached. Because \(G\) is cyclic, there is a unique subgroup of each size \(h\mid p-1\). Hence the best prime for that transition is simply the smallest prime \(q\ne p\) satisfying the discrete-log condition above.
The dynamic program stores \(D(h)\), the smallest known value of \(\log_{10}\) of the partial integer that constructs the subgroup of size \(h\). It starts with
$$D(1)=0,$$
and for every divisor \(\ell\gt 1\) of \(Q=(p-1)/h\), it relaxes
$$D(h\ell)=\min\left(D(h\ell),\;D(h)+(\ell-1)\log_{10}q\right),$$
where \(q\) is the smallest transition prime with \(\gcd(\log_g q,Q)=Q/\ell\). The answer for one prime is \(D(p-1)=\log_{10}S(p)\). Parent pointers record the chosen pairs \((\ell,q)\), which lets the program reconstruct exact small values for validation.
The root-condition lemma proves that polynomial divisibility is equivalent to equal residue counts. The divisor-tiling lemma then proves that any solution must have \(p\nmid s\) and that its divisors must hit the elements of \(G\) exactly once. Thus solving the original problem is equivalent to finding the smallest integer whose divisor box is a collision-free product decomposition of \(G\).
Each DP transition is valid because the quotient-order condition makes the new powers \(1,q,\ldots,q^{\ell-1}\) represent \(\ell\) distinct cosets of the current subgroup. The old subgroup has \(h\) elements, so the enlarged product has \(h\ell\) distinct residues and is exactly the subgroup of that size. By induction, every DP path from \(1\) to \(p-1\) constructs a valid divisor tiling and hence a valid integer \(s\).
Conversely, in the cyclic group setting relevant here, an exact divisor-box tiling can be read as a sequence of quotient complements: at each stage one chooses a divisor-box direction whose images are distinct cosets over the subgroup already constructed. Since the group has only one subgroup of each divisor size, the state \(h\) loses no subgroup identity information. Therefore the DP considers the necessary canonical transitions, and taking the minimum over them yields \(S(p)\).
For \(p=2\), \(f_2(x)=1+x\), and \(g_1(x)=1+x\), so \(S(2)=1\). This is the degenerate group case \(G=\mathbb{F}_2^\times\), whose order is \(1\); the DP starts and finishes at the same state.
For \(p=5\), \(G\) has order \(4\). The smallest primitive residue is \(2\). A single transition with \(\ell=4\) gives
$$S(5)=2^{4-1}=8,$$
matching the problem statement. Its divisors \(1,2,4,8\) reduce modulo \(5\) to \(1,2,4,3\), all non-zero residues exactly once.
For \(p=7\), the optimal chain can be expressed as \((\ell,q)=(3,2)\) followed by \((2,3)\). The resulting integer is
$$S(7)=2^{3-1}3^{2-1}=12.$$
The divisors \(1,2,4,3,6,12\) reduce modulo \(7\) to \(1,2,4,3,6,5\), again a complete tiling of \(\mathbb{F}_7^\times\). The full implementation checks these local examples and also verifies the product checkpoints \(T(20)=1348422598656\) and \(T(100)=1.37451\mathrm{e}123\).
The C++, Python, and Java versions follow the same pipeline. They sieve primes up to \(2\,000\,000\), factor \(p-1\), enumerate all divisors of \(p-1\), find a primitive root modulo \(p\), and build a discrete-log table mapping each non-zero residue to its exponent with respect to that root.
The function that searches a transition prime scans the precomputed prime list and rejects \(q=p\). If no suitable prime appears inside the sieve range, the implementation continues by trial primality testing beyond the sieve. In practice the bound is generous for the \(p\lt 20000\) instances, but the fallback keeps the logic complete rather than dependent on a guessed cutoff.
All large products are handled logarithmically. Exact multiplication is retained only for reconstructed small \(S(p)\) values and for \(T(20)\). This separation is important: the final \(T(20000)\) has hundreds of thousands of decimal digits, while its scientific notation only needs the fractional part and integer part of the summed base-10 logarithm.
For a single prime \(p\), the DP state count is \(\tau(p-1)\), the number of divisors of \(p-1\). Each state tests divisor lengths \(\ell\mid (p-1)/h\), and each transition scans primes until it finds a residue with the required quotient order. The memory use for the discrete-log table is \(O(p)\), and it is discarded after that prime is solved.
The full target has only \(2262\) primes below \(20000\). The algorithm therefore spends its time on small divisor lattices of \(p-1\), not on polynomial coefficients and not on divisors of a gigantic candidate integer. Long-double logarithms are sufficient because the output requires a rounded mantissa with five digits after the decimal point; the exact small checkpoints guard against structural errors in the reduction.
Problem 995 sieht zunächst wie eine Frage über die Teilbarkeit zweier dünn besetzter Polynome aus, aber die nützliche Struktur liegt nicht in einer Polynomexpansion. Für eine Primzahl \(p\) ist \(f_p(x)=1+x+\cdots+x^{p-1}\) das Kreisteilungspolynom \(\Phi_p(x)\). Teilbarkeit durch \(f_p\) lässt sich deshalb an einer primitiven \(p\)-ten Einheitswurzel testen. Dadurch wird die Aufgabe zu einer Frage darüber, wie die Teilermenge eines Integers \(s\) auf Restklassen modulo \(p\) verteilt ist.
Die zentrale Reduktion lautet: \(f_p(x)\mid g_s(x)\) gilt genau dann, wenn die positiven Teiler von \(s\) eine perfekte Pflasterung von \(\mathbb{F}_p^\times\) durch Restklassen bilden. Folglich gilt \(p\nmid s\), \(\tau(s)=p-1\), und jede von null verschiedene Restklasse modulo \(p\) muss von genau einem Teiler von \(s\) getroffen werden. Die Implementierung sucht dieses kleinste \(s\) nicht durch Probieren von Kandidaten, sondern durch den Aufbau einer Untergruppenkette in der zyklischen Gruppe \(\mathbb{F}_p^\times\).
Das Endprodukt \(T(20000)\) ist viel zu groß, um als Integer gespeichert zu werden. Das Programm berechnet daher für jedes \(p\) den Wert \(\log_{10}S(p)\), summiert diese Logarithmen über alle Primzahlen \(p\lt 20000\) und formatiert am Ende Mantisse und Exponent. Exakte Integer-Rekonstruktion dient nur kleinen Kontrollen wie \(S(5)=8\), \(T(20)=1348422598656\) und dem angegebenen Kontrollwert für \(T(100)\).
Für eine Primzahl \(p\) und einen positiven Integer \(n\) definiert die Aufgabe
$$f_p(x)=\sum_{i=0}^{p-1}x^i,\qquad g_n(x)=1+\sum_{d\mid n}x^d.$$
Der Term \(1\) in \(g_n\) ist wesentlich: Er ist ein zusätzlicher konstanter Term mit Exponent \(0\). Die Teiler \(d\mid n\) sind positive Teiler und liefern die Exponenten \(d\). Gesucht ist der kleinste positive Integer \(s\), für den \(f_p(x)\mid g_s(x)\) gilt; dieser Wert heißt \(S(p)\).
Im Folgenden bezeichnet \(G=\mathbb{F}_p^\times\) die multiplikative Gruppe der von null verschiedenen Reste modulo \(p\). Diese Gruppe ist zyklisch und hat Ordnung \(p-1\). Ist \(g\) eine primitive Wurzel modulo \(p\), dann besitzt jeder von null verschiedene Rest eine eindeutige Darstellung \(g^e\), \(0\le e\lt p-1\); dieser Exponent \(e\) ist der diskrete Logarithmus, den der Code verwendet.
Sei \(\zeta\ne 1\) eine primitive \(p\)-te Einheitswurzel. Da \(p\) prim ist, gilt
$$f_p(x)=1+x+\cdots+x^{p-1}=\Phi_p(x),$$
und \(\Phi_p(x)\) ist das Minimalpolynom von \(\zeta\) über \(\mathbb{Q}\). Somit gilt \(f_p(x)\mid g_s(x)\) genau dann, wenn \(g_s(\zeta)=0\).
Wir gruppieren die Exponenten von \(g_s\) nach ihren Restklassen modulo \(p\). Sei \(c_r\) die Anzahl der Terme von \(g_s\), deren Exponent kongruent zu \(r\pmod p\) ist. Dann gilt
$$g_s(\zeta)=\sum_{r=0}^{p-1}c_r\zeta^r.$$
Die Potenzen \(1,\zeta,\ldots,\zeta^{p-1}\) erfüllen genau eine rationale lineare Relation, nämlich \(1+\zeta+\cdots+\zeta^{p-1}=0\), und jede rationale Relation ist ein Vielfaches davon. Daher ist \(g_s(\zeta)=0\) äquivalent zu
$$c_0=c_1=\cdots=c_{p-1}.$$
Die Polynomteilbarkeit ist damit eine Gleichverteilungsbedingung für Restklassen. Die Polynomkoeffizienten selbst müssen zu keinem Zeitpunkt expandiert werden.
Nehmen wir zunächst \(p\mid s\) an und schreiben \(s=p^a u\), mit \(a\ge 1\) und \(p\nmid u\). Die nicht durch \(p\) teilbaren Teiler sind genau die Teiler von \(u\), daher erhalten alle von null verschiedenen Restklassen zusammen \(\tau(u)\) Beiträge. Ist der gemeinsame Restklassenzähler \(C\), dann gilt
$$\tau(u)=(p-1)C.$$
Die Nullklasse erhält den zusätzlichen konstanten Term und jeden Teiler, der mindestens einen Faktor \(p\) enthält. Ihre Anzahl ist also \(1+a\tau(u)\). Gleichheit aller \(c_r\) würde erfordern
$$C=1+a\tau(u)=1+a(p-1)C,$$
was für positives \(C\) unmöglich ist. Damit kann keine gültige Lösung, auch keine nicht minimale, durch \(p\) teilbar sein.
Nun gilt \(p\nmid s\). Jeder Teiler von \(s\) ist modulo \(p\) von null verschieden, und zur Restklasse \(0\) trägt nur der separate konstante Term von \(g_s\) bei. Also ist \(c_0=1\). Da alle \(c_r\) gleich sein müssen, muss jede von null verschiedene Klasse ebenfalls genau einmal auftreten. Die Teilbarkeitsbedingung ist daher äquivalent zur Bijektion
$$\{d:d\mid s\}\longrightarrow \mathbb{F}_p^\times,\qquad d\longmapsto d\bmod p.$$
Insbesondere muss die Teileranzahl
$$\tau(s)=p-1$$
betragen.
Schreiben wir den gesuchten Integer als
$$s=\prod_{j=1}^k q_j^{a_j},\qquad q_j\ne p,$$
und setzen \(\ell_j=a_j+1\). Weil \(\tau(s)=\prod_j(a_j+1)\), müssen die Längen
$$\prod_{j=1}^k \ell_j=p-1$$
erfüllen. Ein Faktor \(q_j^{a_j}\) fügt der Teilerbox die endliche Progression \(1,q_j,q_j^2,\ldots,q_j^{\ell_j-1}\) hinzu. Modulo \(p\) sollen diese Progressionen kollisionsfrei multiplizieren und schließlich die ganze zyklische Gruppe \(G\) überdecken. Die Implementierung nutzt dafür die kanonische Untergruppenkettenform: Nach einigen Schritten bilden die bereits konstruierten Reste die eindeutige Untergruppe \(H\le G\) der Größe \(h\mid p-1\).
Hat die aktuelle Untergruppe Größe \(h\), so hat die Faktorgruppe \(G/H\) die Ordnung
$$Q={p-1\over h}.$$
Ein neuer Primrest \(q\) darf mit Länge \(\ell\mid Q\) verwendet werden, wenn die Nebenklasse \(qH\) in \(G/H\) Ordnung \(\ell\) hat. Dann sind die Nebenklassen
$$H,\;qH,\;q^2H,\;\ldots,\;q^{\ell-1}H$$
verschieden, und die Multiplikation der alten Untergruppe mit \(1,q,\ldots,q^{\ell-1}\) ergibt die eindeutige Untergruppe der Größe \(h\ell\). Genau dies ist die Kollisionsfreiheit, die die Teilerpflasterung verlangt.
Mit einer primitiven Wurzel \(g\) schreiben wir \(q\equiv g^e\pmod p\). In der Faktorgruppe der Ordnung \(Q\) ist die Ordnung von \(qH\)
$$\operatorname{ord}_{G/H}(qH)={Q\over \gcd(e,Q)}.$$
Damit lautet die im Solver verwendete Übergangsbedingung
$$\operatorname{ord}_{G/H}(qH)=\ell \quad\Longleftrightarrow\quad \gcd(e,Q)={Q\over \ell}.$$
Der Wert von \(s\) soll als Integer minimal sein. Verwendet ein Übergang den Primfaktor \(q\) mit Länge \(\ell\), dann trägt er den Faktor \(q^{\ell-1}\) zu \(s\) bei. Der Code minimiert Logarithmen; die Übergangskosten sind also
$$w(\ell,q)=(\ell-1)\log_{10}q.$$
Für einen festen Zustand \(h\) und eine feste Länge \(\ell\) hängt der Folgezustand nur von \(h\ell\) ab, nicht vom Weg, auf dem \(h\) erreicht wurde. Da \(G\) zyklisch ist, gibt es zu jeder Größe \(h\mid p-1\) genau eine Untergruppe. Der beste Primfaktor für diesen Übergang ist deshalb einfach der kleinste Primfaktor \(q\ne p\), der die diskrete-Log-Bedingung erfüllt.
Die dynamische Programmierung speichert \(D(h)\), den kleinsten bekannten \(\log_{10}\)-Wert des partiellen Integers, der die Untergruppe der Größe \(h\) erzeugt. Sie startet mit
$$D(1)=0,$$
und relaxiert für jeden Teiler \(\ell\gt 1\) von \(Q=(p-1)/h\)
$$D(h\ell)=\min\left(D(h\ell),\;D(h)+(\ell-1)\log_{10}q\right),$$
wobei \(q\) der kleinste Übergangsprimfaktor mit \(\gcd(\log_g q,Q)=Q/\ell\) ist. Die Antwort für eine Primzahl ist \(D(p-1)=\log_{10}S(p)\). Elternzeiger speichern die gewählten Paare \((\ell,q)\), sodass kleine Werte exakt rekonstruiert werden können.
Das Wurzellemma zeigt, dass Polynomteilbarkeit gleichbedeutend mit gleichen Restklassenzählern ist. Das Teilerpflasterungslemma zeigt anschließend, dass jede Lösung \(p\nmid s\) erfüllen muss und dass ihre Teiler die Elemente von \(G\) genau einmal treffen. Damit ist die ursprüngliche Aufgabe äquivalent zur Suche nach dem kleinsten Integer, dessen Teilerbox eine kollisionsfreie Produktzerlegung von \(G\) ist.
Jeder DP-Übergang ist gültig, weil die Quotientenordnungsbedingung die neuen Potenzen \(1,q,\ldots,q^{\ell-1}\) zu \(\ell\) verschiedenen Nebenklassen der aktuellen Untergruppe macht. Die alte Untergruppe hat \(h\) Elemente; das vergrößerte Produkt hat daher \(h\ell\) verschiedene Reste und ist genau die Untergruppe dieser Größe. Induktiv konstruiert jeder Pfad von \(1\) nach \(p-1\) eine gültige Teilerpflasterung und damit einen gültigen Integer \(s\).
Umgekehrt kann eine exakte Teilerboxpflasterung in der hier relevanten zyklischen Gruppe als Folge von Quotientenkomplementen gelesen werden: In jedem Schritt wählt man eine Richtung der Teilerbox, deren Bilder verschiedene Nebenklassen über der bereits konstruierten Untergruppe bilden. Weil es in der zyklischen Gruppe nur eine Untergruppe jeder Teilergröße gibt, verliert der Zustand \(h\) keine Information über die Identität der Untergruppe. Die DP betrachtet daher die nötigen kanonischen Übergänge, und das Minimum liefert \(S(p)\).
Für \(p=2\) gilt \(f_2(x)=1+x\), und \(g_1(x)=1+x\), also \(S(2)=1\). Dies ist der degenerierte Gruppenfall \(G=\mathbb{F}_2^\times\) mit Ordnung \(1\); die DP startet und endet im selben Zustand.
Für \(p=5\) hat \(G\) Ordnung \(4\). Der kleinste primitive Rest ist \(2\). Ein einziger Übergang mit \(\ell=4\) liefert
$$S(5)=2^{4-1}=8,$$
wie in der Aufgabenstellung. Die Teiler \(1,2,4,8\) werden modulo \(5\) zu \(1,2,4,3\), also zu allen von null verschiedenen Resten genau einmal.
Für \(p=7\) kann die optimale Kette als \((\ell,q)=(3,2)\) gefolgt von \((2,3)\) geschrieben werden. Der resultierende Integer ist
$$S(7)=2^{3-1}3^{2-1}=12.$$
Die Teiler \(1,2,4,3,6,12\) werden modulo \(7\) zu \(1,2,4,3,6,5\), also wieder zu einer vollständigen Pflasterung von \(\mathbb{F}_7^\times\). Die Implementierung prüft diese lokalen Beispiele und zusätzlich die Produktkontrollen \(T(20)=1348422598656\) und \(T(100)=1.37451\mathrm{e}123\).
Die C++-, Python- und Java-Versionen folgen derselben Pipeline. Sie sieben Primzahlen bis \(2\,000\,000\), faktorisieren \(p-1\), enumerieren alle Teiler von \(p-1\), finden eine primitive Wurzel modulo \(p\), und bauen eine diskrete-Log-Tabelle, die jedem von null verschiedenen Rest seinen Exponenten bezüglich dieser Wurzel zuordnet.
Die Suche nach einem Übergangsprimfaktor scannt die vorberechnete Primzahlliste und verwirft \(q=p\). Falls innerhalb des Siebbereichs kein passender Primfaktor erscheint, setzt die Implementierung mit Primzahltests jenseits des Siebs fort. In der Praxis ist die Schranke für \(p\lt 20000\) großzügig, aber der Fallback macht die Logik unabhängig von einem geratenen Cutoff.
Alle großen Produkte werden logarithmisch behandelt. Exakte Multiplikation bleibt nur für rekonstruierte kleine \(S(p)\)-Werte und für \(T(20)\) erhalten. Diese Trennung ist entscheidend: Das endgültige \(T(20000)\) besitzt Hunderttausende Dezimalstellen, während die wissenschaftliche Schreibweise nur den gebrochenen und den ganzzahligen Anteil der summierten Zehnerlogarithmen benötigt.
Für eine einzelne Primzahl \(p\) ist die Zahl der DP-Zustände \(\tau(p-1)\), also die Anzahl der Teiler von \(p-1\). Jeder Zustand testet Längen \(\ell\mid (p-1)/h\), und jeder Übergang scannt Primzahlen, bis ein Rest mit der verlangten Quotientenordnung gefunden ist. Die diskrete-Log-Tabelle benötigt \(O(p)\) Speicher und wird nach dieser Primzahl verworfen.
Unter \(20000\) gibt es nur \(2262\) Primzahlen. Der Algorithmus arbeitet daher auf kleinen Teilerverbänden von \(p-1\), nicht auf Polynomkoeffizienten und nicht auf den Teilern eines riesigen Kandidatenintegers. Long-double-Logarithmen reichen aus, weil die Ausgabe nur eine auf fünf Nachkommastellen gerundete Mantisse verlangt; die exakten kleinen Kontrollwerte sichern die strukturelle Reduktion ab.
Problem 995 ilk bakışta iki seyrek polinomun bölünebilirliği hakkında bir soru gibi görünür; fakat işe yarayan nesne polinomları açmak değildir. Bir asal \(p\) için \(f_p(x)=1+x+\cdots+x^{p-1}\), siklotomik polinom \(\Phi_p(x)\)'tir. Bu nedenle \(f_p\)'ye bölünebilirlik, ilkel bir \(p\). birim kökünde test edilebilir. Böylece problem, bir \(s\) tamsayısının bölenlerinin modulo \(p\) kalıntı sınıflarına nasıl dağıldığı sorusuna dönüşür.
Ana indirgeme şudur: \(f_p(x)\mid g_s(x)\) ancak ve ancak \(s\)'nin pozitif bölenleri \(\mathbb{F}_p^\times\) grubunu kalıntılarla kusursuz biçimde kaplıyorsa doğrudur. Sonuç olarak \(p\nmid s\), \(\tau(s)=p-1\), ve modulo \(p\) her sıfır dışı kalıntı sınıfı \(s\)'nin tam bir böleni tarafından tam bir kez vurulmalıdır. Uygulama bu en küçük \(s\)'yi aday sayıları deneyerek değil, çevrimsel grup \(\mathbb{F}_p^\times\) içinde bir altgrup zinciri kurarak arar.
Son ürün \(T(20000)\) bir tamsayı olarak saklanamayacak kadar büyüktür. Program her \(p\) için \(\log_{10}S(p)\) hesaplar, bu logaritmaları \(p\lt 20000\) asalları üzerinde toplar ve sonunda mantis ile üssü biçimlendirir. Tam tamsayı yeniden kurma yalnızca \(S(5)=8\), \(T(20)=1348422598656\) ve verilen \(T(100)\) kontrolü gibi küçük doğrulamalarda kullanılır.
Bir asal \(p\) ve pozitif tamsayı \(n\) için problem şu polinomları tanımlar:
$$f_p(x)=\sum_{i=0}^{p-1}x^i,\qquad g_n(x)=1+\sum_{d\mid n}x^d.$$
\(g_n\) içindeki \(1\) terimi kritiktir: üssü \(0\) olan ek bir sabit terimdir. \(d\mid n\) ifadeleri pozitif bölenleri gösterir ve bunlar \(d\) üslerini üretir. Amaç, \(f_p(x)\mid g_s(x)\) yapan en küçük pozitif \(s\) tamsayısını bulmaktır; bu değer \(S(p)\) olarak adlandırılır.
Analizde \(G=\mathbb{F}_p^\times\), modulo \(p\) sıfır dışı kalıntıların çarpımsal grubunu gösterecektir. Bu grup çevrimseldir ve mertebesi \(p-1\)'dir. \(g\) modulo \(p\) bir ilkel kökse, her sıfır dışı kalıntı tek biçimde \(g^e\), \(0\le e\lt p-1\), olarak yazılır; kodun kullandığı ayrık logaritma bu \(e\) değeridir.
\(\zeta\ne 1\) ilkel bir \(p\). birim kökü olsun. \(p\) asal olduğundan
$$f_p(x)=1+x+\cdots+x^{p-1}=\Phi_p(x),$$
ve \(\Phi_p(x)\), \(\zeta\)'nın \(\mathbb{Q}\) üzerindeki minimal polinomudur. Bu yüzden \(f_p(x)\mid g_s(x)\) koşulu tam olarak \(g_s(\zeta)=0\) koşuluna denktir.
\(g_s\)'nin üslerini modulo \(p\) kalıntı sınıflarına göre gruplayalım. \(c_r\), üssü \(r\pmod p\) olan terimlerin sayısı olsun. O zaman
$$g_s(\zeta)=\sum_{r=0}^{p-1}c_r\zeta^r.$$
\(1,\zeta,\ldots,\zeta^{p-1}\) kuvvetleri arasındaki tek rasyonel doğrusal ilişki \(1+\zeta+\cdots+\zeta^{p-1}=0\) ilişkisidir; diğer tüm rasyonel ilişkiler bunun katıdır. Dolayısıyla \(g_s(\zeta)=0\) koşulu
$$c_0=c_1=\cdots=c_{p-1}$$
koşuluna denktir. Böylece polinom bölünebilirliği, kalıntı sınıfı sayılarının dengelenmesi problemine dönüşür. Polinom katsayılarını açmaya hiç gerek kalmaz.
Önce \(p\mid s\) olduğunu varsayalım ve \(s=p^a u\), \(a\ge 1\), \(p\nmid u\), yazalım. \(p\)'ye bölünmeyen bölenler tam olarak \(u\)'nun bölenleridir; dolayısıyla tüm sıfır dışı kalıntı sınıfları toplamda \(\tau(u)\) katkı alır. Ortak kalıntı sayısı \(C\) ise
$$\tau(u)=(p-1)C$$
olmalıdır. Sıfır kalıntı sınıfı ise ek sabit terimi ve en az bir \(p\) çarpanı içeren tüm bölenleri alır; bu nedenle sayısı \(1+a\tau(u)\) olur. Tüm \(c_r\) değerlerinin eşit olması
$$C=1+a\tau(u)=1+a(p-1)C$$
eşitliğini gerektirir; bu pozitif \(C\) için olanaksızdır. Demek ki geçerli hiçbir çözüm, minimal olsun ya da olmasın, \(p\)'ye bölünemez.
Artık \(p\nmid s\). \(s\)'nin her böleni modulo \(p\) sıfır dışıdır ve \(0\) kalıntı sınıfına katkı yapan tek şey \(g_s\)'deki ayrı sabit terimdir. Bu nedenle \(c_0=1\). Tüm \(c_r\)'ler eşit olacağına göre, her sıfır dışı sınıf da tam bir kez görünmelidir. Bölünebilirlik koşulu şu bijeksiyona denktir:
$$\{d:d\mid s\}\longrightarrow \mathbb{F}_p^\times,\qquad d\longmapsto d\bmod p.$$
Özellikle bölen sayısı
$$\tau(s)=p-1$$
olmalıdır.
Aranan tamsayıyı asal kuvvetlere ayıralım:
$$s=\prod_{j=1}^k q_j^{a_j},\qquad q_j\ne p,$$
ve bölen kutusu uzunluklarını \(\ell_j=a_j+1\) olarak tanımlayalım. \(\tau(s)=\prod_j(a_j+1)\) olduğundan uzunluklar
$$\prod_{j=1}^k \ell_j=p-1$$
eşitliğini sağlamalıdır. Bir \(q_j^{a_j}\) çarpanı, bölen kutusuna \(1,q_j,q_j^2,\ldots,q_j^{\ell_j-1}\) sonlu dizisini ekler. Modulo \(p\) bu dizilerin çarpımları çakışmasız olmalı ve sonunda tüm çevrimsel grup \(G\)'yi kaplamalıdır. Kod bu şartın kanonik altgrup zinciri biçimini kullanır: bazı adımlardan sonra kurulmuş kalıntılar, \(h\mid p-1\) boyutundaki tekil altgrup \(H\le G\)'dir.
Mevcut altgrubun boyutu \(h\) ise bölüm grubu \(G/H\)'nin mertebesi
$$Q={p-1\over h}$$
olur. Yeni bir asal kalıntı \(q\), \(\ell\mid Q\) uzunluğu ile ancak \(qH\) yan sınıfının \(G/H\) içinde mertebesi \(\ell\) ise kullanılabilir. Bu durumda
$$H,\;qH,\;q^2H,\;\ldots,\;q^{\ell-1}H$$
yan sınıfları birbirinden farklıdır ve eski altgrubu \(1,q,\ldots,q^{\ell-1}\) ile çarpmak \(h\ell\) boyutundaki tekil altgrubu verir. Bölen kaplamasının istediği çakışmasızlık tam olarak budur.
Bir ilkel kök \(g\) kullanarak \(q\equiv g^e\pmod p\) yazalım. Mertebesi \(Q\) olan bölümde \(qH\)'nin mertebesi
$$\operatorname{ord}_{G/H}(qH)={Q\over \gcd(e,Q)}$$
olur. Bu yüzden solver'ın kullandığı geçiş koşulu
$$\operatorname{ord}_{G/H}(qH)=\ell \quad\Longleftrightarrow\quad \gcd(e,Q)={Q\over \ell}$$
şeklindedir.
\(s\)'nin tamsayı olarak en küçük olması gerekir. Bir geçiş \(\ell\) uzunluğuyla \(q\) asalını kullanıyorsa, \(s\)'ye \(q^{\ell-1}\) çarpanı ekler. Kod logaritmaları minimize eder; bu yüzden geçiş maliyeti
$$w(\ell,q)=(\ell-1)\log_{10}q$$
olur. Sabit bir \(h\) durumu ve sabit bir \(\ell\) uzunluğu için gelecek durum yalnızca \(h\ell\)'dir; \(h\)'ye hangi yoldan ulaşıldığı önemli değildir. Çünkü \(G\) çevrimseldir ve her \(h\mid p-1\) boyutu için tek bir altgrup vardır. Dolayısıyla bu geçiş için en iyi asal, ayrık-log koşulunu sağlayan \(q\ne p\) en küçük asal sayıdır.
Dinamik programlama \(D(h)\) değerini tutar: \(h\) boyutundaki altgrubu kuran kısmi tamsayının bilinen en küçük \(\log_{10}\) değeri. Başlangıç
$$D(1)=0$$
olur ve \(Q=(p-1)/h\)'nin her \(\ell\gt 1\) böleni için
$$D(h\ell)=\min\left(D(h\ell),\;D(h)+(\ell-1)\log_{10}q\right)$$
gevşetmesi yapılır. Burada \(q\), \(\gcd(\log_g q,Q)=Q/\ell\) koşulunu sağlayan en küçük geçiş asalıdır. Bir asal \(p\) için cevap \(D(p-1)=\log_{10}S(p)\)'dir. Ebeveyn işaretçileri seçilen \((\ell,q)\) çiftlerini saklar ve küçük kontrollerin tam olarak yeniden kurulmasını sağlar.
Kök koşulu leması, polinom bölünebilirliğinin eşit kalıntı sayılarıyla aynı şey olduğunu gösterir. Bölen kaplama leması ise her çözümün \(p\nmid s\) sağlaması gerektiğini ve bölenlerin \(G\)'nin elemanlarını tam birer kez vurması gerektiğini kanıtlar. Böylece asıl problem, bölen kutusu \(G\)'nin çakışmasız bir çarpım ayrışımı olan en küçük tamsayıyı bulma problemine eşdeğerdir.
Her DP geçişi geçerlidir, çünkü bölüm mertebesi koşulu yeni kuvvetleri \(1,q,\ldots,q^{\ell-1}\), mevcut altgrubun üzerinde \(\ell\) ayrı yan sınıf temsilcisine dönüştürür. Eski altgrupta \(h\) eleman vardır; genişletilmiş çarpımda \(h\ell\) farklı kalıntı olur ve bu küme tam olarak o boyuttaki altgruptur. Tümevarımla, \(1\)'den \(p-1\)'e giden her DP yolu geçerli bir bölen kaplaması ve dolayısıyla geçerli bir \(s\) üretir.
Ters yönde, burada kullanılan çevrimsel grup ortamında kesin bir bölen-kutusu kaplaması bölüm tamamlayıcılarının dizisi olarak okunabilir: her adımda, daha önce kurulmuş altgrup üzerinde farklı yan sınıflara düşen bir bölen-kutusu yönü seçilir. Çevrimsel grupta her bölen boyutunda yalnızca bir altgrup bulunduğundan, \(h\) durumu altgrubun kimliğine dair bilgi kaybetmez. Böylece DP gerekli kanonik geçişleri kapsar ve minimum \(S(p)\)'yi verir.
\(p=2\) için \(f_2(x)=1+x\) ve \(g_1(x)=1+x\), dolayısıyla \(S(2)=1\). Bu, \(G=\mathbb{F}_2^\times\) grubunun mertebesi \(1\) olan dejenere durumudur; DP başladığı durumda biter.
\(p=5\) için \(G\)'nin mertebesi \(4\)'tür. En küçük ilkel kalıntı \(2\)'dir. \(\ell=4\) olan tek geçiş
$$S(5)=2^{4-1}=8$$
değerini verir; bu problem metnindeki örnekle aynıdır. Bölenler \(1,2,4,8\) modulo \(5\)'te \(1,2,4,3\) olur ve sıfır dışı tüm kalıntıları tam birer kez verir.
\(p=7\) için optimal zincir \((\ell,q)=(3,2)\) ve ardından \((2,3)\) olarak yazılabilir. Ortaya çıkan tamsayı
$$S(7)=2^{3-1}3^{2-1}=12$$
olur. \(1,2,4,3,6,12\) bölenleri modulo \(7\)'de \(1,2,4,3,6,5\) kalıntılarına gider; bu da \(\mathbb{F}_7^\times\)'in tam kaplamasıdır. Tam uygulama bu yerel örnekleri ve ayrıca \(T(20)=1348422598656\), \(T(100)=1.37451\mathrm{e}123\) ürün kontrollerini doğrular.
C++, Python ve Java sürümleri aynı hattı izler. Önce \(2\,000\,000\)'a kadar asal eleği kurulur; sonra \(p-1\) çarpanlara ayrılır, \(p-1\)'in tüm bölenleri listelenir, modulo \(p\) ilkel kök bulunur ve her sıfır dışı kalıntıyı bu köke göre üssüne eşleyen ayrık logaritma tablosu oluşturulur.
Geçiş asalını arayan fonksiyon önceden hesaplanmış asal listesini tarar ve \(q=p\) durumunu reddeder. Elek aralığında uygun asal bulunmazsa, uygulama eleğin ötesinde deneme yoluyla asallık testi yapmaya devam eder. Pratikte bu sınır \(p\lt 20000\) örnekleri için geniştir; fakat yedek yol, mantığın tahmin edilmiş bir kesme noktasına bağlı kalmamasını sağlar.
Büyük ürünlerin tamamı logaritmik olarak ele alınır. Tam çarpma yalnızca yeniden kurulan küçük \(S(p)\) değerleri ve \(T(20)\) için tutulur. Bu ayrım önemlidir: son \(T(20000)\) yüz binlerce ondalık basamağa sahipken, bilimsel gösterim için toplanmış onluk logaritmanın kesirli kısmı ve tam kısmı yeterlidir.
Tek bir asal \(p\) için DP durum sayısı \(\tau(p-1)\), yani \(p-1\)'in bölen sayısıdır. Her durum \(\ell\mid (p-1)/h\) uzunluklarını dener; her geçiş de istenen bölüm mertebesine sahip kalıntıyı bulana kadar asal sayıları tarar. Ayrık logaritma tablosu \(O(p)\) bellek kullanır ve o asal çözüldükten sonra atılır.
\(20000\)'in altında yalnızca \(2262\) asal vardır. Dolayısıyla algoritma zamanını \(p-1\)'in küçük bölen kafesleri üzerinde harcar; polinom katsayılarıyla ya da dev bir aday tamsayının bölenleriyle çalışmaz. Long double logaritmaları yeterlidir, çünkü çıktı beş ondalık basamağa yuvarlanan bir mantis ister; küçük kesin kontrol değerleri ise indirgeme hatalarını yakalar.
El problema 995 parece al principio una pregunta sobre divisibilidad de dos polinomios dispersos, pero el objeto útil no es una expansión polinómica. Para un primo \(p\), \(f_p(x)=1+x+\cdots+x^{p-1}\) es el polinomio ciclotómico \(\Phi_p(x)\). Por tanto, la divisibilidad por \(f_p\) puede comprobarse en una raíz primitiva \(p\)-ésima de la unidad. Así, el problema se transforma en una cuestión sobre la distribución de los divisores de un entero \(s\) entre las clases de residuos módulo \(p\).
La reducción principal es que \(f_p(x)\mid g_s(x)\) se cumple exactamente cuando los divisores positivos de \(s\) forman un recubrimiento perfecto de \(\mathbb{F}_p^\times\) por residuos. En consecuencia, \(p\nmid s\), \(\tau(s)=p-1\), y cada clase no nula módulo \(p\) debe ser alcanzada exactamente una vez por un divisor de \(s\). La implementación busca ese \(s\) mínimo no enumerando enteros candidatos, sino construyendo una cadena de subgrupos dentro del grupo cíclico \(\mathbb{F}_p^\times\).
El producto final \(T(20000)\) es demasiado grande para guardarse como entero. El programa calcula cada \(\log_{10}S(p)\), suma esos logaritmos sobre todos los primos \(p\lt 20000\), y finalmente formatea mantisa y exponente. La reconstrucción exacta con enteros solo se usa para verificaciones pequeñas como \(S(5)=8\), \(T(20)=1348422598656\), y el punto de control dado para \(T(100)\).
Para un primo \(p\) y un entero positivo \(n\), el problema define
$$f_p(x)=\sum_{i=0}^{p-1}x^i,\qquad g_n(x)=1+\sum_{d\mid n}x^d.$$
El término \(1\) en \(g_n\) es esencial: es un término constante adicional cuyo exponente es \(0\). Los divisores \(d\mid n\) son divisores positivos y aportan exponentes \(d\). Buscamos el menor entero positivo \(s\) tal que \(f_p(x)\mid g_s(x)\), denotado por \(S(p)\).
En el análisis, \(G=\mathbb{F}_p^\times\) denota el grupo multiplicativo de los residuos no nulos módulo \(p\). Este grupo es cíclico y tiene orden \(p-1\). Si \(g\) es una raíz primitiva módulo \(p\), todo residuo no nulo se escribe de manera única como \(g^e\), \(0\le e\lt p-1\); el exponente \(e\) es el logaritmo discreto usado por el código.
Sea \(\zeta\ne 1\) una raíz primitiva \(p\)-ésima de la unidad. Como \(p\) es primo,
$$f_p(x)=1+x+\cdots+x^{p-1}=\Phi_p(x),$$
y \(\Phi_p(x)\) es el polinomio mínimo de \(\zeta\) sobre \(\mathbb{Q}\). Por tanto, \(f_p(x)\mid g_s(x)\) si y solo si \(g_s(\zeta)=0\).
Agrupemos los exponentes de \(g_s\) por sus clases de residuos módulo \(p\). Sea \(c_r\) el número de términos de \(g_s\) cuyo exponente es congruente con \(r\pmod p\). Entonces
$$g_s(\zeta)=\sum_{r=0}^{p-1}c_r\zeta^r.$$
Las potencias \(1,\zeta,\ldots,\zeta^{p-1}\) satisfacen una sola relación lineal racional, \(1+\zeta+\cdots+\zeta^{p-1}=0\), y toda relación racional es múltiplo de ella. Por ello \(g_s(\zeta)=0\) equivale a
$$c_0=c_1=\cdots=c_{p-1}.$$
La divisibilidad polinómica queda convertida en una condición de balance de conteos por clases de residuos. No hace falta expandir los coeficientes de los polinomios.
Supongamos primero que \(p\mid s\), y escribamos \(s=p^a u\), con \(a\ge 1\) y \(p\nmid u\). Los divisores no divisibles por \(p\) son exactamente los divisores de \(u\), de modo que las clases no nulas reciben en total \(\tau(u)\) contribuciones. Si el conteo común por clase es \(C\), entonces
$$\tau(u)=(p-1)C.$$
La clase cero recibe el término constante adicional y todo divisor que contiene al menos un factor \(p\), por lo que su conteo es \(1+a\tau(u)\). La igualdad de todos los \(c_r\) exigiría
$$C=1+a\tau(u)=1+a(p-1)C,$$
lo cual es imposible para \(C\) positivo. Por tanto, ninguna solución válida, mínima o no, puede ser divisible por \(p\).
Ahora \(p\nmid s\). Todo divisor de \(s\) es no nulo módulo \(p\), y la única contribución a la clase \(0\) es el término constante separado de \(g_s\). Así \(c_0=1\). Como todos los \(c_r\) deben ser iguales, cada clase no nula debe aparecer exactamente una vez. La condición de divisibilidad es equivalente a la biyección
$$\{d:d\mid s\}\longrightarrow \mathbb{F}_p^\times,\qquad d\longmapsto d\bmod p.$$
En particular, el número de divisores debe ser
$$\tau(s)=p-1.$$
Escribimos el entero desconocido como
$$s=\prod_{j=1}^k q_j^{a_j},\qquad q_j\ne p,$$
y definimos las longitudes de la caja de divisores por \(\ell_j=a_j+1\). Como \(\tau(s)=\prod_j(a_j+1)\), las longitudes deben satisfacer
$$\prod_{j=1}^k \ell_j=p-1.$$
Escoger un factor \(q_j^{a_j}\) añade a la caja de divisores la progresión finita \(1,q_j,q_j^2,\ldots,q_j^{\ell_j-1}\). Módulo \(p\), estas progresiones deben multiplicarse sin colisiones y finalmente cubrir todo el grupo cíclico \(G\). La implementación usa la forma canónica de cadena de subgrupos: después de algunos pasos, los residuos ya construidos son el subgrupo único \(H\le G\) de tamaño \(h\mid p-1\).
Si el subgrupo actual tiene tamaño \(h\), el grupo cociente \(G/H\) tiene orden
$$Q={p-1\over h}.$$
Un nuevo residuo primo \(q\) puede usarse con longitud \(\ell\mid Q\) exactamente cuando la clase lateral \(qH\) tiene orden \(\ell\) en \(G/H\). Entonces las clases
$$H,\;qH,\;q^2H,\;\ldots,\;q^{\ell-1}H$$
son distintas, y multiplicar el subgrupo antiguo por \(1,q,\ldots,q^{\ell-1}\) produce el subgrupo único de tamaño \(h\ell\). Esa es precisamente la condición sin colisiones requerida por el recubrimiento de divisores.
Usando una raíz primitiva \(g\), escribimos \(q\equiv g^e\pmod p\). En el cociente de orden \(Q\), el orden de \(qH\) es
$$\operatorname{ord}_{G/H}(qH)={Q\over \gcd(e,Q)}.$$
Por tanto, la condición de transición usada por el solver es
$$\operatorname{ord}_{G/H}(qH)=\ell \quad\Longleftrightarrow\quad \gcd(e,Q)={Q\over \ell}.$$
El valor de \(s\) debe ser mínimo como entero. Si una transición usa un primo \(q\) con longitud \(\ell\), aporta el factor \(q^{\ell-1}\) a \(s\). El código minimiza logaritmos, de modo que el peso de la transición es
$$w(\ell,q)=(\ell-1)\log_{10}q.$$
Para un estado fijo \(h\) y una longitud fija \(\ell\), el estado futuro depende solo de \(h\ell\), no del camino usado para alcanzar \(h\). Como \(G\) es cíclico, existe un único subgrupo de cada tamaño \(h\mid p-1\). Así, el mejor primo para esa transición es simplemente el menor primo \(q\ne p\) que satisface la condición de logaritmo discreto anterior.
La programación dinámica almacena \(D(h)\), el menor valor conocido de \(\log_{10}\) del entero parcial que construye el subgrupo de tamaño \(h\). Comienza con
$$D(1)=0,$$
y para cada divisor \(\ell\gt 1\) de \(Q=(p-1)/h\) relaja
$$D(h\ell)=\min\left(D(h\ell),\;D(h)+(\ell-1)\log_{10}q\right),$$
donde \(q\) es el menor primo de transición con \(\gcd(\log_g q,Q)=Q/\ell\). La respuesta para un primo es \(D(p-1)=\log_{10}S(p)\). Los punteros de padres registran los pares \((\ell,q)\), lo que permite reconstruir valores pequeños exactos para verificación.
El lema de la raíz prueba que la divisibilidad polinómica equivale a conteos iguales de residuos. El lema de recubrimiento prueba después que toda solución debe cumplir \(p\nmid s\) y que sus divisores deben alcanzar los elementos de \(G\) exactamente una vez. Por tanto, resolver el problema original equivale a hallar el menor entero cuya caja de divisores sea una descomposición producto sin colisiones de \(G\).
Cada transición de la DP es válida porque la condición de orden en el cociente hace que las nuevas potencias \(1,q,\ldots,q^{\ell-1}\) representen \(\ell\) clases laterales distintas del subgrupo actual. El subgrupo antiguo tiene \(h\) elementos; el producto ampliado tiene \(h\ell\) residuos distintos y es exactamente el subgrupo de ese tamaño. Por inducción, todo camino de la DP desde \(1\) hasta \(p-1\) construye un recubrimiento válido de divisores y por tanto un entero \(s\) válido.
En sentido inverso, en el contexto cíclico usado aquí, un recubrimiento exacto por una caja de divisores puede leerse como una secuencia de complementos en cocientes: en cada etapa se escoge una dirección de la caja cuyas imágenes son clases laterales distintas sobre el subgrupo ya construido. Como el grupo cíclico tiene un solo subgrupo de cada tamaño divisor, el estado \(h\) no pierde información sobre la identidad del subgrupo. La DP considera así las transiciones canónicas necesarias, y su mínimo produce \(S(p)\).
Para \(p=2\), \(f_2(x)=1+x\), y \(g_1(x)=1+x\), por lo que \(S(2)=1\). Es el caso degenerado \(G=\mathbb{F}_2^\times\), cuyo orden es \(1\); la DP empieza y termina en el mismo estado.
Para \(p=5\), \(G\) tiene orden \(4\). El menor residuo primitivo es \(2\). Una sola transición con \(\ell=4\) da
$$S(5)=2^{4-1}=8,$$
tal como indica el enunciado. Sus divisores \(1,2,4,8\) se reducen módulo \(5\) a \(1,2,4,3\), todos los residuos no nulos exactamente una vez.
Para \(p=7\), una cadena óptima puede escribirse como \((\ell,q)=(3,2)\) seguida de \((2,3)\). El entero resultante es
$$S(7)=2^{3-1}3^{2-1}=12.$$
Los divisores \(1,2,4,3,6,12\) se reducen módulo \(7\) a \(1,2,4,3,6,5\), otra vez un recubrimiento completo de \(\mathbb{F}_7^\times\). La implementación completa comprueba estos ejemplos locales y también los controles de producto \(T(20)=1348422598656\) y \(T(100)=1.37451\mathrm{e}123\).
Las versiones C++, Python y Java siguen la misma tubería. Criban primos hasta \(2\,000\,000\), factorizan \(p-1\), enumeran todos los divisores de \(p-1\), encuentran una raíz primitiva módulo \(p\), y construyen una tabla de logaritmos discretos que asigna a cada residuo no nulo su exponente respecto de esa raíz.
La función que busca un primo de transición recorre la lista de primos precalculada y rechaza \(q=p\). Si no aparece un primo adecuado dentro del rango cribado, la implementación continúa con pruebas de primalidad por ensayo más allá del cribado. En la práctica el límite es generoso para los casos \(p\lt 20000\), pero la ruta de respaldo mantiene completa la lógica y no la ata a un corte supuesto.
Todos los productos grandes se manejan con logaritmos. La multiplicación exacta se conserva solo para valores pequeños reconstruidos de \(S(p)\) y para \(T(20)\). Esta separación es importante: el \(T(20000)\) final tiene cientos de miles de dígitos decimales, mientras que su notación científica solo necesita la parte fraccionaria y la parte entera del logaritmo decimal acumulado.
Para un primo \(p\), el número de estados de la DP es \(\tau(p-1)\), el número de divisores de \(p-1\). Cada estado prueba longitudes \(\ell\mid (p-1)/h\), y cada transición escanea primos hasta encontrar un residuo con el orden requerido en el cociente. La tabla de logaritmos discretos usa \(O(p)\) memoria y se descarta al terminar ese primo.
Hay solo \(2262\) primos por debajo de \(20000\). El algoritmo trabaja por tanto sobre pequeños retículos de divisores de \(p-1\), no sobre coeficientes polinómicos ni sobre divisores de un entero candidato gigantesco. Los logaritmos en long double bastan porque la salida requiere una mantisa redondeada a cinco decimales; los controles exactos pequeños protegen contra errores estructurales en la reducción.
问题 995 表面上是两个稀疏多项式的整除问题，但真正有用的对象并不是展开后的多项式。对素数 \(p\)，\(f_p(x)=1+x+\cdots+x^{p-1}\) 正是分圆多项式 \(\Phi_p(x)\)。因此，是否被 \(f_p\) 整除可以在一个本原 \(p\) 次单位根处检验。这样，问题就转化为：整数 \(s\) 的因子集合在模 \(p\) 的剩余类中如何分布。
核心化简是：\(f_p(x)\mid g_s(x)\) 当且仅当 \(s\) 的正因子按模 \(p\) 的剩余恰好完美铺满 \(\mathbb{F}_p^\times\)。于是必有 \(p\nmid s\)，\(\tau(s)=p-1\)，并且每个模 \(p\) 的非零剩余类必须被 \(s\) 的一个因子恰好击中一次。实现中并不枚举候选整数，而是在循环群 \(\mathbb{F}_p^\times\) 内构造子群链来寻找最小的 \(s\)。
最终乘积 \(T(20000)\) 大到无法作为整数保存。程序对每个 \(p\) 计算 \(\log_{10}S(p)\)，把所有 \(p\lt 20000\) 的素数对应的对数相加，最后格式化尾数和指数。精确整数重构只用于小型校验，例如 \(S(5)=8\)、\(T(20)=1348422598656\)，以及题目给出的 \(T(100)\) 校验值。
对素数 \(p\) 和正整数 \(n\)，题目定义
$$f_p(x)=\sum_{i=0}^{p-1}x^i,\qquad g_n(x)=1+\sum_{d\mid n}x^d.$$
\(g_n\) 中的 \(1\) 很重要：它是额外的常数项，其指数为 \(0\)。符号 \(d\mid n\) 表示正因子，并贡献指数 \(d\)。我们要求最小的正整数 \(s\)，使得 \(f_p(x)\mid g_s(x)\)；这个值记为 \(S(p)\)。
下文中，\(G=\mathbb{F}_p^\times\) 表示模 \(p\) 非零剩余构成的乘法群。这个群是循环群，阶为 \(p-1\)。若 \(g\) 是模 \(p\) 的本原根，则每个非零剩余都能唯一写成 \(g^e\)，其中 \(0\le e\lt p-1\)；指数 \(e\) 就是代码中使用的离散对数。
令 \(\zeta\ne 1\) 为本原 \(p\) 次单位根。因为 \(p\) 是素数，
$$f_p(x)=1+x+\cdots+x^{p-1}=\Phi_p(x),$$
而 \(\Phi_p(x)\) 是 \(\zeta\) 在 \(\mathbb{Q}\) 上的最小多项式。因此 \(f_p(x)\mid g_s(x)\) 当且仅当 \(g_s(\zeta)=0\)。
把 \(g_s\) 的指数按模 \(p\) 的剩余类分组。令 \(c_r\) 表示指数同余于 \(r\pmod p\) 的项数，则
$$g_s(\zeta)=\sum_{r=0}^{p-1}c_r\zeta^r.$$
幂 \(1,\zeta,\ldots,\zeta^{p-1}\) 之间只有一个有理线性关系，即 \(1+\zeta+\cdots+\zeta^{p-1}=0\)，并且所有有理关系都是它的倍数。因此 \(g_s(\zeta)=0\) 等价于
$$c_0=c_1=\cdots=c_{p-1}.$$
于是，多项式整除问题变成了剩余类计数的平衡条件。算法完全不需要展开多项式系数。
先假设 \(p\mid s\)，写成 \(s=p^a u\)，其中 \(a\ge 1\) 且 \(p\nmid u\)。不被 \(p\) 整除的因子正好是 \(u\) 的因子，所以所有非零剩余类合计收到 \(\tau(u)\) 个贡献。若公共计数为 \(C\)，则
$$\tau(u)=(p-1)C.$$
零剩余类还会收到额外常数项，以及所有至少含有一个因子 \(p\) 的因子，所以它的计数是 \(1+a\tau(u)\)。所有 \(c_r\) 相等将要求
$$C=1+a\tau(u)=1+a(p-1)C,$$
这对正的 \(C\) 不可能成立。因此任何有效解，无论是否最小，都不能满足 \(p\mid s\)。
现在 \(p\nmid s\)。\(s\) 的每个因子模 \(p\) 都非零，而剩余类 \(0\) 只收到 \(g_s\) 中独立的常数项贡献。因此 \(c_0=1\)。既然所有 \(c_r\) 必须相等，每个非零类也必须恰好出现一次。整除条件等价于双射
$$\{d:d\mid s\}\longrightarrow \mathbb{F}_p^\times,\qquad d\longmapsto d\bmod p.$$
特别地，因子个数必须为
$$\tau(s)=p-1.$$
把未知整数写成素数幂形式
$$s=\prod_{j=1}^k q_j^{a_j},\qquad q_j\ne p,$$
并定义因子盒的长度 \(\ell_j=a_j+1\)。由于 \(\tau(s)=\prod_j(a_j+1)\)，这些长度必须满足
$$\prod_{j=1}^k \ell_j=p-1.$$
选择一个因子 \(q_j^{a_j}\)，等于向因子盒加入有限等比段 \(1,q_j,q_j^2,\ldots,q_j^{\ell_j-1}\)。模 \(p\) 后，这些段的乘积应当无碰撞，并最终覆盖整个循环群 \(G\)。实现采用这种条件的标准子群链形式：若干步之后，已经构造出的剩余构成大小为 \(h\mid p-1\) 的唯一子群 \(H\le G\)。
若当前子群大小为 \(h\)，则商群 \(G/H\) 的阶为
$$Q={p-1\over h}.$$
新的素数剩余 \(q\) 可以以长度 \(\ell\mid Q\) 使用，当且仅当陪集 \(qH\) 在 \(G/H\) 中的阶为 \(\ell\)。此时
$$H,\;qH,\;q^2H,\;\ldots,\;q^{\ell-1}H$$
互不相同，用 \(1,q,\ldots,q^{\ell-1}\) 乘旧子群就得到大小为 \(h\ell\) 的唯一子群。这正是因子铺满所需的无碰撞条件。
取本原根 \(g\)，写 \(q\equiv g^e\pmod p\)。在阶为 \(Q\) 的商群中，\(qH\) 的阶是
$$\operatorname{ord}_{G/H}(qH)={Q\over \gcd(e,Q)}.$$
因此求解器使用的转移条件为
$$\operatorname{ord}_{G/H}(qH)=\ell \quad\Longleftrightarrow\quad \gcd(e,Q)={Q\over \ell}.$$
\(s\) 需要作为整数最小。若一个转移用素数 \(q\) 和长度 \(\ell\)，它给 \(s\) 贡献因子 \(q^{\ell-1}\)。代码最小化对数，所以转移权重为
$$w(\ell,q)=(\ell-1)\log_{10}q.$$
对固定状态 \(h\) 和固定长度 \(\ell\)，后继状态只依赖于 \(h\ell\)，不依赖于到达 \(h\) 的路径。因为 \(G\) 是循环群，每个大小 \(h\mid p-1\) 的子群唯一。因此该转移的最佳素数就是满足上述离散对数条件的最小素数 \(q\ne p\)。
动态规划保存 \(D(h)\)，即构造大小为 \(h\) 的子群所需的部分整数的最小已知 \(\log_{10}\) 值。初始为
$$D(1)=0,$$
对 \(Q=(p-1)/h\) 的每个 \(\ell\gt 1\) 因子，进行松弛
$$D(h\ell)=\min\left(D(h\ell),\;D(h)+(\ell-1)\log_{10}q\right),$$
其中 \(q\) 是满足 \(\gcd(\log_g q,Q)=Q/\ell\) 的最小转移素数。单个素数的答案是 \(D(p-1)=\log_{10}S(p)\)。父指针记录所选的 \((\ell,q)\) 对，从而可以为小规模校验重构精确值。
根条件引理证明，多项式整除等价于剩余计数相等。因子铺满引理进一步证明，任何解都必须满足 \(p\nmid s\)，并且它的因子必须恰好一次击中 \(G\) 的每个元素。因此原问题等价于寻找最小整数，使它的因子盒成为 \(G\) 的无碰撞乘积分解。
每个 DP 转移都是有效的，因为商群阶条件保证新幂 \(1,q,\ldots,q^{\ell-1}\) 表示当前子群上的 \(\ell\) 个不同陪集。旧子群有 \(h\) 个元素，因此扩大的乘积有 \(h\ell\) 个不同剩余，并且正是该大小的子群。由归纳可知，从 \(1\) 到 \(p-1\) 的每条 DP 路径都构造出有效的因子铺满，因而给出有效整数 \(s\)。
反过来，在这里的循环群情形中，一个精确的因子盒铺满可以被读成一系列商群补集：每一步选择一个因子盒方向，使其像在已经构造的子群上形成不同陪集。由于循环群对每个因子大小只有一个子群，状态 \(h\) 不会丢失子群身份信息。因此 DP 覆盖所需的标准转移，取最小值即得到 \(S(p)\)。
当 \(p=2\) 时，\(f_2(x)=1+x\)，且 \(g_1(x)=1+x\)，所以 \(S(2)=1\)。这是 \(G=\mathbb{F}_2^\times\) 的退化情形，其阶为 \(1\)；DP 从同一个状态开始并结束。
当 \(p=5\) 时，\(G\) 的阶为 \(4\)。最小本原剩余是 \(2\)。一个 \(\ell=4\) 的单步转移给出
$$S(5)=2^{4-1}=8,$$
与题目示例一致。它的因子 \(1,2,4,8\) 模 \(5\) 后为 \(1,2,4,3\)，恰好是所有非零剩余。
当 \(p=7\) 时，一条最优链可写成 \((\ell,q)=(3,2)\)，再接 \((2,3)\)。得到的整数为
$$S(7)=2^{3-1}3^{2-1}=12.$$
因子 \(1,2,4,3,6,12\) 模 \(7\) 后为 \(1,2,4,3,6,5\)，再次完整铺满 \(\mathbb{F}_7^\times\)。完整实现检查这些局部例子，并验证 \(T(20)=1348422598656\) 与 \(T(100)=1.37451\mathrm{e}123\) 两个乘积校验。
C++、Python 与 Java 版本遵循同一流程。它们先筛出 \(2\,000\,000\) 以内的素数，分解 \(p-1\)，枚举 \(p-1\) 的所有因子，寻找模 \(p\) 的本原根，并建立离散对数表，把每个非零剩余映射到相对于该本原根的指数。
寻找转移素数的函数扫描预先计算的素数列表，并排除 \(q=p\)。如果筛选范围内没有合适素数，实现会继续在筛外用试除法检测素数。对 \(p\lt 20000\) 的实例而言这个界限已经很宽松，但后备路径让逻辑完整，而不是依赖一个猜测的截断值。
所有大乘积都用对数处理。精确乘法只保留给重构的小 \(S(p)\) 值和 \(T(20)\)。这种分离很重要：最终的 \(T(20000)\) 有数十万个十进制数字，而科学记数法只需要累积十进制对数的整数部分和小数部分。
对单个素数 \(p\)，DP 状态数是 \(\tau(p-1)\)，即 \(p-1\) 的因子数。每个状态测试 \(\ell\mid (p-1)/h\) 的长度，每个转移扫描素数直到找到具有所需商群阶的剩余。离散对数表使用 \(O(p)\) 内存，并在该素数求解完后丢弃。
\(20000\) 以下只有 \(2262\) 个素数。因此算法的工作集中在 \(p-1\) 的小因子格上，而不是多项式系数，也不是巨型候选整数的因子。Long double 对数足够，因为输出只要求尾数四舍五入到小数点后五位；精确的小校验则用于捕获结构性化简错误。
Задача 995 сначала выглядит как вопрос о делимости двух разреженных многочленов, но полезный объект здесь не развернутый многочлен. Для простого \(p\) многочлен \(f_p(x)=1+x+\cdots+x^{p-1}\) является циклотомическим многочленом \(\Phi_p(x)\). Поэтому делимость на \(f_p\) можно проверять в примитивном корне единицы степени \(p\). Так задача превращается в вопрос о том, как множество делителей числа \(s\) распределено по классам вычетов modulo \(p\).
Главное сведение таково: \(f_p(x)\mid g_s(x)\) выполняется тогда и только тогда, когда положительные делители \(s\) образуют совершенное покрытие \(\mathbb{F}_p^\times\) вычетами. Следовательно, \(p\nmid s\), \(\tau(s)=p-1\), и каждый ненулевой класс вычетов modulo \(p\) должен быть достигнут ровно одним делителем \(s\). Реализация ищет минимальное такое \(s\) не перебором кандидатов, а построением цепочки подгрупп в циклической группе \(\mathbb{F}_p^\times\).
Итоговое произведение \(T(20000)\) слишком велико, чтобы хранить его как целое число. Программа вычисляет каждое \(\log_{10}S(p)\), суммирует эти логарифмы по всем простым \(p\lt 20000\), а затем форматирует мантиссу и показатель. Точная целочисленная реконструкция используется только для малых проверок, таких как \(S(5)=8\), \(T(20)=1348422598656\), и заданный контроль для \(T(100)\).
Для простого \(p\) и положительного целого \(n\) задача задает
$$f_p(x)=\sum_{i=0}^{p-1}x^i,\qquad g_n(x)=1+\sum_{d\mid n}x^d.$$
Член \(1\) в \(g_n\) существенен: это дополнительный постоянный член с показателем \(0\). Делители \(d\mid n\) являются положительными делителями и дают показатели \(d\). Нужно найти наименьшее положительное целое \(s\), для которого \(f_p(x)\mid g_s(x)\); это значение обозначается \(S(p)\).
В анализе \(G=\mathbb{F}_p^\times\) обозначает мультипликативную группу ненулевых вычетов modulo \(p\). Эта группа циклическая и имеет порядок \(p-1\). Если \(g\) является первообразным корнем modulo \(p\), то каждый ненулевой вычет единственным образом записывается как \(g^e\), \(0\le e\lt p-1\); показатель \(e\) является дискретным логарифмом, который использует код.
Пусть \(\zeta\ne 1\) - примитивный корень единицы степени \(p\). Так как \(p\) простое,
$$f_p(x)=1+x+\cdots+x^{p-1}=\Phi_p(x),$$
а \(\Phi_p(x)\) является минимальным многочленом \(\zeta\) над \(\mathbb{Q}\). Поэтому \(f_p(x)\mid g_s(x)\) тогда и только тогда, когда \(g_s(\zeta)=0\).
Сгруппируем показатели в \(g_s\) по классам вычетов modulo \(p\). Пусть \(c_r\) - число членов \(g_s\), показатель которых сравним с \(r\pmod p\). Тогда
$$g_s(\zeta)=\sum_{r=0}^{p-1}c_r\zeta^r.$$
Степени \(1,\zeta,\ldots,\zeta^{p-1}\) удовлетворяют одной рациональной линейной связи, а именно \(1+\zeta+\cdots+\zeta^{p-1}=0\); все рациональные связи являются ее кратными. Поэтому \(g_s(\zeta)=0\) эквивалентно условию
$$c_0=c_1=\cdots=c_{p-1}.$$
Таким образом, делимость многочленов превращается в условие равновесия счетчиков по классам вычетов. Раскрывать коэффициенты многочленов не требуется.
Сначала предположим, что \(p\mid s\), и запишем \(s=p^a u\), где \(a\ge 1\) и \(p\nmid u\). Делители, не делящиеся на \(p\), - это ровно делители \(u\), поэтому все ненулевые классы вместе получают \(\tau(u)\) вкладов. Если общий счетчик класса равен \(C\), то
$$\tau(u)=(p-1)C.$$
Нулевой класс получает дополнительный постоянный член и каждый делитель, содержащий хотя бы один множитель \(p\), поэтому его счетчик равен \(1+a\tau(u)\). Равенство всех \(c_r\) потребовало бы
$$C=1+a\tau(u)=1+a(p-1)C,$$
что невозможно для положительного \(C\). Следовательно, ни одно допустимое решение, минимальное или нет, не может делиться на \(p\).
Теперь \(p\nmid s\). Каждый делитель \(s\) ненулевой modulo \(p\), а единственный вклад в класс \(0\) дает отдельный постоянный член в \(g_s\). Значит, \(c_0=1\). Поскольку все \(c_r\) должны быть равны, каждый ненулевой класс тоже обязан появиться ровно один раз. Условие делимости эквивалентно биекции
$$\{d:d\mid s\}\longrightarrow \mathbb{F}_p^\times,\qquad d\longmapsto d\bmod p.$$
В частности, число делителей должно быть
$$\tau(s)=p-1.$$
Запишем искомое целое в виде произведения степеней простых:
$$s=\prod_{j=1}^k q_j^{a_j},\qquad q_j\ne p,$$
и определим длины ящика делителей \(\ell_j=a_j+1\). Так как \(\tau(s)=\prod_j(a_j+1)\), эти длины должны удовлетворять
$$\prod_{j=1}^k \ell_j=p-1.$$
Выбор множителя \(q_j^{a_j}\) добавляет к ящику делителей конечную прогрессию \(1,q_j,q_j^2,\ldots,q_j^{\ell_j-1}\). Modulo \(p\) эти прогрессии должны перемножаться без столкновений и в итоге покрывать всю циклическую группу \(G\). Реализация использует каноническую форму цепочки подгрупп: после нескольких шагов уже построенные вычеты являются единственной подгруппой \(H\le G\) размера \(h\mid p-1\).
Если текущая подгруппа имеет размер \(h\), то факторгруппа \(G/H\) имеет порядок
$$Q={p-1\over h}.$$
Новый простой вычет \(q\) можно использовать с длиной \(\ell\mid Q\) ровно тогда, когда смежный класс \(qH\) имеет порядок \(\ell\) в \(G/H\). Тогда классы
$$H,\;qH,\;q^2H,\;\ldots,\;q^{\ell-1}H$$
различны, а умножение старой подгруппы на \(1,q,\ldots,q^{\ell-1}\) дает единственную подгруппу размера \(h\ell\). Именно это является условием отсутствия столкновений для покрытия делителями.
Используя первообразный корень \(g\), запишем \(q\equiv g^e\pmod p\). В факторгруппе порядка \(Q\) порядок \(qH\) равен
$$\operatorname{ord}_{G/H}(qH)={Q\over \gcd(e,Q)}.$$
Поэтому условие перехода, используемое решателем, имеет вид
$$\operatorname{ord}_{G/H}(qH)=\ell \quad\Longleftrightarrow\quad \gcd(e,Q)={Q\over \ell}.$$
Значение \(s\) должно быть минимальным как целое число. Если переход использует простое \(q\) с длиной \(\ell\), он добавляет к \(s\) множитель \(q^{\ell-1}\). Код минимизирует логарифмы, поэтому вес перехода равен
$$w(\ell,q)=(\ell-1)\log_{10}q.$$
Для фиксированного состояния \(h\) и фиксированной длины \(\ell\) следующее состояние зависит только от \(h\ell\), а не от пути, которым достигнуто \(h\). Поскольку \(G\) циклическая, существует единственная подгруппа каждого размера \(h\mid p-1\). Поэтому лучший простой для такого перехода - это наименьший простой \(q\ne p\), удовлетворяющий условию на дискретный логарифм.
Динамическая программа хранит \(D(h)\), наименьшее известное значение \(\log_{10}\) частичного целого, строящего подгруппу размера \(h\). Начальное значение
$$D(1)=0,$$
и для каждого делителя \(\ell\gt 1\) числа \(Q=(p-1)/h\) выполняется релаксация
$$D(h\ell)=\min\left(D(h\ell),\;D(h)+(\ell-1)\log_{10}q\right),$$
где \(q\) - наименьший переходный простой с \(\gcd(\log_g q,Q)=Q/\ell\). Ответ для одного простого равен \(D(p-1)=\log_{10}S(p)\). Родительские указатели записывают пары \((\ell,q)\), что позволяет точно реконструировать малые значения для проверки.
Лемма о корне доказывает, что делимость многочленов эквивалентна равенству счетчиков вычетов. Лемма о покрытии делителями затем доказывает, что любое решение должно удовлетворять \(p\nmid s\), а его делители должны ровно по одному разу попасть в элементы \(G\). Значит, исходная задача эквивалентна поиску наименьшего целого, чей ящик делителей является бесстолкновительным произведением, покрывающим \(G\).
Каждый переход DP корректен, потому что условие порядка в факторгруппе делает новые степени \(1,q,\ldots,q^{\ell-1}\) представителями \(\ell\) разных смежных классов над текущей подгруппой. Старая подгруппа имеет \(h\) элементов; расширенное произведение имеет \(h\ell\) различных вычетов и является именно подгруппой такого размера. По индукции каждый путь DP от \(1\) до \(p-1\) строит допустимое покрытие делителями и, следовательно, допустимое целое \(s\).
Обратно, в используемой здесь циклической группе точное покрытие ящиком делителей можно читать как последовательность дополнений в факторгруппах: на каждом шаге выбирается направление ящика, чьи образы являются различными смежными классами над уже построенной подгруппой. Поскольку в циклической группе есть только одна подгруппа каждого размера-делителя, состояние \(h\) не теряет сведений об идентичности подгруппы. Поэтому DP рассматривает необходимые канонические переходы, и минимум дает \(S(p)\).
Для \(p=2\) имеем \(f_2(x)=1+x\) и \(g_1(x)=1+x\), поэтому \(S(2)=1\). Это вырожденный случай \(G=\mathbb{F}_2^\times\), порядок которого равен \(1\); DP начинается и заканчивается в одном состоянии.
Для \(p=5\) группа \(G\) имеет порядок \(4\). Наименьший примитивный вычет равен \(2\). Один переход с \(\ell=4\) дает
$$S(5)=2^{4-1}=8,$$
что совпадает с примером в условии. Его делители \(1,2,4,8\) modulo \(5\) дают \(1,2,4,3\), то есть все ненулевые вычеты ровно по одному разу.
Для \(p=7\) оптимальную цепочку можно записать как \((\ell,q)=(3,2)\), затем \((2,3)\). Полученное целое равно
$$S(7)=2^{3-1}3^{2-1}=12.$$
Делители \(1,2,4,3,6,12\) modulo \(7\) дают \(1,2,4,3,6,5\), снова полное покрытие \(\mathbb{F}_7^\times\). Полная реализация проверяет эти локальные примеры, а также контрольные произведения \(T(20)=1348422598656\) и \(T(100)=1.37451\mathrm{e}123\).
Версии на C++, Python и Java следуют одной и той же схеме. Они строят решето простых до \(2\,000\,000\), факторизуют \(p-1\), перечисляют все делители \(p-1\), находят первообразный корень modulo \(p\), и строят таблицу дискретных логарифмов, сопоставляющую каждому ненулевому вычету показатель относительно этого корня.
Функция поиска переходного простого сканирует заранее вычисленный список простых и отвергает \(q=p\). Если подходящий простой не найден в пределах решета, реализация продолжает проверять простоту пробным делением за пределами решета. На практике граница щедра для \(p\lt 20000\), но резервный путь делает логику полной, а не зависящей от угаданного отсечения.
Все большие произведения обрабатываются логарифмически. Точное умножение сохраняется только для реконструированных малых значений \(S(p)\) и для \(T(20)\). Это разделение важно: итоговое \(T(20000)\) имеет сотни тысяч десятичных цифр, тогда как научная запись требует только дробную и целую части суммы десятичных логарифмов.
Для одного простого \(p\) число состояний DP равно \(\tau(p-1)\), то есть числу делителей \(p-1\). Каждое состояние проверяет длины \(\ell\mid (p-1)/h\), а каждый переход сканирует простые, пока не найдет вычет с требуемым порядком в факторгруппе. Таблица дискретных логарифмов требует \(O(p)\) памяти и отбрасывается после решения данного простого.
Ниже \(20000\) имеется только \(2262\) простых. Поэтому алгоритм работает с малыми решетками делителей \(p-1\), а не с коэффициентами многочленов и не с делителями гигантского кандидата. Логарифмов long double достаточно, потому что выход требует мантиссу, округленную до пяти знаков после десятичной точки; точные малые проверки защищают от структурных ошибок в сведении.
تبدو المسألة 995 في البداية مسألة قسمة بين كثيري حدود متناثرين، لكن الكائن المفيد ليس التوسيع الكامل لكثيرات الحدود. لكل عدد أولي \(p\)، يكون \(f_p(x)=1+x+\cdots+x^{p-1}\) هو كثير الحدود الدائري \(\Phi_p(x)\). لذلك يمكن اختبار القسمة على \(f_p\) عند جذر وحدة بدائي من الرتبة \(p\). بهذا تتحول المسألة إلى سؤال عن توزيع قواسم عدد صحيح \(s\) على فئات البواقي بترديد \(p\).
الاختزال الأساسي هو أن \(f_p(x)\mid g_s(x)\) يتحقق بالضبط عندما تشكل القواسم الموجبة للعدد \(s\) تبليطا كاملا للمجموعة \(\mathbb{F}_p^\times\) بواسطة البواقي. ومن ثم لا بد أن \(p\nmid s\)، وأن \(\tau(s)=p-1\)، وأن كل فئة غير صفرية بترديد \(p\) تصاب بقاسم واحد فقط من قواسم \(s\). لا تبحث الخوارزمية عن هذا \(s\) بتعداد الأعداد المرشحة، بل تبنيه عبر سلسلة زمر جزئية داخل الزمرة الدورية \(\mathbb{F}_p^\times\).
حاصل الضرب النهائي \(T(20000)\) كبير جدا بحيث لا يخزن كعدد صحيح. لذلك يحسب البرنامج \(\log_{10}S(p)\) لكل \(p\)، ثم يجمع هذه اللوغاريتمات لكل الأعداد الأولية \(p\lt 20000\)، ثم ينسق الجزء العشري والأس. أما إعادة البناء الصحيحة بعدد صحيح فتستخدم فقط في اختبارات صغيرة مثل \(S(5)=8\)، و \(T(20)=1348422598656\)، وقيمة التحقق المعطاة لـ \(T(100)\).
لعدد أولي \(p\) وعدد صحيح موجب \(n\)، تعرف المسألة
$$f_p(x)=\sum_{i=0}^{p-1}x^i,\qquad g_n(x)=1+\sum_{d\mid n}x^d.$$
الحد \(1\) في \(g_n\) مهم: إنه حد ثابت إضافي أسه \(0\). أما \(d\mid n\) فهي القواسم الموجبة وتضيف الأسس \(d\). نريد أصغر عدد صحيح موجب \(s\) يحقق \(f_p(x)\mid g_s(x)\)، ونرمز إليه بـ \(S(p)\).
في التحليل، نرمز بـ \(G=\mathbb{F}_p^\times\) إلى زمرة الضرب للبواقي غير الصفرية بترديد \(p\). هذه الزمرة دورية ورتبتها \(p-1\). إذا كان \(g\) جذرا بدائيا بترديد \(p\)، فإن كل باق غير صفري يكتب بشكل وحيد على صورة \(g^e\)، حيث \(0\le e\lt p-1\)؛ وهذا الأس \(e\) هو اللوغاريتم المتقطع الذي يستعمله الكود.
لتكن \(\zeta\ne 1\) جذرا بدائيا من جذور الوحدة من الرتبة \(p\). بما أن \(p\) أولي، فإن
$$f_p(x)=1+x+\cdots+x^{p-1}=\Phi_p(x),$$
و \(\Phi_p(x)\) هو كثير الحدود الأدنى لـ \(\zeta\) فوق \(\mathbb{Q}\). لذلك فإن \(f_p(x)\mid g_s(x)\) إذا وفقط إذا كان \(g_s(\zeta)=0\).
نقسم أسس \(g_s\) حسب فئاتها بترديد \(p\). ليكن \(c_r\) عدد حدود \(g_s\) التي أسها يساوي \(r\pmod p\). عندئذ
$$g_s(\zeta)=\sum_{r=0}^{p-1}c_r\zeta^r.$$
القوى \(1,\zeta,\ldots,\zeta^{p-1}\) تحقق علاقة خطية نسبية واحدة، وهي \(1+\zeta+\cdots+\zeta^{p-1}=0\)، وكل علاقة نسبية أخرى هي مضاعف لها. لذلك فإن \(g_s(\zeta)=0\) يكافئ
$$c_0=c_1=\cdots=c_{p-1}.$$
بهذا تصير قسمة كثيرات الحدود شرط توازن في أعداد فئات البواقي. لا حاجة إلى توسيع معاملات كثيرات الحدود.
نفترض أولا أن \(p\mid s\)، ونكتب \(s=p^a u\)، حيث \(a\ge 1\) و \(p\nmid u\). القواسم التي لا تقبل القسمة على \(p\) هي بالضبط قواسم \(u\)، ولذلك تستقبل كل الفئات غير الصفرية معا \(\tau(u)\) مساهمة. إذا كان العدد المشترك لكل فئة هو \(C\)، فإن
$$\tau(u)=(p-1)C.$$
الفئة الصفرية تستقبل الحد الثابت الإضافي وكل قاسم يحتوي على عامل \(p\) واحد على الأقل، ولذلك يكون عددها \(1+a\tau(u)\). مساواة كل \(c_r\) تفرض
$$C=1+a\tau(u)=1+a(p-1)C,$$
وهذا مستحيل عندما يكون \(C\) موجبا. إذن لا يمكن لأي حل صحيح، سواء كان أصغر حل أم لا، أن يكون قابلا للقسمة على \(p\).
الآن \(p\nmid s\). كل قاسم من قواسم \(s\) غير صفري بترديد \(p\)، والمساهمة الوحيدة في الفئة \(0\) هي الحد الثابت المنفصل في \(g_s\). لذلك \(c_0=1\). وبما أن كل \(c_r\) يجب أن تكون متساوية، فيجب أن تظهر كل فئة غير صفرية مرة واحدة بالضبط. شرط القسمة يكافئ التقابل
$$\{d:d\mid s\}\longrightarrow \mathbb{F}_p^\times,\qquad d\longmapsto d\bmod p.$$
وعلى وجه الخصوص يجب أن يكون عدد القواسم
$$\tau(s)=p-1.$$
نكتب العدد الصحيح المجهول بالشكل
$$s=\prod_{j=1}^k q_j^{a_j},\qquad q_j\ne p,$$
ونعرف أطوال صندوق القواسم بـ \(\ell_j=a_j+1\). بما أن \(\tau(s)=\prod_j(a_j+1)\)، فيجب أن تحقق الأطوال
$$\prod_{j=1}^k \ell_j=p-1.$$
اختيار عامل \(q_j^{a_j}\) يضيف إلى صندوق القواسم المتتالية المحدودة \(1,q_j,q_j^2,\ldots,q_j^{\ell_j-1}\). بترديد \(p\)، يجب أن تتضاعف هذه المتتاليات من دون تصادم وأن تغطي في النهاية الزمرة الدورية كلها \(G\). تستخدم الخوارزمية الصيغة القانونية كسلسلة زمر جزئية: بعد بعض الخطوات تكون البواقي المبنية هي الزمرة الجزئية الوحيدة \(H\le G\) ذات الحجم \(h\mid p-1\).
إذا كان حجم الزمرة الجزئية الحالية \(h\)، فإن زمرة القسمة \(G/H\) لها الرتبة
$$Q={p-1\over h}.$$
يمكن استعمال باق أولي جديد \(q\) بطول \(\ell\mid Q\) بالضبط عندما تكون الفئة \(qH\) ذات رتبة \(\ell\) في \(G/H\). حينئذ تكون الفئات
$$H,\;qH,\;q^2H,\;\ldots,\;q^{\ell-1}H$$
مختلفة، وضرب الزمرة القديمة في \(1,q,\ldots,q^{\ell-1}\) يعطي الزمرة الجزئية الوحيدة ذات الحجم \(h\ell\). وهذا هو شرط عدم التصادم المطلوب لتبليط القواسم.
باستخدام جذر بدائي \(g\)، نكتب \(q\equiv g^e\pmod p\). في زمرة القسمة ذات الرتبة \(Q\)، تكون رتبة \(qH\)
$$\operatorname{ord}_{G/H}(qH)={Q\over \gcd(e,Q)}.$$
لذلك فإن شرط الانتقال الذي يستعمله الحل هو
$$\operatorname{ord}_{G/H}(qH)=\ell \quad\Longleftrightarrow\quad \gcd(e,Q)={Q\over \ell}.$$
يجب أن تكون قيمة \(s\) أصغر ما يمكن كعدد صحيح. إذا استعمل انتقال عددا أوليا \(q\) بطول \(\ell\)، فإنه يضيف العامل \(q^{\ell-1}\) إلى \(s\). الكود يصغر اللوغاريتمات، لذلك وزن الانتقال هو
$$w(\ell,q)=(\ell-1)\log_{10}q.$$
للحالة الثابتة \(h\) والطول الثابت \(\ell\)، تعتمد الحالة التالية فقط على \(h\ell\)، لا على الطريق الذي أوصل إلى \(h\). وبما أن \(G\) دورية، توجد زمرة جزئية وحيدة لكل حجم \(h\mid p-1\). لذلك فإن أفضل عدد أولي لذلك الانتقال هو ببساطة أصغر عدد أولي \(q\ne p\) يحقق شرط اللوغاريتم المتقطع أعلاه.
تخزن البرمجة الديناميكية \(D(h)\)، أي أصغر قيمة معروفة لـ \(\log_{10}\) للعدد الجزئي الذي يبني الزمرة الجزئية ذات الحجم \(h\). تبدأ من
$$D(1)=0,$$
ولكل قاسم \(\ell\gt 1\) للعدد \(Q=(p-1)/h\) تقوم بالتحديث
$$D(h\ell)=\min\left(D(h\ell),\;D(h)+(\ell-1)\log_{10}q\right),$$
حيث \(q\) هو أصغر عدد أولي انتقالي يحقق \(\gcd(\log_g q,Q)=Q/\ell\). الجواب لعدد أولي واحد هو \(D(p-1)=\log_{10}S(p)\). تحفظ مؤشرات الآباء الأزواج المختارة \((\ell,q)\)، وهذا يسمح بإعادة بناء القيم الصغيرة بدقة للتحقق.
تثبت لمّة الجذر أن قسمة كثيرات الحدود تكافئ تساوي أعداد البواقي. وتثبت لمّة تبليط القواسم بعد ذلك أن كل حل يجب أن يحقق \(p\nmid s\)، وأن قواسمه يجب أن تصيب عناصر \(G\) مرة واحدة بالضبط. لذلك تصبح المسألة الأصلية مكافئة لإيجاد أصغر عدد صحيح يكون صندوق قواسمه تفكيكا ضربيا بلا تصادم للمجموعة \(G\).
كل انتقال في DP صحيح، لأن شرط الرتبة في زمرة القسمة يجعل القوى الجديدة \(1,q,\ldots,q^{\ell-1}\) تمثل \(\ell\) فئات مختلفة فوق الزمرة الجزئية الحالية. الزمرة القديمة فيها \(h\) عناصر؛ لذلك يحتوي الناتج الموسع على \(h\ell\) بواقي مختلفة، وهو بالضبط الزمرة الجزئية بذلك الحجم. بالاستقراء، كل مسار من \(1\) إلى \(p-1\) يبني تبليطا صحيحا للقواسم، ومن ثم عددا صحيحا صالحا \(s\).
وبالعكس، في الزمرة الدورية المستعملة هنا، يمكن قراءة أي تبليط دقيق بصندوق القواسم كسلسلة من المتممات في زمر القسمة: في كل مرحلة نختار اتجاها من صندوق القواسم تكون صوره فئات مختلفة فوق الزمرة التي بنيت سابقا. وبما أن الزمرة الدورية تملك زمرة جزئية واحدة فقط لكل حجم قاسم، فإن الحالة \(h\) لا تفقد معلومات عن هوية الزمرة الجزئية. لذلك تنظر DP في الانتقالات القانونية اللازمة، وأخذ الحد الأدنى يعطي \(S(p)\).
عند \(p=2\)، لدينا \(f_2(x)=1+x\)، و \(g_1(x)=1+x\)، ولذلك \(S(2)=1\). هذه هي الحالة المتدهورة \(G=\mathbb{F}_2^\times\)، ورتبتها \(1\)؛ تبدأ DP وتنتهي في الحالة نفسها.
عند \(p=5\)، رتبة \(G\) هي \(4\). أصغر باق بدائي هو \(2\). انتقال واحد بطول \(\ell=4\) يعطي
$$S(5)=2^{4-1}=8,$$
مطابقا لنص المسألة. قواسمه \(1,2,4,8\) تصير بترديد \(5\) إلى \(1,2,4,3\)، أي كل البواقي غير الصفرية مرة واحدة.
عند \(p=7\)، يمكن كتابة سلسلة مثلى على صورة \((\ell,q)=(3,2)\) ثم \((2,3)\). العدد الناتج هو
$$S(7)=2^{3-1}3^{2-1}=12.$$
القواسم \(1,2,4,3,6,12\) تصير بترديد \(7\) إلى \(1,2,4,3,6,5\)، وهذا تبليط كامل آخر لـ \(\mathbb{F}_7^\times\). تتحقق النسخة الكاملة من هذه الأمثلة المحلية ومن قيمتي المنتج \(T(20)=1348422598656\) و \(T(100)=1.37451\mathrm{e}123\).
تتبع إصدارات C++ و Python و Java المسار نفسه. تبني غربالا للأعداد الأولية حتى \(2\,000\,000\)، وتفكك \(p-1\)، وتعدد كل قواسم \(p-1\)، وتجد جذرا بدائيا بترديد \(p\)، ثم تبني جدول لوغاريتمات متقطعة يربط كل باق غير صفري بأسه بالنسبة إلى ذلك الجذر.
الدالة التي تبحث عن عدد أولي انتقالي تمسح قائمة الأعداد الأولية المحسوبة مسبقا وترفض \(q=p\). إذا لم يظهر عدد أولي مناسب داخل مدى الغربال، تستمر الخوارزمية باختبار الأولية بالتجربة بعد ذلك المدى. عمليا، الحد واسع بما يكفي للحالات \(p\lt 20000\)، لكن المسار الاحتياطي يجعل المنطق كاملا وغير معتمد على حد مقطوع مفترض.
كل المنتجات الكبيرة تعالج لوغاريتميا. الضرب الصحيح الكامل يبقى فقط للقيم الصغيرة المعاد بناؤها من \(S(p)\) ولـ \(T(20)\). هذا الفصل مهم: الناتج \(T(20000)\) يملك مئات الآلاف من الأرقام العشرية، بينما تحتاج الصيغة العلمية فقط إلى الجزء الكسري والجزء الصحيح من مجموع اللوغاريتمات العشرية.
لعدد أولي واحد \(p\)، عدد حالات DP هو \(\tau(p-1)\)، أي عدد قواسم \(p-1\). كل حالة تختبر الأطوال \(\ell\mid (p-1)/h\)، وكل انتقال يمسح الأعداد الأولية حتى يجد باقيا ذا الرتبة المطلوبة في زمرة القسمة. جدول اللوغاريتمات المتقطعة يحتاج \(O(p)\) من الذاكرة، ثم يحذف بعد حل ذلك العدد الأولي.
يوجد فقط \(2262\) عددا أوليا أصغر من \(20000\). لذلك يعمل алгоритم على شبكات قواسم صغيرة لـ \(p-1\)، لا على معاملات كثيرات الحدود ولا على قواسم عدد مرشح ضخم. لوغاريتمات long double كافية لأن الخرج يحتاج Mantissa مقربة إلى خمسة أرقام بعد الفاصلة؛ أما الاختبارات الصغيرة الدقيقة فتحمي من أخطاء بنيوية في الاختزال.