For every prime \(p \ge 5\), define
$$S(p)=\sum_{k=1}^{5}(p-k)!\pmod{p}=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!\pmod{p}.$$
The problem asks for the prime sum
$$\sum_{5 \le p \lt 10^8} S(p).$$
A naive implementation would recompute factorial residues for every prime, but the local C++, Python, and Java solutions all exploit the same fact: after Wilson's theorem, the five factorial terms collapse to one constant-size modular expression.
For every prime \(p\), Wilson's theorem gives
$$(p-1)! \equiv -1 \pmod{p}.$$
Because the problem only uses primes \(p \ge 5\), the numbers \(2\), \(3\), \(4\), \(8\), and \(24\) are all invertible modulo \(p\). That lets us divide congruences safely.
Using \(p-1 \equiv -1\), \(p-2 \equiv -2\), \(p-3 \equiv -3\), and \(p-4 \equiv -4 \pmod{p}\), we obtain
$$(p-2)! \equiv \frac{(p-1)!}{p-1} \equiv \frac{-1}{-1} \equiv 1 \pmod{p},$$
$$(p-3)! \equiv \frac{(p-2)!}{p-2} \equiv \frac{1}{-2} \equiv -\frac{1}{2} \pmod{p},$$
$$(p-4)! \equiv \frac{(p-3)!}{p-3} \equiv \frac{-1/2}{-3} \equiv \frac{1}{6} \pmod{p},$$
$$(p-5)! \equiv \frac{(p-4)!}{p-4} \equiv \frac{1/6}{-4} \equiv -\frac{1}{24} \pmod{p}.$$
So the five required terms are known without ever computing a factorial explicitly.
Substituting the four derived congruences back into \(S(p)\) gives
$$S(p)\equiv -1+1-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}\pmod{p}.$$
The integer parts cancel, and the remaining rational combination is
$$-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}=-\frac{12}{24}+\frac{4}{24}-\frac{1}{24}=-\frac{9}{24}=-\frac{3}{8}.$$
Therefore
$$\boxed{S(p)\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}\pmod{p}.}$$
This is the entire mathematical core of the implementation: one modular inverse of \(8\), then one multiplication by \(-3\).
The source files do not call an extended Euclidean algorithm. Instead, they build an integer representative of \(8^{-1}\pmod{p}\) directly. Let
$$r=p\bmod 8,\qquad k=8-r,\qquad \mathrm{inv8}=\frac{kp+1}{8}.$$
For an odd prime \(p\), we have \(r\in\{1,3,5,7\}\). Then \(r^2\equiv 1\pmod{8}\), so
$$kp+1\equiv (8-r)r+1=1-r^2\equiv 0\pmod{8},$$
which proves that \(\mathrm{inv8}\) is an integer. Also, since \(kp\equiv 0\pmod{p}\),
$$8\cdot \mathrm{inv8}=kp+1\equiv 1\pmod{p},$$
so \(\mathrm{inv8}\equiv 8^{-1}\pmod{p}\). The per-prime contribution is therefore computed as
$$S(p)\equiv -3\cdot \mathrm{inv8}\pmod{p}.$$
The C++ and Java versions write this as
$$\left(2p-\left((3\cdot \mathrm{inv8})\bmod p\right)\right)\bmod p,$$
which is just a non-negative way to represent the same residue.
The C++ solution contains explicit tests. For \(p=7\), \(8^{-1}\equiv 1\pmod{7}\), so
$$S(7)\equiv -3\equiv 4\pmod{7},$$
matching the checkpoint S_of_prime(7) == 4. It also verifies the closed form against a brute-force factorial computation for \(p\in\{5,7,11,13,17,19\}\), and checks
$$\sum_{5 \le p \lt 100} S(p)=480.$$
Those checkpoints confirm both the derivation and the implementation details.
The C++ file exposes the structure most clearly. primes_below(limit) runs a standard sieve of Eratosthenes and returns all primes below the bound. inv8_mod_prime(p) computes \((kp+1)/8\) using the low three bits of \(p\), namely p & 7. S_of_prime(p) then evaluates the closed form in \(O(1)\) time. The main loop skips \(2\) and \(3\), sums the value for every prime \(p \ge 5\), and returns the total.
The Python solution mirrors the same mathematics with a bytearray sieve. The Java solution uses a boolean composite table and computes the inverse inline inside the prime loop. None of the three implementations ever forms \((p-k)!\) directly for large \(p\); only the optional C++ checkpoint routine does that for tiny primes.
Let \(L=10^8\). The dominant cost is generating all primes below \(L\) with the sieve, which takes \(O(L\log\log L)\) time. After that, each prime contributes only a constant number of arithmetic operations, so the post-processing cost is \(O(\pi(L))\), which is asymptotically smaller than the sieve. Memory usage is \(O(L)\) for the sieve array.
This is dramatically better than evaluating factorial residues separately for every prime, which would introduce much larger per-prime work.
Für jede Primzahl \(p \ge 5\) sei
$$S(p)=\sum_{k=1}^{5}(p-k)!\pmod{p}=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!\pmod{p}.$$
Gesucht ist die Primzahlsumme
$$\sum_{5 \le p \lt 10^8} S(p).$$
Eine direkte Berechnung der fünf Fakultäten für jede Primzahl wäre viel zu langsam. Die lokalen Lösungen in C++, Python und Java zeigen, dass sich nach Anwendung des Satzes von Wilson alles auf einen Ausdruck konstanter Größe pro Primzahl reduziert.
Für jede Primzahl \(p\) gilt
$$(p-1)! \equiv -1 \pmod{p}.$$
Da im Problem nur Primzahlen \(p \ge 5\) vorkommen, sind \(2\), \(3\), \(4\), \(8\) und \(24\) modulo \(p\) invertierbar. Man darf also die folgenden Kongruenzen gefahrlos dividieren.
Mit \(p-1 \equiv -1\), \(p-2 \equiv -2\), \(p-3 \equiv -3\) und \(p-4 \equiv -4 \pmod{p}\) erhält man
$$(p-2)! \equiv \frac{(p-1)!}{p-1} \equiv \frac{-1}{-1} \equiv 1 \pmod{p},$$
$$(p-3)! \equiv \frac{(p-2)!}{p-2} \equiv \frac{1}{-2} \equiv -\frac{1}{2} \pmod{p},$$
$$(p-4)! \equiv \frac{(p-3)!}{p-3} \equiv \frac{-1/2}{-3} \equiv \frac{1}{6} \pmod{p},$$
$$(p-5)! \equiv \frac{(p-4)!}{p-4} \equiv \frac{1/6}{-4} \equiv -\frac{1}{24} \pmod{p}.$$
Damit kennt man alle fünf benötigten Summanden, ohne jemals eine große Fakultät explizit auszurechnen.
Einsetzen in \(S(p)\) liefert
$$S(p)\equiv -1+1-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}\pmod{p}.$$
Die ganzzahligen Terme heben sich auf, und für den Rest gilt
$$-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}=-\frac{12}{24}+\frac{4}{24}-\frac{1}{24}=-\frac{9}{24}=-\frac{3}{8}.$$
Also
$$\boxed{S(p)\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}\pmod{p}.}$$
Genau das ist der mathematische Kern der Implementierung: ein modulares Inverses von \(8\) und danach eine Multiplikation mit \(-3\).
Die Quelltexte verwenden keinen erweiterten Euklidischen Algorithmus. Stattdessen wird ein ganzzahliger Repräsentant von \(8^{-1}\pmod{p}\) direkt konstruiert. Setze
$$r=p\bmod 8,\qquad k=8-r,\qquad \mathrm{inv8}=\frac{kp+1}{8}.$$
Für eine ungerade Primzahl gilt \(r\in\{1,3,5,7\}\). Dann ist \(r^2\equiv 1\pmod{8}\), also
$$kp+1\equiv (8-r)r+1=1-r^2\equiv 0\pmod{8},$$
und \(\mathrm{inv8}\) ist tatsächlich eine ganze Zahl. Außerdem folgt aus \(kp\equiv 0\pmod{p}\), dass
$$8\cdot \mathrm{inv8}=kp+1\equiv 1\pmod{p},$$
weshalb \(\mathrm{inv8}\equiv 8^{-1}\pmod{p}\) gilt. Der Beitrag einer Primzahl wird also als
$$S(p)\equiv -3\cdot \mathrm{inv8}\pmod{p}$$
berechnet. C++ und Java schreiben denselben Wert in nichtnegativer Form als
$$\left(2p-\left((3\cdot \mathrm{inv8})\bmod p\right)\right)\bmod p.$$
Die C++-Datei enthält explizite Tests. Für \(p=7\) gilt \(8^{-1}\equiv 1\pmod{7}\), also
$$S(7)\equiv -3\equiv 4\pmod{7},$$
genau wie im Checkpoint S_of_prime(7) == 4. Außerdem vergleicht der Code die geschlossene Formel mit einer Brute-Force-Fakultätsrechnung für \(p\in\{5,7,11,13,17,19\}\) und prüft zusätzlich
$$\sum_{5 \le p \lt 100} S(p)=480.$$
Diese Tests bestätigen sowohl die Herleitung als auch die konkrete Implementierung.
Die C++-Lösung zeigt die Struktur am deutlichsten. primes_below(limit) implementiert ein klassisches Sieb des Eratosthenes und liefert alle Primzahlen unterhalb der Schranke. inv8_mod_prime(p) berechnet \((kp+1)/8\) über die unteren drei Bits von \(p\), also p & 7. S_of_prime(p) wertet anschließend die geschlossene Formel in \(O(1)\) aus. Die Hauptschleife überspringt \(2\) und \(3\), addiert den Wert für jede Primzahl \(p \ge 5\) und liefert die Gesamtsumme.
Die Python-Version verwendet dieselbe Mathematik mit einem bytearray-Sieb. Die Java-Version nutzt ein boolesches Komposit-Feld und berechnet das Inverse direkt in der Primzahlschleife. Keine der drei Fassungen bildet für große \(p\) jemals \((p-k)!\) direkt; nur die optionale C++-Prüfroutine macht das für sehr kleine Primzahlen.
Sei \(L=10^8\). Der dominierende Aufwand ist das Sieb zur Primzahlgenerierung bis \(L\), also \(O(L\log\log L)\) Zeit. Danach braucht jede Primzahl nur noch konstant viele arithmetische Operationen, sodass die Nachbearbeitung \(O(\pi(L))\) kostet und asymptotisch kleiner bleibt als das Sieb. Der Speicherverbrauch ist \(O(L)\) für das Siebarray.
Verglichen mit einer direkten Fakultätsberechnung pro Primzahl ist das ein massiver Gewinn, weil die Arbeit pro Primzahl auf konstante Zeit sinkt.
Her \(p \ge 5\) asalı için
$$S(p)=\sum_{k=1}^{5}(p-k)!\pmod{p}=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!\pmod{p}$$
tanımlanır. Hesaplanması istenen toplam
$$\sum_{5 \le p \lt 10^8} S(p)$$
değeridir. Her asal için beş faktöriyeli ayrı ayrı mod \(p\) altında hesaplamak çok pahalı olur; yerel C++, Python ve Java çözümleri bunun yerine Wilson teoremini kullanarak ifadeyi asal başına sabit maliyetli tek bir forma indirger.
Her asal \(p\) için
$$(p-1)! \equiv -1 \pmod{p}$$
eşitliği geçerlidir. Problem sadece \(p \ge 5\) asallarını kullandığı için \(2\), \(3\), \(4\), \(8\) ve \(24\) sayıları mod \(p\) altında terslenebilir; dolayısıyla aşağıdaki bölme adımları geçerlidir.
\(p-1 \equiv -1\), \(p-2 \equiv -2\), \(p-3 \equiv -3\) ve \(p-4 \equiv -4 \pmod{p}\) olduğundan
$$(p-2)! \equiv \frac{(p-1)!}{p-1} \equiv \frac{-1}{-1} \equiv 1 \pmod{p},$$
$$(p-3)! \equiv \frac{(p-2)!}{p-2} \equiv \frac{1}{-2} \equiv -\frac{1}{2} \pmod{p},$$
$$(p-4)! \equiv \frac{(p-3)!}{p-3} \equiv \frac{-1/2}{-3} \equiv \frac{1}{6} \pmod{p},$$
$$(p-5)! \equiv \frac{(p-4)!}{p-4} \equiv \frac{1/6}{-4} \equiv -\frac{1}{24} \pmod{p}.$$
Böylece büyük faktöriyel hesaplamasına hiç girmeden tüm gerekli terimler elde edilir.
Bu değerleri yerine koyunca
$$S(p)\equiv -1+1-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}\pmod{p}$$
olur. Tam sayı kısmı yok olur ve kalan rasyonel toplam
$$-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}=-\frac{12}{24}+\frac{4}{24}-\frac{1}{24}=-\frac{9}{24}=-\frac{3}{8}$$
şeklindedir. Sonuç olarak
$$\boxed{S(p)\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}\pmod{p}.}$$
Uygulamanın özü tam olarak budur: önce \(8\)'in modüler tersi, sonra \(-3\) ile çarpma.
Kaynak kodlar genişletilmiş Öklid algoritması çağırmıyor. Bunun yerine \(8^{-1}\pmod{p}\) için doğrudan bir tam sayı temsilcisi kuruyor. Şöyle tanımlanıyor:
$$r=p\bmod 8,\qquad k=8-r,\qquad \mathrm{inv8}=\frac{kp+1}{8}.$$
Tek bir asal için \(r\in\{1,3,5,7\}\) olur. Tek sayıların karesi mod \(8\) altında \(1\) olduğundan
$$kp+1\equiv (8-r)r+1=1-r^2\equiv 0\pmod{8},$$
yani \(\mathrm{inv8}\) gerçekten tam sayıdır. Ayrıca \(kp\equiv 0\pmod{p}\) olduğundan
$$8\cdot \mathrm{inv8}=kp+1\equiv 1\pmod{p},$$
ve dolayısıyla \(\mathrm{inv8}\equiv 8^{-1}\pmod{p}\). Bu yüzden asal başına katkı
$$S(p)\equiv -3\cdot \mathrm{inv8}\pmod{p}$$
olur. C++ ve Java bunu negatif ara değer oluşturmamak için
$$\left(2p-\left((3\cdot \mathrm{inv8})\bmod p\right)\right)\bmod p$$
biçiminde yazar.
C++ çözümü içinde açık kontrol noktaları vardır. Örneğin \(p=7\) için \(8^{-1}\equiv 1\pmod{7}\) olduğundan
$$S(7)\equiv -3\equiv 4\pmod{7},$$
ve bu değer S_of_prime(7) == 4 testiyle aynıdır. Ayrıca kapalı form, \(p\in\{5,7,11,13,17,19\}\) için kaba kuvvet faktöriyel hesabıyla karşılaştırılır ve şu toplam da doğrulanır:
$$\sum_{5 \le p \lt 100} S(p)=480.$$
Bu kontroller hem matematiksel türetmeyi hem de kodun uygulanışını doğrular.
C++ dosyası yapıyı en net gösterir. primes_below(limit) klasik Eratosthenes eleğini çalıştırıp sınır altındaki asalları döndürür. inv8_mod_prime(p), \(p\)'nin alt üç bitini yani p & 7 ifadesini kullanarak \((kp+1)/8\) değerini hesaplar. S_of_prime(p) bu kapalı formülü \(O(1)\) zamanda uygular. Ana döngü \(2\) ve \(3\)'ü atlar, her \(p \ge 5\) asalı için değeri toplar ve toplam sonucu döndürür.
Python çözümü aynı matematiği bir bytearray eleği ile tekrarlar. Java çözümü ise bileşik sayıları tutan bir boolean dizi kullanır ve tersi asal döngüsünün içinde hesaplar. Üç çözümün hiçbiri büyük \(p\) için \((p-k)!\) değerlerini doğrudan üretmez; bunu sadece küçük asallar için çalışan isteğe bağlı C++ test yordamı yapar.
\(L=10^8\) olsun. Baskın maliyet, \(L\) altındaki asalları üreten elektir ve bu adım \(O(L\log\log L)\) zamanda çalışır. Sonrasında her asal için yalnızca sabit sayıda aritmetik işlem yapıldığından ek maliyet \(O(\pi(L))\) olur ve asimptotik olarak elekten küçüktür. Bellek kullanımı elek dizisi nedeniyle \(O(L)\)'dir.
Bu yaklaşım, her asal için faktöriyelleri tek tek hesaplamaya göre çok daha verimlidir; asal başına maliyet sabit zamana düşer.
Para cada primo \(p \ge 5\), se define
$$S(p)=\sum_{k=1}^{5}(p-k)!\pmod{p}=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!\pmod{p}.$$
La cantidad pedida es
$$\sum_{5 \le p \lt 10^8} S(p).$$
Calcular cinco factoriales módulo \(p\) para cada primo sería innecesariamente costoso. Los archivos locales en C++, Python y Java usan la misma observación: con el teorema de Wilson, toda la suma se reduce a una fórmula modular de tiempo constante por primo.
Para todo primo \(p\), se cumple
$$(p-1)! \equiv -1 \pmod{p}.$$
Como el problema sólo considera primos \(p \ge 5\), los números \(2\), \(3\), \(4\), \(8\) y \(24\) son invertibles módulo \(p\). Por eso las divisiones modulares siguientes son válidas.
Usando \(p-1 \equiv -1\), \(p-2 \equiv -2\), \(p-3 \equiv -3\) y \(p-4 \equiv -4 \pmod{p}\), obtenemos
$$(p-2)! \equiv \frac{(p-1)!}{p-1} \equiv \frac{-1}{-1} \equiv 1 \pmod{p},$$
$$(p-3)! \equiv \frac{(p-2)!}{p-2} \equiv \frac{1}{-2} \equiv -\frac{1}{2} \pmod{p},$$
$$(p-4)! \equiv \frac{(p-3)!}{p-3} \equiv \frac{-1/2}{-3} \equiv \frac{1}{6} \pmod{p},$$
$$(p-5)! \equiv \frac{(p-4)!}{p-4} \equiv \frac{1/6}{-4} \equiv -\frac{1}{24} \pmod{p}.$$
Así se conocen los cinco términos requeridos sin formar factoriales grandes de manera explícita.
Al sustituir en \(S(p)\), resulta
$$S(p)\equiv -1+1-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}\pmod{p}.$$
Las partes enteras se cancelan, y el resto se simplifica como
$$-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}=-\frac{12}{24}+\frac{4}{24}-\frac{1}{24}=-\frac{9}{24}=-\frac{3}{8}.$$
Por lo tanto,
$$\boxed{S(p)\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}\pmod{p}.}$$
Ésta es toda la idea matemática utilizada por el código: calcular el inverso modular de \(8\) y multiplicar por \(-3\).
Las implementaciones no llaman al algoritmo extendido de Euclides. En su lugar construyen directamente un representante entero de \(8^{-1}\pmod{p}\). Definen
$$r=p\bmod 8,\qquad k=8-r,\qquad \mathrm{inv8}=\frac{kp+1}{8}.$$
Para un primo impar, \(r\in\{1,3,5,7\}\). Entonces \(r^2\equiv 1\pmod{8}\), y por eso
$$kp+1\equiv (8-r)r+1=1-r^2\equiv 0\pmod{8},$$
de modo que \(\mathrm{inv8}\) es entero. Además, como \(kp\equiv 0\pmod{p}\), se tiene
$$8\cdot \mathrm{inv8}=kp+1\equiv 1\pmod{p},$$
y por tanto \(\mathrm{inv8}\equiv 8^{-1}\pmod{p}\). La contribución de cada primo se calcula como
$$S(p)\equiv -3\cdot \mathrm{inv8}\pmod{p}.$$
Las versiones en C++ y Java escriben el mismo residuo de forma no negativa:
$$\left(2p-\left((3\cdot \mathrm{inv8})\bmod p\right)\right)\bmod p.$$
El archivo C++ incluye comprobaciones explícitas. Para \(p=7\), se tiene \(8^{-1}\equiv 1\pmod{7}\), luego
$$S(7)\equiv -3\equiv 4\pmod{7},$$
que coincide con la prueba S_of_prime(7) == 4. Además, la fórmula cerrada se compara con un cálculo directo de factoriales para \(p\in\{5,7,11,13,17,19\}\), y también se verifica que
$$\sum_{5 \le p \lt 100} S(p)=480.$$
Esos puntos de control respaldan tanto la derivación matemática como la implementación concreta.
El archivo en C++ muestra la estructura con mayor claridad. primes_below(limit) ejecuta una criba de Eratóstenes estándar y devuelve todos los primos menores que el límite. inv8_mod_prime(p) calcula \((kp+1)/8\) usando los tres bits bajos de \(p\), es decir, p & 7. Después, S_of_prime(p) evalúa la fórmula cerrada en \(O(1)\). El bucle principal omite \(2\) y \(3\), suma el valor para cada primo \(p \ge 5\) y devuelve el total.
La solución en Python repite exactamente la misma matemática con una criba basada en bytearray. La versión en Java usa un arreglo booleano de compuestos y calcula el inverso dentro del propio recorrido de primos. Ninguna de las tres implementaciones forma \((p-k)!\) directamente para primos grandes; sólo la rutina opcional de comprobación en C++ lo hace para primos pequeños.
Sea \(L=10^8\). El coste dominante es la generación de primos con la criba hasta \(L\), que requiere \(O(L\log\log L)\) tiempo. Después de eso, cada primo aporta únicamente una cantidad constante de operaciones aritméticas, así que el procesamiento adicional cuesta \(O(\pi(L))\), asintóticamente menor que la criba. El uso de memoria es \(O(L)\) por el arreglo de la criba.
Esto es mucho mejor que recalcular residuos factoriales para cada primo, porque el coste por primo queda reducido a tiempo constante.
对每个素数 \(p \ge 5\)，定义
$$S(p)=\sum_{k=1}^{5}(p-k)!\pmod{p}=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!\pmod{p}$$
题目要求计算
$$\sum_{5 \le p \lt 10^8} S(p)$$
如果对每个素数都单独计算五个阶乘余数，代价会非常高。仓库中的 C++、Python 和 Java 解法都利用同一个结论：应用 Wilson 定理后，这五项可以压缩成每个素数只需常数时间的一条模公式。
对任意素数 \(p\)，有
$$(p-1)! \equiv -1 \pmod{p}$$
由于本题只考虑 \(p \ge 5\) 的素数，所以 \(2\)、\(3\)、\(4\)、\(8\)、\(24\) 在模 \(p\) 意义下都有逆元，因此后续的除法都是合法的。
利用 \(p-1 \equiv -1\)、\(p-2 \equiv -2\)、\(p-3 \equiv -3\)、\(p-4 \equiv -4 \pmod{p}\)，可得
$$(p-2)! \equiv \frac{(p-1)!}{p-1} \equiv \frac{-1}{-1} \equiv 1 \pmod{p},$$
$$(p-3)! \equiv \frac{(p-2)!}{p-2} \equiv \frac{1}{-2} \equiv -\frac{1}{2} \pmod{p},$$
$$(p-4)! \equiv \frac{(p-3)!}{p-3} \equiv \frac{-1/2}{-3} \equiv \frac{1}{6} \pmod{p},$$
$$(p-5)! \equiv \frac{(p-4)!}{p-4} \equiv \frac{1/6}{-4} \equiv -\frac{1}{24} \pmod{p}$$
这样就不需要真正去构造大阶乘，五个目标项已经全部得到。
代回 \(S(p)\) 后有
$$S(p)\equiv -1+1-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}\pmod{p}$$
整数部分相消，剩余部分化简为
$$-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}=-\frac{12}{24}+\frac{4}{24}-\frac{1}{24}=-\frac{9}{24}=-\frac{3}{8}$$
因此
$$\boxed{S(p)\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}\pmod{p}}$$
这就是实现的数学核心：先求 \(8\) 的模逆，再乘上 \(-3\)。
这些实现并没有调用扩展欧几里得算法，而是直接构造 \(8^{-1}\pmod{p}\) 的一个整数代表。定义
$$r=p\bmod 8,\qquad k=8-r,\qquad \mathrm{inv8}=\frac{kp+1}{8}$$
当 \(p\) 是奇素数时，\(r\in\{1,3,5,7\}\)。由于奇数平方满足 \(r^2\equiv 1\pmod{8}\)，于是
$$kp+1\equiv (8-r)r+1=1-r^2\equiv 0\pmod{8},$$
所以 \(\mathrm{inv8}\) 确实是整数。又因为 \(kp\equiv 0\pmod{p}\)，得到
$$8\cdot \mathrm{inv8}=kp+1\equiv 1\pmod{p},$$
从而 \(\mathrm{inv8}\equiv 8^{-1}\pmod{p}\)。因此每个素数的贡献就是
$$S(p)\equiv -3\cdot \mathrm{inv8}\pmod{p}$$
C++ 与 Java 为了避免负中间值，把它写成
$$\left(2p-\left((3\cdot \mathrm{inv8})\bmod p\right)\right)\bmod p$$
C++ 文件内置了检查点。对 \(p=7\)，有 \(8^{-1}\equiv 1\pmod{7}\)，因此
$$S(7)\equiv -3\equiv 4\pmod{7},$$
这与 S_of_prime(7) == 4 完全一致。代码还把闭式结果与小素数 \(p\in\{5,7,11,13,17,19\}\) 的直接阶乘计算进行比较，并验证
$$\sum_{5 \le p \lt 100} S(p)=480$$
这些校验同时说明推导和实现都是正确的。
C++ 文件把整体结构展示得最清楚。primes_below(limit) 使用标准埃拉托斯特尼筛生成上界以下的全部素数。inv8_mod_prime(p) 通过 p & 7 取得 \(p\) 的最低三位，从而算出 \((kp+1)/8\)。S_of_prime(p) 再用闭式在 \(O(1)\) 时间内得到单个素数的贡献。主循环跳过 \(2\) 和 \(3\)，对每个 \(p \ge 5\) 的素数累加结果。
Python 版本用 bytearray 实现同样的筛法与同样的数学公式。Java 版本使用布尔数组记录合数，并在素数循环内部直接计算逆元。这三份实现都不会对大素数真正计算 \((p-k)!\)；只有 C++ 中的可选检查函数会对很小的素数做直接验证。
令 \(L=10^8\)。主导成本是筛出所有小于 \(L\) 的素数，这一步的时间复杂度为 \(O(L\log\log L)\)。之后每个素数只需要常数次算术运算，所以额外处理成本是 \(O(\pi(L))\)，渐近上小于筛法本身。空间复杂度为 \(O(L)\)，对应筛数组。
与对每个素数分别计算多个阶乘余数相比，这种方法把单个素数的工作量降到了常数级。
Для каждого простого числа \(p \ge 5\) определяется
$$S(p)=\sum_{k=1}^{5}(p-k)!\pmod{p}=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!\pmod{p}.$$
Нужно вычислить сумму
$$\sum_{5 \le p \lt 10^8} S(p).$$
Если для каждого простого отдельно пересчитывать пять факториалов по модулю \(p\), решение будет слишком тяжёлым. Локальные реализации на C++, Python и Java используют одно и то же сокращение: после теоремы Вильсона вся задача сводится к формуле постоянной стоимости на один простой.
Для любого простого \(p\) верно
$$(p-1)! \equiv -1 \pmod{p}.$$
Поскольку в задаче рассматриваются только простые \(p \ge 5\), числа \(2\), \(3\), \(4\), \(8\) и \(24\) обратимы по модулю \(p\). Поэтому далее можно делить конгруэнции без дополнительных оговорок.
Из \(p-1 \equiv -1\), \(p-2 \equiv -2\), \(p-3 \equiv -3\) и \(p-4 \equiv -4 \pmod{p}\) следует
$$(p-2)! \equiv \frac{(p-1)!}{p-1} \equiv \frac{-1}{-1} \equiv 1 \pmod{p},$$
$$(p-3)! \equiv \frac{(p-2)!}{p-2} \equiv \frac{1}{-2} \equiv -\frac{1}{2} \pmod{p},$$
$$(p-4)! \equiv \frac{(p-3)!}{p-3} \equiv \frac{-1/2}{-3} \equiv \frac{1}{6} \pmod{p},$$
$$(p-5)! \equiv \frac{(p-4)!}{p-4} \equiv \frac{1/6}{-4} \equiv -\frac{1}{24} \pmod{p}.$$
Тем самым все нужные слагаемые получены без явного вычисления больших факториалов.
Подставляя эти выражения в \(S(p)\), получаем
$$S(p)\equiv -1+1-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}\pmod{p}.$$
Целые части сокращаются, а оставшаяся дробная комбинация равна
$$-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}=-\frac{12}{24}+\frac{4}{24}-\frac{1}{24}=-\frac{9}{24}=-\frac{3}{8}.$$
Следовательно,
$$\boxed{S(p)\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}\pmod{p}.}$$
Это и есть вся математическая сущность программы: найти обратный к \(8\) по модулю \(p\) и умножить на \(-3\).
Исходники не вызывают расширенный алгоритм Евклида. Вместо этого они сразу строят целочисленного представителя для \(8^{-1}\pmod{p}\). Вводятся величины
$$r=p\bmod 8,\qquad k=8-r,\qquad \mathrm{inv8}=\frac{kp+1}{8}.$$
Для нечётного простого \(p\) имеем \(r\in\{1,3,5,7\}\). Тогда \(r^2\equiv 1\pmod{8}\), и потому
$$kp+1\equiv (8-r)r+1=1-r^2\equiv 0\pmod{8},$$
то есть \(\mathrm{inv8}\) действительно является целым числом. Кроме того, из \(kp\equiv 0\pmod{p}\) следует
$$8\cdot \mathrm{inv8}=kp+1\equiv 1\pmod{p},$$
значит \(\mathrm{inv8}\equiv 8^{-1}\pmod{p}\). Поэтому вклад одного простого вычисляется как
$$S(p)\equiv -3\cdot \mathrm{inv8}\pmod{p}.$$
В C++ и Java тот же остаток записан в неотрицательной форме:
$$\left(2p-\left((3\cdot \mathrm{inv8})\bmod p\right)\right)\bmod p.$$
В файле C++ есть явные контрольные точки. Для \(p=7\) имеем \(8^{-1}\equiv 1\pmod{7}\), откуда
$$S(7)\equiv -3\equiv 4\pmod{7},$$
что совпадает с тестом S_of_prime(7) == 4. Кроме того, закрытая формула сверяется с прямым вычислением факториалов для \(p\in\{5,7,11,13,17,19\}\), а также проверяется равенство
$$\sum_{5 \le p \lt 100} S(p)=480.$$
Эти проверки подтверждают и вывод формулы, и корректность её программной реализации.
Наиболее наглядно структура видна в C++-версии. Функция primes_below(limit) выполняет обычное решето Эратосфена и возвращает все простые ниже заданной границы. Функция inv8_mod_prime(p) вычисляет \((kp+1)/8\), используя три младших бита числа \(p\), то есть выражение p & 7. Затем S_of_prime(p) за \(O(1)\) получает вклад данного простого. Основной цикл пропускает \(2\) и \(3\), суммирует значения для всех простых \(p \ge 5\) и возвращает итог.
Решение на Python повторяет ту же математику с решетом на базе bytearray. Версия на Java использует булев массив составных чисел и вычисляет обратный элемент прямо внутри прохода по простым. Ни одна из этих реализаций не вычисляет \((p-k)!\) напрямую для больших простых; так делает только вспомогательная C++-функция проверки на маленьких значениях.
Пусть \(L=10^8\). Главная стоимость связана с построением решета до \(L\), что требует \(O(L\log\log L)\) времени. После этого на каждый простой приходится лишь постоянное число арифметических операций, поэтому дополнительная обработка стоит \(O(\pi(L))\) и асимптотически меньше решета. Память составляет \(O(L)\) из-за массива решета.
По сравнению с прямым пересчётом факториальных остатков для каждого простого это радикально быстрее, потому что работа на один простой становится константной.
لكل عدد أولي \(p \ge 5\) نعرّف
$$S(p)=\sum_{k=1}^{5}(p-k)!\pmod{p}=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!\pmod{p}.$$
والمطلوب حساب المجموع
$$\sum_{5 \le p \lt 10^8} S(p).$$
الحساب المباشر لخمسة مضروبات لكل أولي سيكون مكلفًا جدًا. ملفات الحل المحلية في C++ وPython وJava تعتمد الفكرة نفسها: بعد استخدام مبرهنة ويلسون، تتحول المسألة كلها إلى صيغة معيارية ثابتة الكلفة لكل عدد أولي.
لكل عدد أولي \(p\) لدينا
$$(p-1)! \equiv -1 \pmod{p}.$$
وبما أن المسألة تستخدم فقط الأعداد الأولية \(p \ge 5\)، فإن الأعداد \(2\) و\(3\) و\(4\) و\(8\) و\(24\) تملك معكوسًا ضربيًا modulo \(p\). لذلك فإن القسمة في الخطوات التالية صحيحة داخل الحساب المعياري.
باستخدام \(p-1 \equiv -1\)، و\(p-2 \equiv -2\)، و\(p-3 \equiv -3\)، و\(p-4 \equiv -4 \pmod{p}\)، نحصل على
$$(p-2)! \equiv \frac{(p-1)!}{p-1} \equiv \frac{-1}{-1} \equiv 1 \pmod{p},$$
$$(p-3)! \equiv \frac{(p-2)!}{p-2} \equiv \frac{1}{-2} \equiv -\frac{1}{2} \pmod{p},$$
$$(p-4)! \equiv \frac{(p-3)!}{p-3} \equiv \frac{-1/2}{-3} \equiv \frac{1}{6} \pmod{p},$$
$$(p-5)! \equiv \frac{(p-4)!}{p-4} \equiv \frac{1/6}{-4} \equiv -\frac{1}{24} \pmod{p}.$$
وهكذا نحصل على الحدود الخمسة المطلوبة من دون تكوين مضروبات كبيرة بشكل صريح.
بالتعويض في \(S(p)\) نحصل على
$$S(p)\equiv -1+1-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}\pmod{p}.$$
الجزآن الصحيحان يتلاشيان، ويبقى
$$-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}=-\frac{12}{24}+\frac{4}{24}-\frac{1}{24}=-\frac{9}{24}=-\frac{3}{8}.$$
إذن
$$\boxed{S(p)\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}\pmod{p}.}$$
وهذه هي الفكرة الرياضية الأساسية في التنفيذ: نحسب معكوس \(8\) modulo \(p\)، ثم نضرب في \(-3\).
الملفات المصدرية لا تستخدم خوارزمية إقليدس الموسعة. بدلًا من ذلك تبني ممثلًا صحيحًا مباشرًا لـ \(8^{-1}\pmod{p}\). يتم تعريف
$$r=p\bmod 8,\qquad k=8-r,\qquad \mathrm{inv8}=\frac{kp+1}{8}.$$
إذا كان \(p\) أوليًا فرديًا فإن \(r\in\{1,3,5,7\}\). وبما أن مربع أي عدد فردي يساوي \(1\) modulo \(8\)، فإن
$$kp+1\equiv (8-r)r+1=1-r^2\equiv 0\pmod{8},$$
ومن ثم فإن \(\mathrm{inv8}\) عدد صحيح فعلًا. كذلك لأن \(kp\equiv 0\pmod{p}\)، فإن
$$8\cdot \mathrm{inv8}=kp+1\equiv 1\pmod{p},$$
وهذا يعني أن \(\mathrm{inv8}\equiv 8^{-1}\pmod{p}\). بالتالي تصبح مساهمة كل أولي
$$S(p)\equiv -3\cdot \mathrm{inv8}\pmod{p}.$$
نسختا C++ وJava تكتبان الباقي نفسه بصيغة غير سالبة:
$$\left(2p-\left((3\cdot \mathrm{inv8})\bmod p\right)\right)\bmod p.$$
ملف C++ يحتوي على اختبارات صريحة. عندما \(p=7\) يكون \(8^{-1}\equiv 1\pmod{7}\)، ولذلك
$$S(7)\equiv -3\equiv 4\pmod{7},$$
وهو نفس الناتج الموجود في الاختبار S_of_prime(7) == 4. كما أن الكود يقارن الصيغة المغلقة مع حساب مباشر للمضروبات عند القيم \(p\in\{5,7,11,13,17,19\}\)، ويتحقق أيضًا من أن
$$\sum_{5 \le p \lt 100} S(p)=480.$$
هذه النقاط تؤكد صحة الاشتقاق الرياضي وصحة التنفيذ في الوقت نفسه.
ملف C++ يوضح البنية العامة بأفضل شكل. الدالة primes_below(limit) تنفذ غربال إراتوستينس القياسي وتعيد جميع الأعداد الأولية الأصغر من الحد. الدالة inv8_mod_prime(p) تحسب \((kp+1)/8\) باستخدام الثلاثة بتات الدنيا من \(p\)، أي التعبير p & 7. بعد ذلك تحسب S_of_prime(p) الصيغة المغلقة في زمن \(O(1)\). الحلقة الرئيسية تتجاوز \(2\) و\(3\)، ثم تجمع مساهمة كل أولي \(p \ge 5\).
حل Python يكرر الرياضيات نفسها باستخدام غربال مبني على bytearray. أما حل Java فيستخدم مصفوفة منطقية للأعداد المركبة ويحسِب المعكوس داخل حلقة الأعداد الأولية نفسها. ولا تقوم أي من هذه النسخ بحساب \((p-k)!\) مباشرة للأعداد الأولية الكبيرة؛ هذا يحدث فقط داخل روتين التحقق الاختياري في C++ ولأعداد صغيرة جدًا.
لنفرض أن \(L=10^8\). الكلفة الغالبة هي توليد جميع الأعداد الأولية الأقل من \(L\) بواسطة الغربال، وهذا يتطلب زمنًا \(O(L\log\log L)\). بعد ذلك يحتاج كل أولي إلى عدد ثابت فقط من العمليات الحسابية، لذا فإن المعالجة الإضافية تكلف \(O(\pi(L))\)، وهي أصغر تقاربيًا من كلفة الغربال. أما الذاكرة فهي \(O(L)\) بسبب مصفوفة الغربال.
وهذا أفضل بكثير من إعادة حساب بواقي المضروبات لكل أولي على حدة، لأن كلفة كل أولي أصبحت ثابتة.