Let \(E_n=(\mathbb{Z}_{>0})^n\). For two positive-integer vectors \(u=(u_1,\dots,u_n)\) and \(v=(v_1,\dots,v_n)\), define
$$\langle u,v\rangle=\sum_{i=1}^{n}u_iv_i,\qquad u\star v=\prod_{i=1}^{n}(u_i+v_i).$$
The quantity \(R_n(M)\) is the sum of \(u\star v\) over all ordered pairs \((u,v)\in E_n\times E_n\) satisfying \(\langle u,v\rangle=M\). The target is
$$R_6(10000!) \pmod{10^9+7}.$$
A direct enumeration of six-dimensional vector pairs is hopeless, so the solution converts the problem into coefficient extraction from a generating function and then reduces that generating function with quasimodular-form identities.
The computation rests on two ideas: first, each coordinate contributes independently through a one-variable divisor sum; second, the sixth power of the resulting generating series can be rewritten in a weight-12 quasimodular basis whose coefficients are easy to evaluate at \(10000!\).
For \(n=1\), the condition \(\langle u,v\rangle=M\) is simply \(uv=M\). Every divisor \(d\mid M\) gives the ordered pair \((d,M/d)\), whose contribution to \(u\star v\) is
$$d+\frac{M}{d}.$$
Therefore
$$R_1(M)=\sum_{d\mid M}\left(d+\frac{M}{d}\right)=2\sum_{d\mid M}d=2\sigma_1(M),$$
where \(\sigma_1(M)\) is the usual sum-of-divisors function.
For a general pair of vectors, set
$$m_i=u_iv_i \qquad (1\le i\le n).$$
Then
$$m_1+\cdots+m_n=M,$$
and for a fixed decomposition \(M=m_1+\cdots+m_n\), the contributions from the coordinates multiply. Hence
$$R_n(M)=\sum_{\substack{m_1+\cdots+m_n=M\\m_i\ge 1}}R_1(m_1)\cdots R_1(m_n).$$
If we define the generating series
$$G(q)=\sum_{m\ge 1}R_1(m)q^m,$$
then this is exactly the \(n\)-fold additive convolution identity
$$R_n(M)=[q^M]\,G(q)^n.$$
The normalized quasimodular Eisenstein series \(E_2\) satisfies
$$E_2(q)=1-24\sum_{m\ge 1}\sigma_1(m)q^m.$$
Since \(R_1(m)=2\sigma_1(m)\), we obtain
$$G(q)=2\sum_{m\ge 1}\sigma_1(m)q^m=\frac{1-E_2(q)}{12}.$$
For the required dimension \(n=6\), this gives
$$R_6(M)=[q^M]\left(\frac{1-E_2(q)}{12}\right)^6.$$
Because \(M=10000!>0\), the constant term contributes nothing, so the task becomes the extraction of the positive-\(q\) coefficients of powers of \(E_2\).
Write
$$D=q\frac{d}{dq}.$$
For any series \(f(q)=\sum_{m\ge 0}a_mq^m\), we have
$$[q^M]D^r f=M^r a_M.$$
The implementation uses the standard quasimodular reductions
$$E_2^2=E_4+12DE_2,$$
$$E_2^3=E_6+9DE_4+72D^2E_2,$$
$$E_2^4=E_8+8DE_6+\frac{216}{5}D^2E_4+288D^3E_2,$$
$$E_2^5=E_{10}+\frac{15}{2}DE_8+\frac{240}{7}D^2E_6+144D^3E_4+864D^4E_2,$$
$$E_2^6=E_{12}-\frac{4608}{24185}\Delta+\frac{36}{5}DE_{10}+30D^2E_8+\frac{720}{7}D^3E_6+\frac{2592}{7}D^4E_4+\frac{10368}{5}D^5E_2.$$
Here \(\Delta(q)=\sum_{m\ge 1}\tau(m)q^m\) is the discriminant cusp form. The positive-\(q\) coefficients of the Eisenstein series are
$$[q^M]E_2=-24\sigma_1(M),\qquad [q^M]E_4=240\sigma_3(M),\qquad [q^M]E_6=-504\sigma_5(M),$$
$$[q^M]E_8=480\sigma_7(M),\qquad [q^M]E_{10}=-264\sigma_9(M),\qquad [q^M]E_{12}=\frac{65520}{691}\sigma_{11}(M),$$
and
$$[q^M]\Delta=\tau(M).$$
So every coefficient needed for \((1-E_2)^6\) becomes a linear combination of \(M^r\sigma_{2k-1}(M)\) and \(\tau(M)\).
Let \(N=10000\). For every prime \(p\le N\), Legendre's formula gives the exponent of \(p\) in \(N!\):
$$v_p(N!)=\sum_{t\ge 1}\left\lfloor\frac{N}{p^t}\right\rfloor.$$
Thus
$$10000!=\prod_{p\le 10000}p^{v_p(10000!)}.$$
For every odd \(r\in\{1,3,5,7,9,11\}\), multiplicativity gives
$$\sigma_r(10000!)=\prod_{p\le 10000}\left(1+p^r+\cdots+p^{r\,v_p(10000!)}\right)=\prod_{p\le 10000}\frac{p^{r(v_p(10000!)+1)}-1}{p^r-1}.$$
The Ramanujan tau function is multiplicative as well, so
$$\tau(10000!)=\prod_{p^e\parallel 10000!}\tau(p^e),$$
with the prime-power recurrence
$$\tau(p^e)=\tau(p)\tau(p^{e-1})-p^{11}\tau(p^{e-2}).$$
To obtain the prime values \(\tau(p)\), the implementation first builds the sequence \(\tau(n)\) up to \(10000\) from
$$\tau(1)=1,\qquad (n-1)\tau(n)=-24\sum_{k=1}^{n-1}\sigma_1(k)\tau(n-k)\qquad (n\ge 2).$$
For \(M=10\), the divisor pairs are \((1,10)\), \((2,5)\), \((5,2)\), and \((10,1)\). Their contributions are \(11\), \(7\), \(7\), and \(11\), so
$$R_1(10)=11+7+7+11=36=2(1+2+5+10).$$
Now use convolution for \(n=2\) and \(M=3\). The only decompositions into positive parts are \(3=1+2\) and \(3=2+1\). Since \(R_1(1)=2\) and \(R_1(2)=2(1+2)=6\), we get
$$R_2(3)=R_1(1)R_1(2)+R_1(2)R_1(1)=2\cdot 6+6\cdot 2=24.$$
This small case shows exactly why generating functions turn the problem into a power of one basic series.
The C++, Python, and Java implementations all follow the same pipeline. First they sieve the primes up to \(10000\) and compute every \(v_p(10000!)\). From those exponents they evaluate \(\sigma_1,\sigma_3,\sigma_5,\sigma_7,\sigma_9,\sigma_{11}\) multiplicatively modulo \(10^9+7\), and they also compute \(10000! \bmod (10^9+7)\) so that the factors \(M,M^2,\dots,M^5\) needed after differentiation are available.
Next the implementation builds \(\sigma_1(n)\) for all \(1\le n\le 10000\), uses the recurrence above to obtain \(\tau(n)\) up to \(10000\), and then extends from prime values to prime powers through the second-order recurrence for \(\tau(p^e)\). A \(2\times 2\) matrix power is used to evaluate that recurrence efficiently for each prime power.
Finally the program substitutes all divisor sums, the \(\tau\) term, and the powers of \(10000!\) into the weight-12 reduction of \((1-E_2)^6\). The last step is division by \(12^6=2985984\), implemented modulo \(10^9+7\) by multiplying with the modular inverse.
Let \(N=10000\). The prime sieve and the factorial valuations cost \(O(N\log\log N)\) time. Building the table of \(\sigma_1(n)\) by divisor accumulation costs \(O(N\log N)\). The recurrence for \(\tau(n)\) is quadratic, \(O(N^2)\), and this is the dominant step in the actual implementations. The remaining prime-product evaluations and prime-power recurrences are lower-order, roughly \(O(\pi(N)\log N)\). Memory usage is \(O(N)\).
Sei \(E_n=(\mathbb{Z}_{>0})^n\). Für zwei positive ganzzahlige Vektoren \(u=(u_1,\dots,u_n)\) und \(v=(v_1,\dots,v_n)\) sind definiert
$$\langle u,v\rangle=\sum_{i=1}^{n}u_iv_i,\qquad u\star v=\prod_{i=1}^{n}(u_i+v_i).$$
\(R_n(M)\) ist die Summe von \(u\star v\) über alle geordneten Paare \((u,v)\in E_n\times E_n\) mit \(\langle u,v\rangle=M\). Gesucht ist
$$R_6(10000!) \pmod{10^9+7}.$$
Direkte Enumeration ist aussichtslos. Deshalb formt die Lösung das Problem in eine Koeffizientenextraktion einer erzeugenden Funktion um und reduziert diese anschließend mit Identitäten aus der Theorie quasimodularer Formen.
Die Rechnung besteht aus zwei Schichten. Zuerst wird jede Koordinate auf eine eindimensionale Teilerfunktion zurückgeführt. Danach wird die sechste Potenz der entstehenden erzeugenden Reihe in eine Gewicht-12-Basis zerlegt, deren Koeffizienten bei \(10000!\) effizient ausgewertet werden können.
Für \(n=1\) bedeutet \(\langle u,v\rangle=M\) einfach \(uv=M\). Jeder Teiler \(d\mid M\) liefert das geordnete Paar \((d,M/d)\) mit Beitrag
$$d+\frac{M}{d}.$$
Also gilt
$$R_1(M)=\sum_{d\mid M}\left(d+\frac{M}{d}\right)=2\sum_{d\mid M}d=2\sigma_1(M).$$
Für ein allgemeines Paar setzen wir
$$m_i=u_iv_i\qquad (1\le i\le n).$$
Dann ist
$$m_1+\cdots+m_n=M,$$
und für eine feste Zerlegung von \(M\) multiplizieren sich die Beiträge der einzelnen Koordinaten. Daher
$$R_n(M)=\sum_{\substack{m_1+\cdots+m_n=M\\m_i\ge 1}}R_1(m_1)\cdots R_1(m_n).$$
Mit der erzeugenden Reihe
$$G(q)=\sum_{m\ge 1}R_1(m)q^m$$
folgt unmittelbar
$$R_n(M)=[q^M]\,G(q)^n.$$
Für die quasimodulare Reihe \(E_2\) gilt
$$E_2(q)=1-24\sum_{m\ge 1}\sigma_1(m)q^m.$$
Wegen \(R_1(m)=2\sigma_1(m)\) erhalten wir
$$G(q)=2\sum_{m\ge 1}\sigma_1(m)q^m=\frac{1-E_2(q)}{12}.$$
Damit reduziert sich der Zielwert auf
$$R_6(M)=[q^M]\left(\frac{1-E_2(q)}{12}\right)^6.$$
Da \(M=10000!>0\) ist, spielt der konstante Term keine Rolle mehr; entscheidend sind also nur die positiven Koeffizienten der Potenzen von \(E_2\).
Schreibe
$$D=q\frac{d}{dq}.$$
Für jede Reihe \(f(q)=\sum_{m\ge 0}a_mq^m\) gilt
$$[q^M]D^r f=M^r a_M.$$
Die verwendeten Reduktionsformeln sind
$$E_2^2=E_4+12DE_2,$$
$$E_2^3=E_6+9DE_4+72D^2E_2,$$
$$E_2^4=E_8+8DE_6+\frac{216}{5}D^2E_4+288D^3E_2,$$
$$E_2^5=E_{10}+\frac{15}{2}DE_8+\frac{240}{7}D^2E_6+144D^3E_4+864D^4E_2,$$
$$E_2^6=E_{12}-\frac{4608}{24185}\Delta+\frac{36}{5}DE_{10}+30D^2E_8+\frac{720}{7}D^3E_6+\frac{2592}{7}D^4E_4+\frac{10368}{5}D^5E_2.$$
Dabei ist \(\Delta(q)=\sum_{m\ge 1}\tau(m)q^m\) die Diskriminantenform. Für positive Koeffizienten gilt
$$[q^M]E_2=-24\sigma_1(M),\qquad [q^M]E_4=240\sigma_3(M),\qquad [q^M]E_6=-504\sigma_5(M),$$
$$[q^M]E_8=480\sigma_7(M),\qquad [q^M]E_{10}=-264\sigma_9(M),\qquad [q^M]E_{12}=\frac{65520}{691}\sigma_{11}(M),$$
sowie
$$[q^M]\Delta=\tau(M).$$
Somit wird jeder benötigte Koeffizient von \((1-E_2)^6\) zu einer Linearkombination aus \(M^r\sigma_{2k-1}(M)\) und \(\tau(M)\).
Setze \(N=10000\). Für jedes Prim \(p\le N\) liefert die Formel von Legendre
$$v_p(N!)=\sum_{t\ge 1}\left\lfloor\frac{N}{p^t}\right\rfloor.$$
Also
$$10000!=\prod_{p\le 10000}p^{v_p(10000!)}.$$
Für ungerades \(r\in\{1,3,5,7,9,11\}\) folgt aus der Multiplikativität
$$\sigma_r(10000!)=\prod_{p\le 10000}\left(1+p^r+\cdots+p^{r\,v_p(10000!)}\right)=\prod_{p\le 10000}\frac{p^{r(v_p(10000!)+1)}-1}{p^r-1}.$$
Auch die Ramanujan-Tau-Funktion ist multiplikativ:
$$\tau(10000!)=\prod_{p^e\parallel 10000!}\tau(p^e),$$
wobei für Primzahlpotenzen gilt
$$\tau(p^e)=\tau(p)\tau(p^{e-1})-p^{11}\tau(p^{e-2}).$$
Die Primwerte \(\tau(p)\) entstehen zunächst aus der Rekursion
$$\tau(1)=1,\qquad (n-1)\tau(n)=-24\sum_{k=1}^{n-1}\sigma_1(k)\tau(n-k)\qquad (n\ge 2).$$
Für \(M=10\) lauten die Teilerpaare \((1,10)\), \((2,5)\), \((5,2)\) und \((10,1)\). Die Beiträge sind \(11\), \(7\), \(7\) und \(11\), also
$$R_1(10)=11+7+7+11=36=2(1+2+5+10).$$
Für \(n=2\) und \(M=3\) gibt es nur die Zerlegungen \(3=1+2\) und \(3=2+1\). Mit \(R_1(1)=2\) und \(R_1(2)=6\) ergibt sich
$$R_2(3)=R_1(1)R_1(2)+R_1(2)R_1(1)=2\cdot 6+6\cdot 2=24.$$
Dieses kleine Beispiel zeigt exakt die Faltungsstruktur, die später durch Potenzen der erzeugenden Funktion erfasst wird.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst werden alle Primzahlen bis \(10000\) gesiebt und die Exponenten \(v_p(10000!)\) bestimmt. Daraus werden die sechs benötigten Divisorsummen \(\sigma_1,\sigma_3,\sigma_5,\sigma_7,\sigma_9,\sigma_{11}\) multiplicativ modulo \(10^9+7\) berechnet. Zusätzlich wird \(10000!\bmod(10^9+7)\) bestimmt, damit die Faktoren \(M,M^2,\dots,M^5\) aus den Ableitungen verfügbar sind.
Danach erzeugt die Implementierung alle Werte \(\sigma_1(n)\) für \(1\le n\le 10000\), berechnet daraus die Folge \(\tau(n)\) bis \(10000\) und erweitert anschließend von den Primwerten zu den Primzahlpotenzen \(\tau(p^e)\). Für diese zweite Stufe wird die lineare Rekursion mit einer \(2\times 2\)-Matrixpotenz ausgewertet.
Im letzten Schritt werden die Divisorsummen, der \(\tau\)-Term und die Potenzen von \(10000!\) in die Gewicht-12-Zerlegung von \((1-E_2)^6\) eingesetzt. Die Division durch \(12^6=2985984\) erfolgt modulo \(10^9+7\) über das multiplikative Inverse.
Für \(N=10000\) benötigen Primzahlsieb und Faktoriellbewertungen \(O(N\log\log N)\) Zeit. Die Tabelle \(\sigma_1(n)\) per Teilersummenverfahren kostet \(O(N\log N)\). Die Rekursion für \(\tau(n)\) ist quadratisch, also \(O(N^2)\), und dominiert damit die tatsächliche Laufzeit. Die verbleibenden Primprodukte und Primzahlpotenz-Rekursionen liegen nur bei etwa \(O(\pi(N)\log N)\). Der Speicherbedarf ist \(O(N)\).
\(E_n=(\mathbb{Z}_{>0})^n\) olsun. İki pozitif tamsayı vektörü \(u=(u_1,\dots,u_n)\) ve \(v=(v_1,\dots,v_n)\) için
$$\langle u,v\rangle=\sum_{i=1}^{n}u_iv_i,\qquad u\star v=\prod_{i=1}^{n}(u_i+v_i)$$
tanımlanır. \(R_n(M)\), \(\langle u,v\rangle=M\) şartını sağlayan tüm sıralı \((u,v)\in E_n\times E_n\) çiftleri üzerinde \(u\star v\) toplamıdır. İstenen değer
$$R_6(10000!) \pmod{10^9+7}$$
olduğundan doğrudan sayım mümkün değildir. Çözüm, önce problemi bir üreteç fonksiyon katsayısı bulma işine dönüştürür, sonra da bu fonksiyonu kuasimodüler form özdeşlikleriyle sadeleştirir.
Yöntemin özü şudur: tek bir koordinat basit bir bölen-toplamına indirgenir; ardından bu tek-boyutlu çekirdek altı kez evriştirilir; son olarak ortaya çıkan altıncı kuvvet, ağırlık 12 uzayında daha yönetilebilir bir tabana açılır.
\(n=1\) için \(\langle u,v\rangle=M\) şartı yalnızca \(uv=M\) demektir. Her \(d\mid M\) böleni, \((d,M/d)\) sıralı çiftini verir ve katkı
$$d+\frac{M}{d}$$
olur. Dolayısıyla
$$R_1(M)=\sum_{d\mid M}\left(d+\frac{M}{d}\right)=2\sum_{d\mid M}d=2\sigma_1(M).$$
Genel durumda
$$m_i=u_iv_i\qquad (1\le i\le n)$$
yazalım. O zaman
$$m_1+\cdots+m_n=M$$
olur ve sabit bir ayrışım için koordinat katkıları çarpılır. Bu yüzden
$$R_n(M)=\sum_{\substack{m_1+\cdots+m_n=M\\m_i\ge 1}}R_1(m_1)\cdots R_1(m_n).$$
Şimdi
$$G(q)=\sum_{m\ge 1}R_1(m)q^m$$
tanımını yaparsak, bu tam olarak
$$R_n(M)=[q^M]\,G(q)^n$$
kimliğini verir.
Kuasimodüler seri \(E_2\) için
$$E_2(q)=1-24\sum_{m\ge 1}\sigma_1(m)q^m$$
olduğundan ve \(R_1(m)=2\sigma_1(m)\) eşitliği geçerli olduğundan
$$G(q)=2\sum_{m\ge 1}\sigma_1(m)q^m=\frac{1-E_2(q)}{12}.$$
Böylece hedef değer
$$R_6(M)=[q^M]\left(\frac{1-E_2(q)}{12}\right)^6$$
şeklini alır. \(M=10000!>0\) olduğu için sabit terim hiçbir katkı vermez; önemli olan yalnızca \(E_2\)'nin kuvvetlerinin pozitif dereceli katsayılarıdır.
$$D=q\frac{d}{dq}$$
operatörünü kullanalım. Eğer \(f(q)=\sum_{m\ge 0}a_mq^m\) ise
$$[q^M]D^r f=M^r a_M$$
olur. Kullanılan standart indirgemeler şunlardır:
$$E_2^2=E_4+12DE_2,$$
$$E_2^3=E_6+9DE_4+72D^2E_2,$$
$$E_2^4=E_8+8DE_6+\frac{216}{5}D^2E_4+288D^3E_2,$$
$$E_2^5=E_{10}+\frac{15}{2}DE_8+\frac{240}{7}D^2E_6+144D^3E_4+864D^4E_2,$$
$$E_2^6=E_{12}-\frac{4608}{24185}\Delta+\frac{36}{5}DE_{10}+30D^2E_8+\frac{720}{7}D^3E_6+\frac{2592}{7}D^4E_4+\frac{10368}{5}D^5E_2.$$
Burada \(\Delta(q)=\sum_{m\ge 1}\tau(m)q^m\) diskriminant cusp formudur. Eisenstein serilerinin pozitif katsayıları
$$[q^M]E_2=-24\sigma_1(M),\qquad [q^M]E_4=240\sigma_3(M),\qquad [q^M]E_6=-504\sigma_5(M),$$
$$[q^M]E_8=480\sigma_7(M),\qquad [q^M]E_{10}=-264\sigma_9(M),\qquad [q^M]E_{12}=\frac{65520}{691}\sigma_{11}(M),$$
ve ayrıca
$$[q^M]\Delta=\tau(M)$$
şeklindedir. Sonuç olarak \((1-E_2)^6\)'nin ihtiyaç duyulan her katsayısı, \(M^r\sigma_{2k-1}(M)\) ve \(\tau(M)\) cinsinden yazılır.
\(N=10000\) olsun. Her \(p\le N\) asalı için Legendre formülü
$$v_p(N!)=\sum_{t\ge 1}\left\lfloor\frac{N}{p^t}\right\rfloor$$
değerini verir. Böylece
$$10000!=\prod_{p\le 10000}p^{v_p(10000!)}.$$
Tek kuvvetli bölen toplamları için çarpımsal formül
$$\sigma_r(10000!)=\prod_{p\le 10000}\left(1+p^r+\cdots+p^{r\,v_p(10000!)}\right)=\prod_{p\le 10000}\frac{p^{r(v_p(10000!)+1)}-1}{p^r-1}$$
şeklindedir; burada \(r\in\{1,3,5,7,9,11\}\).
Ramanujan \(\tau\) fonksiyonu da çarpımsaldır:
$$\tau(10000!)=\prod_{p^e\parallel 10000!}\tau(p^e),$$
ve asal kuvvet bağıntısı
$$\tau(p^e)=\tau(p)\tau(p^{e-1})-p^{11}\tau(p^{e-2})$$
olarak kullanılır. Asal değerler için önce
$$\tau(1)=1,\qquad (n-1)\tau(n)=-24\sum_{k=1}^{n-1}\sigma_1(k)\tau(n-k)\qquad (n\ge 2)$$
reküransı ile \(\tau(n)\) dizisi kurulup, daha sonra gerekli asal kuvvetlere yükseltilir.
\(M=10\) için bölen çiftleri \((1,10)\), \((2,5)\), \((5,2)\) ve \((10,1)\)'dir. Katkılar sırasıyla \(11\), \(7\), \(7\) ve \(11\) olur. Dolayısıyla
$$R_1(10)=11+7+7+11=36=2(1+2+5+10).$$
Şimdi \(n=2\), \(M=3\) için yalnızca \(3=1+2\) ve \(3=2+1\) ayrışımları vardır. \(R_1(1)=2\) ve \(R_1(2)=6\) olduğundan
$$R_2(3)=R_1(1)R_1(2)+R_1(2)R_1(1)=2\cdot 6+6\cdot 2=24.$$
Bu küçük örnek, neden üreteç fonksiyon kuvvetlerinin doğru araç olduğunu açıkça gösterir.
C++, Python ve Java uygulamaları aynı mantıksal sırayı izler. Önce \(10000\)'e kadar asallar elenir ve her asal için \(v_p(10000!)\) bulunur. Bu üsler üzerinden \(\sigma_1,\sigma_3,\sigma_5,\sigma_7,\sigma_9,\sigma_{11}\) değerleri mod \(10^9+7\) altında çarpımsal olarak hesaplanır. Aynı aşamada \(10000! \bmod (10^9+7)\) elde edilerek türevlerden gelecek \(M,M^2,\dots,M^5\) çarpanları hazırlanır.
Ardından uygulama \(1\le n\le 10000\) için \(\sigma_1(n)\) tablosunu üretir, bu tabloyu kullanarak \(\tau(n)\) dizisini \(10000\)'e kadar hesaplar ve sonra asal değerlerden asal kuvvet değerlerine geçer. İkinci dereceden bu lineer rekürans, her asal kuvvet için \(2\times 2\) matris üs alma yöntemiyle hızlandırılır.
Son aşamada tüm bölen toplamları, \(\tau\) katkısı ve \(10000!\)'in kuvvetleri, \((1-E_2)^6\)'nin ağırlık 12 ayrışımındaki katsayılara yerleştirilir. En sonda \(12^6=2985984\) ile bölme işlemi, modüler tersle çarpma olarak yapılır.
\(N=10000\) için asal eleği ve faktöriyel üsleri \(O(N\log\log N)\) zamanda bulunur. Bölen-toplam tablosu \(O(N\log N)\) maliyetlidir. \(\tau(n)\) reküransı ise \(O(N^2)\) zamanda çalışır ve gerçek koşuda baskın adımdır. Geriye kalan asal çarpımları ve asal kuvvet işlemleri yaklaşık \(O(\pi(N)\log N)\) düzeyindedir. Bellek kullanımı \(O(N)\)'dir.
Sea \(E_n=(\mathbb{Z}_{>0})^n\). Para dos vectores de enteros positivos \(u=(u_1,\dots,u_n)\) y \(v=(v_1,\dots,v_n)\), se define
$$\langle u,v\rangle=\sum_{i=1}^{n}u_iv_i,\qquad u\star v=\prod_{i=1}^{n}(u_i+v_i).$$
\(R_n(M)\) es la suma de \(u\star v\) sobre todos los pares ordenados \((u,v)\in E_n\times E_n\) tales que \(\langle u,v\rangle=M\). El objetivo es calcular
$$R_6(10000!) \pmod{10^9+7}.$$
Una enumeración directa es inviable. Por eso la solución transforma el problema en una extracción de coeficientes de una serie generadora y luego reduce esa serie con identidades de formas cuasimodulares.
La estructura es la siguiente: primero se resuelve una coordenada, luego se usa la independencia entre coordenadas para obtener una convolución aditiva, y finalmente se reescribe la sexta potencia resultante en una base de peso 12.
Cuando \(n=1\), la condición \(\langle u,v\rangle=M\) es simplemente \(uv=M\). Cada divisor \(d\mid M\) produce el par ordenado \((d,M/d)\), con contribución
$$d+\frac{M}{d}.$$
Por tanto,
$$R_1(M)=\sum_{d\mid M}\left(d+\frac{M}{d}\right)=2\sum_{d\mid M}d=2\sigma_1(M).$$
Para un par general definimos
$$m_i=u_iv_i\qquad (1\le i\le n).$$
Entonces
$$m_1+\cdots+m_n=M,$$
y para una descomposición fija de \(M\) las contribuciones se multiplican coordenada por coordenada. Así
$$R_n(M)=\sum_{\substack{m_1+\cdots+m_n=M\\m_i\ge 1}}R_1(m_1)\cdots R_1(m_n).$$
Si escribimos
$$G(q)=\sum_{m\ge 1}R_1(m)q^m,$$
entonces
$$R_n(M)=[q^M]\,G(q)^n.$$
La serie cuasimodular \(E_2\) satisface
$$E_2(q)=1-24\sum_{m\ge 1}\sigma_1(m)q^m.$$
Como \(R_1(m)=2\sigma_1(m)\), se obtiene
$$G(q)=2\sum_{m\ge 1}\sigma_1(m)q^m=\frac{1-E_2(q)}{12}.$$
Por consiguiente,
$$R_6(M)=[q^M]\left(\frac{1-E_2(q)}{12}\right)^6.$$
Dado que \(M=10000!>0\), el término constante no interviene; lo que importa es extraer coeficientes positivos de las potencias de \(E_2\).
Sea
$$D=q\frac{d}{dq}.$$
Si \(f(q)=\sum_{m\ge 0}a_mq^m\), entonces
$$[q^M]D^r f=M^r a_M.$$
Las identidades usadas son
$$E_2^2=E_4+12DE_2,$$
$$E_2^3=E_6+9DE_4+72D^2E_2,$$
$$E_2^4=E_8+8DE_6+\frac{216}{5}D^2E_4+288D^3E_2,$$
$$E_2^5=E_{10}+\frac{15}{2}DE_8+\frac{240}{7}D^2E_6+144D^3E_4+864D^4E_2,$$
$$E_2^6=E_{12}-\frac{4608}{24185}\Delta+\frac{36}{5}DE_{10}+30D^2E_8+\frac{720}{7}D^3E_6+\frac{2592}{7}D^4E_4+\frac{10368}{5}D^5E_2.$$
Aquí \(\Delta(q)=\sum_{m\ge 1}\tau(m)q^m\) es la forma cuspídea discriminante. Los coeficientes positivos de las series de Eisenstein son
$$[q^M]E_2=-24\sigma_1(M),\qquad [q^M]E_4=240\sigma_3(M),\qquad [q^M]E_6=-504\sigma_5(M),$$
$$[q^M]E_8=480\sigma_7(M),\qquad [q^M]E_{10}=-264\sigma_9(M),\qquad [q^M]E_{12}=\frac{65520}{691}\sigma_{11}(M),$$
mientras que
$$[q^M]\Delta=\tau(M).$$
Así, cada coeficiente necesario de \((1-E_2)^6\) queda escrito como combinación lineal de \(M^r\sigma_{2k-1}(M)\) y de \(\tau(M)\).
Tomemos \(N=10000\). Para cada primo \(p\le N\), la fórmula de Legendre da
$$v_p(N!)=\sum_{t\ge 1}\left\lfloor\frac{N}{p^t}\right\rfloor.$$
Luego
$$10000!=\prod_{p\le 10000}p^{v_p(10000!)}.$$
Para \(r\in\{1,3,5,7,9,11\}\), la multiplicatividad produce
$$\sigma_r(10000!)=\prod_{p\le 10000}\left(1+p^r+\cdots+p^{r\,v_p(10000!)}\right)=\prod_{p\le 10000}\frac{p^{r(v_p(10000!)+1)}-1}{p^r-1}.$$
La función tau de Ramanujan también es multiplicativa:
$$\tau(10000!)=\prod_{p^e\parallel 10000!}\tau(p^e),$$
con la recurrencia
$$\tau(p^e)=\tau(p)\tau(p^{e-1})-p^{11}\tau(p^{e-2}).$$
Para obtener los valores primos \(\tau(p)\), primero se calcula \(\tau(n)\) hasta \(10000\) mediante
$$\tau(1)=1,\qquad (n-1)\tau(n)=-24\sum_{k=1}^{n-1}\sigma_1(k)\tau(n-k)\qquad (n\ge 2).$$
Para \(M=10\), los pares son \((1,10)\), \((2,5)\), \((5,2)\) y \((10,1)\). Sus contribuciones son \(11\), \(7\), \(7\) y \(11\), así que
$$R_1(10)=11+7+7+11=36=2(1+2+5+10).$$
Ahora, para \(n=2\) y \(M=3\), las únicas descomposiciones positivas son \(3=1+2\) y \(3=2+1\). Como \(R_1(1)=2\) y \(R_1(2)=6\), se obtiene
$$R_2(3)=R_1(1)R_1(2)+R_1(2)R_1(1)=2\cdot 6+6\cdot 2=24.$$
Este ejemplo pequeño muestra con claridad la estructura de convolución que después se codifica mediante una potencia de series generadoras.
Las implementaciones en C++, Python y Java siguen la misma ruta algebraica. Primero generan los primos hasta \(10000\) y calculan cada exponente \(v_p(10000!)\). Con esos exponentes evalúan multiplicativamente \(\sigma_1,\sigma_3,\sigma_5,\sigma_7,\sigma_9,\sigma_{11}\) módulo \(10^9+7\), y también calculan \(10000!\bmod(10^9+7)\) para disponer de \(M,M^2,\dots,M^5\).
Después la implementación construye la tabla de \(\sigma_1(n)\) para \(1\le n\le 10000\), obtiene \(\tau(n)\) hasta \(10000\) con la recurrencia anterior y extiende esos valores a las potencias primas \(\tau(p^e)\). Esa extensión se acelera usando una potencia de matrices \(2\times 2\) asociada a la recurrencia lineal de segundo orden.
Por último, el programa sustituye las sumas de divisores, el término \(\tau\) y las potencias de \(10000!\) en la descomposición de peso 12 de \((1-E_2)^6\). La división final por \(12^6=2985984\) se hace multiplicando por el inverso modular.
Con \(N=10000\), la criba y las valuaciones del factorial cuestan \(O(N\log\log N)\). La tabla de \(\sigma_1(n)\) cuesta \(O(N\log N)\). La recurrencia para \(\tau(n)\) es \(O(N^2)\) y domina el tiempo total de ejecución. Los productos sobre primos y las recurrencias en potencias primas son de orden menor, aproximadamente \(O(\pi(N)\log N)\). La memoria utilizada es \(O(N)\).
设 \(E_n=(\mathbb{Z}_{>0})^n\)。对两个正整数向量 \(u=(u_1,\dots,u_n)\) 与 \(v=(v_1,\dots,v_n)\)，定义
$$\langle u,v\rangle=\sum_{i=1}^{n}u_iv_i,\qquad u\star v=\prod_{i=1}^{n}(u_i+v_i).$$
\(R_n(M)\) 表示所有满足 \(\langle u,v\rangle=M\) 的有序向量对 \((u,v)\in E_n\times E_n\) 上，\(u\star v\) 的总和。目标是求
$$R_6(10000!) \pmod{10^9+7}.$$
如果直接枚举六维向量对，规模完全不可接受。因此解法先把问题改写成一个生成函数的系数提取问题，再用权 12 的拟模形式恒等式把这个系数表达成若干经典算术函数的组合。
整个推导可以分成三个层次。第一层把单个坐标的贡献写成约数和；第二层利用各坐标的独立性把 \(R_6(M)\) 变成一个六重加法卷积；第三层用 Eisenstein 级数、导数算子和 Ramanujan \(\tau\) 函数，把这个卷积对应的生成函数化到可直接计算的形式。
当 \(n=1\) 时，条件 \(\langle u,v\rangle=M\) 就是 \(uv=M\)。如果 \(d\mid M\)，那么就有一个有序对 \((d,M/d)\)，它对 \(u\star v\) 的贡献为
$$d+\frac{M}{d}.$$
于是
$$R_1(M)=\sum_{d\mid M}\left(d+\frac{M}{d}\right)=2\sum_{d\mid M}d=2\sigma_1(M).$$
这一步非常关键，因为它告诉我们：原问题里每个坐标的本质贡献，实际上就是一个标准的约数函数。
对一般的 \(n\)，记
$$m_i=u_iv_i\qquad (1\le i\le n).$$
那么内积条件变成
$$m_1+\cdots+m_n=M.$$
而乘积权重 \(u\star v=\prod_{i=1}^{n}(u_i+v_i)\) 会按坐标拆开，因此对于一个固定的分拆 \(M=m_1+\cdots+m_n\)，总贡献恰好是
$$R_1(m_1)\cdots R_1(m_n).$$
所以
$$R_n(M)=\sum_{\substack{m_1+\cdots+m_n=M\\m_i\ge 1}}R_1(m_1)\cdots R_1(m_n).$$
如果定义生成函数
$$G(q)=\sum_{m\ge 1}R_1(m)q^m,$$
那么上式正是
$$R_n(M)=[q^M]\,G(q)^n.$$
也就是说，原来的组合求和被完全转化成了一个系数提取问题。
拟模 Eisenstein 级数 \(E_2\) 满足
$$E_2(q)=1-24\sum_{m\ge 1}\sigma_1(m)q^m.$$
而前面已经知道 \(R_1(m)=2\sigma_1(m)\)，因此
$$G(q)=2\sum_{m\ge 1}\sigma_1(m)q^m=\frac{1-E_2(q)}{12}.$$
于是目标值变成
$$R_6(M)=[q^M]\left(\frac{1-E_2(q)}{12}\right)^6.$$
由于目标 \(M=10000!\) 是正数，常数项只会影响 \(q^0\) 的系数，因此这里完全可以忽略，只需关注 \(E_2\) 各次幂的正次项系数。
记微分算子
$$D=q\frac{d}{dq}.$$
若 \(f(q)=\sum_{m\ge 0}a_mq^m\)，则
$$[q^M]D^r f=M^r a_M.$$
实现中使用的标准化简公式为
$$E_2^2=E_4+12DE_2,$$
$$E_2^3=E_6+9DE_4+72D^2E_2,$$
$$E_2^4=E_8+8DE_6+\frac{216}{5}D^2E_4+288D^3E_2,$$
$$E_2^5=E_{10}+\frac{15}{2}DE_8+\frac{240}{7}D^2E_6+144D^3E_4+864D^4E_2,$$
$$E_2^6=E_{12}-\frac{4608}{24185}\Delta+\frac{36}{5}DE_{10}+30D^2E_8+\frac{720}{7}D^3E_6+\frac{2592}{7}D^4E_4+\frac{10368}{5}D^5E_2.$$
这里 \(\Delta(q)=\sum_{m\ge 1}\tau(m)q^m\) 是判别式 cusp form。Eisenstein 级数的正次项系数为
$$[q^M]E_2=-24\sigma_1(M),\qquad [q^M]E_4=240\sigma_3(M),\qquad [q^M]E_6=-504\sigma_5(M),$$
$$[q^M]E_8=480\sigma_7(M),\qquad [q^M]E_{10}=-264\sigma_9(M),\qquad [q^M]E_{12}=\frac{65520}{691}\sigma_{11}(M),$$
同时
$$[q^M]\Delta=\tau(M).$$
因此，\((1-E_2)^6\) 的每一个所需系数都可以改写成 \(M^r\sigma_{2k-1}(M)\) 和 \(\tau(M)\) 的线性组合。这正是程序最终代入计算的核心公式。
令 \(N=10000\)。对每个素数 \(p\le N\)，由 Legendre 公式可得
$$v_p(N!)=\sum_{t\ge 1}\left\lfloor\frac{N}{p^t}\right\rfloor.$$
于是
$$10000!=\prod_{p\le 10000}p^{v_p(10000!)}.$$
对所有需要的奇数 \(r\in\{1,3,5,7,9,11\}\)，有
$$\sigma_r(10000!)=\prod_{p\le 10000}\left(1+p^r+\cdots+p^{r\,v_p(10000!)}\right)=\prod_{p\le 10000}\frac{p^{r(v_p(10000!)+1)}-1}{p^r-1}.$$
Ramanujan \(\tau\) 函数同样具有乘法性，因此
$$\tau(10000!)=\prod_{p^e\parallel 10000!}\tau(p^e).$$
对素数幂，使用递推
$$\tau(p^e)=\tau(p)\tau(p^{e-1})-p^{11}\tau(p^{e-2}).$$
为了先得到各个素数上的 \(\tau(p)\)，实现会先按下面的递推把 \(\tau(n)\) 算到 \(10000\)：
$$\tau(1)=1,\qquad (n-1)\tau(n)=-24\sum_{k=1}^{n-1}\sigma_1(k)\tau(n-k)\qquad (n\ge 2).$$
先看 \(M=10\)。有序约数对是 \((1,10)\)、\((2,5)\)、\((5,2)\)、\((10,1)\)，对应贡献分别为 \(11\)、\(7\)、\(7\)、\(11\)。所以
$$R_1(10)=11+7+7+11=36=2(1+2+5+10).$$
再看 \(n=2\)、\(M=3\)。正整数分拆只有 \(3=1+2\) 与 \(3=2+1\)。因为 \(R_1(1)=2\)，\(R_1(2)=2(1+2)=6\)，所以
$$R_2(3)=R_1(1)R_1(2)+R_1(2)R_1(1)=2\cdot 6+6\cdot 2=24.$$
这个小例子已经完整展示了“单坐标核函数 + 多坐标卷积”的思路，而六维情形只是再加上一层拟模形式化简。
C++、Python 和 Java 三个实现遵循同一条数学管线。首先筛出不超过 \(10000\) 的所有素数，并计算每个素数在 \(10000!\) 中的指数 \(v_p(10000!)\)。利用这些指数，可以乘法式地求出 \(\sigma_1,\sigma_3,\sigma_5,\sigma_7,\sigma_9,\sigma_{11}\) 在模 \(10^9+7\) 下的值。同时还会计算 \(10000!\bmod(10^9+7)\)，从而得到导数项所需要的 \(M,M^2,\dots,M^5\)。
接着，实现构造 \(1\le n\le 10000\) 的 \(\sigma_1(n)\) 表，并据此递推出 \(\tau(n)\) 到 \(10000\)。拿到素数上的 \(\tau(p)\) 以后，再通过素数幂递推求 \(\tau(p^e)\)。这个二阶线性递推用一个 \(2\times 2\) 矩阵快速幂来加速，因此对每个素数幂都可以高效求值。
最后，程序把所有约数和、\(\tau\) 项以及 \(10000!\) 的幂代入 \((1-E_2)^6\) 的权 12 展开式中。由于要除以 \(12^6=2985984\)，实现会在模 \(10^9+7\) 下乘上这个数的逆元，得到最终答案。
记 \(N=10000\)。筛法和阶乘素因子指数的计算是 \(O(N\log\log N)\)。利用约数枚举方式构造 \(\sigma_1(n)\) 表需要 \(O(N\log N)\)。而 \(\tau(n)\) 的递推是双重循环，因此是 \(O(N^2)\)，这也是实际实现中的主导时间开销。后面的素数乘积和素数幂递推只占较低阶，大约为 \(O(\pi(N)\log N)\)。空间复杂度为 \(O(N)\)。
Пусть \(E_n=(\mathbb{Z}_{>0})^n\). Для двух векторов положительных целых чисел \(u=(u_1,\dots,u_n)\) и \(v=(v_1,\dots,v_n)\) заданы
$$\langle u,v\rangle=\sum_{i=1}^{n}u_iv_i,\qquad u\star v=\prod_{i=1}^{n}(u_i+v_i).$$
Величина \(R_n(M)\) равна сумме \(u\star v\) по всем упорядоченным парам \((u,v)\in E_n\times E_n\), для которых \(\langle u,v\rangle=M\). Нужно найти
$$R_6(10000!) \pmod{10^9+7}.$$
Перебирать шестимерные векторы напрямую невозможно. Поэтому решение переводит задачу к извлечению коэффициента из производящей функции, а затем упрощает эту функцию с помощью тождеств для квазимодулярных форм.
Ключевая идея состоит в том, что вклад каждой координаты сначала сводится к обычной функции делителей, после чего вся задача становится шестикратной аддитивной сверткой. Затем эта свертка переписывается через \(E_2\), а степени \(E_2\) раскладываются в базисе веса 12.
При \(n=1\) условие \(\langle u,v\rangle=M\) означает просто \(uv=M\). Каждый делитель \(d\mid M\) задает упорядоченную пару \((d,M/d)\), чей вклад равен
$$d+\frac{M}{d}.$$
Следовательно,
$$R_1(M)=\sum_{d\mid M}\left(d+\frac{M}{d}\right)=2\sum_{d\mid M}d=2\sigma_1(M).$$
Для общего \(n\) положим
$$m_i=u_iv_i\qquad (1\le i\le n).$$
Тогда
$$m_1+\cdots+m_n=M,$$
а вес \(u\star v\) раскладывается по координатам. Поэтому для фиксированного разбиения \(M=m_1+\cdots+m_n\) полный вклад равен
$$R_1(m_1)\cdots R_1(m_n).$$
Итак,
$$R_n(M)=\sum_{\substack{m_1+\cdots+m_n=M\\m_i\ge 1}}R_1(m_1)\cdots R_1(m_n).$$
Если обозначить
$$G(q)=\sum_{m\ge 1}R_1(m)q^m,$$
то получаем точную формулу
$$R_n(M)=[q^M]\,G(q)^n.$$
Квазимодулярный ряд \(E_2\) имеет вид
$$E_2(q)=1-24\sum_{m\ge 1}\sigma_1(m)q^m.$$
Так как \(R_1(m)=2\sigma_1(m)\), отсюда сразу следует
$$G(q)=2\sum_{m\ge 1}\sigma_1(m)q^m=\frac{1-E_2(q)}{12}.$$
Значит,
$$R_6(M)=[q^M]\left(\frac{1-E_2(q)}{12}\right)^6.$$
Поскольку \(M=10000!>0\), постоянный член не влияет на искомый коэффициент. Остается разобрать только положительные коэффициенты степеней \(E_2\).
Обозначим
$$D=q\frac{d}{dq}.$$
Если \(f(q)=\sum_{m\ge 0}a_mq^m\), то
$$[q^M]D^r f=M^r a_M.$$
Используются следующие тождества:
$$E_2^2=E_4+12DE_2,$$
$$E_2^3=E_6+9DE_4+72D^2E_2,$$
$$E_2^4=E_8+8DE_6+\frac{216}{5}D^2E_4+288D^3E_2,$$
$$E_2^5=E_{10}+\frac{15}{2}DE_8+\frac{240}{7}D^2E_6+144D^3E_4+864D^4E_2,$$
$$E_2^6=E_{12}-\frac{4608}{24185}\Delta+\frac{36}{5}DE_{10}+30D^2E_8+\frac{720}{7}D^3E_6+\frac{2592}{7}D^4E_4+\frac{10368}{5}D^5E_2.$$
Здесь \(\Delta(q)=\sum_{m\ge 1}\tau(m)q^m\) — дискриминантная cusp-форма. Положительные коэффициенты рядов Эйзенштейна равны
$$[q^M]E_2=-24\sigma_1(M),\qquad [q^M]E_4=240\sigma_3(M),\qquad [q^M]E_6=-504\sigma_5(M),$$
$$[q^M]E_8=480\sigma_7(M),\qquad [q^M]E_{10}=-264\sigma_9(M),\qquad [q^M]E_{12}=\frac{65520}{691}\sigma_{11}(M),$$
а также
$$[q^M]\Delta=\tau(M).$$
Тем самым каждый нужный коэффициент из \((1-E_2)^6\) записывается как линейная комбинация величин \(M^r\sigma_{2k-1}(M)\) и \(\tau(M)\).
Положим \(N=10000\). Для любого простого \(p\le N\) формула Лежандра дает
$$v_p(N!)=\sum_{t\ge 1}\left\lfloor\frac{N}{p^t}\right\rfloor.$$
Следовательно,
$$10000!=\prod_{p\le 10000}p^{v_p(10000!)}.$$
Для каждого нечетного \(r\in\{1,3,5,7,9,11\}\) получаем
$$\sigma_r(10000!)=\prod_{p\le 10000}\left(1+p^r+\cdots+p^{r\,v_p(10000!)}\right)=\prod_{p\le 10000}\frac{p^{r(v_p(10000!)+1)}-1}{p^r-1}.$$
Функция Рамануджана \(\tau\) тоже мультипликативна:
$$\tau(10000!)=\prod_{p^e\parallel 10000!}\tau(p^e),$$
где для степеней простого используется рекурсия
$$\tau(p^e)=\tau(p)\tau(p^{e-1})-p^{11}\tau(p^{e-2}).$$
Чтобы получить значения \(\tau(p)\), сначала вычисляется последовательность \(\tau(n)\) до \(10000\) по формуле
$$\tau(1)=1,\qquad (n-1)\tau(n)=-24\sum_{k=1}^{n-1}\sigma_1(k)\tau(n-k)\qquad (n\ge 2).$$
Для \(M=10\) упорядоченные пары равны \((1,10)\), \((2,5)\), \((5,2)\), \((10,1)\). Их вклады — \(11\), \(7\), \(7\), \(11\). Поэтому
$$R_1(10)=11+7+7+11=36=2(1+2+5+10).$$
Для \(n=2\) и \(M=3\) существуют только разложения \(3=1+2\) и \(3=2+1\). Поскольку \(R_1(1)=2\) и \(R_1(2)=6\), имеем
$$R_2(3)=R_1(1)R_1(2)+R_1(2)R_1(1)=2\cdot 6+6\cdot 2=24.$$
На этом маленьком примере уже виден весь механизм: одномерное ядро, затем свертка, а в большой задаче поверх этого еще и квазимодулярное упрощение.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они строят список простых чисел до \(10000\) и вычисляют все показатели \(v_p(10000!)\). По этим показателям мультипликативно находятся значения \(\sigma_1,\sigma_3,\sigma_5,\sigma_7,\sigma_9,\sigma_{11}\) по модулю \(10^9+7\). Параллельно вычисляется и \(10000!\bmod(10^9+7)\), чтобы иметь степени \(M,M^2,\dots,M^5\), возникающие из операторов \(D^r\).
Затем реализация строит таблицу \(\sigma_1(n)\) для \(1\le n\le 10000\), по рекуррентной формуле получает \(\tau(n)\) до \(10000\), а после этого поднимает значения с простых до степеней простых \(\tau(p^e)\). Для ускорения второй части используется быстрое возведение в степень матрицы \(2\times 2\), соответствующей линейной рекурсии второго порядка.
В конце все найденные суммы делителей, значение \(\tau(10000!)\) и степени \(10000!\) подставляются в разложение \((1-E_2)^6\) в весе 12. Деление на \(12^6=2985984\) выполняется по модулю \(10^9+7\) умножением на обратный элемент.
Пусть \(N=10000\). Решето и вычисление показателей факториала занимают \(O(N\log\log N)\) времени. Построение таблицы \(\sigma_1(n)\) стоит \(O(N\log N)\). Рекурсия для \(\tau(n)\) имеет квадратичную сложность \(O(N^2)\) и именно она доминирует в реальном времени работы. Остальные операции — произведения по простым и переход к степеням простых — имеют меньший порядок, примерно \(O(\pi(N)\log N)\). Память — \(O(N)\).
لتكن \(E_n=(\mathbb{Z}_{>0})^n\). وللمتجهين ذوي المركبات الصحيحة الموجبة \(u=(u_1,\dots,u_n)\) و\(v=(v_1,\dots,v_n)\) نعرّف
$$\langle u,v\rangle=\sum_{i=1}^{n}u_iv_i,\qquad u\star v=\prod_{i=1}^{n}(u_i+v_i).$$
الكمية \(R_n(M)\) هي مجموع \(u\star v\) على جميع الأزواج المرتبة \((u,v)\in E_n\times E_n\) التي تحقق \(\langle u,v\rangle=M\). والمطلوب هو حساب
$$R_6(10000!) \pmod{10^9+7}.$$
العد المباشر للأزواج في ستة أبعاد غير عملي تماما، لذلك يحوّل الحل المسألة إلى استخراج معامل من دالة مولدة، ثم يختزل هذه الدالة باستخدام متطابقات من نظرية الأشكال شبه المعيارية.
الفكرة الأساسية تسير على مراحل. في البداية نفهم مساهمة بعد واحد فقط. بعد ذلك نستغل استقلال الإحداثيات لنحصل على التفاف جمعي من الرتبة السادسة. ثم نعيد كتابة السلسلة الناتجة بدلالة \(E_2\) ومشتقات سلاسل Eisenstein ودالة رامانوجان \(\tau\).
عندما \(n=1\) يصبح الشرط \(\langle u,v\rangle=M\) مجرد \(uv=M\). وكل قاسم \(d\mid M\) يعطي الزوج المرتب \((d,M/d)\)، ومساهمته في \(u\star v\) هي
$$d+\frac{M}{d}.$$
ومن ثم
$$R_1(M)=\sum_{d\mid M}\left(d+\frac{M}{d}\right)=2\sum_{d\mid M}d=2\sigma_1(M).$$
في الحالة العامة نكتب
$$m_i=u_iv_i\qquad (1\le i\le n).$$
وعندئذ
$$m_1+\cdots+m_n=M,$$
كما أن الوزن \(u\star v\) ينفصل إلى حاصل ضرب مساهمات الإحداثيات. لذلك، إذا ثبت التفكيك \(M=m_1+\cdots+m_n\)، كان المجموع المرتبط به هو
$$R_1(m_1)\cdots R_1(m_n).$$
وهكذا نحصل على
$$R_n(M)=\sum_{\substack{m_1+\cdots+m_n=M\\m_i\ge 1}}R_1(m_1)\cdots R_1(m_n).$$
ومع تعريف الدالة المولدة
$$G(q)=\sum_{m\ge 1}R_1(m)q^m,$$
تصبح الصيغة
$$R_n(M)=[q^M]\,G(q)^n.$$
السلسلة شبه المعيارية \(E_2\) تحقق
$$E_2(q)=1-24\sum_{m\ge 1}\sigma_1(m)q^m.$$
وبما أن \(R_1(m)=2\sigma_1(m)\)، نحصل مباشرة على
$$G(q)=2\sum_{m\ge 1}\sigma_1(m)q^m=\frac{1-E_2(q)}{12}.$$
ومن ثم
$$R_6(M)=[q^M]\left(\frac{1-E_2(q)}{12}\right)^6.$$
ولأن \(M=10000!>0\)، فإن الحد الثابت لا يسهم في المعامل المطلوب، وبالتالي يكفي تحليل معاملات القوى المختلفة لـ \(E_2\).
لنكتب
$$D=q\frac{d}{dq}.$$
إذا كانت \(f(q)=\sum_{m\ge 0}a_mq^m\)، فلدينا
$$[q^M]D^r f=M^r a_M.$$
المتطابقات المستعملة هي
$$E_2^2=E_4+12DE_2,$$
$$E_2^3=E_6+9DE_4+72D^2E_2,$$
$$E_2^4=E_8+8DE_6+\frac{216}{5}D^2E_4+288D^3E_2,$$
$$E_2^5=E_{10}+\frac{15}{2}DE_8+\frac{240}{7}D^2E_6+144D^3E_4+864D^4E_2,$$
$$E_2^6=E_{12}-\frac{4608}{24185}\Delta+\frac{36}{5}DE_{10}+30D^2E_8+\frac{720}{7}D^3E_6+\frac{2592}{7}D^4E_4+\frac{10368}{5}D^5E_2.$$
وهنا \(\Delta(q)=\sum_{m\ge 1}\tau(m)q^m\) هي الدالة التمييزية cusp form. أما معاملات سلاسل Eisenstein فهي
$$[q^M]E_2=-24\sigma_1(M),\qquad [q^M]E_4=240\sigma_3(M),\qquad [q^M]E_6=-504\sigma_5(M),$$
$$[q^M]E_8=480\sigma_7(M),\qquad [q^M]E_{10}=-264\sigma_9(M),\qquad [q^M]E_{12}=\frac{65520}{691}\sigma_{11}(M),$$
وكذلك
$$[q^M]\Delta=\tau(M).$$
وبهذا تتحول كل المعاملات المطلوبة في \((1-E_2)^6\) إلى تراكيب خطية من \(M^r\sigma_{2k-1}(M)\) ومن \(\tau(M)\).
لنضع \(N=10000\). لكل عدد أولي \(p\le N\) تعطي صيغة Legendre
$$v_p(N!)=\sum_{t\ge 1}\left\lfloor\frac{N}{p^t}\right\rfloor.$$
ومن ثم
$$10000!=\prod_{p\le 10000}p^{v_p(10000!)}.$$
ولكل \(r\in\{1,3,5,7,9,11\}\) نحصل على
$$\sigma_r(10000!)=\prod_{p\le 10000}\left(1+p^r+\cdots+p^{r\,v_p(10000!)}\right)=\prod_{p\le 10000}\frac{p^{r(v_p(10000!)+1)}-1}{p^r-1}.$$
ودالة رامانوجان \(\tau\) ضربية أيضا، لذا
$$\tau(10000!)=\prod_{p^e\parallel 10000!}\tau(p^e),$$
مع علاقة القوى الأولية
$$\tau(p^e)=\tau(p)\tau(p^{e-1})-p^{11}\tau(p^{e-2}).$$
وللحصول على قيم \(\tau(p)\) نفسها، تبنى السلسلة \(\tau(n)\) حتى \(10000\) باستخدام
$$\tau(1)=1,\qquad (n-1)\tau(n)=-24\sum_{k=1}^{n-1}\sigma_1(k)\tau(n-k)\qquad (n\ge 2).$$
عندما \(M=10\)، تكون الأزواج المرتبة هي \((1,10)\)، \((2,5)\)، \((5,2)\)، \((10,1)\). ومساهماتها هي \(11\)، \(7\)، \(7\)، \(11\). لذلك
$$R_1(10)=11+7+7+11=36=2(1+2+5+10).$$
والآن عند \(n=2\) و\(M=3\)، لا توجد إلا التجزئتان \(3=1+2\) و\(3=2+1\). وبما أن \(R_1(1)=2\) و\(R_1(2)=6\)، ينتج
$$R_2(3)=R_1(1)R_1(2)+R_1(2)R_1(1)=2\cdot 6+6\cdot 2=24.$$
هذا المثال الصغير يوضح بشكل كامل لماذا تتحول المسألة إلى قوة لدالة مولدة واحدة.
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. في البداية تُستخرج جميع الأعداد الأولية حتى \(10000\)، ثم تُحسب القيم \(v_p(10000!)\) لكل أولي. ومن هذه القيم تُحسب كميات \(\sigma_1,\sigma_3,\sigma_5,\sigma_7,\sigma_9,\sigma_{11}\) بطريقة ضربية modulo \(10^9+7\). وفي الوقت نفسه يُحسب \(10000!\bmod(10^9+7)\) للحصول على القوى \(M,M^2,\dots,M^5\) اللازمة بعد تطبيق المشتقات.
بعد ذلك تبني التنفيذات جدولا لقيم \(\sigma_1(n)\) من \(1\) إلى \(10000\)، ثم تستخدم العلاقة السابقة لحساب \(\tau(n)\) حتى \(10000\). وبعد الحصول على القيم عند الأعداد الأولية، تُرفع هذه القيم إلى القوى الأولية \(\tau(p^e)\). ولتسريع هذه الخطوة، تُحوَّل العلاقة التراجعية من الرتبة الثانية إلى أسّ لمصفوفة \(2\times 2\).
في النهاية تُجمع حدود سلاسل القواسم مع حد \(\tau\) ومع قوى \(10000!\) داخل التوسيع من الوزن 12 لـ \((1-E_2)^6\). أما القسمة على \(12^6=2985984\)، فتتم في الحساب المعياري بواسطة الضرب في المعكوس الضربي.
إذا كان \(N=10000\)، فإن المصفاة وحساب أسس العوامل الأولية في \(N!\) يكلفان \(O(N\log\log N)\). وبناء جدول \(\sigma_1(n)\) يكلف \(O(N\log N)\). أما علاقة \(\tau(n)\) فهي تربيعية \(O(N^2)\)، وهي الخطوة المسيطرة فعليا في زمن التنفيذ. بقية الضربات على الأعداد الأولية وعلاقات القوى الأولية أصغر رتبة، وتقع تقريبا ضمن \(O(\pi(N)\log N)\). استهلاك الذاكرة هو \(O(N)\).