For a prime \(p\) and an integer \(q\), let \(A_q(p)\) denote the number of \(p\)-element subsets of \(\{1,2,\dots,qp\}\) whose element-sum is divisible by \(p\). Problem 635 asks for
$$\sum_{p\le 10^8}\bigl(A_2(p)+A_3(p)\bigr)\pmod{10^9+9}.$$
A direct subset search is hopeless: even for a single large prime, the number of candidate subsets is astronomically large. The solution works because, for prime moduli, the counting problem collapses to compact closed forms involving binomial coefficients.
The main task is to count \(p\)-element subsets whose sum is congruent to \(0 \pmod p\). A roots-of-unity filter extracts exactly those sums, and the residue pattern of \(\{1,\dots,qp\}\) makes the nontrivial filter terms identical.
Fix \(q\in\{2,3\}\) and a prime \(p\). Consider the bivariate generating function
$$F_q(x,y)=\prod_{n=1}^{qp}(1+y x^n).$$
Choosing the term \(y x^n\) means that \(n\) is included in the subset; choosing \(1\) means it is omitted. Therefore the coefficient of \(y^k x^m\) counts \(k\)-element subsets with total sum \(m\).
In particular, \(A_q(p)\) is obtained by taking \(k=p\) and summing only those coefficients whose exponent of \(x\) is a multiple of \(p\).
Let \(\omega\) be a primitive \(p\)-th root of unity. The standard identity
$$\frac{1}{p}\sum_{j=0}^{p-1}\omega^{jm}= \begin{cases} 1,& p\mid m,\\ 0,& p\nmid m \end{cases}$$
filters out exactly the exponents \(m\) that are divisible by \(p\). Hence
$$A_q(p)=\frac{1}{p}\sum_{j=0}^{p-1}[y^p]\prod_{n=1}^{qp}(1+y\omega^{jn}).$$
Now group the numbers \(1,2,\dots,qp\) by their residues modulo \(p\). Each residue class appears exactly \(q\) times, so when \(j\neq 0\), multiplication by \(j\) merely permutes the residue classes and we get
$$\prod_{n=1}^{qp}(1+y\omega^{jn})=\left(\prod_{r=0}^{p-1}(1+y\omega^r)\right)^q.$$
The cyclotomic product identity
$$\prod_{r=0}^{p-1}(1-t\omega^r)=1-t^p$$
gives, after substituting \(t=-y\),
$$\prod_{r=0}^{p-1}(1+y\omega^r)=1-(-y)^p.$$
Therefore every nonzero filter term contributes
$$[y^p](1-(-y)^p)^q.$$
If \(p\) is odd, then \(1-(-y)^p=1+y^p\), so the coefficient of \(y^p\) is simply \(q\). The \(j=0\) term is different: it is
$$[y^p](1+y)^{qp}=\binom{qp}{p}.$$
For every odd prime \(p\), the \(p-1\) nonzero filter terms all contribute \(q\). Combining them with the \(j=0\) term yields
$$A_q(p)=\frac{\binom{qp}{p}+q(p-1)}{p}.$$
Specializing to the two quantities in the problem gives
$$A_2(p)=\frac{\binom{2p}{p}+2(p-1)}{p},$$
$$A_3(p)=\frac{\binom{3p}{p}+3(p-1)}{p}$$
for every odd prime \(p\).
When \(p=2\), the same identity becomes
$$\prod_{r=0}^{1}(1+y\omega^r)=1-y^2,$$
so the nonzero filter term contributes \([y^2](1-y^2)^q=-q\) instead of \(+q\). Hence
$$A_q(2)=\frac{\binom{2q}{2}-q}{2}.$$
In particular,
$$A_2(2)=2,\qquad A_3(2)=6,$$
which explains why the implementation treats \(p=2\) separately.
For \(p=5\), both formulas apply directly:
$$A_2(5)=\frac{\binom{10}{5}+2\cdot 4}{5}=\frac{252+8}{5}=52,$$
$$A_3(5)=\frac{\binom{15}{5}+3\cdot 4}{5}=\frac{3003+12}{5}=603.$$
So the prime \(5\) contributes \(52+603=655\) to the final sum. As another useful checkpoint,
$$\sum_{p\le 10}A_2(p)=A_2(2)+A_2(3)+A_2(5)+A_2(7)=2+8+52+492=554,$$
which matches the internal verification used by the implementation.
The C++, Python, and Java implementations first sieve all primes up to \(10^8\). They never store complete factorial and inverse-factorial tables up to \(3\cdot 10^8\); that would be unnecessarily large. Instead, they keep only a few checkpoint values for each prime.
A forward scan computes factorials modulo \(10^9+9\) and records the values needed later at \(p-1\), \(2p\), and \(3p\). Then the implementation computes the inverse of \((3\cdot 10^8)!\) once using fast modular exponentiation and performs a backward scan to reconstruct inverse factorials, recording only the checkpoints at \(p\) and \(2p\).
Those saved values are enough to recover
$$\frac{1}{p}=\frac{(p-1)!}{p!},\qquad \binom{2p}{p}=\frac{(2p)!}{p!\,p!},\qquad \binom{3p}{p}=\frac{(3p)!}{p!\,(2p)!}$$
in constant time for each prime. The modulus is prime and larger than \(3\cdot 10^8\), so every factorial value in that range is invertible modulo \(10^9+9\). After reconstructing the binomial terms, the program applies the \(p=2\) special case or the odd-prime formula, adds the two contributions, and reduces modulo \(10^9+9\) throughout.
Let \(L=10^8\). The prime sieve costs \(O(L\log\log L)\) time. The forward factorial scan and the backward inverse-factorial scan both run to \(3L\), so they add \(O(L)\) time. Once the checkpoint tables are ready, each prime is processed in \(O(1)\) time. The overall running time is therefore \(O(L\log\log L)\).
Memory usage consists of an odd-only sieve plus a constant number of checkpoint arrays indexed by primes. Asymptotically this is \(O(L+\pi(L))\), and the important practical point is that the implementation avoids storing all factorials and inverse factorials up to \(3L\).
Für eine Primzahl \(p\) und eine ganze Zahl \(q\) bezeichne \(A_q(p)\) die Anzahl der \(p\)-elementigen Teilmengen von \(\{1,2,\dots,qp\}\), deren Elementsumme durch \(p\) teilbar ist. Gesucht ist also
$$\sum_{p\le 10^8}\bigl(A_2(p)+A_3(p)\bigr)\pmod{10^9+9}.$$
Eine direkte Aufzählung aller Kandidaten ist völlig unrealistisch. Der entscheidende Punkt ist, dass sich die Zählung für Primmoduli auf kompakte geschlossene Formeln mit Binomialkoeffizienten reduzieren lässt.
Wir zählen \(p\)-elementige Teilmengen mit Summe \(0 \pmod p\), indem wir eine erzeugende Funktion aufstellen und anschließend mit einem Einheitswurzelfilter genau die Vielfachen von \(p\) herausfiltern.
Fixiere \(q\in\{2,3\}\) und eine Primzahl \(p\). Betrachte die bivariate erzeugende Funktion
$$F_q(x,y)=\prod_{n=1}^{qp}(1+y x^n).$$
Wählt man den Faktor \(y x^n\), dann wird \(n\) in die Teilmenge aufgenommen; wählt man \(1\), dann nicht. Daher zählt der Koeffizient von \(y^k x^m\) die \(k\)-elementigen Teilmengen mit Gesamtsumme \(m\).
Für \(A_q(p)\) interessieren uns also genau die Koeffizienten mit \(k=p\) und \(m\equiv 0 \pmod p\).
Sei \(\omega\) eine primitive \(p\)-te Einheitswurzel. Dann gilt
$$\frac{1}{p}\sum_{j=0}^{p-1}\omega^{jm}= \begin{cases} 1,& p\mid m,\\ 0,& p\nmid m \end{cases}$$
und genau damit lassen sich die passenden Exponenten auswählen. Also
$$A_q(p)=\frac{1}{p}\sum_{j=0}^{p-1}[y^p]\prod_{n=1}^{qp}(1+y\omega^{jn}).$$
Nun gruppieren wir die Zahlen \(1,2,\dots,qp\) nach ihren Restklassen modulo \(p\). Jede Restklasse kommt genau \(q\)-mal vor. Für \(j\neq 0\) permutiert die Multiplikation mit \(j\) die Restklassen, sodass
$$\prod_{n=1}^{qp}(1+y\omega^{jn})=\left(\prod_{r=0}^{p-1}(1+y\omega^r)\right)^q$$
entsteht.
Mit der zyklotomischen Identität
$$\prod_{r=0}^{p-1}(1-t\omega^r)=1-t^p$$
folgt nach Einsetzen von \(t=-y\)
$$\prod_{r=0}^{p-1}(1+y\omega^r)=1-(-y)^p.$$
Damit liefert jeder nichtnullige Filterterm den Koeffizienten
$$[y^p](1-(-y)^p)^q.$$
Für ungerade Primzahlen ist \(1-(-y)^p=1+y^p\), also ist der Koeffizient von \(y^p\) einfach \(q\). Der Term \(j=0\) ist dagegen
$$[y^p](1+y)^{qp}=\binom{qp}{p}.$$
Für jede ungerade Primzahl \(p\) tragen die \(p-1\) nichtnulligen Filterterme jeweils \(q\) bei. Zusammen mit dem \(j=0\)-Term ergibt das
$$A_q(p)=\frac{\binom{qp}{p}+q(p-1)}{p}.$$
Für die beiden in der Aufgabe benötigten Fälle heißt das
$$A_2(p)=\frac{\binom{2p}{p}+2(p-1)}{p},$$
$$A_3(p)=\frac{\binom{3p}{p}+3(p-1)}{p}$$
für jede ungerade Primzahl \(p\).
Für \(p=2\) wird dieselbe Identität zu
$$\prod_{r=0}^{1}(1+y\omega^r)=1-y^2,$$
also liefert der nichtnullige Filterterm \([y^2](1-y^2)^q=-q\) statt \(+q\). Deshalb gilt
$$A_q(2)=\frac{\binom{2q}{2}-q}{2}.$$
Insbesondere erhält man
$$A_2(2)=2,\qquad A_3(2)=6,$$
genau die beiden Spezialwerte, die in der Implementierung separat behandelt werden.
Für \(p=5\) können wir die geschlossenen Formeln direkt einsetzen:
$$A_2(5)=\frac{\binom{10}{5}+2\cdot 4}{5}=\frac{252+8}{5}=52,$$
$$A_3(5)=\frac{\binom{15}{5}+3\cdot 4}{5}=\frac{3003+12}{5}=603.$$
Die Primzahl \(5\) trägt also insgesamt \(52+603=655\) zur Endsumme bei. Ein kleiner Kontrollwert ist außerdem
$$\sum_{p\le 10}A_2(p)=A_2(2)+A_2(3)+A_2(5)+A_2(7)=2+8+52+492=554,$$
und genau dieser Wert wird intern von der Implementierung überprüft.
Die Implementierungen in C++, Python und Java sieben zunächst alle Primzahlen bis \(10^8\). Anschließend speichern sie aber nicht komplette Fakultäts- und Inversfakultätstabellen bis \(3\cdot 10^8\); das wäre zu groß. Stattdessen werden nur wenige Kontrollpunkte pro Primzahl gesichert.
Ein Vorwärtslauf berechnet Fakultäten modulo \(10^9+9\) und merkt sich nur die Werte bei \(p-1\), \(2p\) und \(3p\). Danach wird das Inverse von \((3\cdot 10^8)!\) einmal mit schneller modularer Potenzierung bestimmt. Ein Rückwärtslauf rekonstruiert daraus die Inversfakultäten und speichert nur die Kontrollpunkte bei \(p\) und \(2p\).
Diese gespeicherten Werte reichen aus, um
$$\frac{1}{p}=\frac{(p-1)!}{p!},\qquad \binom{2p}{p}=\frac{(2p)!}{p!\,p!},\qquad \binom{3p}{p}=\frac{(3p)!}{p!\,(2p)!}$$
für jede Primzahl in konstanter Zeit zurückzugewinnen. Das Modulo ist prim und größer als \(3\cdot 10^8\), also ist jeder dabei auftretende Fakultätswert modulo \(10^9+9\) invertierbar. Danach wendet das Programm entweder den Sonderfall \(p=2\) oder die Formel für ungerade Primzahlen an und akkumuliert die Beiträge fortlaufend modulo \(10^9+9\).
Mit \(L=10^8\) kostet das Primzahlsieb \(O(L\log\log L)\) Zeit. Der Vorwärtslauf für die Fakultäten und der Rückwärtslauf für die Inversfakultäten laufen beide bis \(3L\) und addieren damit \(O(L)\) Zeit. Ist die Kontrollpunktstruktur vorbereitet, wird jede Primzahl in \(O(1)\) verarbeitet. Insgesamt ergibt sich also eine Laufzeit von \(O(L\log\log L)\).
Der Speicherbedarf besteht aus einem ungeraden Sieb und einigen wenigen, nach Primzahlen indizierten Kontrollpunkt-Arrays. Asymptotisch ist das \(O(L+\pi(L))\). Der praktische Gewinn besteht darin, dass gerade keine vollständigen Fakultäts- und Inversfakultätstabellen bis \(3L\) gespeichert werden.
Bir asal \(p\) ve bir tam sayı \(q\) için \(A_q(p)\), \(\{1,2,\dots,qp\}\) kümesinin eleman toplamı \(p\)'ye bölünen \(p\)-elemanlı alt kümelerinin sayısı olsun. Problem 635 şu toplamı ister:
$$\sum_{p\le 10^8}\bigl(A_2(p)+A_3(p)\bigr)\pmod{10^9+9}.$$
Doğrudan alt küme üretmek mümkün değildir; tek bir büyük asal için bile aday sayısı astronomiktir. Çözümün işe yaramasının nedeni, asal modüllerde sayımın binom katsayılarına dayanan kapalı formüllere indirgenebilmesidir.
Amaç, toplamı \(0 \pmod p\) olan \(p\)-elemanlı alt kümeleri saymaktır. Bunun için önce bir üreteç fonksiyonu kurulur, sonra da kök-birlik filtresi ile yalnızca \(p\)'nin katı olan toplamlar seçilir.
\(q\in\{2,3\}\) ve asal \(p\) sabit olsun. Şu iki değişkenli üreteç fonksiyonu ele alalım:
$$F_q(x,y)=\prod_{n=1}^{qp}(1+y x^n).$$
Burada \(y x^n\) terimini seçmek, \(n\)'yi alt kümeye almak anlamına gelir; \(1\) terimini seçmek ise almamak demektir. Dolayısıyla \(y^k x^m\) katsayısı, toplamı \(m\) olan \(k\)-elemanlı alt kümeleri sayar.
Öyleyse \(A_q(p)\), \(k=p\) koşulu altında ve yalnızca \(x\)'in üssü \(p\)'nin katı olan terimlerin toplamıdır.
\(\omega\), \(p\)'inci dereceden asal birim kök olsun. O zaman
$$\frac{1}{p}\sum_{j=0}^{p-1}\omega^{jm}= \begin{cases} 1,& p\mid m,\\ 0,& p\nmid m \end{cases}$$
eşitliği tam olarak istediğimiz filtreyi verir. Bu yüzden
$$A_q(p)=\frac{1}{p}\sum_{j=0}^{p-1}[y^p]\prod_{n=1}^{qp}(1+y\omega^{jn})$$
olur. Şimdi \(1,2,\dots,qp\) sayılarını \(p\)'ye göre kalan sınıflarına ayıralım. Her kalan sınıfı tam \(q\) kez görünür. Bu nedenle \(j\neq 0\) iken \(j\) ile çarpma kalanları sadece yer değiştirir ve
$$\prod_{n=1}^{qp}(1+y\omega^{jn})=\left(\prod_{r=0}^{p-1}(1+y\omega^r)\right)^q$$
elde edilir.
Şu siklotomik özdeşlikten
$$\prod_{r=0}^{p-1}(1-t\omega^r)=1-t^p$$
\(t=-y\) koyarsak
$$\prod_{r=0}^{p-1}(1+y\omega^r)=1-(-y)^p$$
çıkar. Böylece sıfır olmayan her filtre terimi
$$[y^p](1-(-y)^p)^q$$
katkısını verir. \(p\) tek asal olduğunda \(1-(-y)^p=1+y^p\) olur ve \(y^p\)'nin katsayısı sadece \(q\)'dur. Buna karşılık \(j=0\) terimi
$$[y^p](1+y)^{qp}=\binom{qp}{p}$$
şeklindedir.
Her tek asal \(p\) için, sıfır olmayan \(p-1\) filtre teriminin her biri \(q\) katkı verir. \(j=0\) terimi ile birleştirince
$$A_q(p)=\frac{\binom{qp}{p}+q(p-1)}{p}$$
elde edilir. Problemin iki özel durumu için bu
$$A_2(p)=\frac{\binom{2p}{p}+2(p-1)}{p},$$
$$A_3(p)=\frac{\binom{3p}{p}+3(p-1)}{p}$$
biçimine iner.
\(p=2\) için aynı özdeşlik
$$\prod_{r=0}^{1}(1+y\omega^r)=1-y^2$$
haline gelir. Yani sıfır olmayan filtre terimi \([y^2](1-y^2)^q=-q\) verir; burada işaret pozitife değil negatife döner. Bu nedenle
$$A_q(2)=\frac{\binom{2q}{2}-q}{2}$$
olur. Özellikle
$$A_2(2)=2,\qquad A_3(2)=6$$
çıkar ve uygulamanın neden \(p=2\)'yi ayrı ele aldığı anlaşılır.
\(p=5\) için kapalı formülleri doğrudan uygularız:
$$A_2(5)=\frac{\binom{10}{5}+2\cdot 4}{5}=\frac{252+8}{5}=52,$$
$$A_3(5)=\frac{\binom{15}{5}+3\cdot 4}{5}=\frac{3003+12}{5}=603.$$
Dolayısıyla \(5\) asalı toplamda \(52+603=655\) katkı yapar. Ayrıca küçük bir kontrol olarak
$$\sum_{p\le 10}A_2(p)=A_2(2)+A_2(3)+A_2(5)+A_2(7)=2+8+52+492=554$$
elde edilir; bu da uygulamanın iç doğrulamasıyla aynıdır.
C++, Python ve Java uygulamaları önce \(10^8\)'e kadar tüm asalları eler. Ardından \(3\cdot 10^8\)'e kadar tam faktöriyel ve ters faktöriyel tabloları tutmazlar; bu gereksiz yere büyük olurdu. Bunun yerine her asal için yalnızca birkaç kontrol noktası saklanır.
İleri yönde tek bir tarama, faktöriyelleri \(10^9+9\) modunda hesaplar ve yalnızca \(p-1\), \(2p\) ve \(3p\) noktalarındaki değerleri kaydeder. Sonra \((3\cdot 10^8)!\) değerinin tersi hızlı modüler üs alma ile bir kez bulunur. Geri yöndeki ikinci tarama ters faktöriyelleri yeniden kurar ve yalnızca \(p\) ile \(2p\) noktalarını saklar.
Bu kayıtlar sayesinde
$$\frac{1}{p}=\frac{(p-1)!}{p!},\qquad \binom{2p}{p}=\frac{(2p)!}{p!\,p!},\qquad \binom{3p}{p}=\frac{(3p)!}{p!\,(2p)!}$$
ifadeleri her asal için sabit zamanda elde edilir. Modül hem asaldır hem de \(3\cdot 10^8\)'den büyüktür; bu yüzden bu aralıkta oluşan her faktöriyel değeri mod altında terslenebilir. Son aşamada program ya \(p=2\) özel durumunu ya da tek asal formüllerini kullanır ve bütün toplamı sürekli olarak \(10^9+9\) modunda biriktirir.
\(L=10^8\) olsun. Asal eleği \(O(L\log\log L)\) zaman alır. Faktöriyel için ileri tarama ve ters faktöriyel için geri tarama \(3L\)'ye kadar gider; dolayısıyla ek maliyet \(O(L)\)'dir. Kontrol noktaları hazırlandıktan sonra her asalın katkısı \(O(1)\) sürede hesaplanır. Toplam çalışma süresi bu nedenle \(O(L\log\log L)\) olur.
Bellek kullanımı, tek sayılı bir elek ile asallar üzerinden indekslenen birkaç diziye ayrılır. Asimptotik olarak bu \(O(L+\pi(L))\)'dir. Pratik kazanç ise \(3L\)'ye kadar tam faktöriyel ve ters faktöriyel tablolarını saklamamaktır.
Para un primo \(p\) y un entero \(q\), sea \(A_q(p)\) el número de subconjuntos de tamaño \(p\) de \(\{1,2,\dots,qp\}\) cuya suma de elementos es divisible por \(p\). El problema 635 pide calcular
$$\sum_{p\le 10^8}\bigl(A_2(p)+A_3(p)\bigr)\pmod{10^9+9}.$$
Enumerar subconjuntos de forma directa no es viable. La razón por la que el problema se puede resolver es que, cuando el módulo es primo, el conteo se reduce a fórmulas cerradas muy pequeñas en términos de coeficientes binomiales.
Queremos contar subconjuntos de tamaño \(p\) cuya suma sea \(0 \pmod p\). Para ello se usa una función generadora y luego un filtro de raíces de la unidad que conserva exactamente las sumas múltiples de \(p\).
Fijemos \(q\in\{2,3\}\) y un primo \(p\). Consideremos la función generadora bivariante
$$F_q(x,y)=\prod_{n=1}^{qp}(1+y x^n).$$
Elegir el término \(y x^n\) significa incluir \(n\) en el subconjunto; elegir \(1\) significa omitirlo. Por tanto, el coeficiente de \(y^k x^m\) cuenta los subconjuntos de tamaño \(k\) cuya suma total es \(m\).
Así, \(A_q(p)\) se obtiene tomando \(k=p\) y sumando sólo los términos cuyo exponente de \(x\) sea múltiplo de \(p\).
Sea \(\omega\) una raíz \(p\)-ésima primitiva de la unidad. Entonces
$$\frac{1}{p}\sum_{j=0}^{p-1}\omega^{jm}= \begin{cases} 1,& p\mid m,\\ 0,& p\nmid m \end{cases}$$
selecciona exactamente los exponentes \(m\) divisibles por \(p\). De ahí se sigue que
$$A_q(p)=\frac{1}{p}\sum_{j=0}^{p-1}[y^p]\prod_{n=1}^{qp}(1+y\omega^{jn}).$$
Ahora agrupamos \(1,2,\dots,qp\) por sus residuos módulo \(p\). Cada clase residual aparece exactamente \(q\) veces, así que para \(j\neq 0\), multiplicar por \(j\) sólo permuta esas clases y obtenemos
$$\prod_{n=1}^{qp}(1+y\omega^{jn})=\left(\prod_{r=0}^{p-1}(1+y\omega^r)\right)^q.$$
La identidad ciclotómica
$$\prod_{r=0}^{p-1}(1-t\omega^r)=1-t^p$$
da, al sustituir \(t=-y\),
$$\prod_{r=0}^{p-1}(1+y\omega^r)=1-(-y)^p.$$
Por tanto, cada término con \(j\neq 0\) aporta
$$[y^p](1-(-y)^p)^q.$$
Si \(p\) es impar, entonces \(1-(-y)^p=1+y^p\), y el coeficiente de \(y^p\) es simplemente \(q\). En cambio, el término \(j=0\) vale
$$[y^p](1+y)^{qp}=\binom{qp}{p}.$$
Para cada primo impar \(p\), los \(p-1\) términos no nulos del filtro aportan \(q\) cada uno. Sumándolos con el término \(j=0\) se obtiene
$$A_q(p)=\frac{\binom{qp}{p}+q(p-1)}{p}.$$
En los dos casos pedidos por el problema, esto se convierte en
$$A_2(p)=\frac{\binom{2p}{p}+2(p-1)}{p},$$
$$A_3(p)=\frac{\binom{3p}{p}+3(p-1)}{p}$$
para todo primo impar \(p\).
Cuando \(p=2\), la misma identidad se vuelve
$$\prod_{r=0}^{1}(1+y\omega^r)=1-y^2,$$
de modo que el término no trivial del filtro aporta \([y^2](1-y^2)^q=-q\) en lugar de \(+q\). Por ello
$$A_q(2)=\frac{\binom{2q}{2}-q}{2}.$$
En particular,
$$A_2(2)=2,\qquad A_3(2)=6,$$
que son justamente los dos valores especiales usados por la implementación.
Para \(p=5\), las fórmulas cerradas se aplican sin cambios:
$$A_2(5)=\frac{\binom{10}{5}+2\cdot 4}{5}=\frac{252+8}{5}=52,$$
$$A_3(5)=\frac{\binom{15}{5}+3\cdot 4}{5}=\frac{3003+12}{5}=603.$$
Así, el primo \(5\) aporta \(52+603=655\) al total. Como comprobación pequeña, además se tiene
$$\sum_{p\le 10}A_2(p)=A_2(2)+A_2(3)+A_2(5)+A_2(7)=2+8+52+492=554,$$
exactamente el valor de verificación que usa la implementación.
Las implementaciones en C++, Python y Java primero criban todos los primos hasta \(10^8\). Después no almacenan tablas completas de factoriales e inversos factoriales hasta \(3\cdot 10^8\), porque eso sería demasiado grande. En su lugar guardan sólo unos pocos puntos de control por primo.
Un recorrido hacia adelante calcula factoriales módulo \(10^9+9\) y registra los valores en \(p-1\), \(2p\) y \(3p\). Luego la implementación calcula una sola vez el inverso de \((3\cdot 10^8)!\) mediante exponenciación modular rápida. Un recorrido hacia atrás reconstruye los inversos factoriales y guarda únicamente los puntos de control en \(p\) y \(2p\).
Con esos datos basta para recuperar
$$\frac{1}{p}=\frac{(p-1)!}{p!},\qquad \binom{2p}{p}=\frac{(2p)!}{p!\,p!},\qquad \binom{3p}{p}=\frac{(3p)!}{p!\,(2p)!}$$
en tiempo constante para cada primo. El módulo es primo y además mayor que \(3\cdot 10^8\), así que todos los factoriales que aparecen en ese rango son invertibles módulo \(10^9+9\). A continuación el programa aplica el caso especial \(p=2\) o la fórmula para primos impares, suma \(A_2(p)\) y \(A_3(p)\), y reduce siempre módulo \(10^9+9\).
Sea \(L=10^8\). La criba de primos cuesta \(O(L\log\log L)\) tiempo. El barrido directo de factoriales y el barrido inverso de inversos factoriales llegan ambos hasta \(3L\), por lo que añaden \(O(L)\) tiempo. Una vez preparados los puntos de control, cada primo se procesa en \(O(1)\). En consecuencia, el tiempo total es \(O(L\log\log L)\).
La memoria está formada por una criba que sólo representa impares y por unas cuantas tablas de puntos de control indexadas por primos. Asintóticamente eso es \(O(L+\pi(L))\). La optimización esencial es no almacenar todos los factoriales ni todos los inversos factoriales hasta \(3L\).
对一个素数 \(p\) 和整数 \(q\)，记 \(A_q(p)\) 为集合 \(\{1,2,\dots,qp\}\) 中所有大小恰好为 \(p\) 且元素和能被 \(p\) 整除的子集个数。第 635 题要求计算
$$\sum_{p\le 10^8}\bigl(A_2(p)+A_3(p)\bigr)\pmod{10^9+9}.$$
如果直接枚举子集，规模会立刻失控，因为即使只看一个大的素数，候选子集数量也已经大到无法处理。真正可行的办法，是先把计数问题写成生成函数，再利用素数模下的结构把它压缩成只含二项式系数的闭式。
核心目标是统计“选出 \(p\) 个数，且它们的和在模 \(p\) 意义下等于 0”的方案数。单位根筛正适合做这种“只保留某个同余类”的提取，而集合 \(\{1,\dots,qp\}\) 的模 \(p\) 余数分布又恰好非常整齐。
固定 \(q\in\{2,3\}\) 和素数 \(p\)，考虑
$$F_q(x,y)=\prod_{n=1}^{qp}(1+y x^n).$$
展开这个乘积时，若在第 \(n\) 项中选 \(y x^n\)，就表示把 \(n\) 放进子集；若选 \(1\)，就表示不选它。因此，系数 \(y^k x^m\) 正好统计“选了 \(k\) 个数且这些数之和为 \(m\)”的子集个数。
所以 \(A_q(p)\) 就是所有 \(y^p x^m\) 项中，满足 \(m\equiv 0\pmod p\) 的系数总和。
设 \(\omega\) 是一个本原 \(p\) 次单位根。经典恒等式
$$\frac{1}{p}\sum_{j=0}^{p-1}\omega^{jm}= \begin{cases} 1,& p\mid m,\\ 0,& p\nmid m \end{cases}$$
说明它能精确筛出那些指数 \(m\) 是 \(p\) 的倍数的项。于是
$$A_q(p)=\frac{1}{p}\sum_{j=0}^{p-1}[y^p]\prod_{n=1}^{qp}(1+y\omega^{jn}).$$
接下来把 \(1,2,\dots,qp\) 按照模 \(p\) 的余数分组。每个余数类都恰好出现 \(q\) 次。对于 \(j\neq 0\)，乘上 \(j\) 只是把这些余数类重新排列，所以
$$\prod_{n=1}^{qp}(1+y\omega^{jn})=\left(\prod_{r=0}^{p-1}(1+y\omega^r)\right)^q.$$
这一步非常关键，因为它说明除了 \(j=0\) 以外，其余 \(p-1\) 个项其实完全一样。
利用循环多项式恒等式
$$\prod_{r=0}^{p-1}(1-t\omega^r)=1-t^p,$$
令 \(t=-y\) 后得到
$$\prod_{r=0}^{p-1}(1+y\omega^r)=1-(-y)^p.$$
因此每个 \(j\neq 0\) 的筛项都只需要取
$$[y^p](1-(-y)^p)^q$$
这个系数。若 \(p\) 是奇素数，则 \(1-(-y)^p=1+y^p\)，于是 \(y^p\) 的系数就是 \(q\)。而 \(j=0\) 时，没有任何筛选振荡，直接得到
$$[y^p](1+y)^{qp}=\binom{qp}{p}.$$
对每个奇素数 \(p\)，共有 \(p-1\) 个非零筛项，而且每个都贡献 \(q\)。把它们与 \(j=0\) 的二项式系数项合并，就得到
$$A_q(p)=\frac{\binom{qp}{p}+q(p-1)}{p}.$$
题目只需要 \(q=2\) 和 \(q=3\) 两种情况，因此具体就是
$$A_2(p)=\frac{\binom{2p}{p}+2(p-1)}{p},$$
$$A_3(p)=\frac{\binom{3p}{p}+3(p-1)}{p}$$
对所有奇素数 \(p\) 都成立。
\(p=2\) 时，前面的化简会变成
$$\prod_{r=0}^{1}(1+y\omega^r)=1-y^2,$$
于是非零筛项贡献的是 \([y^2](1-y^2)^q=-q\)，符号不再是正的。因此
$$A_q(2)=\frac{\binom{2q}{2}-q}{2}.$$
特别地，
$$A_2(2)=2,\qquad A_3(2)=6,$$
这正是实现里专门分支处理的两个值。
取 \(p=5\) 时，直接代入闭式即可：
$$A_2(5)=\frac{\binom{10}{5}+2\cdot 4}{5}=\frac{252+8}{5}=52,$$
$$A_3(5)=\frac{\binom{15}{5}+3\cdot 4}{5}=\frac{3003+12}{5}=603.$$
所以素数 \(5\) 对最终总和的贡献是 \(52+603=655\)。实现里还用了一个更小的校验点：
$$\sum_{p\le 10}A_2(p)=A_2(2)+A_2(3)+A_2(5)+A_2(7)=2+8+52+492=554,$$
这与程序中的校验值完全一致。
C++、Python 和 Java 三个实现都先筛出不超过 \(10^8\) 的所有素数。接着它们并不会把直到 \(3\cdot 10^8\) 的全部阶乘和逆阶乘都存下来，因为那样的内存代价太高。真正保存的只有每个素数对应的少量检查点。
第一次正向扫描按模 \(10^9+9\) 逐步累乘阶乘，并在 \(p-1\)、\(2p\)、\(3p\) 这几个位置保存所需数值。之后只做一次快速幂，求出 \((3\cdot 10^8)!\) 的模逆。再做一次反向扫描，就可以逐步恢复逆阶乘，并只在 \(p\) 与 \(2p\) 位置留下检查点。
有了这些记录，就足以在每个素数上用常数时间恢复
$$\frac{1}{p}=\frac{(p-1)!}{p!},\qquad \binom{2p}{p}=\frac{(2p)!}{p!\,p!},\qquad \binom{3p}{p}=\frac{(3p)!}{p!\,(2p)!}.$$
这里所用模数 \(10^9+9\) 本身是素数，而且严格大于 \(3\cdot 10^8\)，因此扫描过程中出现的所有阶乘值在模意义下都可逆。最后，程序对 \(p=2\) 走特判，对奇素数使用闭式公式，并把全部贡献持续累加到模 \(10^9+9\) 下。
设 \(L=10^8\)。素数筛部分需要 \(O(L\log\log L)\) 时间。阶乘的正向扫描和逆阶乘的反向扫描都只跑到 \(3L\)，因此额外增加 \(O(L)\) 时间。检查点准备好之后，每个素数的贡献都能在 \(O(1)\) 时间内求出，所以总时间复杂度仍然是 \(O(L\log\log L)\)。
空间方面，需要一个只表示奇数位置的筛，以及若干个按素数编号的检查点数组，总体为 \(O(L+\pi(L))\)。真正重要的优化点是：实现避免了保存从 \(1\) 到 \(3L\) 的完整阶乘表和完整逆阶乘表。
Для простого числа \(p\) и целого \(q\) обозначим через \(A_q(p)\) число \(p\)-элементных подмножеств множества \(\{1,2,\dots,qp\}\), сумма элементов которых делится на \(p\). Тогда задача 635 просит вычислить
$$\sum_{p\le 10^8}\bigl(A_2(p)+A_3(p)\bigr)\pmod{10^9+9}.$$
Прямой перебор подмножеств здесь невозможен. Идея решения в том, что при простом модуле условие на сумму можно выразить через фильтр корней из единицы, после чего задача сводится к коротким формулам с биномиальными коэффициентами.
Нужно посчитать подмножества размера \(p\), сумма элементов которых сравнима с нулем по модулю \(p\). Для этого удобно сначала закодировать размер и сумму порождающей функцией, а затем оставить только нужный класс вычетов.
Зафиксируем \(q\in\{2,3\}\) и простое \(p\). Рассмотрим
$$F_q(x,y)=\prod_{n=1}^{qp}(1+y x^n).$$
Выбор множителя \(y x^n\) означает, что число \(n\) включено в подмножество; выбор \(1\) означает, что оно не выбрано. Поэтому коэффициент при \(y^k x^m\) равен числу подмножеств мощности \(k\) с суммой элементов \(m\).
Следовательно, \(A_q(p)\) получается из коэффициентов при \(y^p x^m\), где \(m\) кратно \(p\).
Пусть \(\omega\) - примитивный \(p\)-й корень из единицы. Тогда
$$\frac{1}{p}\sum_{j=0}^{p-1}\omega^{jm}= \begin{cases} 1,& p\mid m,\\ 0,& p\nmid m \end{cases}$$
выделяет ровно те показатели \(m\), которые делятся на \(p\). Значит,
$$A_q(p)=\frac{1}{p}\sum_{j=0}^{p-1}[y^p]\prod_{n=1}^{qp}(1+y\omega^{jn}).$$
Теперь сгруппируем числа \(1,2,\dots,qp\) по классам вычетов modulo \(p\). Каждый класс встречается ровно \(q\) раз. Поэтому при \(j\neq 0\) умножение вычетов на \(j\) лишь переставляет их, и потому
$$\prod_{n=1}^{qp}(1+y\omega^{jn})=\left(\prod_{r=0}^{p-1}(1+y\omega^r)\right)^q.$$
Из циклотомической тождественности
$$\prod_{r=0}^{p-1}(1-t\omega^r)=1-t^p$$
после подстановки \(t=-y\) получаем
$$\prod_{r=0}^{p-1}(1+y\omega^r)=1-(-y)^p.$$
Следовательно, каждый член с \(j\neq 0\) дает вклад
$$[y^p](1-(-y)^p)^q.$$
Если \(p\) нечетное, то \(1-(-y)^p=1+y^p\), и коэффициент при \(y^p\) равен просто \(q\). А член \(j=0\) равен
$$[y^p](1+y)^{qp}=\binom{qp}{p}.$$
Для каждого нечетного простого \(p\) имеется \(p-1\) одинаковых нетривиальных членов фильтра, и каждый из них вносит \(q\). Складывая их с членом \(j=0\), получаем
$$A_q(p)=\frac{\binom{qp}{p}+q(p-1)}{p}.$$
В двух случаях, нужных задаче, это дает
$$A_2(p)=\frac{\binom{2p}{p}+2(p-1)}{p},$$
$$A_3(p)=\frac{\binom{3p}{p}+3(p-1)}{p}$$
для всех нечетных простых \(p\).
При \(p=2\) та же формула превращается в
$$\prod_{r=0}^{1}(1+y\omega^r)=1-y^2,$$
поэтому нетривиальный член фильтра равен \([y^2](1-y^2)^q=-q\), а не \(+q\). Отсюда
$$A_q(2)=\frac{\binom{2q}{2}-q}{2}.$$
В частности,
$$A_2(2)=2,\qquad A_3(2)=6,$$
и именно поэтому в реализации есть отдельная ветка для \(p=2\).
Для \(p=5\) подставляем в закрытые формулы:
$$A_2(5)=\frac{\binom{10}{5}+2\cdot 4}{5}=\frac{252+8}{5}=52,$$
$$A_3(5)=\frac{\binom{15}{5}+3\cdot 4}{5}=\frac{3003+12}{5}=603.$$
Значит, простое число \(5\) дает вклад \(52+603=655\). Полезная малая проверка:
$$\sum_{p\le 10}A_2(p)=A_2(2)+A_2(3)+A_2(5)+A_2(7)=2+8+52+492=554,$$
и именно это значение используется как внутренняя проверка корректности.
Реализации на C++, Python и Java сначала строят решето всех простых чисел до \(10^8\). Затем они не хранят полные таблицы факториалов и обратных факториалов до \(3\cdot 10^8\), потому что это слишком дорого по памяти. Вместо этого сохраняются только несколько контрольных значений на каждое простое.
Прямой проход считает факториалы по модулю \(10^9+9\) и сохраняет только значения в точках \(p-1\), \(2p\) и \(3p\). После этого один раз вычисляется обратный элемент к \((3\cdot 10^8)!\) с помощью быстрого возведения в степень. Обратный проход восстанавливает обратные факториалы и сохраняет только значения в точках \(p\) и \(2p\).
Этих контрольных точек достаточно, чтобы за \(O(1)\) на простое восстановить
$$\frac{1}{p}=\frac{(p-1)!}{p!},\qquad \binom{2p}{p}=\frac{(2p)!}{p!\,p!},\qquad \binom{3p}{p}=\frac{(3p)!}{p!\,(2p)!}.$$
Модуль \(10^9+9\) сам является простым и больше \(3\cdot 10^8\), поэтому все факториалы в рассматриваемом диапазоне обратимы по этому модулю. Затем программа либо использует специальный случай \(p=2\), либо применяет формулы для нечетных простых, суммируя вклады по модулю \(10^9+9\).
Пусть \(L=10^8\). Решето простых требует \(O(L\log\log L)\) времени. Прямой проход по факториалам и обратный проход по обратным факториалам оба идут до \(3L\), то есть добавляют \(O(L)\) времени. После подготовки контрольных точек вклад каждого простого вычисляется за \(O(1)\). Итого полная асимптотика по времени равна \(O(L\log\log L)\).
По памяти используется решето по нечетным числам и несколько массивов контрольных значений, индексированных простыми. Это дает \(O(L+\pi(L))\). Главная практическая экономия состоит в том, что полные таблицы факториалов и обратных факториалов до \(3L\) не хранятся.
لعدد أولي \(p\) وعدد صحيح \(q\)، لنعرّف \(A_q(p)\) بأنه عدد المجموعات الجزئية ذات الحجم \(p\) من \(\{1,2,\dots,qp\}\) التي يكون مجموع عناصرها قابلاً للقسمة على \(p\). المطلوب في المسألة 635 هو حساب
$$\sum_{p\le 10^8}\bigl(A_2(p)+A_3(p)\bigr)\pmod{10^9+9}.$$
العد المباشر غير ممكن عملياً، لأن عدد المجموعات الجزئية المرشحة هائل حتى لعدد أولي واحد كبير. الفكرة الأساسية هي تحويل المسألة إلى دالة توليد ثم استخدام مرشح جذور الوحدة، وعندها تنضغط النتيجة إلى صيغ مغلقة قصيرة تعتمد على معاملات ثنائية فقط.
نحن نريد عدّ جميع المجموعات الجزئية ذات الحجم \(p\) التي يساوي مجموعها \(0 \pmod p\). هذا النوع من القيود على البواقي يناسبه مرشح جذور الوحدة تماماً، كما أن توزع بواقي الأعداد من \(1\) إلى \(qp\) يجعل جميع الحدود غير الصفرية في المرشح متطابقة.
ثبّت \(q\in\{2,3\}\) وعدداً أولياً \(p\). ننظر إلى
$$F_q(x,y)=\prod_{n=1}^{qp}(1+y x^n).$$
اختيار الحد \(y x^n\) يعني أننا أدخلنا \(n\) في المجموعة الجزئية، بينما اختيار \(1\) يعني أننا تركناه. لذلك فإن معامل \(y^k x^m\) يساوي عدد المجموعات الجزئية ذات الحجم \(k\) ومجموع العناصر \(m\).
وبالتالي فإن \(A_q(p)\) هو مجموع معاملات \(y^p x^m\) عندما يكون \(m\) من مضاعفات \(p\).
لتكن \(\omega\) جذراً أولياً من الدرجة \(p\) للوحدة. عندئذٍ
$$\frac{1}{p}\sum_{j=0}^{p-1}\omega^{jm}= \begin{cases} 1,& p\mid m,\\ 0,& p\nmid m \end{cases}$$
ينتقي بالضبط الحدود التي يكون فيها الأس \(m\) قابلاً للقسمة على \(p\). لهذا نحصل على
$$A_q(p)=\frac{1}{p}\sum_{j=0}^{p-1}[y^p]\prod_{n=1}^{qp}(1+y\omega^{jn}).$$
الآن نقسم الأعداد \(1,2,\dots,qp\) حسب بواقيها modulo \(p\). كل فئة بواقٍ تظهر بالضبط \(q\) مرات. لذلك عندما يكون \(j\neq 0\)، فإن الضرب في \(j\) يبدل فئات البواقي فقط، فنحصل على
$$\prod_{n=1}^{qp}(1+y\omega^{jn})=\left(\prod_{r=0}^{p-1}(1+y\omega^r)\right)^q.$$
من الهوية الدورية
$$\prod_{r=0}^{p-1}(1-t\omega^r)=1-t^p$$
وبالتعويض \(t=-y\) نحصل على
$$\prod_{r=0}^{p-1}(1+y\omega^r)=1-(-y)^p.$$
إذن كل حد غير صفري في المرشح يساهم بمقدار
$$[y^p](1-(-y)^p)^q.$$
إذا كان \(p\) أولياً فردياً، فلدينا \(1-(-y)^p=1+y^p\)، ولذلك يكون معامل \(y^p\) مساوياً ببساطة لـ \(q\). أما الحد الموافق لـ \(j=0\) فهو
$$[y^p](1+y)^{qp}=\binom{qp}{p}.$$
لكل عدد أولي فردي \(p\)، يوجد \(p-1\) حدود غير صفرية في المرشح، وكل واحد منها يضيف \(q\). بضم ذلك إلى حد \(j=0\) نحصل على
$$A_q(p)=\frac{\binom{qp}{p}+q(p-1)}{p}.$$
وفي الحالتين المطلوبتين في المسألة يصبح هذا
$$A_2(p)=\frac{\binom{2p}{p}+2(p-1)}{p},$$
$$A_3(p)=\frac{\binom{3p}{p}+3(p-1)}{p}$$
لكل عدد أولي فردي \(p\).
عندما يكون \(p=2\)، تتحول الهوية نفسها إلى
$$\prod_{r=0}^{1}(1+y\omega^r)=1-y^2,$$
ومن ثم يكون الحد غير الصفري في المرشح هو \([y^2](1-y^2)^q=-q\) وليس \(+q\). لذلك
$$A_q(2)=\frac{\binom{2q}{2}-q}{2}.$$
وبشكل خاص
$$A_2(2)=2,\qquad A_3(2)=6,$$
وهذا يفسر تماماً سبب وجود فرع خاص لـ \(p=2\) في التنفيذ.
عند \(p=5\) نطبق الصيغ مباشرة:
$$A_2(5)=\frac{\binom{10}{5}+2\cdot 4}{5}=\frac{252+8}{5}=52,$$
$$A_3(5)=\frac{\binom{15}{5}+3\cdot 4}{5}=\frac{3003+12}{5}=603.$$
إذن مساهمة العدد الأولي \(5\) في المجموع النهائي هي \(52+603=655\). وهناك نقطة تحقق صغيرة أخرى:
$$\sum_{p\le 10}A_2(p)=A_2(2)+A_2(3)+A_2(5)+A_2(7)=2+8+52+492=554,$$
وهي نفس القيمة المستخدمة داخلياً للتحقق من صحة التنفيذ.
تبدأ تطبيقات C++ وPython وJava بعمل غربال لجميع الأعداد الأولية حتى \(10^8\). بعد ذلك لا تحتفظ بجداول كاملة للفكتوريال والمعكوسات حتى \(3\cdot 10^8\)، لأن ذلك سيكون مكلفاً جداً في الذاكرة. بدلاً من ذلك تُخزَّن فقط قيم مرجعية محددة لكل عدد أولي.
يمر التنفيذ مرةً إلى الأمام ليحسب الفكتوريال modulo \(10^9+9\)، ويحفظ القيم عند المواضع \(p-1\) و\(2p\) و\(3p\). ثم يحسب مرةً واحدة معكوس \((3\cdot 10^8)!\) باستخدام الرفع السريع للأس. بعد ذلك يقوم بمرور عكسي لإعادة بناء المعكوسات factorial ويخزن فقط القيم عند \(p\) و\(2p\).
هذه النقاط المرجعية تكفي لاسترجاع
$$\frac{1}{p}=\frac{(p-1)!}{p!},\qquad \binom{2p}{p}=\frac{(2p)!}{p!\,p!},\qquad \binom{3p}{p}=\frac{(3p)!}{p!\,(2p)!}$$
بزمن ثابت لكل عدد أولي. والموديل \(10^9+9\) عدد أولي وأكبر من \(3\cdot 10^8\)، لذلك فإن جميع قيم الفكتوريال في هذا المجال قابلة للعكس modulo هذا العدد. في النهاية يطبّق البرنامج الحالة الخاصة \(p=2\) أو صيغة الأعداد الأولية الفردية، ثم يجمع جميع المساهمات تحت modulo \(10^9+9\).
لنضع \(L=10^8\). غربلة الأعداد الأولية تكلف \(O(L\log\log L)\) زمناً. والمرور الأمامي للفكتوريال مع المرور الخلفي للمعكوسات يصلان كلاهما إلى \(3L\)، فيضيفان \(O(L)\) زمناً. وبعد تجهيز القيم المرجعية يصبح حساب مساهمة كل عدد أولي في \(O(1)\). لذلك يكون التعقيد الزمني الكلي \(O(L\log\log L)\).
أما الذاكرة فتتكوّن من غربال للأعداد الفردية وعدة مصفوفات مرجعية مفهرسة بحسب الأعداد الأولية، أي \(O(L+\pi(L))\) بصورة أسيمبتوطية. والميزة العملية الأساسية هي تجنب تخزين كل قيم الفكتوريال وكل المعكوسات حتى \(3L\).