We study factor pairs of \(100!\). For every pair \((a,b)\) with \(ab=100!\) and \(a\le b\), we ask whether \(a\) and \(b\) have the same number of positive divisors. If \(\tau\) denotes the divisor-counting function, the required quantity is
$$C(100!)=\#\left\{(a,b):ab=100!,\ a\le b,\ \tau(a)=\tau(b)\right\}.$$
A naive scan over all divisors of \(100!\) is far too large. The successful approach works with prime exponents and balances the prime factors of \(\tau(a)\) and \(\tau(b)\) instead of comparing \(a\) and \(b\) directly.
Write the prime factorization of \(100!\) as
$$100!=\prod_{p\le 100} p^{e_p},\qquad e_p=\sum_{k\ge 1}\left\lfloor\frac{100}{p^k}\right\rfloor.$$
Each prime \(p\) contributes an exponent \(e_p\), and every factor pair of \(100!\) comes from deciding how much of that exponent belongs to \(a\) and how much belongs to \(b\).
Choose integers \(x_p\) with \(0\le x_p\le e_p\) and define
$$a=\prod_{p\le 100} p^{x_p},\qquad b=\prod_{p\le 100} p^{e_p-x_p}.$$
Every ordered factorization \(ab=100!\) arises exactly once in this way. The divisor-count formulas become
$$\tau(a)=\prod_{p\le 100}(x_p+1),\qquad \tau(b)=\prod_{p\le 100}(e_p-x_p+1).$$
So the problem reduces to choosing one integer from each interval \(0,\dots,e_p\) so that these two products are equal.
Two positive integers are equal if and only if every prime appears with the same exponent in both. Therefore \(\tau(a)=\tau(b)\) is equivalent to
$$\sum_{p\le 100}\nu_q(x_p+1)=\sum_{p\le 100}\nu_q(e_p-x_p+1).$$
This identity must hold for every prime \(q\).
Define the balance at prime \(q\) by
$$D_q=\sum_{p\le 100}\left(\nu_q(x_p+1)-\nu_q(e_p-x_p+1)\right).$$
Then a choice of exponents is valid exactly when
$$D_q=0.$$
This must again hold for every prime \(q\).
This reformulation is the core of the method: we count exponent assignments whose valuation-balance vector is identically zero.
Legendre's formula gives
$$e_2=97,\qquad e_3=48,\qquad e_5=24,\qquad e_7=16,$$
while every prime \(p>7\) satisfies
$$e_p\le 9.$$
Hence, for \(p>7\), the numbers \(x_p+1\) and \(e_p-x_p+1\) always lie between \(1\) and \(10\). Their prime factors can only belong to
$$\{2,3,5,7\}.$$
That means every prime \(p>7\) can affect only the four balances \(D_2,D_3,D_5,D_7\). It can never create or cancel a balance at any larger prime \(q>7\).
The previous observation implies that every balance \(D_q\) with \(q>7\) must already vanish inside the contribution coming from \(p\in\{2,3,5,7\}\). The search therefore splits naturally.
First, enumerate all choices for the four exceptional primes \(2,3,5,7\). For each choice, compute the full balance vector \((D_q)\). Since \(x_2+1\) can be as large as \(98\), this stage may involve primes such as \(11,13,\dots,97\). Keep only those assignments for which every coordinate with \(q>7\) is already zero.
After that filter, only the four coordinates
$$\left(D_2,D_3,D_5,D_7\right)$$
still matter. Second, process the primes \(p>7\). Each such prime contributes one small four-dimensional delta vector, because only \(2,3,5,7\) can appear in the corresponding divisor-count factors.
Let \(\mathbf d=(d_2,d_3,d_5,d_7)\) be a state produced by the exceptional primes after the large-prime balances have been forced to zero. Let \(\mathbf r\) be a state produced by the remaining primes. A complete exponent assignment is valid exactly when
$$\mathbf d+\mathbf r=\mathbf 0.$$
So the ordered answer is obtained by counting, for every state from the exceptional-prime side, how many states from the remaining-prime side are its exact negative.
The construction above counts ordered pairs \((a,b)\). The problem asks for unordered pairs with \(a\le b\). Swapping \(a\) and \(b\) replaces every \(x_p\) by \(e_p-x_p\), so non-fixed solutions come in symmetric pairs. Therefore
$$C(100!)=\frac{M+F}{2},$$
where \(M\) is the ordered count and \(F=1\) only if \(100!\) is a perfect square. Here \(F=0\), because not all exponents \(e_p\) are even.
The same machinery is easy to inspect on
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7.$$
In this smaller case there are no primes \(p>7\), so only the exceptional stage remains. The primes \(5\) and \(7\) together can produce the six balances
$$(-1,-1,0,0),\ (-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),\ (1,1,0,0).$$
The primes \(2\) and \(3\) produce the opposite balances with multiplicities \(2,1,1,2\) on the four vectors
$$(-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),$$
and no matches for \((-1,-1,0,0)\) or \((1,1,0,0)\). Hence the ordered count is
$$M=2+1+1+2=6.$$
Since \(10!\) is not a square, \(F=0\), so
$$C(10!)=\frac{6}{2}=3.$$
This is the small checkpoint reproduced by the implementation.
The C++, Python, and Java implementations follow the same pipeline. They first generate all primes up to \(100\) and compute every exponent \(e_p\) with Legendre's formula. Next they precompute the prime factorizations of all integers from \(1\) to \(\max(e_p)+1\). That turns every quantity of the form \(\nu_q(x_p+1)\) or \(\nu_q(e_p-x_p+1)\) into a fast table lookup.
For the exceptional primes \(2,3,5,7\), the implementation enumerates every possible complementary pair \((x_p+1,e_p-x_p+1)\), builds the corresponding balance vectors, and merges them in two batches before forming the full four-prime combinations. Only combinations whose coordinates for primes \(q>7\) are all zero are kept, and their remaining four-coordinate balances are stored with multiplicities.
For each prime \(p>7\), the implementation computes all possible deltas on \((D_2,D_3,D_5,D_7)\) and updates a sparse map from four-dimensional balance states to counts. The ordered total is the sum of products of matching complementary states from the two stages. A final symmetry correction converts that ordered total into the requested count with \(a\le b\).
Let
$$A=(e_2+1)(e_3+1)(e_5+1)(e_7+1).$$
Enumerating the exceptional primes costs \(O(A\cdot B)\), where \(B\) is the number of prime coordinates that may appear in the divisor-count factors. For \(100!\), this is practical because only four primes have large exponent ranges.
For the remaining primes, if \(S_k\) denotes the number of distinct four-dimensional states after processing the first \(k\) primes greater than \(7\), then the dynamic program costs
$$O\left(\sum_k S_{k-1}(e_{p_k}+1)\right)$$
time and \(O(\max_k S_k)\) memory. Since every prime \(p>7\) has \(e_p+1\le 10\), the branching factor is tiny and the sparse state space stays manageable.
Wir betrachten Faktorpaarungen von \(100!\). Für jedes Paar \((a,b)\) mit \(ab=100!\) und \(a\le b\) soll geprüft werden, ob \(a\) und \(b\) gleich viele positive Teiler besitzen. Mit der Teilerfunktion \(\tau\) ist also zu berechnen:
$$C(100!)=\#\left\{(a,b):ab=100!,\ a\le b,\ \tau(a)=\tau(b)\right\}.$$
Eine naive Durchmusterung aller Teiler von \(100!\) ist viel zu groß. Die Lösung arbeitet deshalb mit Primexponenten und vergleicht nicht direkt \(a\) und \(b\), sondern die Primfaktorzerlegungen von \(\tau(a)\) und \(\tau(b)\).
Schreibe die Primfaktorzerlegung von \(100!\) als
$$100!=\prod_{p\le 100} p^{e_p},\qquad e_p=\sum_{k\ge 1}\left\lfloor\frac{100}{p^k}\right\rfloor.$$
Jede Wahl eines Faktorpaars entspricht genau der Entscheidung, wie viel von jedem Exponenten \(e_p\) nach \(a\) und wie viel nach \(b\) geht.
Wähle ganze Zahlen \(x_p\) mit \(0\le x_p\le e_p\) und setze
$$a=\prod_{p\le 100} p^{x_p},\qquad b=\prod_{p\le 100} p^{e_p-x_p}.$$
Jede geordnete Zerlegung \(ab=100!\) entsteht genau einmal auf diese Weise. Für die Anzahl der Teiler gilt damit
$$\tau(a)=\prod_{p\le 100}(x_p+1),\qquad \tau(b)=\prod_{p\le 100}(e_p-x_p+1).$$
Damit reduziert sich die Aufgabe auf die Wahl eines Werts aus jedem Intervall \(0,\dots,e_p\), sodass diese beiden Produkte gleich werden.
Zwei positive ganze Zahlen sind genau dann gleich, wenn jede Primzahl in beiden mit demselben Exponenten vorkommt. Also ist \(\tau(a)=\tau(b)\) äquivalent zu
$$\sum_{p\le 100}\nu_q(x_p+1)=\sum_{p\le 100}\nu_q(e_p-x_p+1).$$
Diese Gleichung muss für jede Primzahl \(q\) gelten.
Definiere dazu die Bilanz an der Primzahl \(q\) durch
$$D_q=\sum_{p\le 100}\left(\nu_q(x_p+1)-\nu_q(e_p-x_p+1)\right).$$
Eine Exponentenwahl ist also genau dann gültig, wenn
$$D_q=0.$$
Auch dies muss für jede Primzahl \(q\) erfüllt sein.
Das ist der Kern der Methode: Gezählt werden alle Zuweisungen, deren Bewertungsvektor in jeder Koordinate verschwindet.
Aus der Legendre-Formel folgt
$$e_2=97,\qquad e_3=48,\qquad e_5=24,\qquad e_7=16,$$
während für jede Primzahl \(p>7\) gilt
$$e_p\le 9.$$
Damit liegen für \(p>7\) die Zahlen \(x_p+1\) und \(e_p-x_p+1\) immer zwischen \(1\) und \(10\). Ihre Primteiler können also nur aus
$$\{2,3,5,7\}$$
stammen. Jede Primzahl \(p>7\) kann deshalb nur die vier Bilanzen \(D_2,D_3,D_5,D_7\) beeinflussen. Eine Bilanz an einer größeren Primzahl \(q>7\) kann dadurch weder erzeugt noch aufgehoben werden.
Die vorige Beobachtung bedeutet: Jede Bilanz \(D_q\) mit \(q>7\) muss bereits vollständig aus dem Beitrag von \(p\in\{2,3,5,7\}\) verschwinden. Deshalb zerfällt die Suche natürlich in zwei Teile.
Zuerst werden alle Möglichkeiten für die vier besonderen Primzahlen \(2,3,5,7\) enumeriert. Für jede Wahl wird der vollständige Bilanzvektor \((D_q)\) berechnet. Da \(x_2+1\) bis \(98\) groß werden kann, können in diesem Schritt auch Primzahlen wie \(11,13,\dots,97\) auftreten. Behalten werden nur diejenigen Zuweisungen, bei denen alle Koordinaten mit \(q>7\) schon Null sind.
Danach bleiben nur noch die vier Koordinaten
$$\left(D_2,D_3,D_5,D_7\right)$$
relevant. Anschließend werden die Primzahlen \(p>7\) verarbeitet. Jede davon liefert nur einen kleinen vierdimensionalen Delta-Vektor, weil in den zugehörigen Teilerfaktoren nur \(2,3,5,7\) auftreten können.
Sei \(\mathbf d=(d_2,d_3,d_5,d_7)\) ein Zustand aus dem Teil mit \(2,3,5,7\), nachdem alle größeren Primkoordinaten auf Null erzwungen wurden. Sei \(\mathbf r\) ein Zustand aus den übrigen Primzahlen. Genau dann entsteht eine gültige Gesamtlösung, wenn
$$\mathbf d+\mathbf r=\mathbf 0.$$
Die geordnete Gesamtzahl erhält man also, indem man für jeden Zustand der ersten Hälfte zählt, wie viele Zustände der zweiten Hälfte exakt sein Negatives liefern.
Die bisherige Konstruktion zählt geordnete Paare \((a,b)\). Gefragt sind aber ungeordnete Paare mit \(a\le b\). Vertauscht man \(a\) und \(b\), so wird jedes \(x_p\) durch \(e_p-x_p\) ersetzt; nichtfeste Lösungen treten daher paarweise auf. Folglich gilt
$$C(100!)=\frac{M+F}{2},$$
wobei \(M\) die geordnete Anzahl ist und \(F=1\) nur dann, wenn \(100!\) ein Quadrat ist. Hier ist \(F=0\), denn nicht alle Exponenten \(e_p\) sind gerade.
Dasselbe Verfahren lässt sich gut an
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7$$
beobachten. In diesem kleineren Fall gibt es keine Primzahlen \(p>7\), also bleibt nur der Teil mit den besonderen Primzahlen. Die Primzahlen \(5\) und \(7\) erzeugen gemeinsam die sechs Bilanzen
$$(-1,-1,0,0),\ (-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),\ (1,1,0,0).$$
Die Primzahlen \(2\) und \(3\) liefern die entgegengesetzten Vektoren mit den Multiplizitäten \(2,1,1,2\) auf den vier Zuständen
$$(-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),$$
während es für \((-1,-1,0,0)\) und \((1,1,0,0)\) keine Treffer gibt. Damit ist die geordnete Anzahl
$$M=2+1+1+2=6.$$
Da \(10!\) kein Quadrat ist, gilt \(F=0\) und somit
$$C(10!)=\frac{6}{2}=3.$$
Genau dieser kleine Kontrollwert erscheint auch in der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst erzeugen sie alle Primzahlen bis \(100\) und berechnen jeden Exponenten \(e_p\) mit der Legendre-Formel. Danach wird die Primfaktorzerlegung aller ganzen Zahlen von \(1\) bis \(\max(e_p)+1\) vorab tabelliert. So werden alle Größen der Form \(\nu_q(x_p+1)\) oder \(\nu_q(e_p-x_p+1)\) zu schnellen Tabellenabfragen.
Für die besonderen Primzahlen \(2,3,5,7\) enumeriert die Implementierung alle möglichen komplementären Paare \((x_p+1,e_p-x_p+1)\), bildet die zugehörigen Bilanzvektoren und kombiniert sie zunächst in zwei Blöcken, bevor die vollständigen Vier-Primzahl-Kombinationen entstehen. Behalten werden nur Kombinationen, bei denen alle Koordinaten für Primzahlen \(q>7\) verschwinden. Die verbleibenden vier Koordinaten werden samt Häufigkeiten gespeichert.
Für jede Primzahl \(p>7\) berechnet die Implementierung alle möglichen Deltas auf \((D_2,D_3,D_5,D_7)\) und aktualisiert damit eine dünn besetzte Abbildung von vierdimensionalen Zuständen auf Anzahlen. Die geordnete Gesamtsumme entsteht anschließend als Summe der Produkte komplementärer Zustände aus beiden Phasen. Eine letzte Symmetrie-Korrektur liefert daraus die gesuchte Anzahl mit \(a\le b\).
Sei
$$A=(e_2+1)(e_3+1)(e_5+1)(e_7+1).$$
Die Enumeration der besonderen Primzahlen kostet \(O(A\cdot B)\), wobei \(B\) die Anzahl der Primkoordinaten bezeichnet, die in den Teilerfaktoren auftreten können. Für \(100!\) ist das praktikabel, weil nur vier Primzahlen große Exponentenbereiche besitzen.
Für die übrigen Primzahlen sei \(S_k\) die Anzahl verschiedener vierdimensionaler Zustände nach den ersten \(k\) Primzahlen größer als \(7\). Dann kostet das dynamische Programm
$$O\left(\sum_k S_{k-1}(e_{p_k}+1)\right)$$
Zeit und \(O(\max_k S_k)\) Speicher. Da jede Primzahl \(p>7\) nur \(e_p+1\le 10\) Möglichkeiten besitzt, bleibt der Verzweigungsfaktor klein und der dünn besetzte Zustandsraum beherrschbar.
\(100!\) sayısının çarpan çiftlerini inceliyoruz. \(ab=100!\) ve \(a\le b\) olan her \((a,b)\) çifti için, \(a\) ile \(b\)'nin pozitif bölen sayılarının eşit olup olmadığı soruluyor. \(\tau\) bölen sayısı fonksiyonu olmak üzere aranan büyüklük
$$C(100!)=\#\left\{(a,b):ab=100!,\ a\le b,\ \tau(a)=\tau(b)\right\}$$
değeridir. \(100!\)'ın tüm bölenlerini doğrudan gezmek çok pahalıdır. Bu nedenle çözüm, \(a\) ile \(b\)'yi doğrudan karşılaştırmak yerine \(\tau(a)\) ve \(\tau(b)\)'nin asal üs dengelerini sayar.
\(100!\)'ın asal çarpanlara ayrılışını
$$100!=\prod_{p\le 100} p^{e_p},\qquad e_p=\sum_{k\ge 1}\left\lfloor\frac{100}{p^k}\right\rfloor$$
şeklinde yazalım. Her asal \(p\) için \(e_p\) üssünün ne kadarının \(a\)'ya, ne kadarının \(b\)'ye gideceğini seçmek bir çarpan çifti belirler.
\(0\le x_p\le e_p\) olacak şekilde tamsayılar seçip
$$a=\prod_{p\le 100} p^{x_p},\qquad b=\prod_{p\le 100} p^{e_p-x_p}$$
tanımını yapalım. \(ab=100!\) olan her sıralı ayrışım tam olarak bir kez bu şekilde elde edilir. O zaman bölen sayıları
$$\tau(a)=\prod_{p\le 100}(x_p+1),\qquad \tau(b)=\prod_{p\le 100}(e_p-x_p+1)$$
olur. Böylece sorun, her aralık \(0,\dots,e_p\) içinden bir değer seçip bu iki çarpımı eşitlemeye dönüşür.
İki pozitif tamsayı ancak ve ancak her asal için aynı üsle görünüyorlarsa eşittir. Dolayısıyla \(\tau(a)=\tau(b)\) koşulu
$$\sum_{p\le 100}\nu_q(x_p+1)=\sum_{p\le 100}\nu_q(e_p-x_p+1).$$
Bu eşitlik her asal \(q\) için sağlanmalıdır.
ile denktir. \(q\) asalı için dengeyi
$$D_q=\sum_{p\le 100}\left(\nu_q(x_p+1)-\nu_q(e_p-x_p+1)\right)$$
şeklinde tanımlarsak, geçerli bir seçim tam olarak
$$D_q=0.$$
Bu koşul da yine her asal \(q\) için geçerlidir.
koşulunu sağlamalıdır. Yöntemin özü budur: tüm koordinatlarda sıfır olan değerleme denge vektörlerini saymak.
Legendre formülünden
$$e_2=97,\qquad e_3=48,\qquad e_5=24,\qquad e_7=16$$
elde edilir; buna karşılık \(p>7\) olan her asal için
$$e_p\le 9$$
olur. Bu yüzden \(p>7\) olduğunda hem \(x_p+1\) hem de \(e_p-x_p+1\) sayıları \(1\) ile \(10\) arasındadır. Dolayısıyla bunların asal çarpanları sadece
$$\{2,3,5,7\}$$
kümesinden gelebilir. Yani \(p>7\) tarafındaki seçimler yalnızca \(D_2,D_3,D_5,D_7\) dengelerini etkileyebilir; daha büyük bir \(q>7\) asalında denge yaratamaz ya da düzeltemez.
Bir önceki gözlem şunu söyler: \(q>7\) olan her denge, zaten \(p\in\{2,3,5,7\}\) tarafından tek başına sıfırlanmak zorundadır. Bu yüzden arama doğal olarak iki bölüme ayrılır.
Önce \(2,3,5,7\) için tüm seçimler taranır. Her seçim için tam denge vektörü \((D_q)\) hesaplanır. \(x_2+1\) değeri \(98\)'e kadar çıkabildiği için bu aşamada \(11,13,\dots,97\) gibi asallar da görünebilir. Yalnızca \(q>7\) koordinatlarının tamamı sıfır olan seçimler tutulur.
Bu filtreden sonra geriye yalnızca
$$\left(D_2,D_3,D_5,D_7\right)$$
dörtlüsü kalır. Ardından \(p>7\) olan asallar işlenir. Bu asalların her biri yalnızca küçük bir dört boyutlu delta vektörü üretir, çünkü ilgili bölen-sayısı çarpanlarında sadece \(2,3,5,7\) görünebilir.
\(q>7\) koordinatları sıfıra zorlandıktan sonra, özel asallardan gelen bir durumu \(\mathbf d=(d_2,d_3,d_5,d_7)\) ile gösterelim. Geri kalan asallardan gelen duruma da \(\mathbf r\) diyelim. Tam bir seçim ancak
$$\mathbf d+\mathbf r=\mathbf 0$$
olduğunda geçerlidir. O halde sıralı toplam cevap, ilk taraftaki her durum için ikinci tarafta onun tam tersine kaç kez ulaşıldığını sayarak bulunur.
Yukarıdaki yapı sıralı \((a,b)\) çiftlerini sayar. Soruda ise \(a\le b\) olacak şekilde sırasız çiftler istenir. \(a\) ile \(b\)'yi yer değiştirmek her \(x_p\)'yi \(e_p-x_p\) ile değiştirir; sabit olmayan çözümler bu yüzden ikili simetriyle gelir. Sonuç olarak
$$C(100!)=\frac{M+F}{2}$$
olur. Burada \(M\) sıralı sayım, \(F=1\) ise ancak \(100!\) tam kare olduğunda geçerlidir. Bu problemde tüm üsler çift olmadığı için \(F=0\)'dır.
Aynı yöntem
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7$$
için rahatça görülebilir. Bu küçük örnekte \(p>7\) asal yoktur; dolayısıyla yalnızca özel-asal aşaması kalır. \(5\) ve \(7\) asalları birlikte şu altı dengeyi üretir:
$$(-1,-1,0,0),\ (-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),\ (1,1,0,0).$$
\(2\) ve \(3\) asalları ise bunların ters işaretli sürümlerini şu dört vektörde sırasıyla \(2,1,1,2\) çokluklarıyla üretir:
$$(-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0).$$
\((-1,-1,0,0)\) ve \((1,1,0,0)\) için eşleşme yoktur. Bu yüzden sıralı çözüm sayısı
$$M=2+1+1+2=6$$
olur. \(10!\) tam kare olmadığı için \(F=0\), dolayısıyla
$$C(10!)=\frac{6}{2}=3.$$
Uygulamanın küçük kontrol değeri de budur.
C++, Python ve Java implementasyonları aynı akışı izler. Önce \(100\)'e kadar tüm asallar üretilir ve her \(e_p\) üssü Legendre formülüyle hesaplanır. Sonra \(1\) ile \(\max(e_p)+1\) arasındaki tüm sayıların asal çarpan ayrışımları önceden tabloya alınır. Böylece \(\nu_q(x_p+1)\) ve \(\nu_q(e_p-x_p+1)\) türündeki değerler tekrar tekrar çarpanlara ayırma yapmadan okunabilir.
\(2,3,5,7\) için implementasyon tüm tamamlayıcı çiftleri \((x_p+1,e_p-x_p+1)\) dener, karşılık gelen denge vektörlerini üretir ve tam dört-asal birleşiminden önce bunları iki blok halinde birleştirir. Yalnızca \(q>7\) asal koordinatlarının tamamı sıfır olan birleşimler saklanır; geriye kalan dört koordinat ise çokluklarıyla birlikte depolanır.
\(p>7\) olan her asal için implementasyon \((D_2,D_3,D_5,D_7)\) üzerindeki tüm olası delta katkılarını çıkarır ve dört boyutlu durumları sayan seyrek bir tabloyu günceller. Sıralı toplam, iki aşamadaki tamamlayıcı durumların çarpımlarının toplanmasıyla elde edilir. Son olarak simetri düzeltmesi yapılarak \(a\le b\) şartını sağlayan sonuç bulunur.
Şunu tanımlayalım:
$$A=(e_2+1)(e_3+1)(e_5+1)(e_7+1).$$
Özel asalların taranması \(O(A\cdot B)\) maliyetlidir; burada \(B\), bölen-sayısı çarpanlarında görünebilecek asal koordinat sayısıdır. \(100!\) için bu bölüm pratiktir, çünkü geniş üs aralıklarına sahip yalnızca dört asal vardır.
Kalan asallar için, \(7\)'den büyük ilk \(k\) asal işlendiğinde oluşan farklı dört boyutlu durum sayısına \(S_k\) diyelim. O zaman dinamik programın zamanı
$$O\left(\sum_k S_{k-1}(e_{p_k}+1)\right)$$
ve belleği \(O(\max_k S_k)\) olur. Her \(p>7\) asalında \(e_p+1\le 10\) olduğu için dallanma küçük kalır ve seyrek durum uzayı yönetilebilir boyutta kalır.
Estudiamos los pares de factores de \(100!\). Para cada par \((a,b)\) con \(ab=100!\) y \(a\le b\), se pregunta si \(a\) y \(b\) tienen el mismo número de divisores positivos. Si \(\tau\) es la función que cuenta divisores, la cantidad buscada es
$$C(100!)=\#\left\{(a,b):ab=100!,\ a\le b,\ \tau(a)=\tau(b)\right\}.$$
Recorrer de forma ingenua todos los divisores de \(100!\) es imposible en la práctica. Por eso la solución trabaja con exponentes primos y equilibra los factores primos de \(\tau(a)\) y \(\tau(b)\) en lugar de comparar directamente \(a\) y \(b\).
Escribimos la factorización prima de \(100!\) como
$$100!=\prod_{p\le 100} p^{e_p},\qquad e_p=\sum_{k\ge 1}\left\lfloor\frac{100}{p^k}\right\rfloor.$$
Cada exponente \(e_p\) debe repartirse entre \(a\) y \(b\), y esa decisión determina completamente el par de factores.
Elegimos enteros \(x_p\) con \(0\le x_p\le e_p\) y definimos
$$a=\prod_{p\le 100} p^{x_p},\qquad b=\prod_{p\le 100} p^{e_p-x_p}.$$
Toda factorización ordenada \(ab=100!\) aparece exactamente una vez de esta forma. Entonces
$$\tau(a)=\prod_{p\le 100}(x_p+1),\qquad \tau(b)=\prod_{p\le 100}(e_p-x_p+1).$$
El problema se convierte en escoger un valor dentro de cada intervalo \(0,\dots,e_p\) de modo que estos dos productos sean iguales.
Dos enteros positivos son iguales si y solo si cada primo aparece con el mismo exponente en ambos. Por tanto, \(\tau(a)=\tau(b)\) equivale a exigir
$$\sum_{p\le 100}\nu_q(x_p+1)=\sum_{p\le 100}\nu_q(e_p-x_p+1).$$
Esta igualdad debe cumplirse para todo primo \(q\).
Definimos el balance en el primo \(q\) por
$$D_q=\sum_{p\le 100}\left(\nu_q(x_p+1)-\nu_q(e_p-x_p+1)\right).$$
Entonces una elección de exponentes es válida exactamente cuando
$$D_q=0.$$
De nuevo, esta condición debe valer para todo primo \(q\).
Esta reformulación es la idea central: contar asignaciones cuyo vector de balances sea nulo en todas las coordenadas.
La fórmula de Legendre da
$$e_2=97,\qquad e_3=48,\qquad e_5=24,\qquad e_7=16,$$
mientras que para todo primo \(p>7\) se cumple
$$e_p\le 9.$$
Por eso, si \(p>7\), los números \(x_p+1\) y \(e_p-x_p+1\) siempre están entre \(1\) y \(10\). Sus factores primos solo pueden pertenecer a
$$\{2,3,5,7\}.$$
Así, cada primo \(p>7\) solo puede alterar los cuatro balances \(D_2,D_3,D_5,D_7\). No puede crear ni cancelar balances en ningún primo mayor \(q>7\).
La observación anterior implica que todo balance \(D_q\) con \(q>7\) debe anularse por completo dentro de la contribución de \(p\in\{2,3,5,7\}\). Por eso la búsqueda se separa naturalmente en dos partes.
Primero se enumeran todas las elecciones para los cuatro primos excepcionales \(2,3,5,7\). Para cada una se calcula el vector completo \((D_q)\). Como \(x_2+1\) puede llegar a \(98\), en esta etapa pueden intervenir primos como \(11,13,\dots,97\). Solo se conservan las asignaciones para las que todas las coordenadas con \(q>7\) ya valen cero.
Después de ese filtro, solo siguen importando las cuatro coordenadas
$$\left(D_2,D_3,D_5,D_7\right).$$
Luego se procesan los primos \(p>7\). Cada uno aporta un pequeño vector delta de dimensión cuatro, porque en los factores correspondientes del número de divisores solo pueden aparecer \(2,3,5,7\).
Sea \(\mathbf d=(d_2,d_3,d_5,d_7)\) un estado producido por los primos excepcionales, una vez forzadas a cero todas las coordenadas grandes. Sea \(\mathbf r\) un estado producido por los primos restantes. Una asignación completa es válida exactamente cuando
$$\mathbf d+\mathbf r=\mathbf 0.$$
Por tanto, la respuesta ordenada se obtiene contando, para cada estado de la primera parte, cuántos estados de la segunda parte son exactamente su opuesto.
La construcción anterior cuenta pares ordenados \((a,b)\). El problema pide pares no ordenados con \(a\le b\). Intercambiar \(a\) y \(b\) reemplaza cada \(x_p\) por \(e_p-x_p\), así que las soluciones no fijas aparecen en parejas simétricas. En consecuencia,
$$C(100!)=\frac{M+F}{2},$$
donde \(M\) es el conteo ordenado y \(F=1\) solo si \(100!\) es un cuadrado perfecto. Aquí \(F=0\), porque no todos los exponentes \(e_p\) son pares.
El mismo método se ve con claridad en
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7.$$
En este caso pequeño no existen primos \(p>7\), así que solo queda la etapa excepcional. Los primos \(5\) y \(7\) producen conjuntamente los seis balances
$$(-1,-1,0,0),\ (-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),\ (1,1,0,0).$$
Los primos \(2\) y \(3\) generan los vectores opuestos con multiplicidades \(2,1,1,2\) sobre los cuatro estados
$$(-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),$$
y no producen coincidencias para \((-1,-1,0,0)\) ni para \((1,1,0,0)\). Por tanto, el conteo ordenado es
$$M=2+1+1+2=6.$$
Como \(10!\) no es un cuadrado, \(F=0\), y entonces
$$C(10!)=\frac{6}{2}=3.$$
Ese es exactamente el pequeño punto de control que reproduce la implementación.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero generan todos los primos hasta \(100\) y calculan cada exponente \(e_p\) mediante la fórmula de Legendre. Después precalculan la factorización prima de todos los enteros entre \(1\) y \(\max(e_p)+1\). Así, cualquier valor del tipo \(\nu_q(x_p+1)\) o \(\nu_q(e_p-x_p+1)\) se obtiene por consulta directa en una tabla.
Para los primos excepcionales \(2,3,5,7\), la implementación recorre todos los pares complementarios posibles \((x_p+1,e_p-x_p+1)\), construye sus vectores de balance y los fusiona en dos bloques antes de formar las combinaciones completas de los cuatro primos. Solo se conservan las combinaciones cuyas coordenadas para \(q>7\) ya son todas cero, y sus balances de cuatro coordenadas se guardan con sus multiplicidades.
Para cada primo \(p>7\), la implementación calcula todos los deltas posibles sobre \((D_2,D_3,D_5,D_7)\) y actualiza un mapa disperso de estados de cuatro dimensiones a cantidades. El total ordenado final es la suma de productos de estados complementarios de las dos etapas. Una corrección final por simetría convierte ese total ordenado en la cantidad pedida con \(a\le b\).
Sea
$$A=(e_2+1)(e_3+1)(e_5+1)(e_7+1).$$
La enumeración de los primos excepcionales cuesta \(O(A\cdot B)\), donde \(B\) es el número de coordenadas primas que pueden aparecer en los factores del número de divisores. Para \(100!\), esto sigue siendo viable porque solo cuatro primos tienen rangos de exponente grandes.
Para los primos restantes, si \(S_k\) es el número de estados de dimensión cuatro distintos después de procesar los primeros \(k\) primos mayores que \(7\), entonces el programa dinámico cuesta
$$O\left(\sum_k S_{k-1}(e_{p_k}+1)\right)$$
tiempo y \(O(\max_k S_k)\) memoria. Como cada primo \(p>7\) cumple \(e_p+1\le 10\), el factor de ramificación es muy pequeño y el espacio disperso de estados permanece controlable.
我们研究 \(100!\) 的因子对。对于每个满足 \(ab=100!\) 且 \(a\le b\) 的二元组 \((a,b)\)，要求判断 \(a\) 与 \(b\) 的正约数个数是否相同。若 \(\tau\) 表示约数个数函数，则目标数量是
$$C(100!)=\#\left\{(a,b):ab=100!,\ a\le b,\ \tau(a)=\tau(b)\right\}.$$
如果直接枚举 \(100!\) 的全部约数，规模会大得无法处理。真正可行的方法不是直接比较 \(a\) 和 \(b\)，而是比较 \(\tau(a)\) 与 \(\tau(b)\) 的素因子指数平衡。
把 \(100!\) 的素因子分解写成
$$100!=\prod_{p\le 100} p^{e_p},\qquad e_p=\sum_{k\ge 1}\left\lfloor\frac{100}{p^k}\right\rfloor.$$
对每个素数 \(p\)，只要决定指数 \(e_p\) 中有多少分给 \(a\)，剩下的部分就自动分给 \(b\)。
取整数 \(x_p\)，满足 \(0\le x_p\le e_p\)，并定义
$$a=\prod_{p\le 100} p^{x_p},\qquad b=\prod_{p\le 100} p^{e_p-x_p}.$$
这样一来，每个有序分解 \(ab=100!\) 都恰好对应一组这样的选择。于是约数个数公式变成
$$\tau(a)=\prod_{p\le 100}(x_p+1),\qquad \tau(b)=\prod_{p\le 100}(e_p-x_p+1).$$
问题就转化为：在每个区间 \(0,\dots,e_p\) 中选一个值，使这两个乘积相等。
两个正整数相等，当且仅当它们在每个素数上的指数都相同。因此 \(\tau(a)=\tau(b)\) 等价于
$$\sum_{p\le 100}\nu_q(x_p+1)=\sum_{p\le 100}\nu_q(e_p-x_p+1).$$
这个等式必须对每个素数 \(q\) 都成立。
定义素数 \(q\) 上的平衡量
$$D_q=\sum_{p\le 100}\left(\nu_q(x_p+1)-\nu_q(e_p-x_p+1)\right).$$
那么一组指数选择合法，当且仅当
$$D_q=0.$$
同样，这个条件也必须对每个素数 \(q\) 都成立。
这就是整个方法的核心：统计所有估值平衡向量在每个坐标上都为零的方案。
由 Legendre 公式可得
$$e_2=97,\qquad e_3=48,\qquad e_5=24,\qquad e_7=16,$$
而对所有 \(p>7\) 都有
$$e_p\le 9.$$
因此当 \(p>7\) 时，\(x_p+1\) 与 \(e_p-x_p+1\) 一定都落在 \(1\) 到 \(10\) 之间。它们的素因子只能来自
$$\{2,3,5,7\}.$$
这意味着任何 \(p>7\) 的选择都只能影响四个平衡量 \(D_2,D_3,D_5,D_7\)，不可能制造或抵消更大素数 \(q>7\) 上的平衡。
由上面的结论可知，所有 \(q>7\) 的平衡必须完全由 \(p\in\{2,3,5,7\}\) 这一部分自己消掉。因此搜索自然拆成两段。
第一段，枚举四个特殊素数 \(2,3,5,7\) 的所有选择，并计算完整平衡向量 \((D_q)\)。由于 \(x_2+1\) 最多可以达到 \(98\)，这一段中确实可能出现 \(11,13,\dots,97\) 这样的素数坐标。只保留那些在所有 \(q>7\) 坐标上已经恰好为零的方案。
过滤之后，真正还需要继续跟踪的只剩下
$$\left(D_2,D_3,D_5,D_7\right)$$
这四个坐标。第二段处理所有 \(p>7\) 的素数。每个这样的素数只会产生一个很小的四维增量向量，因为对应的约数个数因子里只可能出现 \(2,3,5,7\)。
设 \(\mathbf d=(d_2,d_3,d_5,d_7)\) 是特殊素数部分在大素数坐标全部归零后留下的状态，设 \(\mathbf r\) 是其余素数部分产生的状态。完整方案合法，当且仅当
$$\mathbf d+\mathbf r=\mathbf 0.$$
所以有序答案的计算方式就是：对第一部分产生的每个状态，统计第二部分中有多少状态恰好等于它的相反向量。
上面的构造统计的是有序对 \((a,b)\)。题目要求的是满足 \(a\le b\) 的无序因子对。交换 \(a\) 与 \(b\) 相当于把每个 \(x_p\) 替换为 \(e_p-x_p\)，因此非固定解总是成对出现。于是有
$$C(100!)=\frac{M+F}{2},$$
其中 \(M\) 是有序计数，只有当 \(100!\) 是完全平方数时才有 \(F=1\)。本题中并非所有 \(e_p\) 都是偶数，所以 \(F=0\)。
同样的思路在
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7$$
上也很容易看清。这个较小的例子中没有 \(p>7\) 的素数，因此只剩下特殊素数这一段。素数 \(5\) 与 \(7\) 合在一起可以产生六个平衡向量
$$(-1,-1,0,0),\ (-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),\ (1,1,0,0).$$
而素数 \(2\) 与 \(3\) 在下面四个向量上分别给出相反状态，其出现次数是 \(2,1,1,2\)：
$$(-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0).$$
对于 \((-1,-1,0,0)\) 和 \((1,1,0,0)\) 并没有匹配，因此有序方案总数为
$$M=2+1+1+2=6.$$
由于 \(10!\) 不是完全平方数，所以 \(F=0\)，于是
$$C(10!)=\frac{6}{2}=3.$$
这正是实现中使用的小型校验结果。
C++、Python 和 Java 实现遵循同一条流程。它们先生成不超过 \(100\) 的所有素数，并用 Legendre 公式计算每个 \(e_p\)。接着，程序预处理从 \(1\) 到 \(\max(e_p)+1\) 的所有整数的素因子分解。这样一来，任何 \(\nu_q(x_p+1)\) 或 \(\nu_q(e_p-x_p+1)\) 这样的量都能通过查表得到，而不需要重复分解。
对于特殊素数 \(2,3,5,7\)，实现会枚举所有可能的互补对 \((x_p+1,e_p-x_p+1)\)，构造相应的平衡向量，并先按两批合并，再形成完整的四素数组合。只有当所有 \(q>7\) 的坐标都已经为零时，该组合才会保留；其余下的四维平衡状态会连同出现次数一起存储。
对于每个 \(p>7\) 的素数，实现计算它在 \((D_2,D_3,D_5,D_7)\) 上的全部可能增量，并用这些增量更新一个稀疏的四维状态计数表。最终的有序总数来自两阶段互补状态的乘积求和，最后再做一次对称性修正，就得到满足 \(a\le b\) 的答案。
记
$$A=(e_2+1)(e_3+1)(e_5+1)(e_7+1).$$
枚举特殊素数的代价是 \(O(A\cdot B)\)，其中 \(B\) 是约数个数因子中可能出现的素数坐标数量。对 \(100!\) 而言，这一部分仍然可行，因为只有四个素数拥有较大的指数范围。
对剩余素数，如果 \(S_k\) 表示处理完前 \(k\) 个大于 \(7\) 的素数后出现的不同四维状态数，那么动态规划的时间复杂度为
$$O\left(\sum_k S_{k-1}(e_{p_k}+1)\right)$$
，空间复杂度为 \(O(\max_k S_k)\)。由于每个 \(p>7\) 都满足 \(e_p+1\le 10\)，分支数很小，稀疏状态空间也就保持在可控范围内。
Мы рассматриваем пары множителей числа \(100!\). Для каждой пары \((a,b)\), удовлетворяющей \(ab=100!\) и \(a\le b\), нужно проверить, совпадает ли число положительных делителей у \(a\) и у \(b\). Если \(\tau\) обозначает функцию числа делителей, то требуется найти
$$C(100!)=\#\left\{(a,b):ab=100!,\ a\le b,\ \tau(a)=\tau(b)\right\}.$$
Прямой перебор всех делителей \(100!\) слишком велик. Поэтому решение работает не с самими \(a\) и \(b\), а с простыми показателями в разложениях \(\tau(a)\) и \(\tau(b)\).
Запишем разложение \(100!\) на простые множители в виде
$$100!=\prod_{p\le 100} p^{e_p},\qquad e_p=\sum_{k\ge 1}\left\lfloor\frac{100}{p^k}\right\rfloor.$$
Каждый показатель \(e_p\) нужно разделить между \(a\) и \(b\), и именно это полностью определяет пару множителей.
Выберем целые числа \(x_p\), для которых \(0\le x_p\le e_p\), и положим
$$a=\prod_{p\le 100} p^{x_p},\qquad b=\prod_{p\le 100} p^{e_p-x_p}.$$
Каждое упорядоченное разложение \(ab=100!\) получается ровно один раз. Тогда
$$\tau(a)=\prod_{p\le 100}(x_p+1),\qquad \tau(b)=\prod_{p\le 100}(e_p-x_p+1).$$
Значит, задача сводится к выбору одного числа из каждого интервала \(0,\dots,e_p\) так, чтобы эти два произведения совпали.
Два положительных целых числа равны тогда и только тогда, когда каждый простой входит в них с одинаковым показателем. Поэтому условие \(\tau(a)=\tau(b)\) эквивалентно системе
$$\sum_{p\le 100}\nu_q(x_p+1)=\sum_{p\le 100}\nu_q(e_p-x_p+1).$$
Это равенство должно выполняться для любого простого \(q\).
Введем баланс по простому \(q\):
$$D_q=\sum_{p\le 100}\left(\nu_q(x_p+1)-\nu_q(e_p-x_p+1)\right).$$
Тогда выбор показателей корректен ровно в том случае, когда
$$D_q=0.$$
И это условие также должно выполняться для любого простого \(q\).
Именно это и считает алгоритм: количество назначений, у которых вектор оценочных балансов равен нулю по всем координатам.
По формуле Лежандра имеем
$$e_2=97,\qquad e_3=48,\qquad e_5=24,\qquad e_7=16,$$
а для любого простого \(p>7\) выполняется
$$e_p\le 9.$$
Следовательно, при \(p>7\) числа \(x_p+1\) и \(e_p-x_p+1\) всегда лежат между \(1\) и \(10\). Их простые делители могут принадлежать только множеству
$$\{2,3,5,7\}.$$
Значит, каждый простой \(p>7\) может влиять лишь на четыре баланса \(D_2,D_3,D_5,D_7\). Создать или устранить дисбаланс по какому-либо простому \(q>7\) он уже не способен.
Из предыдущего наблюдения следует, что любой баланс \(D_q\) при \(q>7\) должен полностью занулиться внутри вклада от \(p\in\{2,3,5,7\}\). Поэтому поиск естественно распадается на две части.
Сначала перебираются все варианты для четырех особых простых \(2,3,5,7\). Для каждого варианта вычисляется полный вектор \((D_q)\). Так как \(x_2+1\) может достигать \(98\), на этом этапе реально возникают простые \(11,13,\dots,97\). Сохраняются только те варианты, у которых все координаты с \(q>7\) уже равны нулю.
После этого фильтра остаются только четыре координаты
$$\left(D_2,D_3,D_5,D_7\right).$$
Затем обрабатываются простые \(p>7\). Каждый из них дает лишь небольшой четырехмерный дельта-вектор, потому что в соответствующих множителях числа делителей могут появляться только \(2,3,5,7\).
Пусть \(\mathbf d=(d_2,d_3,d_5,d_7)\) обозначает состояние, полученное от особых простых после зануления всех больших координат. Пусть \(\mathbf r\) приходит от остальных простых. Полное назначение корректно тогда и только тогда, когда
$$\mathbf d+\mathbf r=\mathbf 0.$$
Поэтому упорядоченный ответ получается так: для каждого состояния первой части нужно посчитать, сколько состояний второй части являются точным отрицанием этого вектора.
Построение выше считает упорядоченные пары \((a,b)\). В задаче же нужны неупорядоченные пары с условием \(a\le b\). Перестановка \(a\) и \(b\) заменяет каждый \(x_p\) на \(e_p-x_p\), поэтому все нефиксированные решения разбиваются на симметричные пары. Следовательно,
$$C(100!)=\frac{M+F}{2},$$
где \(M\) обозначает упорядоченный счет, а \(F=1\) только в том случае, если \(100!\) является полным квадратом. Здесь \(F=0\), потому что не все показатели \(e_p\) четные.
Тот же метод удобно увидеть на числе
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7.$$
В этом меньшем примере нет простых \(p>7\), так что остается только особая часть. Простые \(5\) и \(7\) вместе дают шесть балансов
$$(-1,-1,0,0),\ (-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),\ (1,1,0,0).$$
Простые \(2\) и \(3\) дают противоположные состояния с кратностями \(2,1,1,2\) на четырех векторах
$$(-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),$$
и не дают совпадений для \((-1,-1,0,0)\) и \((1,1,0,0)\). Поэтому упорядоченное число решений равно
$$M=2+1+1+2=6.$$
Так как \(10!\) не является квадратом, \(F=0\), и значит
$$C(10!)=\frac{6}{2}=3.$$
Это и есть малый контрольный результат, который воспроизводит реализация.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они генерируют все простые числа до \(100\) и вычисляют каждый показатель \(e_p\) по формуле Лежандра. Затем заранее табулируют простые разложения всех чисел от \(1\) до \(\max(e_p)+1\). Благодаря этому величины вида \(\nu_q(x_p+1)\) и \(\nu_q(e_p-x_p+1)\) получаются простым чтением из таблицы.
Для особых простых \(2,3,5,7\) реализация перебирает все возможные комплементарные пары \((x_p+1,e_p-x_p+1)\), строит соответствующие векторы балансов и сначала объединяет их попарно, прежде чем формировать полные комбинации четырех простых. Сохраняются только те комбинации, у которых все координаты для \(q>7\) уже равны нулю. Оставшиеся четырехмерные балансы записываются вместе с их кратностями.
Для каждого простого \(p>7\) реализация вычисляет все возможные дельты на \((D_2,D_3,D_5,D_7)\) и обновляет разреженное отображение из четырехмерных состояний в количества. Итоговый упорядоченный счет получается как сумма произведений по комплементарным состояниям из двух этапов. Финальная поправка на симметрию превращает этот счет в ответ с условием \(a\le b\).
Положим
$$A=(e_2+1)(e_3+1)(e_5+1)(e_7+1).$$
Перебор особых простых требует \(O(A\cdot B)\), где \(B\) обозначает число простых координат, которые вообще могут появиться в множителях числа делителей. Для \(100!\) это практично, потому что широкий диапазон показателей есть только у четырех простых.
Для остальных простых, если \(S_k\) означает число различных четырехмерных состояний после обработки первых \(k\) простых больше \(7\), то динамическая часть работает за
$$O\left(\sum_k S_{k-1}(e_{p_k}+1)\right)$$
времени и использует \(O(\max_k S_k)\) памяти. Поскольку для каждого \(p>7\) выполнено \(e_p+1\le 10\), ветвление очень мало, а разреженное пространство состояний остается умеренным.
نبحث في أزواج العوامل للعدد \(100!\). لكل زوج \((a,b)\) يحقق \(ab=100!\) و\(a\le b\)، نريد معرفة ما إذا كان لـ \(a\) و\(b\) العدد نفسه من القواسم الموجبة. إذا كانت \(\tau\) هي دالة عدد القواسم، فالكمية المطلوبة هي
$$C(100!)=\#\left\{(a,b):ab=100!,\ a\le b,\ \tau(a)=\tau(b)\right\}.$$
العد المباشر لجميع قواسم \(100!\) غير عملي إطلاقًا. لذلك يعتمد الحل على أسس العوامل الأولية، ويوازن بين التحليل الأولي لـ \(\tau(a)\) و\(\tau(b)\) بدلًا من مقارنة \(a\) و\(b\) مباشرة.
نكتب التحليل الأولي لـ \(100!\) على الصورة
$$100!=\prod_{p\le 100} p^{e_p},\qquad e_p=\sum_{k\ge 1}\left\lfloor\frac{100}{p^k}\right\rfloor.$$
كل أسّ \(e_p\) يجب أن يُقسَّم بين \(a\) و\(b\)، وهذا التقسيم هو الذي يحدد زوج العوامل بالكامل.
نختار أعدادًا صحيحة \(x_p\) بحيث \(0\le x_p\le e_p\)، ثم نعرّف
$$a=\prod_{p\le 100} p^{x_p},\qquad b=\prod_{p\le 100} p^{e_p-x_p}.$$
كل تحليل مرتب يحقق \(ab=100!\) يظهر مرة واحدة فقط بهذه الطريقة. ومن ثم نحصل على
$$\tau(a)=\prod_{p\le 100}(x_p+1),\qquad \tau(b)=\prod_{p\le 100}(e_p-x_p+1).$$
إذًا أصبحت المسألة اختيار قيمة واحدة من كل مجال \(0,\dots,e_p\) بحيث يتساوى هذان المضروبان.
يتساوى عددان صحيحان موجبان إذا وفقط إذا ظهر كل عدد أولي فيهما بالأس نفسه. لذلك فإن الشرط \(\tau(a)=\tau(b)\) يكافئ
$$\sum_{p\le 100}\nu_q(x_p+1)=\sum_{p\le 100}\nu_q(e_p-x_p+1).$$
ويجب أن تتحقق هذه المساواة لكل عدد أولي \(q\).
ونعرّف توازن العدد الأولي \(q\) بالصيغة
$$D_q=\sum_{p\le 100}\left(\nu_q(x_p+1)-\nu_q(e_p-x_p+1)\right).$$
وعندئذ تكون مجموعة الاختيارات صالحة بالضبط عندما يتحقق
$$D_q=0.$$
وكذلك يجب أن يتحقق هذا الشرط لكل عدد أولي \(q\).
هذه هي الفكرة المركزية في الحل: عد جميع التعيينات التي يكون فيها متجه التوازن صفريًا في كل الإحداثيات.
تعطينا صيغة ليجاندر
$$e_2=97,\qquad e_3=48,\qquad e_5=24,\qquad e_7=16,$$
بينما لكل عدد أولي \(p>7\) نحصل على
$$e_p\le 9.$$
إذًا إذا كان \(p>7\)، فإن العددين \(x_p+1\) و\(e_p-x_p+1\) يقعان دائمًا بين \(1\) و\(10\). وبالتالي فإن عواملهما الأولية لا يمكن أن تأتي إلا من المجموعة
$$\{2,3,5,7\}.$$
وهذا يعني أن أي اختيار تابع لـ \(p>7\) لا يؤثر إلا في التوازنات الأربعة \(D_2,D_3,D_5,D_7\)، ولا يمكنه أن يصنع أو يلغي توازنًا عند أي أولي أكبر \(q>7\).
ينتج من الملاحظة السابقة أن كل توازن \(D_q\) عند \(q>7\) يجب أن يختفي بالكامل داخل مساهمة \(p\in\{2,3,5,7\}\). ولهذا ينقسم البحث طبيعيًا إلى مرحلتين.
في المرحلة الأولى نعدّد جميع الاختيارات الخاصة بالأوليات الاستثنائية \(2,3,5,7\)، ونحسب لكل اختيار متجه التوازن الكامل \((D_q)\). وبما أن \(x_2+1\) قد يصل إلى \(98\)، فقد تظهر في هذه المرحلة أوليات مثل \(11,13,\dots,97\). نحتفظ فقط بالتعيينات التي تكون فيها كل الإحداثيات ذات \(q>7\) مساوية للصفر مسبقًا.
بعد هذا الترشيح لا يبقى مهمًا إلا الإحداثيات الأربع
$$\left(D_2,D_3,D_5,D_7\right).$$
بعد ذلك نعالج جميع الأوليات \(p>7\). كل أولي من هذا النوع يولّد متجه زيادة صغيرًا ذا أربعة أبعاد فقط، لأن عوامل عدد القواسم المقابلة لا يمكن أن تحتوي إلا على \(2,3,5,7\).
لنرمز بالحالة \(\mathbf d=(d_2,d_3,d_5,d_7)\) إلى ما تنتجه الأوليات الاستثنائية بعد فرض انعدام جميع الإحداثيات الكبيرة، ولنرمز بـ \(\mathbf r\) إلى الحالة الناتجة من بقية الأوليات. يكون التعيين الكامل صحيحًا إذا وفقط إذا تحقق
$$\mathbf d+\mathbf r=\mathbf 0.$$
لذلك يُحسب الجواب المرتب بعدّ عدد الحالات في المرحلة الثانية التي تساوي السالب الدقيق لكل حالة صادرة من المرحلة الأولى.
البناء السابق يعد الأزواج المرتبة \((a,b)\). أما المطلوب فهو الأزواج غير المرتبة مع الشرط \(a\le b\). تبديل \(a\) و\(b\) يستبدل كل \(x_p\) بـ \(e_p-x_p\)، ولذلك تأتي الحلول غير الثابتة في أزواج متناظرة. ومن ثم
$$C(100!)=\frac{M+F}{2},$$
حيث \(M\) هو العد المرتب، و\(F=1\) فقط إذا كان \(100!\) مربعًا كاملًا. في هذه المسألة \(F=0\)، لأن جميع الأسس \(e_p\) ليست زوجية.
يمكن رؤية الفكرة نفسها بوضوح على
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7.$$
في هذا المثال الأصغر لا توجد أوليات \(p>7\)، لذا تبقى المرحلة الاستثنائية فقط. يولّد الأوليان \(5\) و\(7\) معًا متجهات التوازن الستة التالية:
$$(-1,-1,0,0),\ (-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),\ (1,1,0,0).$$
أما الأوليان \(2\) و\(3\) فيولدان الحالات المعاكسة مع المضاعفات \(2,1,1,2\) على المتجهات الأربعة
$$(-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),$$
ولا يعطيان أي تطابق عند \((-1,-1,0,0)\) أو \((1,1,0,0)\). لذلك يكون عدد الحلول المرتبة
$$M=2+1+1+2=6.$$
ولأن \(10!\) ليس مربعًا كاملًا فإن \(F=0\)، ومن ثم
$$C(10!)=\frac{6}{2}=3.$$
وهذه هي القيمة الصغيرة التي يعيد إنتاجها التنفيذ كفحص sanity بسيط.
تتبع تطبيقات C++ وPython وJava المسار نفسه. تبدأ بتوليد جميع الأعداد الأولية حتى \(100\)، ثم تحسب كل أسّ \(e_p\) بواسطة صيغة ليجاندر. بعد ذلك تُحسب مسبقًا التحليلات الأولية لكل الأعداد من \(1\) حتى \(\max(e_p)+1\). بهذا تصبح كل كمية من النوع \(\nu_q(x_p+1)\) أو \(\nu_q(e_p-x_p+1)\) مجرد قراءة سريعة من جدول.
بالنسبة إلى الأوليات الاستثنائية \(2,3,5,7\)، يقوم التنفيذ بتعداد كل زوج تكميلي ممكن \((x_p+1,e_p-x_p+1)\)، وبناء متجهات التوازن المقابلة، ثم دمجها على دفعتين قبل تكوين تراكيب الأوليات الأربع كاملة. لا تُحتفظ إلا بالتراكيب التي تكون فيها جميع الإحداثيات عند \(q>7\) مساوية للصفر، وتُخزَّن الحالات الرباعية الباقية مع عدد مرات ظهورها.
أما لكل أولي \(p>7\)، فيحسب التنفيذ جميع الزيادات الممكنة على \((D_2,D_3,D_5,D_7)\)، ويحدّث خريطة sparse للحالات الرباعية إلى أعدادها. ويُستخرج المجموع المرتب النهائي بجمع حاصل ضرب الحالات المتكاملة بين المرحلتين. وفي النهاية تُطبَّق تصحيحة تناظر واحدة للحصول على الجواب المطلوب مع الشرط \(a\le b\).
لنعرّف
$$A=(e_2+1)(e_3+1)(e_5+1)(e_7+1).$$
يكلف تعداد الأوليات الاستثنائية \(O(A\cdot B)\)، حيث إن \(B\) هو عدد الإحداثيات الأولية التي قد تظهر في عوامل عدد القواسم. وبالنسبة إلى \(100!\) يظل هذا عمليًا لأن أربعة أوليات فقط تمتلك مجالات أسس كبيرة.
وبالنسبة إلى بقية الأوليات، إذا كان \(S_k\) هو عدد الحالات الرباعية المختلفة بعد معالجة أول \(k\) من الأوليات الأكبر من \(7\)، فإن البرمجة الديناميكية تكلف
$$O\left(\sum_k S_{k-1}(e_{p_k}+1)\right)$$
زمنًا و\(O(\max_k S_k)\) ذاكرة. ولأن كل أولي \(p>7\) يحقق \(e_p+1\le 10\)، فإن عامل التفرع صغير، كما يبقى فضاء الحالات sparse ضمن حجم يمكن التعامل معه.