Let \(\pi(x)\) denote the number of primes not exceeding \(x\), and let \(p_r\) be the \(r\)-th prime. The problem asks for the number \(T(n,k)\) of ordered \(k\)-tuples of positive integers \((x_1,\dots,x_k)\) such that
$$\pi(x_1)+\pi(x_2)+\cdots+\pi(x_k)=n,$$
with the final result taken modulo
$$M=1004535809.$$
The decisive observation is that many different integers share the same prime-count value, and those multiplicities are controlled exactly by consecutive prime gaps.
The implementations turn the tuple-counting problem into coefficient extraction from a generating function, and then accelerate the polynomial arithmetic with an NTT.
For \(r=0\), there is only one positive integer with \(\pi(x)=0\), namely \(x=1\). Therefore
$$a_0=1.$$
For every \(r\ge 1\), the condition \(\pi(x)=r\) means that \(x\) lies between the \(r\)-th and \((r+1)\)-st primes:
$$\pi(x)=r \iff p_r \le x \le p_{r+1}-1.$$
So the number of such integers is exactly the prime gap
$$a_r=p_{r+1}-p_r \qquad (r\ge 1).$$
These coefficients are the basic weights of the whole problem: \(a_r\) counts how many choices one coordinate has if it contributes exactly \(r\) to the total sum of prime counts.
If the first coordinate contributes \(i\), there are \(a_i\) possible values for it, and the remaining \(k-1\) coordinates must contribute \(n-i\). This gives the convolution recurrence
$$T(n,k)=\sum_{i=0}^{n} a_i\,T(n-i,k-1).$$
The natural initial conditions are
$$T(0,0)=1,\qquad T(n,0)=0 \text{ for } n>0,$$
and for one coordinate we simply have
$$T(n,1)=a_n.$$
So the combinatorics is already telling us that each extra coordinate adds one more discrete convolution with the sequence \((a_0,a_1,a_2,\dots)\).
Introduce the ordinary generating series
$$A(x)=\sum_{r\ge 0} a_r x^r$$
and, for fixed \(k\),
$$F_k(x)=\sum_{n\ge 0} T(n,k)x^n.$$
The recurrence from the previous step becomes
$$F_k(x)=A(x)\,F_{k-1}(x).$$
Iterating this identity and using \(F_0(x)=1\), we get
$$F_k(x)=A(x)^k.$$
Therefore the answer is the coefficient of \(x^n\):
$$\boxed{T(n,k)=[x^n]A(x)^k.}$$
This is the exact mathematical statement implemented by the C++, Python, and Java versions.
When we only need \([x^n]A(x)^k\), no coefficient of degree greater than \(n\) can ever become relevant later. Every multiplication adds nonnegative exponents, so once a term has degree \(>n\), future multiplications can only push it to even higher degree.
Hence after every polynomial product we may safely discard all terms above degree \(n\) and keep only
$$c_0+c_1x+\cdots+c_nx^n.$$
This is why the implementations always work with truncated polynomials of length \(n+1\), even while repeatedly squaring during exponentiation.
A naive convolution of two degree-\(n\) polynomials costs \(O(n^2)\), which is too slow for the target size. The chosen modulus is
$$M=1004535809=479\cdot 2^{21}+1.$$
Because \(M-1\) contains a large power of \(2\), every transform length
$$L=2^m \le 2^{21}$$
has the necessary primitive \(L\)-th roots of unity modulo \(M\). In particular, the primitive root \(3\) generates all the roots needed by the transform. So polynomial multiplication can be done exactly modulo \(M\) with a Number Theoretic Transform in
$$O(L\log L)$$
time instead of quadratic time.
The first few coefficient buckets are easy to read off from the primes:
$$a_0=1,\qquad a_1=3-2=1,\qquad a_2=5-3=2,\qquad a_3=7-5=2.$$
Indeed, the corresponding sets are
$$\pi(x)=0 \Rightarrow \{1\},\qquad \pi(x)=1 \Rightarrow \{2\},\qquad \pi(x)=2 \Rightarrow \{3,4\},\qquad \pi(x)=3 \Rightarrow \{5,6\}.$$
Now
$$T(3,2)=[x^3]A(x)^2=a_0a_3+a_1a_2+a_2a_1+a_3a_0=2+2+2+2=8.$$
The eight ordered pairs are
$$(1,5),(1,6),(2,3),(2,4),(3,2),(4,2),(5,1),(6,1).$$
This small example shows exactly why coefficient extraction matches the tuple count.
The implementations first generate enough consecutive primes to know the gaps \(p_{r+1}-p_r\) for all \(0\le r\le n\). From those gaps they build the truncated coefficient list of \(A(x)\) up to degree \(n\).
Polynomial multiplication is then performed by padding both coefficient arrays to the next power of two, applying the forward NTT, multiplying pointwise, and applying the inverse NTT. After every product, the result is truncated back to degree \(n\).
To obtain \(A(x)^k\), the implementations use binary exponentiation in the polynomial ring: when the current bit of \(k\) is set, the running result is multiplied by the current base; after that, the base is squared. Because every intermediate product is truncated, the degree never grows beyond what is needed.
Once the exponentiation finishes, the coefficient of \(x^n\) is returned modulo \(M\).
Let \(B\) be a sieve bound large enough to contain \(p_{n+1}\), and let \(L\) be the smallest power of two satisfying \(L\ge 2n+1\). Generating the needed primes by a sieve costs \(O(B\log\log B)\) time and \(O(B)\) memory.
Each truncated polynomial multiplication costs \(O(L\log L)\), and binary exponentiation performs \(O(\log k)\) such multiplications. Therefore the full running time is
$$O(B\log\log B + L\log L\log k).$$
Since \(L=O(n)\), the polynomial part is usually summarized as
$$O(n\log n\log k).$$
The memory usage is \(O(B+L)\) while the sieve and polynomial buffers coexist.
Sei \(\pi(x)\) die Anzahl der Primzahlen \(\le x\), und sei \(p_r\) die \(r\)-te Primzahl. Gesucht ist die Anzahl \(T(n,k)\) der geordneten \(k\)-Tupel positiver ganzer Zahlen \((x_1,\dots,x_k)\) mit
$$\pi(x_1)+\pi(x_2)+\cdots+\pi(x_k)=n,$$
wobei das Ergebnis modulo
$$M=1004535809$$
ausgegeben wird. Der entscheidende Punkt ist, dass viele verschiedene Zahlen denselben Primzahlzählwert haben, und diese Häufigkeiten werden exakt durch die Lücken zwischen aufeinanderfolgenden Primzahlen beschrieben.
Die Lösung formt das Zählproblem in eine Koeffizientenextraktion aus einer erzeugenden Funktion um und beschleunigt die Polynomarithmetik anschließend mit einer NTT.
Für \(r=0\) gibt es genau eine positive Zahl mit \(\pi(x)=0\), nämlich \(x=1\). Daher
$$a_0=1.$$
Für jedes \(r\ge 1\) bedeutet \(\pi(x)=r\), dass \(x\) zwischen der \(r\)-ten und der \((r+1)\)-ten Primzahl liegt:
$$\pi(x)=r \iff p_r \le x \le p_{r+1}-1.$$
Also ist die Anzahl solcher Zahlen genau die Primzahllücke
$$a_r=p_{r+1}-p_r \qquad (r\ge 1).$$
Diese Koeffizienten sind die Grundgewichte des Problems: \(a_r\) zählt, wie viele Möglichkeiten eine einzelne Koordinate hat, wenn sie genau \(r\) zum Gesamtwert beiträgt.
Wenn die erste Koordinate den Beitrag \(i\) liefert, gibt es dafür \(a_i\) Möglichkeiten, und die übrigen \(k-1\) Koordinaten müssen zusammen \(n-i\) liefern. Daraus folgt die Faltungsrekurrenz
$$T(n,k)=\sum_{i=0}^{n} a_i\,T(n-i,k-1).$$
Die natürlichen Anfangsbedingungen sind
$$T(0,0)=1,\qquad T(n,0)=0 \text{ für } n>0,$$
und für ein einzelnes Element gilt einfach
$$T(n,1)=a_n.$$
Die Kombinatorik sagt also bereits, dass jede zusätzliche Koordinate genau eine weitere diskrete Faltung mit der Folge \((a_0,a_1,a_2,\dots)\) erzeugt.
Wir definieren die gewöhnliche erzeugende Reihe
$$A(x)=\sum_{r\ge 0} a_r x^r$$
und für festes \(k\)
$$F_k(x)=\sum_{n\ge 0} T(n,k)x^n.$$
Die Rekurrenz aus dem vorigen Schritt wird dann zu
$$F_k(x)=A(x)\,F_{k-1}(x).$$
Durch Iteration und mit \(F_0(x)=1\) erhält man
$$F_k(x)=A(x)^k.$$
Damit ist die gesuchte Zahl genau der Koeffizient von \(x^n\):
$$\boxed{T(n,k)=[x^n]A(x)^k.}$$
Genau diese mathematische Aussage setzen die Implementierungen um.
Wenn nur \([x^n]A(x)^k\) gebraucht wird, kann kein Koeffizient von Grad größer als \(n\) später noch wichtig werden. Bei jeder weiteren Multiplikation addieren sich nur nichtnegative Exponenten, also können Terme mit Grad \(>n\) nie wieder auf Grad \(n\) zurückfallen.
Daher darf nach jedem Produkt sicher alles oberhalb von Grad \(n\) verworfen werden, und man behält nur
$$c_0+c_1x+\cdots+c_nx^n.$$
Deshalb arbeiten die Programme während der gesamten Potenzierung immer nur mit abgeschnittenen Polynomen der Länge \(n+1\).
Eine naive Faltung zweier Polynome vom Grad \(n\) kostet \(O(n^2)\) und ist für die Zielgröße zu langsam. Der verwendete Modulus ist
$$M=1004535809=479\cdot 2^{21}+1.$$
Weil \(M-1\) eine große Zweierpotenz enthält, besitzt jede Transformationslänge
$$L=2^m \le 2^{21}$$
die nötigen primitiven \(L\)-ten Einheitswurzeln modulo \(M\). Insbesondere liefert die primitive Wurzel \(3\) alle benötigten Wurzeln für die NTT. Damit gelingt jede Polynom-Multiplikation exakt modulo \(M\) in
$$O(L\log L)$$
statt in quadratischer Zeit.
Die ersten Koeffizienten liest man direkt aus den Primzahlen ab:
$$a_0=1,\qquad a_1=3-2=1,\qquad a_2=5-3=2,\qquad a_3=7-5=2.$$
Dazu gehören die Mengen
$$\pi(x)=0 \Rightarrow \{1\},\qquad \pi(x)=1 \Rightarrow \{2\},\qquad \pi(x)=2 \Rightarrow \{3,4\},\qquad \pi(x)=3 \Rightarrow \{5,6\}.$$
Dann gilt
$$T(3,2)=[x^3]A(x)^2=a_0a_3+a_1a_2+a_2a_1+a_3a_0=2+2+2+2=8.$$
Die acht geordneten Paare sind
$$(1,5),(1,6),(2,3),(2,4),(3,2),(4,2),(5,1),(6,1).$$
Dieses kleine Beispiel zeigt direkt, warum Koeffizientenextraktion und Tupelzählung dasselbe Problem sind.
Die Implementierungen erzeugen zunächst genügend aufeinanderfolgende Primzahlen, um die Lücken \(p_{r+1}-p_r\) für alle \(0\le r\le n\) zu kennen. Aus diesen Lücken wird die abgeschnittene Koeffizientenliste von \(A(x)\) bis Grad \(n\) aufgebaut.
Die Polynom-Multiplikation erfolgt dann durch Auffüllen beider Koeffizientenfelder auf die nächste Zweierpotenz, anschließende Vorwärts-NTT, punktweise Multiplikation und Rücktransformation. Nach jedem Produkt wird sofort wieder auf Grad \(n\) abgeschnitten.
Um \(A(x)^k\) zu berechnen, verwenden die Implementierungen binäre Exponentiation im Polynomring: Ist das aktuelle Bit von \(k\) gesetzt, wird das laufende Ergebnis mit der aktuellen Basis multipliziert; anschließend wird die Basis quadriert. Durch das Abschneiden bleiben die Grade stets kontrolliert.
Nach Abschluss der Exponentiation wird der Koeffizient von \(x^n\) modulo \(M\) ausgegeben.
Sei \(B\) eine Siebgrenze, die \(p_{n+1}\) enthält, und sei \(L\) die kleinste Zweierpotenz mit \(L\ge 2n+1\). Das Erzeugen der benötigten Primzahlen per Sieb kostet \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher.
Jede abgeschnittene Polynom-Multiplikation kostet \(O(L\log L)\), und die binäre Exponentiation benötigt \(O(\log k)\) solcher Multiplikationen. Damit ergibt sich insgesamt
$$O(B\log\log B + L\log L\log k).$$
Da \(L=O(n)\) ist, fasst man den Polynomteil meist als
$$O(n\log n\log k)$$
zusammen. Der Speicherverbrauch beträgt \(O(B+L)\), solange Sieb und Polynom-Puffer gleichzeitig vorliegen.
\(\pi(x)\), \(x\)'i aşmayan asal sayıların sayısı olsun ve \(p_r\) de \(r\). asal sayı olsun. Problem,
$$\pi(x_1)+\pi(x_2)+\cdots+\pi(x_k)=n$$
koşulunu sağlayan sıralı pozitif tamsayı \(k\)-lilerinin \((x_1,\dots,x_k)\) sayısı olan \(T(n,k)\) değerini
$$M=1004535809$$
modunda istemektedir. Buradaki temel gözlem, aynı asal-sayım değerine sahip çok sayıda tamsayı olması ve bu çoklukların ardışık asal farklarıyla tam olarak belirlenmesidir.
Çözüm, tuple sayımını bir üreteç fonksiyondan katsayı çıkarma problemine dönüştürür ve polinom çarpımlarını NTT ile hızlandırır.
\(r=0\) için \(\pi(x)=0\) olan tek pozitif tamsayı \(x=1\)'dir. Bu yüzden
$$a_0=1.$$
\(r\ge 1\) için \(\pi(x)=r\) demek, \(x\)'in \(r\). asal ile \((r+1)\). asal arasında kalması demektir:
$$\pi(x)=r \iff p_r \le x \le p_{r+1}-1.$$
Dolayısıyla böyle sayıların adedi tam olarak asal farkıdır:
$$a_r=p_{r+1}-p_r \qquad (r\ge 1).$$
Bu katsayılar problemin temel ağırlıklarıdır; \(a_r\), tek bir koordinatın toplam prime-count değerine tam \(r\) katkı yapması durumunda kaç seçim olduğunu söyler.
İlk koordinat \(i\) katkısı yapıyorsa bunun için \(a_i\) farklı seçim vardır; geri kalan \(k-1\) koordinatın toplam katkısı ise \(n-i\) olmalıdır. Böylece evrişim reküransı elde edilir:
$$T(n,k)=\sum_{i=0}^{n} a_i\,T(n-i,k-1).$$
Başlangıç koşulları
$$T(0,0)=1,\qquad T(n,0)=0 \text{ for } n>0,$$
ve tek koordinat için
$$T(n,1)=a_n$$
şeklindedir. Yani her yeni koordinat, \((a_0,a_1,a_2,\dots)\) dizisiyle bir kez daha ayrık evrişim yapılması anlamına gelir.
Şu adi üreteç serisini tanımlayalım:
$$A(x)=\sum_{r\ge 0} a_r x^r$$
ve sabit \(k\) için
$$F_k(x)=\sum_{n\ge 0} T(n,k)x^n.$$
Önceki adımdaki rekürans doğrudan
$$F_k(x)=A(x)\,F_{k-1}(x)$$
ilişkisine dönüşür. \(F_0(x)=1\) ile iterasyon yapınca
$$F_k(x)=A(x)^k$$
elde edilir. Dolayısıyla aranan değer
$$\boxed{T(n,k)=[x^n]A(x)^k.}$$
C++, Python ve Java uygulamalarının tam olarak yaptığı şey budur.
Yalnızca \([x^n]A(x)^k\) katsayısı gerektiği için, derecesi \(n\)'den büyük bir terim daha sonra tekrar işe yarar hale gelemez. Sonraki her çarpım yalnızca negatif olmayan üsler eklediğinden, bir kez \(n\)'yi aşan derece ancak daha da büyür.
Bu nedenle her çarpımdan sonra derece \(n\)'in üzerindeki tüm terimler güvenle atılabilir ve sadece
$$c_0+c_1x+\cdots+c_nx^n$$
saklanır. Bu yüzden tüm üs alma süreci boyunca polinomlar uzunluk \(n+1\) ile sınırlandırılır.
Derecesi \(n\) olan iki polinomu naif biçimde çarpmak \(O(n^2)\) zaman alır ve hedef boyutta yeterli değildir. Kullanılan modül
$$M=1004535809=479\cdot 2^{21}+1$$
olduğundan, \(M-1\) büyük bir \(2\) kuvveti içerir. Böylece
$$L=2^m \le 2^{21}$$
olan her dönüşüm uzunluğu için gerekli ilkel \(L\). birim kökler mod \(M\) altında vardır. Özellikle ilkel kök \(3\), dönüşümün ihtiyaç duyduğu bütün kökleri üretir. Böylece polinom çarpımı tam olarak mod \(M\) altında
$$O(L\log L)$$
zamanda yapılabilir.
İlk katsayı kovaları asal sayılardan doğrudan okunur:
$$a_0=1,\qquad a_1=3-2=1,\qquad a_2=5-3=2,\qquad a_3=7-5=2.$$
Bunların karşılık geldiği kümeler
$$\pi(x)=0 \Rightarrow \{1\},\qquad \pi(x)=1 \Rightarrow \{2\},\qquad \pi(x)=2 \Rightarrow \{3,4\},\qquad \pi(x)=3 \Rightarrow \{5,6\}$$
şeklindedir. O halde
$$T(3,2)=[x^3]A(x)^2=a_0a_3+a_1a_2+a_2a_1+a_3a_0=2+2+2+2=8.$$
Sekiz sıralı çift şunlardır:
$$(1,5),(1,6),(2,3),(2,4),(3,2),(4,2),(5,1),(6,1).$$
Bu küçük örnek, katsayı çıkarmanın neden tuple sayımına tam karşılık geldiğini açıkça gösterir.
Uygulamalar önce \(0\le r\le n\) için \(p_{r+1}-p_r\) farklarını hesaplayabilecek kadar ardışık asal üretir. Sonra bu farklardan, derece \(n\)'e kadar kesilmiş \(A(x)\) katsayı listesini kurar.
Polinom çarpımı için iki katsayı dizisi bir sonraki \(2\) kuvvetine kadar sıfırlarla uzatılır, ileri NTT uygulanır, değerler noktadan noktaya çarpılır ve ters NTT ile katsayılara geri dönülür. Her çarpımdan sonra sonuç hemen derece \(n\)'e kesilir.
\(A(x)^k\) hesabı polinom halkasında binary exponentiation ile yapılır: \(k\)'nin ilgili biti \(1\) ise o anki sonuç mevcut tabanla çarpılır; sonra taban karesine yükseltilir. Her ara adımda kesme yapıldığı için derece kontrol altında kalır.
İşlem bittiğinde \(x^n\) katsayısı mod \(M\) olarak döndürülür.
\(p_{n+1}\)'i içerecek kadar büyük bir süzgeç sınırı \(B\) ve \(L\ge 2n+1\) koşulunu sağlayan en küçük \(2\) kuvveti \(L\) olsun. Gerekli asalları süzgeçle üretmek \(O(B\log\log B)\) zaman ve \(O(B)\) bellek ister.
Her kesmeli polinom çarpımı \(O(L\log L)\) maliyetlidir ve binary exponentiation toplam \(O(\log k)\) adet böyle çarpım yapar. Bu yüzden toplam çalışma süresi
$$O(B\log\log B + L\log L\log k)$$
olur. \(L=O(n)\) olduğundan polinom kısmı genellikle
$$O(n\log n\log k)$$
şeklinde özetlenir. Bellek kullanımı, süzgeç ve polinom tamponları birlikte düşünülürse \(O(B+L)\)'dir.
Sea \(\pi(x)\) el número de primos menores o iguales que \(x\), y sea \(p_r\) el \(r\)-ésimo primo. Se pide calcular \(T(n,k)\), el número de \(k\)-tuplas ordenadas de enteros positivos \((x_1,\dots,x_k)\) tales que
$$\pi(x_1)+\pi(x_2)+\cdots+\pi(x_k)=n,$$
tomando el resultado módulo
$$M=1004535809.$$
La observación central es que muchos enteros distintos comparten el mismo valor de \(\pi(x)\), y esas multiplicidades están gobernadas exactamente por las diferencias entre primos consecutivos.
La solución convierte el conteo de tuplas en un problema de extracción de coeficientes y luego acelera las multiplicaciones de polinomios mediante NTT.
Para \(r=0\), solo existe un entero positivo con \(\pi(x)=0\), a saber \(x=1\). Por eso
$$a_0=1.$$
Para todo \(r\ge 1\), la condición \(\pi(x)=r\) significa que \(x\) está entre el \(r\)-ésimo primo y el siguiente:
$$\pi(x)=r \iff p_r \le x \le p_{r+1}-1.$$
Así, la cantidad de tales enteros es exactamente el salto primo
$$a_r=p_{r+1}-p_r \qquad (r\ge 1).$$
Estos coeficientes son los pesos básicos del problema: \(a_r\) cuenta cuántas opciones tiene una coordenada si aporta exactamente \(r\) al total.
Si la primera coordenada aporta \(i\), hay \(a_i\) maneras de elegirla, y las \(k-1\) coordenadas restantes deben aportar \(n-i\). De aquí sale la recurrencia por convolución
$$T(n,k)=\sum_{i=0}^{n} a_i\,T(n-i,k-1).$$
Las condiciones iniciales naturales son
$$T(0,0)=1,\qquad T(n,0)=0 \text{ para } n>0,$$
y para una sola coordenada simplemente
$$T(n,1)=a_n.$$
En otras palabras, cada nueva coordenada añade una convolución discreta más con la sucesión \((a_0,a_1,a_2,\dots)\).
Definimos la serie generadora ordinaria
$$A(x)=\sum_{r\ge 0} a_r x^r$$
y, para \(k\) fijo,
$$F_k(x)=\sum_{n\ge 0} T(n,k)x^n.$$
La recurrencia anterior se transforma en
$$F_k(x)=A(x)\,F_{k-1}(x).$$
Iterando y usando \(F_0(x)=1\), obtenemos
$$F_k(x)=A(x)^k.$$
Por tanto, la respuesta es exactamente el coeficiente de \(x^n\):
$$\boxed{T(n,k)=[x^n]A(x)^k.}$$
Esa es la afirmación matemática que implementan directamente las soluciones.
Si solo nos interesa \([x^n]A(x)^k\), ningún coeficiente de grado mayor que \(n\) podrá volver a influir después. Cada multiplicación futura solo suma exponentes no negativos, así que un término que ya superó el grado \(n\) jamás regresará al grado \(n\).
Por eso, tras cada producto, se pueden eliminar con seguridad todos los términos de grado superior y conservar únicamente
$$c_0+c_1x+\cdots+c_nx^n.$$
Así se mantiene siempre una longitud \(n+1\) durante toda la exponenciación binaria.
Una convolución ingenua de dos polinomios de grado \(n\) cuesta \(O(n^2)\), demasiado para los parámetros reales. El módulo elegido es
$$M=1004535809=479\cdot 2^{21}+1.$$
Como \(M-1\) contiene una gran potencia de \(2\), toda longitud de transformada
$$L=2^m \le 2^{21}$$
dispone de raíces primitivas \(L\)-ésimas de la unidad módulo \(M\). En particular, la raíz primitiva \(3\) permite construir todas las raíces necesarias. Así, cada multiplicación polinómica puede hacerse exactamente módulo \(M\) en
$$O(L\log L)$$
mediante Number Theoretic Transform.
Los primeros cubos de coeficientes salen directamente de los primos:
$$a_0=1,\qquad a_1=3-2=1,\qquad a_2=5-3=2,\qquad a_3=7-5=2.$$
Eso corresponde a
$$\pi(x)=0 \Rightarrow \{1\},\qquad \pi(x)=1 \Rightarrow \{2\},\qquad \pi(x)=2 \Rightarrow \{3,4\},\qquad \pi(x)=3 \Rightarrow \{5,6\}.$$
Entonces
$$T(3,2)=[x^3]A(x)^2=a_0a_3+a_1a_2+a_2a_1+a_3a_0=2+2+2+2=8.$$
Las ocho parejas ordenadas son
$$(1,5),(1,6),(2,3),(2,4),(3,2),(4,2),(5,1),(6,1).$$
Este ejemplo pequeño muestra con claridad por qué la extracción de coeficientes coincide exactamente con el conteo pedido.
Las implementaciones generan primero suficientes primos consecutivos para conocer todos los saltos \(p_{r+1}-p_r\) con \(0\le r\le n\). A partir de esos saltos construyen la lista truncada de coeficientes de \(A(x)\) hasta grado \(n\).
La multiplicación de polinomios se hace rellenando ambos arreglos de coeficientes hasta la siguiente potencia de dos, aplicando la NTT directa, multiplicando punto a punto y aplicando la NTT inversa. Después de cada producto, se descartan enseguida los términos de grado mayor que \(n\).
Para obtener \(A(x)^k\), las implementaciones usan exponenciación binaria en el anillo de polinomios: cuando el bit actual de \(k\) vale \(1\), el resultado acumulado se multiplica por la base actual; luego la base se eleva al cuadrado. Gracias al recorte, ningún polinomio crece más de lo necesario.
Al final se devuelve el coeficiente de \(x^n\) módulo \(M\).
Sea \(B\) una cota de criba suficiente para contener \(p_{n+1}\), y sea \(L\) la menor potencia de dos con \(L\ge 2n+1\). Generar los primos necesarios mediante criba cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria.
Cada multiplicación truncada cuesta \(O(L\log L)\), y la exponenciación binaria realiza \(O(\log k)\) multiplicaciones de este tipo. Por tanto, el coste total es
$$O(B\log\log B + L\log L\log k).$$
Como \(L=O(n)\), la parte polinómica suele resumirse como
$$O(n\log n\log k).$$
La memoria total es \(O(B+L)\) mientras conviven la criba y los búferes de polinomios.
设 \(\pi(x)\) 表示不超过 \(x\) 的素数个数，\(p_r\) 表示第 \(r\) 个素数。题目要求计算有序 \(k\) 元组 \((x_1,\dots,x_k)\) 的个数 \(T(n,k)\)，其中每个 \(x_i\) 都是正整数，并满足
$$\pi(x_1)+\pi(x_2)+\cdots+\pi(x_k)=n,$$
最后答案对
$$M=1004535809$$
取模。真正让问题变得可做的关键，是把“一个整数对总和贡献多少”这件事先按 \(\pi(x)\) 的取值分类，而同一类整数的个数恰好由相邻素数之间的间隔给出。
整个解法可以分成两层：第一层把计数问题写成一个普通生成函数的系数提取问题；第二层用 NTT 快速完成多次多项式卷积。
当 \(r=0\) 时，\(\pi(x)=0\) 的正整数只有 \(x=1\) 一个，因此
$$a_0=1.$$
当 \(r\ge 1\) 时，条件 \(\pi(x)=r\) 等价于说 \(x\) 落在第 \(r\) 个素数和第 \(r+1\) 个素数之间：
$$\pi(x)=r \iff p_r \le x \le p_{r+1}-1.$$
所以这类整数的数量就是相邻两个素数之间的差：
$$a_r=p_{r+1}-p_r \qquad (r\ge 1).$$
这一步非常重要，因为它把原题中“选整数”的自由度压缩成了一个简单序列 \((a_0,a_1,a_2,\dots)\)。以后每当某个坐标需要贡献 \(r\)，可选值的个数就正好是 \(a_r\)。
如果第一个坐标贡献 \(i\)，那么这个坐标有 \(a_i\) 种取法，剩下的 \(k-1\) 个坐标必须一共贡献 \(n-i\)。于是得到递推式
$$T(n,k)=\sum_{i=0}^{n} a_i\,T(n-i,k-1).$$
自然的初值是
$$T(0,0)=1,\qquad T(n,0)=0 \text{ 当 } n>0,$$
而只有一个坐标时显然有
$$T(n,1)=a_n.$$
从这个式子已经可以看出，问题的本质就是不断把序列 \((a_r)\) 与已有答案做卷积。也就是说，题目真正的计算核心是快速多项式乘法，而不是直接枚举元组。
定义普通生成函数
$$A(x)=\sum_{r\ge 0} a_r x^r,$$
再定义固定 \(k\) 时的答案生成函数
$$F_k(x)=\sum_{n\ge 0} T(n,k)x^n.$$
由上面的卷积递推立刻得到
$$F_k(x)=A(x)\,F_{k-1}(x).$$
再配合 \(F_0(x)=1\) 递推下去，就有
$$F_k(x)=A(x)^k.$$
因此原题答案正是
$$\boxed{T(n,k)=[x^n]A(x)^k.}$$
这一步把一个看似复杂的组合计数问题，压缩成了“求某个多项式幂的第 \(n\) 项系数”。这也正是三种实现的共同数学核心。
既然最终只需要 \(x^n\) 的系数，那么任何次数大于 \(n\) 的项以后都不可能重新影响答案。原因很简单：后续乘法只会把指数相加，而不会减少指数。
所以某次乘法产生了 \(x^{n+1},x^{n+2},\dots\) 这样的高次项之后，它们在后面的所有步骤里只会继续保持高次，不可能再“降回” \(x^n\)。因此每做完一次卷积，都可以立刻把结果裁剪成
$$c_0+c_1x+\cdots+c_nx^n$$
而不会改变最终答案。这个结论非常关键，因为它让中间多项式的长度始终保持在 \(n+1\)，否则重复平方时次数会迅速膨胀。
如果直接做多项式卷积，两个 \(n\) 次多项式相乘需要 \(O(n^2)\) 时间，对题目的目标规模来说太慢。这里选用的模数是
$$M=1004535809=479\cdot 2^{21}+1.$$
因为 \(M-1\) 含有很大的 \(2\) 的幂，所以对于任意
$$L=2^m \le 2^{21}$$
这样的长度，都存在模 \(M\) 下的原始 \(L\) 次单位根。特别地，原始根 \(3\) 可以生成变换所需的全部单位根。于是就能用 Number Theoretic Transform 在模 \(M\) 下精确地完成卷积，而不需要浮点 FFT，也不会有舍入误差。
这样一次卷积的复杂度就从 \(O(n^2)\) 降到
$$O(L\log L).$$
再配合二进制快速幂，就足以处理 \(n\) 和 \(k\) 都很大的情形。
先看前几个系数：
$$a_0=1,\qquad a_1=3-2=1,\qquad a_2=5-3=2,\qquad a_3=7-5=2.$$
它们对应的整数集合分别是
$$\pi(x)=0 \Rightarrow \{1\},\qquad \pi(x)=1 \Rightarrow \{2\},\qquad \pi(x)=2 \Rightarrow \{3,4\},\qquad \pi(x)=3 \Rightarrow \{5,6\}.$$
因此
$$T(3,2)=[x^3]A(x)^2=a_0a_3+a_1a_2+a_2a_1+a_3a_0=2+2+2+2=8.$$
如果把实际的有序二元组列出来，就是
$$(1,5),(1,6),(2,3),(2,4),(3,2),(4,2),(5,1),(6,1).$$
这个例子很小，但已经完整展示了方法的含义：先按每个坐标的 prime-count 贡献分桶，再通过生成函数乘法把各个坐标的贡献合并起来。
三种实现的整体流程一致。第一步是先筛出足够多的连续素数，从而拿到所有需要的相邻素数差 \(p_{r+1}-p_r\)，并据此构造出 \(A(x)\) 的前 \(n+1\) 个系数。
第二步是把多项式乘法实现成 NTT 卷积。做法是把两个系数数组补零到合适的 \(2\) 的幂长度，做正变换，在频域逐点相乘，再做逆变换恢复系数。乘完以后立刻把高于 \(n\) 次的部分截掉。
第三步是用二进制快速幂来求 \(A(x)^k\)。当前指数位为 \(1\) 时，就把当前结果与当前底多项式相乘；然后把底多项式平方。由于每一步都截断，中间多项式始终不会超过需要的长度。
最后只要读取 \(x^n\) 的系数并对 \(M\) 取模即可。
设 \(B\) 是足以包含 \(p_{n+1}\) 的筛法上界，设 \(L\) 是满足 \(L\ge 2n+1\) 的最小 \(2\) 的幂。筛出所需素数的代价是 \(O(B\log\log B)\) 时间和 \(O(B)\) 空间。
一次截断卷积需要 \(O(L\log L)\) 时间，而二进制快速幂总共需要 \(O(\log k)\) 次这样的卷积，所以总时间复杂度是
$$O(B\log\log B + L\log L\log k).$$
因为 \(L=O(n)\)，多项式部分通常记作
$$O(n\log n\log k).$$
在筛数组和多项式缓冲区同时存在时，总空间复杂度为 \(O(B+L)\)。
Пусть \(\pi(x)\) обозначает число простых чисел, не превосходящих \(x\), а \(p_r\) обозначает \(r\)-е простое число. Нужно найти \(T(n,k)\), то есть число упорядоченных \(k\)-кортежей положительных целых чисел \((x_1,\dots,x_k)\), для которых
$$\pi(x_1)+\pi(x_2)+\cdots+\pi(x_k)=n,$$
и выдать ответ по модулю
$$M=1004535809.$$
Ключевая идея состоит в том, что многие разные целые числа дают одно и то же значение функции \(\pi(x)\), а число таких целых выражается через промежутки между соседними простыми.
Решение сначала переводит задачу о кортежах в задачу о коэффициенте производящей функции, а затем ускоряет полиномиальные умножения с помощью NTT.
Для \(r=0\) существует только одно положительное число с \(\pi(x)=0\), а именно \(x=1\). Поэтому
$$a_0=1.$$
Для любого \(r\ge 1\) условие \(\pi(x)=r\) эквивалентно тому, что \(x\) лежит между \(r\)-м и \((r+1)\)-м простыми:
$$\pi(x)=r \iff p_r \le x \le p_{r+1}-1.$$
Значит, количество таких чисел равно точно промежутку между соседними простыми:
$$a_r=p_{r+1}-p_r \qquad (r\ge 1).$$
Эти коэффициенты являются базовыми весами задачи: \(a_r\) показывает, сколько существует вариантов для одной координаты, если она должна внести ровно \(r\) в общую сумму.
Если первая координата вносит \(i\), то ее можно выбрать \(a_i\) способами, а остальные \(k-1\) координат должны суммарно дать \(n-i\). Отсюда получается свёрточная рекурсия
$$T(n,k)=\sum_{i=0}^{n} a_i\,T(n-i,k-1).$$
Начальные условия естественны:
$$T(0,0)=1,\qquad T(n,0)=0 \text{ при } n>0,$$
а для одного элемента имеем просто
$$T(n,1)=a_n.$$
Тем самым уже видно, что каждая новая координата добавляет еще одну дискретную свёртку с последовательностью \((a_0,a_1,a_2,\dots)\).
Введем обычную производящую функцию
$$A(x)=\sum_{r\ge 0} a_r x^r$$
и для фиксированного \(k\)
$$F_k(x)=\sum_{n\ge 0} T(n,k)x^n.$$
Тогда предыдущая рекурсия переписывается в виде
$$F_k(x)=A(x)\,F_{k-1}(x).$$
Итерируя это соотношение и используя \(F_0(x)=1\), получаем
$$F_k(x)=A(x)^k.$$
Следовательно, искомый ответ равен коэффициенту при \(x^n\):
$$\boxed{T(n,k)=[x^n]A(x)^k.}$$
Именно это равенство и реализовано в программах.
Если нас интересует только коэффициент \([x^n]A(x)^k\), то любой член степени больше \(n\) уже никогда не сможет повлиять на ответ. При дальнейших умножениях показатели степеней только складываются и никогда не уменьшаются.
Значит, после каждого произведения можно безопасно отбрасывать все члены выше степени \(n\) и оставлять только
$$c_0+c_1x+\cdots+c_nx^n.$$
Именно поэтому во всех промежуточных шагах длина полинома ограничивается \(n+1\), хотя возведение в степень выполняется методом двоичного быстрого возведения.
Наивная свёртка двух полиномов степени \(n\) стоит \(O(n^2)\), что слишком дорого для реальных параметров. Используемый модуль равен
$$M=1004535809=479\cdot 2^{21}+1.$$
Так как \(M-1\) содержит большую степень двойки, для любой длины преобразования
$$L=2^m \le 2^{21}$$
существуют необходимые примитивные \(L\)-е корни единицы по модулю \(M\). В частности, примитивный корень \(3\) позволяет получить все корни, нужные для NTT. Поэтому каждое полиномиальное произведение можно вычислять точно по модулю \(M\) за
$$O(L\log L)$$
вместо квадратичного времени.
Первые коэффициенты легко выписываются из первых простых:
$$a_0=1,\qquad a_1=3-2=1,\qquad a_2=5-3=2,\qquad a_3=7-5=2.$$
Им соответствуют множества
$$\pi(x)=0 \Rightarrow \{1\},\qquad \pi(x)=1 \Rightarrow \{2\},\qquad \pi(x)=2 \Rightarrow \{3,4\},\qquad \pi(x)=3 \Rightarrow \{5,6\}.$$
Тогда
$$T(3,2)=[x^3]A(x)^2=a_0a_3+a_1a_2+a_2a_1+a_3a_0=2+2+2+2=8.$$
Восемь упорядоченных пар таковы:
$$(1,5),(1,6),(2,3),(2,4),(3,2),(4,2),(5,1),(6,1).$$
Этот небольшой пример наглядно показывает, почему извлечение коэффициента точно совпадает с исходным подсчетом кортежей.
Сначала реализации генерируют достаточно много последовательных простых чисел, чтобы знать все разности \(p_{r+1}-p_r\) для \(0\le r\le n\). Из этих разностей строится усеченный список коэффициентов полинома \(A(x)\) до степени \(n\).
Умножение полиномов выполняется так: оба массива коэффициентов дополняются нулями до ближайшей степени двойки, затем применяется прямая NTT, выполняется покомпонентное умножение и затем обратная NTT. После каждого произведения все коэффициенты степеней выше \(n\) сразу отбрасываются.
Чтобы получить \(A(x)^k\), программы используют двоичное быстрое возведение в степень в кольце полиномов: если текущий бит показателя равен \(1\), текущее накопленное значение умножается на текущую базу; затем база возводится в квадрат. Благодаря усечению размеры промежуточных полиномов не растут лишним образом.
В конце возвращается коэффициент при \(x^n\) по модулю \(M\).
Пусть \(B\) обозначает границу решета, достаточную для включения \(p_{n+1}\), а \(L\) обозначает наименьшую степень двойки с \(L\ge 2n+1\). Построение нужных простых чисел решетом требует \(O(B\log\log B)\) времени и \(O(B)\) памяти.
Каждое усеченное умножение полиномов стоит \(O(L\log L)\), а двоичное возведение в степень выполняет \(O(\log k)\) таких умножений. Поэтому общее время равно
$$O(B\log\log B + L\log L\log k).$$
Так как \(L=O(n)\), полиномиальную часть обычно записывают как
$$O(n\log n\log k).$$
Память составляет \(O(B+L)\), пока одновременно существуют решето и буферы полиномов.
لتكن \(\pi(x)\) دالة عدّ الأعداد الأولية التي لا تتجاوز \(x\)، وليكن \(p_r\) هو العدد الأولي رقم \(r\). المطلوب حساب \(T(n,k)\)، أي عدد \(k\)-tuples المرتبة من الأعداد الصحيحة الموجبة \((x_1,\dots,x_k)\) التي تحقق
$$\pi(x_1)+\pi(x_2)+\cdots+\pi(x_k)=n,$$
مع أخذ النتيجة بترديد
$$M=1004535809.$$
الفكرة الحاسمة هي أن كثيرا من الأعداد المختلفة تعطي القيمة نفسها للدالة \(\pi(x)\)، وعدد هذه الأعداد يساوي تماما الفجوة بين عددين أوليين متتاليين.
يحوّل الحل مسألة عدّ tuples إلى مسألة استخراج معامل من دالة مولدة، ثم يسرّع ضرب كثيرات الحدود باستعمال NTT.
عندما يكون \(r=0\)، يوجد عدد صحيح موجب واحد فقط يحقق \(\pi(x)=0\)، وهو \(x=1\). لذلك
$$a_0=1.$$
أما عندما \(r\ge 1\)، فإن الشرط \(\pi(x)=r\) يكافئ أن يقع \(x\) بين العدد الأولي رقم \(r\) والذي يليه:
$$\pi(x)=r \iff p_r \le x \le p_{r+1}-1.$$
ومن ثم فإن عدد هذه القيم يساوي فجوة الأعداد الأولية:
$$a_r=p_{r+1}-p_r \qquad (r\ge 1).$$
هذه المعاملات هي الأوزان الأساسية في المسألة: فالقيمة \(a_r\) تعدّ عدد اختيارات الإحداثي الواحد إذا كان مطلوبا منه أن يساهم بمقدار \(r\) في المجموع النهائي.
إذا ساهم الإحداثي الأول بمقدار \(i\)، فلدينا \(a_i\) اختيارا له، ويجب على الإحداثيات \(k-1\) الباقية أن تساهم بمجموع \(n-i\). وهكذا نحصل على علاقة التفاف:
$$T(n,k)=\sum_{i=0}^{n} a_i\,T(n-i,k-1).$$
والشروط الابتدائية الطبيعية هي
$$T(0,0)=1,\qquad T(n,0)=0.$$
والعلاقة الثانية تخص الحالة \(n>0\).
أما عندما يوجد إحداثي واحد فقط فلدينا ببساطة
$$T(n,1)=a_n.$$
إذن البنية التجميعية للمسألة تقول مباشرة إن إضافة كل إحداثي جديد تعني إجراء التفاف جديد مع المتتالية \((a_0,a_1,a_2,\dots)\).
نعرّف الدالة المولدة العادية
$$A(x)=\sum_{r\ge 0} a_r x^r$$
ونعرّف أيضا، عند تثبيت \(k\)،
$$F_k(x)=\sum_{n\ge 0} T(n,k)x^n.$$
العلاقة السابقة تتحول فورا إلى
$$F_k(x)=A(x)\,F_{k-1}(x).$$
وبالتكرار مع \(F_0(x)=1\) نحصل على
$$F_k(x)=A(x)^k.$$
لذلك تكون الإجابة المطلوبة هي معامل \(x^n\):
$$\boxed{T(n,k)=[x^n]A(x)^k.}$$
وهذه هي الصياغة الرياضية الدقيقة التي تعتمدها جميع التطبيقات.
بما أننا نريد فقط المعامل \([x^n]A(x)^k\)، فإن أي حد درجته أكبر من \(n\) لن يعود مهما لاحقا. ففي جميع الضربات اللاحقة لا نفعل إلا جمع الأسس غير السالبة، لذلك لا يمكن لحد تجاوز الدرجة \(n\) أن يعود إلى الدرجة \(n\).
ولهذا السبب يمكن بعد كل ضرب أن نحتفظ فقط بالجزء
$$c_0+c_1x+\cdots+c_nx^n$$
ونحذف كل ما فوقه دون أي تأثير على الجواب النهائي. هذه النقطة هي ما يسمح باستعمال كثيرات حدود مقصوصة بطول \(n+1\) طوال عملية الرفع السريع للأس.
الالتفاف الساذج بين كثيري حدود من الدرجة \(n\) يكلف \(O(n^2)\)، وهذا بطيء جدا للقيم المطلوبة. المود المستخدم هو
$$M=1004535809=479\cdot 2^{21}+1.$$
ولأن \(M-1\) يحتوي على قوة كبيرة للعدد \(2\)، فإن كل طول تحويل من الشكل
$$L=2^m \le 2^{21}$$
يملك الجذور البدائية اللازمة من الرتبة \(L\) بترديد \(M\). وبصورة خاصة فإن الجذر البدائي \(3\) يولّد جميع الجذور التي تحتاجها NTT. لذلك يمكن تنفيذ التفاف كثيرات الحدود بدقة تامة بترديد \(M\) في
$$O(L\log L)$$
بدلا من الزمن التربيعي.
أول معاملات السلسلة نحصل عليها مباشرة من الأعداد الأولية الأولى:
$$a_0=1,\qquad a_1=3-2=1,\qquad a_2=5-3=2,\qquad a_3=7-5=2.$$
وهذا يعني أن
$$\pi(x)=0 \Rightarrow \{1\},\qquad \pi(x)=1 \Rightarrow \{2\},\qquad \pi(x)=2 \Rightarrow \{3,4\},\qquad \pi(x)=3 \Rightarrow \{5,6\}.$$
وعليه فإن
$$T(3,2)=[x^3]A(x)^2=a_0a_3+a_1a_2+a_2a_1+a_3a_0=2+2+2+2=8.$$
والأزواج المرتبة الثمانية هي
$$(1,5),(1,6),(2,3),(2,4),(3,2),(4,2),(5,1),(6,1).$$
هذا المثال الصغير يوضح تماما لماذا تساوي عملية استخراج المعامل عملية العد الأصلية.
تبدأ التطبيقات بتوليد عدد كاف من الأعداد الأولية المتتالية حتى تتوفر جميع الفجوات \(p_{r+1}-p_r\) اللازمة للقيم \(0\le r\le n\). ومن هذه الفجوات تُبنى قائمة معاملات \(A(x)\) المقطوعة حتى الدرجة \(n\).
بعد ذلك يُنفَّذ ضرب كثيرات الحدود بواسطة NTT: تُمدّ مصفوفتا المعاملات بالأصفار حتى أقرب قوة للعدد \(2\)، ثم يُجرى التحويل الأمامي، ثم الضرب نقطة بنقطة، ثم التحويل العكسي. وبعد كل ضرب تُحذف الحدود ذات الدرجة الأعلى من \(n\) مباشرة.
ولحساب \(A(x)^k\)، تستعمل التطبيقات الرفع الثنائي للأس داخل حلقة كثيرات الحدود. إذا كانت البتة الحالية في \(k\) تساوي \(1\)، يُضرب الناتج الجاري في الأساس الجاري، ثم يُربّع الأساس. وبما أن القطع يحدث بعد كل خطوة، تبقى أطوال كثيرات الحدود ضمن الحد المطلوب فقط.
وفي النهاية يُعاد معامل \(x^n\) بترديد \(M\).
ليكن \(B\) حدا أعلى للغربال يكفي لاحتواء \(p_{n+1}\)، ولتكن \(L\) أصغر قوة للعدد \(2\) تحقق \(L\ge 2n+1\). توليد الأعداد الأولية المطلوبة بالغربال يكلف \(O(B\log\log B)\) زمنا و\(O(B)\) ذاكرة.
كل ضرب مقصوص لكثيرات الحدود يكلف \(O(L\log L)\)، والرفع الثنائي للأس يحتاج إلى \(O(\log k)\) عمليات ضرب من هذا النوع. لذلك يكون التعقيد الكلي
$$O(B\log\log B + L\log L\log k).$$
وبما أن \(L=O(n)\)، فعادة تختصر المرحلة كثيرية الحدود إلى
$$O(n\log n\log k).$$
أما الذاكرة فمقدارها \(O(B+L)\) عندما تتواجد بنى الغربال ومخازن كثيرات الحدود في الوقت نفسه.