For Problem 773, the implementations begin with the first \(k\) primes whose last digit is \(7\). The target quantity is then reduced to an inclusion-exclusion calculation in which a large multiplicative term is corrected by a small decimal-residue term. After that reduction, the whole answer depends only on the product of those primes, the totient of that product, and a short alternating binomial sum with period \(4\).
Let
$$p_1,p_2,\dots,p_k$$
be the first \(k\) primes satisfying
$$p_i \equiv 7 \pmod{10}.$$
Define the two central products
$$P_k=\prod_{i=1}^k p_i,\qquad \Phi_k=\prod_{i=1}^k (p_i-1).$$
Because the primes are distinct, \(\Phi_k\) is exactly Euler's totient of \(P_k\):
$$\Phi_k=\varphi(P_k).$$
The derived counting formula used by the implementations splits each inclusion-exclusion contribution into a large uniform part and a small decimal correction. The uniform part depends on which primes are excluded from a chosen subset, so the natural sum runs over all subsets \(S\subseteq \{1,\dots,k\}\):
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i.$$
This is a standard product expansion. Each prime \(p_i\) contributes either \(p_i\) or \(-1\), so the whole sum factors as
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i=\prod_{i=1}^k (p_i-1)=\Phi_k.$$
In the final formula this term appears multiplied by \(5\), which is why the dominant contribution is \(5\Phi_k\).
The problem-specific correction depends on the last digit of the product of the selected primes. If a subset has size \(t\), then every chosen prime contributes a factor congruent to \(7 \pmod{10}\), so the subset product has last digit
$$7^t \pmod{10}.$$
The powers of \(7\) modulo \(10\) are periodic with period \(4\):
$$7^0\equiv 1,\quad 7^1\equiv 7,\quad 7^2\equiv 9,\quad 7^3\equiv 3 \pmod{10}.$$
To force the relevant multiple back into the decimal class ending in \(7\), the multiplier must satisfy
$$m \equiv 7\cdot (7^t)^{-1} \pmod{10}.$$
Since the invertible residues modulo \(10\) are \(1,3,7,9\), their inverses are
$$1^{-1}\equiv 1,\qquad 7^{-1}\equiv 3,\qquad 9^{-1}\equiv 9,\qquad 3^{-1}\equiv 7 \pmod{10}.$$
Therefore the correction sequence is
$$w_0=7,\qquad w_1=1,\qquad w_2=3,\qquad w_3=9,$$
and then it repeats every four steps.
The key simplification is that the correction depends only on the subset size \(t\), not on which particular primes were selected. There are exactly \(\binom{k}{t}\) subsets of size \(t\), so the full correction becomes
$$S_k=\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t,$$
where \(w_t\) is understood periodically:
$$w_t=w_{t\bmod 4}\in \{7,1,3,9\}.$$
This is why the code only needs one short period-4 table instead of handling subsets individually.
Combining the multiplicative part and the residue correction yields the exact quantity computed by the implementations:
$$R_k \equiv P_k\left(5\Phi_k + S_k\right)\pmod{10^9+7}.$$
Substituting the explicit definitions gives
$$\boxed{R_k \equiv \left(\prod_{i=1}^k p_i\right)\left(5\prod_{i=1}^k (p_i-1)+\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t\right)\pmod{10^9+7}.}$$
So once the relevant primes are known, the remaining work is purely modular arithmetic.
The first three primes ending in \(7\) are
$$7,\ 17,\ 37.$$
Hence
$$P_3=7\cdot 17\cdot 37=4403,$$
and
$$\Phi_3=(7-1)(17-1)(37-1)=6\cdot 16\cdot 36=3456.$$
The correction sum uses the pattern \(7,1,3,9\):
$$\begin{aligned} S_3&=\binom{3}{0}7-\binom{3}{1}1+\binom{3}{2}3-\binom{3}{3}9\\ &=7-3+9-9\\ &=4. \end{aligned}$$
Therefore
$$R_3=4403\left(5\cdot 3456+4\right)=4403\cdot 17284=76101452,$$
which matches the checkpoint built into the implementations.
The C++, Python, and Java implementations all follow the same sequence. First they scan the arithmetic progression \(7,17,27,\dots\) and retain exactly those terms that are prime. The primality test is straightforward trial division up to \(\sqrt{n}\), which is sufficient because the required \(k\) is small.
After the prime list is built, the implementation multiplies those primes modulo \(10^9+7\) to obtain \(P_k\), and simultaneously multiplies the factors \(p_i-1\) modulo \(10^9+7\) to obtain \(\Phi_k\).
Next it evaluates the correction sum \(S_k\). Instead of recomputing each binomial coefficient from factorials, it updates them iteratively via
$$\binom{k}{t+1}=\binom{k}{t}\frac{k-t}{t+1}.$$
Division modulo the prime modulus is performed with a modular inverse:
$$a^{-1}\equiv a^{M-2}\pmod{M},\qquad M=10^9+7.$$
The alternating sign is handled term by term, the period-4 residue table supplies \(w_t\), and finally the program multiplies \(P_k\) by \(5\Phi_k+S_k\) modulo \(10^9+7\). One implementation also includes the \(k=3\) checkpoint shown above before evaluating the final \(k=97\) case.
Let \(B\) be the largest candidate examined while collecting the first \(k\) primes ending in \(7\). With trial division, primality testing costs \(O(\sqrt{n})\) per candidate, so the prime-generation phase is the dominant part and is bounded by \(O(B^{3/2})\) in the simplest worst-case estimate. The modular accumulation of \(P_k\) and \(\Phi_k\) is \(O(k)\), and the binomial correction loop is \(O(k\log M)\) because each modular inverse is computed by fast exponentiation. Memory usage is \(O(k)\) for the stored prime list.
Für Problem 773 beginnen die Implementierungen mit den ersten \(k\) Primzahlen, deren letzte Ziffer \(7\) ist. Die gesuchte Größe wird dann auf eine Inklusions-Exklusions-Rechnung zurückgeführt, bei der ein großer multiplikativer Hauptterm nur noch durch eine kleine dezimale Restklassenkorrektur ergänzt wird. Nach dieser Umformung hängt das Ergebnis nur noch vom Produkt dieser Primzahlen, von der Totientfunktion dieses Produkts und von einer kurzen alternierenden Binomialsumme mit Periode \(4\) ab.
Seien
$$p_1,p_2,\dots,p_k$$
die ersten \(k\) Primzahlen mit
$$p_i \equiv 7 \pmod{10}.$$
Wir definieren
$$P_k=\prod_{i=1}^k p_i,\qquad \Phi_k=\prod_{i=1}^k (p_i-1).$$
Da alle Primzahlen verschieden sind, gilt sofort
$$\Phi_k=\varphi(P_k).$$
Die aus der Aufgabe abgeleitete Zählformel zerlegt jeden Inklusions-Exklusions-Beitrag in einen großen einheitlichen Teil und eine kleine Dezimalkorrektur. Der Hauptterm führt auf die Summe
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i,$$
wobei \(S\subseteq \{1,\dots,k\}\) über alle Teilmengen läuft. Diese Summe faktorisiert sofort, denn zu jedem Primfaktor gehört entweder \(p_i\) oder \(-1\):
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i=\prod_{i=1}^k (p_i-1)=\Phi_k.$$
Im Endergebnis erscheint dieser Anteil mit dem Vorfaktor \(5\); daher ist der dominante Beitrag \(5\Phi_k\).
Die aufgabenspezifische Korrektur hängt nur von der Endziffer des Produkts der ausgewählten Primzahlen ab. Hat eine Teilmenge die Größe \(t\), dann ist ihr Produkt modulo \(10\)
$$7^t \pmod{10}.$$
Die Potenzen von \(7\) modulo \(10\) bilden einen Zyklus der Länge \(4\):
$$7^0\equiv 1,\quad 7^1\equiv 7,\quad 7^2\equiv 9,\quad 7^3\equiv 3 \pmod{10}.$$
Damit der relevante Faktor wieder in die Endzifferklasse \(7\) fällt, muss der Multiplikator genügen:
$$m \equiv 7\cdot (7^t)^{-1} \pmod{10}.$$
Für die invertierbaren Restklassen modulo \(10\) gilt
$$1^{-1}\equiv 1,\qquad 7^{-1}\equiv 3,\qquad 9^{-1}\equiv 9,\qquad 3^{-1}\equiv 7 \pmod{10}.$$
Daraus folgt die periodische Korrekturfolge
$$w_0=7,\qquad w_1=1,\qquad w_2=3,\qquad w_3=9,$$
die sich anschließend alle vier Schritte wiederholt.
Entscheidend ist, dass die Korrektur nur von \(t=|S|\) abhängt, nicht von der konkreten Auswahl der Primzahlen. Es gibt genau \(\binom{k}{t}\) Teilmengen der Größe \(t\). Deshalb lässt sich der gesamte Korrekturterm schreiben als
$$S_k=\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t,$$
wobei \(w_t\) periodisch verstanden wird:
$$w_t=w_{t\bmod 4}\in \{7,1,3,9\}.$$
Genau diese Beobachtung macht die Lösung so kurz: Statt alle Teilmengen einzeln zu behandeln, reicht eine Binomialsumme.
Fasst man den Hauptterm und die Restklassenkorrektur zusammen, erhält man exakt die Größe, die von den Implementierungen berechnet wird:
$$R_k \equiv P_k\left(5\Phi_k + S_k\right)\pmod{10^9+7}.$$
Mit ausgeschriebenen Definitionen lautet das
$$\boxed{R_k \equiv \left(\prod_{i=1}^k p_i\right)\left(5\prod_{i=1}^k (p_i-1)+\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t\right)\pmod{10^9+7}.}$$
Sobald die benötigten Primzahlen bekannt sind, bleibt also nur noch modulare Arithmetik.
Die ersten drei Primzahlen mit Endziffer \(7\) sind
$$7,\ 17,\ 37.$$
Damit folgt
$$P_3=7\cdot 17\cdot 37=4403,$$
und
$$\Phi_3=(7-1)(17-1)(37-1)=6\cdot 16\cdot 36=3456.$$
Die Korrektursumme ist
$$\begin{aligned} S_3&=\binom{3}{0}7-\binom{3}{1}1+\binom{3}{2}3-\binom{3}{3}9\\ &=7-3+9-9\\ &=4. \end{aligned}$$
Somit ergibt sich
$$R_3=4403\left(5\cdot 3456+4\right)=4403\cdot 17284=76101452,$$
genau der Kontrollwert aus den Implementierungen.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst wird die arithmetische Folge \(7,17,27,\dots\) durchlaufen, und nur die Primzahlen werden übernommen. Der Primzahltest ist einfache Probedivision bis \(\sqrt{n}\), was für die kleine Zielgröße vollkommen ausreicht.
Anschließend wird das Primzahlprodukt modulo \(10^9+7\) gebildet, um \(P_k\) zu erhalten. Parallel dazu wird das Produkt der Werte \(p_i-1\) modulo \(10^9+7\) berechnet, also \(\Phi_k\).
Danach wird die Binomialkorrektur \(S_k\) ausgewertet. Statt Fakultäten vorzubereiten, aktualisiert die Implementierung die Binomialkoeffizienten rekursiv über
$$\binom{k}{t+1}=\binom{k}{t}\frac{k-t}{t+1}.$$
Die Division modulo dem Primmodul geschieht mit dem modularen Inversen
$$a^{-1}\equiv a^{M-2}\pmod{M},\qquad M=10^9+7.$$
Zusammen mit dem Vorzeichenwechsel und der periodischen Restklassenfolge entsteht so \(S_k\); zuletzt wird \(P_k\) mit \(5\Phi_k+S_k\) multipliziert. Eine der Implementierungen prüft zusätzlich den Fall \(k=3\), bevor der Endwert für \(k=97\) ausgegeben wird.
Sei \(B\) der größte geprüfte Kandidat, bis die ersten \(k\) Primzahlen mit Endziffer \(7\) gefunden sind. Bei Probedivision kostet jeder Primzahltest \(O(\sqrt{n})\), daher dominiert die Primzahlerzeugung und lässt sich im einfachsten Worst-Case mit \(O(B^{3/2})\) abschätzen. Die modularen Produkte für \(P_k\) und \(\Phi_k\) brauchen \(O(k)\) Zeit, und die Binomialschleife benötigt \(O(k\log M)\), da jedes modulare Inverse per schneller Potenzierung berechnet wird. Der Speicherbedarf ist \(O(k)\).
Problem 773 için uygulamalar önce son basamağı \(7\) olan ilk \(k\) asal sayıyı alır. Ardından aranan değer, büyük bir çarpımsal ana terim ile küçük bir onluk basamak düzeltmesinin birleştiği bir dahil et-çıkar hesabına indirgenir. Bu indirgeme yapıldıktan sonra sonuç yalnızca bu asalların çarpımına, bu çarpımın Euler totient değerine ve periyodu \(4\) olan kısa bir alternanslı binom toplamına bağlıdır.
Şöyle tanımlayalım:
$$p_1,p_2,\dots,p_k$$
son basamağı \(7\) olan ilk \(k\) asal sayı olsun; yani
$$p_i \equiv 7 \pmod{10}.$$
İki temel çarpımı şöyle tanımlayalım:
$$P_k=\prod_{i=1}^k p_i,\qquad \Phi_k=\prod_{i=1}^k (p_i-1).$$
Asallar birbirinden farklı olduğundan
$$\Phi_k=\varphi(P_k)$$
eşitliği doğrudan geçerlidir.
Uygulamaların kullandığı türetilmiş sayım formülü, her dahil et-çıkar katkısını iki parçaya böler: büyük ve düzenli bir ana terim ile küçük bir basamak düzeltmesi. Ana terim tüm alt kümeler üzerinden
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i$$
şeklindeki toplamı verir; burada \(S\subseteq \{1,\dots,k\}\) tüm alt kümeleri temsil eder. Bu toplam standart bir çarpım açılımıdır ve
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i=\prod_{i=1}^k (p_i-1)=\Phi_k$$
olarak çarpanlarına ayrılır. Nihai formülde bu parçanın önünde \(5\) katsayısı bulunduğu için baskın katkı \(5\Phi_k\) olur.
Probleme özgü düzeltme, seçilen asalların çarpımının son basamağına bağlıdır. Bir alt kümenin boyu \(t\) ise, bu alt kümenin çarpımı modulo \(10\)
$$7^t \pmod{10}$$
olur. \(7\)'nin mod \(10\) kuvvetleri dönemli davranır:
$$7^0\equiv 1,\quad 7^1\equiv 7,\quad 7^2\equiv 9,\quad 7^3\equiv 3 \pmod{10}.$$
İlgili çarpanı tekrar sonu \(7\) ile biten sınıfa getirmek için çarpanın diğer tarafındaki katsayının
$$m \equiv 7\cdot (7^t)^{-1} \pmod{10}$$
koşulunu sağlaması gerekir. Mod \(10\) altında terslenebilir kalanların tersleri
$$1^{-1}\equiv 1,\qquad 7^{-1}\equiv 3,\qquad 9^{-1}\equiv 9,\qquad 3^{-1}\equiv 7 \pmod{10}$$
olduğundan düzeltme dizisi
$$w_0=7,\qquad w_1=1,\qquad w_2=3,\qquad w_3=9$$
şeklinde çıkar ve her dört adımda bir tekrar eder.
Kritik nokta, bu düzeltmenin yalnızca alt kümenin boyuna bağlı olmasıdır; hangi asalların seçildiği önemli değildir. Boyu \(t\) olan tam \(\binom{k}{t}\) adet alt küme vardır. Bu nedenle tüm düzeltme terimi
$$S_k=\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t$$
biçimine iner. Burada \(w_t\) periyodik yorumlanır:
$$w_t=w_{t\bmod 4}\in \{7,1,3,9\}.$$
Böylece üstel sayıda alt kümeyi ayrı ayrı dolaşmak yerine tek bir kısa binom toplamı yeterli olur.
Ana çarpımsal parça ile basamak düzeltmesini birleştirince uygulamaların hesapladığı kesin ifade elde edilir:
$$R_k \equiv P_k\left(5\Phi_k + S_k\right)\pmod{10^9+7}.$$
Tanımları açık yazarsak
$$\boxed{R_k \equiv \left(\prod_{i=1}^k p_i\right)\left(5\prod_{i=1}^k (p_i-1)+\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t\right)\pmod{10^9+7}.}$$
Yani gerekli asallar bulunduktan sonra kalan her şey saf modüler aritmetiktir.
Sonu \(7\) ile biten ilk üç asal
$$7,\ 17,\ 37$$
olur. Dolayısıyla
$$P_3=7\cdot 17\cdot 37=4403,$$
ve
$$\Phi_3=(7-1)(17-1)(37-1)=6\cdot 16\cdot 36=3456.$$
Düzeltme toplamı da
$$\begin{aligned} S_3&=\binom{3}{0}7-\binom{3}{1}1+\binom{3}{2}3-\binom{3}{3}9\\ &=7-3+9-9\\ &=4 \end{aligned}$$
olur. Sonuç olarak
$$R_3=4403\left(5\cdot 3456+4\right)=4403\cdot 17284=76101452,$$
ki bu değer uygulamalardaki kontrol sonucuyla aynıdır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce \(7,17,27,\dots\) dizisi taranır ve yalnızca asal olan terimler tutulur. Asallık testi, \(\sqrt{n}\)'e kadar deneme bölmesiyle yapıldığı için kod basittir ve gereken \(k\) değeri küçük olduğundan yeterince hızlıdır.
Daha sonra bu asallar mod \(10^9+7\) altında çarpılarak \(P_k\) elde edilir. Aynı döngüde \(p_i-1\) terimleri de mod altında çarpılarak \(\Phi_k\) hesaplanır.
Ardından binom düzeltmesi \(S_k\) hesaplanır. Faktöriyel tablosu kurmak yerine binom katsayıları
$$\binom{k}{t+1}=\binom{k}{t}\frac{k-t}{t+1}$$
bağıntısıyla iteratif güncellenir. Modüler bölme ise
$$a^{-1}\equiv a^{M-2}\pmod{M},\qquad M=10^9+7$$
eşitliğiyle, yani hızlı üs alma kullanılarak yapılır. Alternanslı işaret, periodik \(w_t\) tablosu ve son çarpım bir araya geldiğinde cevap mod \(10^9+7\) altında elde edilir. Uygulamalardan biri ayrıca \(k=3\) için yukarıdaki kontrol değerini doğrular.
\(k\) adet asal toplamak için bakılan en büyük aday \(B\) olsun. Deneme bölmesi kullanılan asallık testinde tek bir adayın maliyeti \(O(\sqrt{n})\) olduğundan, en kaba üst sınırla asal üretimi \(O(B^{3/2})\) civarında davranır ve toplam sürede baskın kısım budur. \(P_k\) ve \(\Phi_k\) çarpımları \(O(k)\) zamanda hesaplanır. Binom düzeltme döngüsü ise her modüler tersi hızlı üs alma ile bulduğu için \(O(k\log M)\) zamanda çalışır. Bellek kullanımı saklanan asal listesi nedeniyle \(O(k)\)'dır.
En el Problema 773, las implementaciones empiezan con los primeros \(k\) primos cuya última cifra es \(7\). A partir de ahí, la cantidad buscada se reduce a una cuenta por inclusión-exclusión donde un término multiplicativo grande recibe una corrección pequeña ligada a clases de residuos decimales. Tras esa reducción, la respuesta depende solo del producto de esos primos, de la función totiente de ese producto y de una suma binomial alternada muy corta con período \(4\).
Sean
$$p_1,p_2,\dots,p_k$$
los primeros \(k\) primos tales que
$$p_i \equiv 7 \pmod{10}.$$
Definimos
$$P_k=\prod_{i=1}^k p_i,\qquad \Phi_k=\prod_{i=1}^k (p_i-1).$$
Como los primos son distintos, se cumple inmediatamente
$$\Phi_k=\varphi(P_k).$$
La fórmula derivada que usan las implementaciones divide cada contribución de inclusión-exclusión en una parte grande y uniforme, más una corrección decimal pequeña. La parte principal lleva a la suma
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i,$$
donde \(S\subseteq \{1,\dots,k\}\) recorre todos los subconjuntos. Esta suma se factoriza de forma directa, porque cada primo aporta o bien \(p_i\) o bien \(-1\):
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i=\prod_{i=1}^k (p_i-1)=\Phi_k.$$
En la expresión final este bloque aparece multiplicado por \(5\), de modo que el término dominante es \(5\Phi_k\).
La corrección específica del problema depende solo de la última cifra del producto de los primos seleccionados. Si un subconjunto tiene tamaño \(t\), entonces su producto es congruente con
$$7^t \pmod{10}.$$
Las potencias de \(7\) módulo \(10\) son periódicas con período \(4\):
$$7^0\equiv 1,\quad 7^1\equiv 7,\quad 7^2\equiv 9,\quad 7^3\equiv 3 \pmod{10}.$$
Para devolver el factor relevante a la clase que termina en \(7\), el multiplicador debe satisfacer
$$m \equiv 7\cdot (7^t)^{-1} \pmod{10}.$$
Como las inversas de las clases invertibles módulo \(10\) son
$$1^{-1}\equiv 1,\qquad 7^{-1}\equiv 3,\qquad 9^{-1}\equiv 9,\qquad 3^{-1}\equiv 7 \pmod{10},$$
aparece la sucesión periódica
$$w_0=7,\qquad w_1=1,\qquad w_2=3,\qquad w_3=9,$$
que luego vuelve a empezar cada cuatro pasos.
La simplificación crucial es que la corrección depende únicamente del tamaño \(t\) del subconjunto, no de cuáles primos concretos contiene. Existen exactamente \(\binom{k}{t}\) subconjuntos de tamaño \(t\), así que toda la corrección se resume en
$$S_k=\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t,$$
entendiendo \(w_t\) de forma periódica:
$$w_t=w_{t\bmod 4}\in \{7,1,3,9\}.$$
Por eso el programa no necesita enumerar subconjuntos: basta una suma binomial corta.
Al combinar la parte multiplicativa con la corrección decimal se obtiene exactamente la cantidad calculada por las implementaciones:
$$R_k \equiv P_k\left(5\Phi_k + S_k\right)\pmod{10^9+7}.$$
Es decir, de forma explícita,
$$\boxed{R_k \equiv \left(\prod_{i=1}^k p_i\right)\left(5\prod_{i=1}^k (p_i-1)+\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t\right)\pmod{10^9+7}.}$$
Una vez conocida la lista de primos, el resto del trabajo es aritmética modular directa.
Los tres primeros primos que terminan en \(7\) son
$$7,\ 17,\ 37.$$
Por tanto,
$$P_3=7\cdot 17\cdot 37=4403,$$
y
$$\Phi_3=(7-1)(17-1)(37-1)=6\cdot 16\cdot 36=3456.$$
La suma de corrección vale
$$\begin{aligned} S_3&=\binom{3}{0}7-\binom{3}{1}1+\binom{3}{2}3-\binom{3}{3}9\\ &=7-3+9-9\\ &=4. \end{aligned}$$
Entonces
$$R_3=4403\left(5\cdot 3456+4\right)=4403\cdot 17284=76101452,$$
que coincide con la comprobación incluida en las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero recorren la progresión aritmética \(7,17,27,\dots\) y conservan solo los términos que pasan una prueba elemental de primalidad por división de prueba hasta \(\sqrt{n}\). Dado que el valor de \(k\) es pequeño, ese enfoque basta sin dificultad.
Después calculan \(P_k\) multiplicando los primos módulo \(10^9+7\), y en paralelo calculan \(\Phi_k\) multiplicando los factores \(p_i-1\) bajo el mismo módulo.
La siguiente etapa evalúa la suma \(S_k\). En lugar de usar factoriales, el coeficiente binomial se actualiza con
$$\binom{k}{t+1}=\binom{k}{t}\frac{k-t}{t+1}.$$
La división modular se realiza mediante inversas modulares:
$$a^{-1}\equiv a^{M-2}\pmod{M},\qquad M=10^9+7.$$
Con el signo alternado y la tabla periódica \(7,1,3,9\), el programa acumula la corrección y finalmente multiplica \(P_k\) por \(5\Phi_k+S_k\) módulo \(10^9+7\). Una de las implementaciones también verifica el caso \(k=3\) antes de calcular el valor final para \(k=97\).
Sea \(B\) el mayor candidato examinado hasta reunir los primeros \(k\) primos que terminan en \(7\). Con división de prueba, cada test de primalidad cuesta \(O(\sqrt{n})\), así que la generación de primos domina el tiempo total y puede acotarse de forma simple por \(O(B^{3/2})\). Los productos modulares que forman \(P_k\) y \(\Phi_k\) cuestan \(O(k)\), mientras que el bucle binomial cuesta \(O(k\log M)\) porque cada inversa modular se obtiene por exponenciación rápida. La memoria es \(O(k)\) para almacenar la lista de primos.
对于第 773 题，三种实现都先取出最后一位是 \(7\) 的前 \(k\) 个素数。接着，题目所需的量被改写成一个包含容斥结构的表达式：主体是一个很大的乘法型项，另外再加上一个很小的十进制尾数修正项。完成这一步之后，答案只依赖于这些素数的乘积、该乘积的欧拉函数值，以及一个周期为 \(4\) 的短交错二项式和。
设
$$p_1,p_2,\dots,p_k$$
是满足
$$p_i \equiv 7 \pmod{10}$$
的前 \(k\) 个素数。定义
$$P_k=\prod_{i=1}^k p_i,\qquad \Phi_k=\prod_{i=1}^k (p_i-1).$$
由于这些素数互不相同，所以
$$\Phi_k=\varphi(P_k).$$
也就是说，\(\Phi_k\) 恰好就是 \(P_k\) 的欧拉函数。
实现中使用的推导公式把每一个容斥贡献拆成两部分：一部分是规模较大的统一主项，另一部分是只和十进制末位有关的小修正。主项可以写成对所有子集 \(S\subseteq \{1,\dots,k\}\) 的求和：
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i.$$
这个式子其实就是一个标准的乘积展开。对每个素数 \(p_i\) 而言，在展开时只有两种选择：要么保留 \(p_i\)，要么取到 \(-1\)。因此整个和式直接因式分解为
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i=\prod_{i=1}^k (p_i-1)=\Phi_k.$$
最终公式里这个部分还会再乘上 \(5\)，所以主导项就是 \(5\Phi_k\)。这也解释了为什么答案的主体规模与 \(\varphi(P_k)\) 非常接近。
题目特有的修正来自“末位为 \(7\)”这一十进制条件。若某个子集的大小是 \(t\)，那么其中所有被选中的素数都满足 \(p\equiv 7 \pmod{10}\)，所以该子集对应的乘积末位只取决于 \(t\)：
$$7^t \pmod{10}.$$
模 \(10\) 下，\(7\) 的幂有长度为 \(4\) 的循环：
$$7^0\equiv 1,\quad 7^1\equiv 7,\quad 7^2\equiv 9,\quad 7^3\equiv 3 \pmod{10}.$$
如果要让相关的倍数重新落回“末位是 \(7\)”这一类，那么配套的乘子必须满足
$$m \equiv 7\cdot (7^t)^{-1} \pmod{10}.$$
而模 \(10\) 下可逆的四个奇数剩余类 \(1,3,7,9\) 的逆元分别是
$$1^{-1}\equiv 1,\qquad 7^{-1}\equiv 3,\qquad 9^{-1}\equiv 9,\qquad 3^{-1}\equiv 7 \pmod{10}.$$
于是修正序列就变成
$$w_0=7,\qquad w_1=1,\qquad w_2=3,\qquad w_3=9,$$
之后每四项重复一次。这正是代码里那组长度为 \(4\) 的循环系数的来源。
这里最关键的观察是：修正量只依赖于子集大小 \(t\)，并不依赖于具体选中了哪些素数。大小为 \(t\) 的子集一共有
$$\binom{k}{t}$$
个，所以所有修正项可以直接合并为
$$S_k=\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t,$$
其中 \(w_t\) 按周期 \(4\) 理解：
$$w_t=w_{t\bmod 4}\in \{7,1,3,9\}.$$
这一步非常重要，因为它把原本看起来像是指数级的子集问题压缩成了一个长度只有 \(k+1\) 的一维求和。
把乘法主项和十进制修正项合并起来，就得到实现真正计算的公式：
$$R_k \equiv P_k\left(5\Phi_k + S_k\right)\pmod{10^9+7}.$$
把定义完全展开，就是
$$\boxed{R_k \equiv \left(\prod_{i=1}^k p_i\right)\left(5\prod_{i=1}^k (p_i-1)+\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t\right)\pmod{10^9+7}.}$$
因此，一旦把需要的素数表生成出来，剩余工作就只剩模运算、二项系数递推和快速幂求逆。
末位为 \(7\) 的前三个素数是
$$7,\ 17,\ 37.$$
所以
$$P_3=7\cdot 17\cdot 37=4403,$$
并且
$$\Phi_3=(7-1)(17-1)(37-1)=6\cdot 16\cdot 36=3456.$$
修正和则是
$$\begin{aligned} S_3&=\binom{3}{0}7-\binom{3}{1}1+\binom{3}{2}3-\binom{3}{3}9\\ &=7-3+9-9\\ &=4. \end{aligned}$$
于是
$$R_3=4403\left(5\cdot 3456+4\right)=4403\cdot 17284=76101452.$$
这个值正好就是实现里用于核对的小样例结果，因此它既能验证公式，也能验证程序流程。
C++、Python 和 Java 三份实现的步骤完全一致。第一步是枚举等差数列 \(7,17,27,\dots\)，只保留其中的素数。判素方法采用最直接的试除法，只检查到 \(\sqrt{n}\) 为止；因为目标只需要前 \(97\) 个这样的素数，所以这个做法已经足够。
拿到素数列表之后，程序一边把这些素数在模 \(10^9+7\) 下连乘，得到 \(P_k\)；一边把每个 \(p_i-1\) 在同一模数下连乘，得到 \(\Phi_k\)。
接下来程序计算修正和 \(S_k\)。它不会去预处理阶乘，而是利用递推公式
$$\binom{k}{t+1}=\binom{k}{t}\frac{k-t}{t+1}$$
按顺序更新二项系数。由于模数是素数，除法通过费马小定理转成逆元幂：
$$a^{-1}\equiv a^{M-2}\pmod{M},\qquad M=10^9+7.$$
配合交替正负号以及周期为 \(4\) 的系数表，程序即可在线累加出 \(S_k\)，最后再把 \(P_k\) 与 \(5\Phi_k+S_k\) 相乘并取模。某一份实现还额外检查了上面的 \(k=3\) 数值，以便确认公式和代码没有偏差。
设收集到前 \(k\) 个末位为 \(7\) 的素数时，枚举到的最大候选数为 \(B\)。在试除判素中，每个候选数的成本是 \(O(\sqrt{n})\)，因此质数生成阶段是主要耗时，在最粗略的估计下可记为 \(O(B^{3/2})\)。之后计算 \(P_k\) 与 \(\Phi_k\) 只需 \(O(k)\) 时间；二项修正循环因为每一步都要通过快速幂求一次模逆，所以成本是 \(O(k\log M)\)。额外空间主要是存放素数列表，因此为 \(O(k)\)。
В задаче 773 все реализации сначала берут первые \(k\) простых чисел, оканчивающихся на цифру \(7\). После этого искомая величина сводится к формуле включений-исключений, где большой мультипликативный вклад дополняется небольшой поправкой, связанной с десятичным остатком. В результате ответ выражается только через произведение этих простых, функцию Эйлера от этого произведения и короткую знакопеременную биномиальную сумму с периодом \(4\).
Пусть
$$p_1,p_2,\dots,p_k$$
обозначают первые \(k\) простых чисел, для которых
$$p_i \equiv 7 \pmod{10}.$$
Введем обозначения
$$P_k=\prod_{i=1}^k p_i,\qquad \Phi_k=\prod_{i=1}^k (p_i-1).$$
Так как простые различны, имеем
$$\Phi_k=\varphi(P_k).$$
Формула, лежащая в основе реализации, раскладывает каждый вклад включений-исключений на большую регулярную часть и маленькую десятичную поправку. Основная часть приводит к сумме по всем подмножествам \(S\subseteq \{1,\dots,k\}\):
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i.$$
Это стандартное произведение-раскрытие: для каждого простого \(p_i\) при разложении выбирается либо \(p_i\), либо \(-1\). Поэтому вся сумма факторизуется в
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i=\prod_{i=1}^k (p_i-1)=\Phi_k.$$
В итоговой формуле этот блок умножается на \(5\), поэтому доминирующий член равен \(5\Phi_k\).
Поправка определяется только последней цифрой произведения выбранных простых. Если размер подмножества равен \(t\), то произведение его элементов сравнимо с
$$7^t \pmod{10}.$$
Степени числа \(7\) по модулю \(10\) цикличны с периодом \(4\):
$$7^0\equiv 1,\quad 7^1\equiv 7,\quad 7^2\equiv 9,\quad 7^3\equiv 3 \pmod{10}.$$
Чтобы соответствующий множитель снова попадал в класс чисел, оканчивающихся на \(7\), он должен удовлетворять
$$m \equiv 7\cdot (7^t)^{-1} \pmod{10}.$$
У обратимых классов по модулю \(10\) обратные элементы таковы:
$$1^{-1}\equiv 1,\qquad 7^{-1}\equiv 3,\qquad 9^{-1}\equiv 9,\qquad 3^{-1}\equiv 7 \pmod{10}.$$
Отсюда получается периодическая последовательность
$$w_0=7,\qquad w_1=1,\qquad w_2=3,\qquad w_3=9,$$
которая затем повторяется через каждые четыре шага.
Главное упрощение состоит в том, что поправка зависит только от размера подмножества \(t\), а не от конкретного выбора простых. Подмножеств размера \(t\) ровно \(\binom{k}{t}\), поэтому вся поправка сводится к сумме
$$S_k=\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t,$$
где \(w_t\) понимается периодически:
$$w_t=w_{t\bmod 4}\in \{7,1,3,9\}.$$
Именно поэтому в коде достаточно короткой таблицы длины \(4\), а не перебора всех подмножеств.
Объединяя основной мультипликативный член и десятичную поправку, получаем точную величину, вычисляемую программой:
$$R_k \equiv P_k\left(5\Phi_k + S_k\right)\pmod{10^9+7}.$$
В полностью раскрытом виде это
$$\boxed{R_k \equiv \left(\prod_{i=1}^k p_i\right)\left(5\prod_{i=1}^k (p_i-1)+\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t\right)\pmod{10^9+7}.}$$
После построения списка нужных простых оставшаяся часть задачи становится чистой модульной арифметикой.
Первые три простых, оканчивающихся на \(7\), равны
$$7,\ 17,\ 37.$$
Следовательно,
$$P_3=7\cdot 17\cdot 37=4403,$$
а также
$$\Phi_3=(7-1)(17-1)(37-1)=6\cdot 16\cdot 36=3456.$$
Поправка равна
$$\begin{aligned} S_3&=\binom{3}{0}7-\binom{3}{1}1+\binom{3}{2}3-\binom{3}{3}9\\ &=7-3+9-9\\ &=4. \end{aligned}$$
Поэтому
$$R_3=4403\left(5\cdot 3456+4\right)=4403\cdot 17284=76101452,$$
что совпадает с контрольным значением, используемым в реализациях.
Реализации на C++, Python и Java устроены одинаково. Сначала они перебирают арифметическую прогрессию \(7,17,27,\dots\) и оставляют только простые числа. Проверка простоты выполняется простым пробным делением до \(\sqrt{n}\); для требуемого здесь значения \(k\) этого вполне достаточно.
После получения списка простых программа перемножает их по модулю \(10^9+7\), получая \(P_k\), и параллельно перемножает величины \(p_i-1\), получая \(\Phi_k\).
Затем вычисляется биномиальная поправка \(S_k\). Вместо предварительного вычисления факториалов коэффициент \(\binom{k}{t}\) обновляется по рекуррентной формуле
$$\binom{k}{t+1}=\binom{k}{t}\frac{k-t}{t+1}.$$
Деление по модулю простого числа выполняется через модульный обратный элемент:
$$a^{-1}\equiv a^{M-2}\pmod{M},\qquad M=10^9+7.$$
С учетом чередующегося знака и периодической последовательности \(7,1,3,9\) программа накапливает \(S_k\), после чего умножает \(P_k\) на \(5\Phi_k+S_k\) по модулю \(10^9+7\). В одной из реализаций также проверяется случай \(k=3\), приведенный выше.
Пусть \(B\) обозначает наибольший кандидат, просмотренный до того, как были найдены первые \(k\) простых с последней цифрой \(7\). При пробном делении проверка одного числа занимает \(O(\sqrt{n})\), поэтому именно этап генерации простых доминирует по времени и в грубой верхней оценке дает \(O(B^{3/2})\). Вычисление произведений \(P_k\) и \(\Phi_k\) требует \(O(k)\) времени. Биномиальный цикл стоит \(O(k\log M)\), так как каждое модульное обратное находится быстрым возведением в степень. Память составляет \(O(k)\) на хранение списка простых.
في المسألة 773 تبدأ جميع التطبيقات بأول \(k\) أعداد أولية تنتهي بالرقم \(7\). بعد ذلك تُختزل الكمية المطلوبة إلى صيغة تعتمد على مبدأ الشمول والاستبعاد، حيث يوجد حد ضربي رئيسي كبير وتصحيح صغير مرتبط ببواقي الأعداد في النظام العشري. وبعد هذا الاختزال تصبح الإجابة معتمدة فقط على حاصل ضرب تلك الأعداد الأولية، وعلى قيمة دالة أويلر لذلك الحاصل، وعلى مجموع ثنائي متناوب قصير دوريته \(4\).
لتكن
$$p_1,p_2,\dots,p_k$$
هي أول \(k\) أعداد أولية تحقق
$$p_i \equiv 7 \pmod{10}.$$
ونعرّف
$$P_k=\prod_{i=1}^k p_i,\qquad \Phi_k=\prod_{i=1}^k (p_i-1).$$
وبما أن هذه الأعداد الأولية مختلفة، فإن
$$\Phi_k=\varphi(P_k).$$
الصيغة المستخلصة التي تستخدمها التطبيقات تقسّم كل مساهمة في الشمول والاستبعاد إلى جزأين: جزء رئيسي كبير ومنتظم، وتصحيح عشري صغير. الجزء الرئيسي يقود إلى المجموع
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i,$$
حيث تمر \(S\subseteq \{1,\dots,k\}\) على جميع المجموعات الجزئية. هذا مجموع قياسي يمكن تفكيكه مباشرة، لأن كل عدد أولي \(p_i\) يساهم إما بالعامل \(p_i\) أو بالعامل \(-1\). لذلك نحصل على
$$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i=\prod_{i=1}^k (p_i-1)=\Phi_k.$$
وفي الصيغة النهائية يظهر هذا الجزء مضروبًا في \(5\)، ولهذا يكون الحد المسيطر هو \(5\Phi_k\).
التصحيح الخاص بالمسألة يعتمد فقط على الرقم الأخير لحاصل ضرب الأعداد الأولية المختارة. إذا كان حجم المجموعة الجزئية يساوي \(t\)، فإن حاصل ضرب عناصرها يساوي
$$7^t \pmod{10}.$$
وقوى العدد \(7\) بترديد \(10\) دورية بطول \(4\):
$$7^0\equiv 1,\quad 7^1\equiv 7,\quad 7^2\equiv 9,\quad 7^3\equiv 3 \pmod{10}.$$
ولكي يعود العامل المرتبط بهذه المساهمة إلى الفئة التي تنتهي بالرقم \(7\)، يجب أن يحقق المضروب الآخر
$$m \equiv 7\cdot (7^t)^{-1} \pmod{10}.$$
ومعكوسات البواقي القابلة للعكس modulo \(10\) هي
$$1^{-1}\equiv 1,\qquad 7^{-1}\equiv 3,\qquad 9^{-1}\equiv 9,\qquad 3^{-1}\equiv 7 \pmod{10}.$$
ومن هنا نحصل على المتتالية الدورية
$$w_0=7,\qquad w_1=1,\qquad w_2=3,\qquad w_3=9,$$
ثم تتكرر هذه القيم كل أربع خطوات.
الملاحظة الأساسية هي أن هذا التصحيح يعتمد فقط على حجم المجموعة الجزئية \(t\)، وليس على العناصر المختارة نفسها. وعدد المجموعات الجزئية ذات الحجم \(t\) هو
$$\binom{k}{t}.$$
لذلك يمكن كتابة كامل حد التصحيح على الصورة
$$S_k=\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t,$$
مع تفسير \(w_t\) تفسيرًا دوريًا:
$$w_t=w_{t\bmod 4}\in \{7,1,3,9\}.$$
وهذا هو السبب في أن التنفيذ لا يحتاج إلى استعراض جميع المجموعات الجزئية، بل يكتفي بمجموع ثنائي واحد قصير.
عند جمع الجزء الضربي الرئيسي مع التصحيح العشري نحصل على الكمية نفسها التي تحسبها التطبيقات:
$$R_k \equiv P_k\left(5\Phi_k + S_k\right)\pmod{10^9+7}.$$
وبصورة موسعة تصبح الصيغة
$$\boxed{R_k \equiv \left(\prod_{i=1}^k p_i\right)\left(5\prod_{i=1}^k (p_i-1)+\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t\right)\pmod{10^9+7}.}$$
أي إن الجزء الصعب من المسألة ينحصر في توليد الأعداد الأولية المناسبة، ثم تنفيذ حساب معياري مباشر.
أول ثلاثة أعداد أولية تنتهي بالرقم \(7\) هي
$$7,\ 17,\ 37.$$
إذن
$$P_3=7\cdot 17\cdot 37=4403,$$
وكذلك
$$\Phi_3=(7-1)(17-1)(37-1)=6\cdot 16\cdot 36=3456.$$
أما مجموع التصحيح فيساوي
$$\begin{aligned} S_3&=\binom{3}{0}7-\binom{3}{1}1+\binom{3}{2}3-\binom{3}{3}9\\ &=7-3+9-9\\ &=4. \end{aligned}$$
ومن ثم
$$R_3=4403\left(5\cdot 3456+4\right)=4403\cdot 17284=76101452,$$
وهو نفس مقدار التحقق الصغير المستخدم داخل التطبيقات.
التطبيقات في C++ وPython وJava تتبع الخطوات نفسها. تبدأ بمسح المتتالية الحسابية \(7,17,27,\dots\)، ثم تحتفظ فقط بالقيم الأولية. اختبار الأولية المستخدم بسيط ويعتمد على القسمة التجريبية حتى \(\sqrt{n}\)، وهو كافٍ هنا لأن قيمة \(k\) المطلوبة صغيرة.
بعد بناء قائمة الأعداد الأولية، يحسب التنفيذ حاصل الضرب \(P_k\) modulo \(10^9+7\)، وفي الوقت نفسه يحسب \(\Phi_k\) عبر ضرب الحدود \(p_i-1\) تحت نفس المعيار.
ثم يأتي دور مجموع التصحيح \(S_k\). بدلًا من استعمال مضروبات جاهزة، يتم تحديث المعامل الثنائي تدريجيًا بواسطة
$$\binom{k}{t+1}=\binom{k}{t}\frac{k-t}{t+1}.$$
أما القسمة المعيارية فتُنفَّذ باستخدام المعكوس المعياري
$$a^{-1}\equiv a^{M-2}\pmod{M},\qquad M=10^9+7.$$
ومع الإشارة المتناوبة والجدول الدوري \(7,1,3,9\)، تتكوّن قيمة \(S_k\)، ثم تُضرب في النهاية داخل \(P_k(5\Phi_k+S_k)\) modulo \(10^9+7\). كما أن إحدى التطبيقات تتحقق أولًا من حالة \(k=3\) السابقة قبل حساب القيمة النهائية عند \(k=97\).
لنرمز بـ \(B\) إلى أكبر مرشح جرى فحصه أثناء جمع أول \(k\) أعداد أولية تنتهي بالرقم \(7\). مع اختبار أولية يعتمد على القسمة التجريبية، تكون كلفة فحص مرشح واحد \(O(\sqrt{n})\)، ولذلك تظل مرحلة توليد الأعداد الأولية هي الجزء المسيطر زمنيًا، ويمكن تقديرها في أبسط حد علوي على أنها \(O(B^{3/2})\). أما بناء \(P_k\) و\(\Phi_k\) فيكلف \(O(k)\)، وحلقة المجموع الثنائي تكلف \(O(k\log M)\) لأن كل معكوس معياري يُحسب بالأس السريع. الذاكرة المطلوبة هي \(O(k)\) بسبب تخزين قائمة الأعداد الأولية.