The quantity in this problem is the multiplicative order of
$$a=10^9+7$$
modulo
$$n!=10{,}000{,}000!.$$
In other words, we want the smallest positive integer \(R\) such that
$$a^R\equiv 1 \pmod{n!},$$
and then we report \(R \bmod a\). Because \(a\) is much larger than \(n\), it does not divide \(n!\), so the order is well defined.
The brute-force viewpoint is hopeless. The number \(n!\) is enormous, and the order itself is far beyond direct enumeration. The solution works only because the modulus \(n!\) has a very structured prime-power factorization, and multiplicative orders behave cleanly on prime powers.
The key is to replace one huge congruence modulo \(n!\) by many local congruences modulo prime powers, solve each local problem, and then recombine them through an LCM.
For each prime \(q\le n\), let
$$e_q=v_q(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{q^j}\right\rfloor.$$
This is Legendre's formula, and it gives the exact exponent of \(q\) in the factorization of \(n!\). Therefore
$$n!=\prod_{q\le n} q^{e_q},$$
where the product runs over primes.
Since the prime-power factors are pairwise coprime, the Chinese remainder theorem implies that the order modulo the full factorial is the least common multiple of the local orders:
$$\operatorname{ord}_{n!}(a)=\operatorname{lcm}_{q\le n} \operatorname{ord}_{q^{e_q}}(a).$$
So the problem is reduced to computing \(\operatorname{ord}_{q^{e_q}}(a)\) for every prime \(q\le n\).
Assume first that \(q\) is odd. Let
$$t_q=\operatorname{ord}_q(a).$$
By Fermat's little theorem, \(t_q\mid (q-1)\). That is why the implementations start from \(q-1\), factor it, and repeatedly test whether a prime factor can be removed while keeping the congruence \(a^{t_q}\equiv 1 \pmod q\). After all removable factors are stripped away, the remaining value is the exact order modulo \(q\).
The next question is how this order changes when the modulus is lifted from \(q\) to \(q^2,q^3,\dots,q^{e_q}\). Define
$$s_q=v_q(a^{t_q}-1).$$
This is the first level at which the congruence \(a^{t_q}\equiv 1\) stops being automatic. For odd \(q\), the lifting-the-exponent principle gives
$$v_q\!\left(a^{t_q q^m}-1\right)=s_q+m \qquad (m\ge 0).$$
Hence the minimal exponent that reaches modulus \(q^{e_q}\) is
$$\operatorname{ord}_{q^{e_q}}(a)=t_q\,q^{\max(0,e_q-s_q)}.$$
This formula is exactly what the implementations use. They compute \(t_q\), then test whether \(a^{t_q}\equiv 1\) modulo \(q^2,q^3,\dots\) until the lift fails, and the last successful level is \(s_q\).
The prime \(q=2\) is different because the unit group modulo \(2^e\) does not behave like the odd-prime case. The implementations therefore use explicit \(2\)-adic formulas.
If
$$u=v_2(a-1)$$
and \(a\equiv 1 \pmod 4\), then \(a\) is already very close to 1 in the \(2\)-adic sense, and
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e\le u,\\ 2^{e-u}, & e>u. \end{cases}$$
If instead
$$w=v_2(a+1)$$
and \(a\equiv 3 \pmod 4\), then the order must be even once \(e\ge 2\), and the correct formula is
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e=1,\\ 2^{\max(1,e-w)}, & e\ge 2. \end{cases}$$
For this problem, \(a=10^9+7\equiv 3 \pmod 4\) and \(v_2(a+1)=3\), so the contribution from the \(2\)-power inside \(n!\) is governed by \(2^{\max(1,e_2-3)}\).
Once every local order \(\operatorname{ord}_{q^{e_q}}(a)\) is known, taking their LCM is still too large to do with ordinary integers. The clean way is to collect prime exponents.
For each prime \(r\le n\), define
$$E_r=\max_{q\le n} v_r\!\left(\operatorname{ord}_{q^{e_q}}(a)\right).$$
Then
$$\operatorname{ord}_{n!}(a)=\prod_{r\le n} r^{E_r}.$$
This is why the implementations maintain only a table of maximal exponents. For odd \(q\), the factors coming from \(t_q\) are among the prime divisors of \(q-1\), and the lifting step contributes an extra power of \(q\) itself. No other primes can appear.
The smaller case \(n=12\) shows the whole mechanism in a concrete way. First,
$$12!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11.$$
So we need the orders modulo \(2^{10}\), \(3^5\), \(5^2\), \(7\), and \(11\).
For \(q=2\), we have \(a\equiv 3 \pmod 4\) and \(v_2(a+1)=3\), so
$$\operatorname{ord}_{2^{10}}(a)=2^{\max(1,10-3)}=2^7=128.$$
For \(q=3\), \(a\equiv -1 \pmod 3\), hence \(t_3=2\). Also \(a\equiv -1 \pmod 9\) but not modulo \(27\), so \(s_3=2\). Therefore
$$\operatorname{ord}_{3^5}(a)=2\cdot 3^{5-2}=54.$$
For \(q=5\), \(a\equiv 2 \pmod 5\), whose order modulo 5 is \(t_5=4\). Since \(2^4-1=15\), we get \(s_5=1\), and therefore
$$\operatorname{ord}_{5^2}(a)=4\cdot 5=20.$$
The orders modulo 7 and 11 divide 6 and 10 respectively, so they introduce no new prime powers beyond what is already present in 128, 54, and 20. Hence
$$\operatorname{ord}_{12!}(a)=\operatorname{lcm}(128,54,20)=2^7\cdot 3^3\cdot 5=17280.$$
This is exactly the kind of local-to-global reconstruction used for the full \(n=10^7\) case.
The C++, Python, and Java implementations first build a smallest-prime-factor sieve up to \(n\). That single preprocessing step serves two purposes: it produces the full prime list \(q\le n\), and it allows fast factorizations of numbers like \(q-1\), which are needed when reducing candidate orders.
For each prime \(q\), the implementation evaluates Legendre's formula to obtain \(e_q=v_q(n!)\). This identifies the exact prime-power modulus \(q^{e_q}\) that must be handled.
When \(q\) is odd, the implementation starts from the candidate \(q-1\), factors it, and removes one prime factor at a time whenever modular exponentiation shows that the smaller exponent still works modulo \(q\). That produces \(t_q=\operatorname{ord}_q(a)\).
Next it determines the lift depth \(s_q\) by testing the same exponent \(t_q\) modulo \(q^2,q^3,\dots\). If the congruence survives to a higher power, the order does not grow yet; once it fails, every additional power of \(q\) in the modulus multiplies the order by \(q\). The implementation records both parts of the factorization: the prime factors of \(t_q\), and the extra \(q\)-power coming from \(e_q-s_q\).
For \(q=2\), the implementation bypasses the odd-prime logic and applies the closed \(2\)-adic formulas directly using \(v_2(a-1)\) or \(v_2(a+1)\), depending on whether \(a\equiv 1\) or \(3 \pmod 4\).
Instead of forming gigantic local orders and then taking a literal least common multiple, the implementation updates a global table of maximum prime exponents. After all primes \(q\le n\) are processed, the answer is reconstructed as
$$\prod_{r\le n} r^{E_r}\pmod a.$$
The C++ version uses 128-bit arithmetic for ordinary modular products and switches to multiprecision arithmetic when larger prime powers must be tested exactly. Python gets arbitrary precision automatically, and the Java version uses built-in big integers for the deeper lifting checks.
The sieve up to \(n=10^7\) is \(O(n)\) time and \(O(n)\) memory. This is the dominant storage cost, since both the smallest-prime-factor table and the global exponent table are indexed up to \(n\).
For each prime \(q\le n\), evaluating \(e_q\) costs \(O(\log_q n)\). Factoring \(q-1\) is fast because the sieve is already available, and reducing \(q-1\) to the true order modulo \(q\) requires only a small number of modular exponentiation tests, one for each prime-factor occurrence that might be removed. The lifting phase adds a few more modular exponentiations until the congruence fails at the first unattainable prime power.
So the implementation is best viewed as linear preprocessing plus a per-prime amount of arithmetic that is polylogarithmic in the modulus size. The crucial point is that no part of the algorithm ever tries to build \(n!\) itself or search for the order by repeated multiplication.
Gesucht ist die multiplikative Ordnung von
$$a=10^9+7$$
modulo
$$n!=10{,}000{,}000!.$$
Also sucht man die kleinste positive Zahl \(R\) mit
$$a^R\equiv 1 \pmod{n!},$$
und am Ende wird \(R \bmod a\) ausgegeben. Da \(a\) viel größer als \(n\) ist, teilt \(a\) das Fakultätsprodukt nicht, also ist diese Ordnung wohldefiniert.
Ein direkter Ansatz ist ausgeschlossen. Weder kann man \(n!\) als Ganzes sinnvoll aufbauen, noch die Ordnung durch sukzessives Probieren finden. Die Lösung funktioniert nur, weil \(n!\) in Primzahlpotenzen zerfällt und sich die Ordnung modulo eines Produkts aus teilerfremden Faktoren als kgV lokaler Ordnungen schreiben lässt.
Die gesamte Herleitung besteht aus drei Schritten: Primzahlpotenzen in \(n!\) bestimmen, die Ordnung für jede dieser Primzahlpotenzen berechnen und danach alles über ein kgV wieder zusammensetzen.
Für jede Primzahl \(q\le n\) definiert man
$$e_q=v_q(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{q^j}\right\rfloor.$$
Das ist die Legendre-Formel. Sie liefert exakt den Exponenten von \(q\) in der Primfaktorzerlegung von \(n!\). Also gilt
$$n!=\prod_{q\le n} q^{e_q}.$$
Weil diese Primzahlpotenzen paarweise teilerfremd sind, folgt mit dem chinesischen Restsatz
$$\operatorname{ord}_{n!}(a)=\operatorname{lcm}_{q\le n} \operatorname{ord}_{q^{e_q}}(a).$$
Damit ist das globale Problem auf viele lokale Ordnungsprobleme modulo \(q^{e_q}\) reduziert.
Sei \(q\) ungerade. Dann setzt man
$$t_q=\operatorname{ord}_q(a).$$
Nach dem kleinen Satz von Fermat teilt \(t_q\) die Zahl \(q-1\). Genau deshalb beginnen die Implementierungen mit dem Kandidaten \(q-1\), faktorisieren ihn und versuchen anschließend, Primfaktoren schrittweise herauszuteilen. Immer wenn ein kleinerer Exponent die Kongruenz modulo \(q\) weiterhin erfüllt, ist der entfernte Faktor überflüssig. Was am Ende übrig bleibt, ist die exakte Ordnung modulo \(q\).
Danach muss die Ordnung von \(q\) auf \(q^2,q^3,\dots,q^{e_q}\) angehoben werden. Dazu definiert man
$$s_q=v_q(a^{t_q}-1).$$
Für ungerade \(q\) liefert das LTE-Prinzip
$$v_q\!\left(a^{t_q q^m}-1\right)=s_q+m \qquad (m\ge 0).$$
Also ist die kleinste Potenz, die bereits modulo \(q^{e_q}\) funktioniert, gleich
$$\operatorname{ord}_{q^{e_q}}(a)=t_q\,q^{\max(0,e_q-s_q)}.$$
Genau diese Formel steckt in den drei Implementierungen: Zuerst wird \(t_q\) bestimmt, dann wird getestet, wie weit die Kongruenz \(a^{t_q}\equiv 1\) in höhere \(q\)-Potenzen hinein bestehen bleibt.
Für \(q=2\) gilt eine andere Struktur als für ungerade Primzahlen. Deshalb verwendet der Code hier keine allgemeine Hensel-artige Behandlung, sondern direkte \(2\)-adische Formeln.
Falls
$$u=v_2(a-1)$$
und \(a\equiv 1 \pmod 4\), dann gilt
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e\le u,\\ 2^{e-u}, & e>u. \end{cases}$$
Falls stattdessen
$$w=v_2(a+1)$$
und \(a\equiv 3 \pmod 4\), dann ist die Ordnung ab \(e\ge 2\) zwingend gerade, und man erhält
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e=1,\\ 2^{\max(1,e-w)}, & e\ge 2. \end{cases}$$
Für die konkrete Zahl \(a=10^9+7\) gilt \(a\equiv 3 \pmod 4\) und \(v_2(a+1)=3\). Deshalb wird der Zweieranteil der Gesamtordnung durch \(2^{\max(1,e_2-3)}\) bestimmt.
Selbst nachdem alle lokalen Ordnungen bekannt sind, wäre ein wörtlich ausgerechnetes kgV riesig. Deshalb arbeiten die Implementierungen nur mit Primexponenten.
Für jede Primzahl \(r\le n\) setzt man
$$E_r=\max_{q\le n} v_r\!\left(\operatorname{ord}_{q^{e_q}}(a)\right).$$
Dann gilt
$$\operatorname{ord}_{n!}(a)=\prod_{r\le n} r^{E_r}.$$
Bei ungeradem \(q\) kommen die Primteiler von \(t_q\) nur aus \(q-1\), und das Anheben auf höhere Potenzen fügt höchstens zusätzliche Faktoren \(q\) hinzu. Deshalb genügt eine Tabelle der maximalen Exponenten völlig.
Am kleinen Beispiel \(n=12\) sieht man die Methode vollständig. Zunächst ist
$$12!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11.$$
Also braucht man die Ordnungen modulo \(2^{10}\), \(3^5\), \(5^2\), \(7\) und \(11\).
Für \(q=2\) gilt \(a\equiv 3 \pmod 4\) und \(v_2(a+1)=3\). Also
$$\operatorname{ord}_{2^{10}}(a)=2^{\max(1,10-3)}=2^7=128.$$
Für \(q=3\) ist \(a\equiv -1 \pmod 3\), also \(t_3=2\). Außerdem gilt \(a\equiv -1 \pmod 9\), aber nicht modulo \(27\), also \(s_3=2\). Damit
$$\operatorname{ord}_{3^5}(a)=2\cdot 3^{5-2}=54.$$
Für \(q=5\) ist \(a\equiv 2 \pmod 5\) mit Ordnung \(t_5=4\). Weil \(2^4-1=15\), folgt \(s_5=1\), also
$$\operatorname{ord}_{5^2}(a)=4\cdot 5=20.$$
Die Ordnungen modulo 7 und 11 teilen 6 beziehungsweise 10 und liefern daher keine neuen Primzahlpotenzen mehr. Also
$$\operatorname{ord}_{12!}(a)=\operatorname{lcm}(128,54,20)=2^7\cdot 3^3\cdot 5=17280.$$
Genauso wird im großen Fall gearbeitet, nur eben für alle Primzahlen bis \(10^7\).
Die Implementierungen in C++, Python und Java bauen zuerst ein Sieb der kleinsten Primfaktoren bis \(n\). Damit erhält man sowohl die vollständige Primzahlliste als auch eine schnelle Möglichkeit, Zahlen wie \(q-1\) zu faktorisieren.
Für jede Primzahl \(q\) wird dann mit der Legendre-Formel der Exponent \(e_q=v_q(n!)\) berechnet. Dadurch ist sofort klar, welche Primzahlpotenz \(q^{e_q}\) für die lokale Ordnung relevant ist.
Für ungerade \(q\) startet die Implementierung mit \(q-1\) und reduziert diesen Kandidaten per modularen Potenztests zur echten Ordnung modulo \(q\). Anschließend wird geprüft, ob derselbe Exponent auch noch modulo \(q^2,q^3,\dots\) funktioniert. Aus der letzten erfolgreichen Stufe ergibt sich \(s_q\), und damit die zusätzliche \(q\)-Potenz im lokalen Ordnungswert.
Die Primfaktorzerlegung von \(t_q\) wird sofort in die globale Maximalexponent-Tabelle eingetragen. Dasselbe geschieht mit dem Exponenten \(e_q-s_q\) der Primzahl \(q\) selbst, sofern diese Hebung überhaupt nötig ist.
Für \(q=2\) wird die allgemeine Logik übersprungen; stattdessen wird direkt mit \(v_2(a-1)\) oder \(v_2(a+1)\) gearbeitet, genau entsprechend den oben genannten Fallunterscheidungen.
Am Ende liegt nur noch die Tabelle der maximalen Primexponenten vor. Daraus wird das Ergebnis als
$$\prod_{r\le n} r^{E_r}\pmod a$$
zusammengesetzt. Die C++-Version benutzt 128-Bit-Arithmetik für normale modulare Multiplikationen und Mehrpräzisionsarithmetik für tiefere Hebungstests, die Python-Version profitiert direkt von eingebauter Ganzzahlpräzision, und Java verwendet dafür große Ganzzahlen.
Das Sieb bis \(n=10^7\) benötigt \(O(n)\) Zeit und \(O(n)\) Speicher. Dieser Speicher dominiert die Gesamtnutzung, weil sowohl das SPF-Array als auch die Tabelle der maximalen Primexponenten bis \(n\) indiziert sind.
Für jede Primzahl \(q\le n\) kostet die Berechnung von \(e_q\) nur \(O(\log_q n)\). Die Faktorisierung von \(q-1\) ist durch das Sieb günstig, und die Reduktion zur echten Ordnung modulo \(q\) erfordert nur wenige modulare Potenztests. Die Hebungsphase fügt noch einige wenige weitere Tests hinzu, bis die Kongruenz zum ersten Mal scheitert.
Praktisch ist das Verfahren also lineare Vorverarbeitung plus verhältnismäßig kleine per-Primzahl-Rechnungen. Entscheidend ist, dass an keiner Stelle \(n!\) selbst aufgebaut oder die Ordnung durch wiederholtes Potenzieren gesucht wird.
Bu problemde istenen büyüklük,
$$a=10^9+7$$
sayısının
$$n!=10{,}000{,}000!$$
modülüne göre çarpımsal mertebesidir. Yani aranan değer,
$$a^R\equiv 1 \pmod{n!}$$
eşitliğini sağlayan en küçük pozitif \(R\) sayısıdır; son aşamada da \(R \bmod a\) raporlanır. \(a\), \(n\)'den çok büyük olduğu için \(n!\) ile aralarında ortak bölen yoktur ve mertebe tanımlıdır.
Doğrudan yaklaşım mümkün değildir. Ne \(n!\) açıkça üretilebilir ne de mertebe ardışık üsler denenerek bulunabilir. Çözüm, \(n!\)'in asal kuvvetlere ayrışmasını ve çarpımsal mertebenin bu asal kuvvetler üzerinde ayrı ayrı incelenebilmesini kullanır.
Ana fikir, tek bir dev modül yerine, \(n!\)'in içindeki her asal kuvvet için yerel mertebeyi hesaplayıp bunları EKOK ile birleştirmektir.
Her \(q\le n\) asalı için
$$e_q=v_q(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{q^j}\right\rfloor$$
olsun. Bu Legendre formülüdür ve \(q\)'nun \(n!\) içindeki tam üssünü verir. Dolayısıyla
$$n!=\prod_{q\le n} q^{e_q}$$
olur.
Bu asal kuvvetler aralarında asaldır. Bu yüzden Çin kalan teoremi bize
$$\operatorname{ord}_{n!}(a)=\operatorname{lcm}_{q\le n} \operatorname{ord}_{q^{e_q}}(a)$$
eşitliğini verir. Böylece problem, her asal \(q\) için \(\operatorname{ord}_{q^{e_q}}(a)\) hesabına indirgenir.
Önce \(q\)'nun tek bir asal olduğunu varsayalım. Şu değeri tanımlayalım:
$$t_q=\operatorname{ord}_q(a).$$
Fermat'ın küçük teoremine göre \(t_q\), \(q-1\)'i böler. Bu yüzden uygulamalar önce \(q-1\)'den başlar, onu çarpanlarına ayırır ve mümkün olan asal çarpanları teker teker atarak gerçek mertebeye iner. Daha küçük üssün hâlâ \(a^t\equiv 1 \pmod q\) verdiği her durumda o çarpan gereksizdir.
Asıl önemli nokta, bu mertebenin \(q\)'dan \(q^2,q^3,\dots,q^{e_q}\)'ye çıkarken nasıl büyüdüğüdür. Bunun için
$$s_q=v_q(a^{t_q}-1)$$
tanımlanır. Tek asal \(q\) için LTE mantığı
$$v_q\!\left(a^{t_q q^m}-1\right)=s_q+m \qquad (m\ge 0)$$
sonucunu verir. Buradan
$$\operatorname{ord}_{q^{e_q}}(a)=t_q\,q^{\max(0,e_q-s_q)}$$
elde edilir. Kodun yaptığı şey tam olarak budur: önce \(t_q\) bulunur, sonra aynı üs ile kongruansın \(q^2,q^3,\dots\) modlarında ne kadar sürdüğü ölçülür.
\(q=2\) durumu, tek asallar için kullanılan formülden ayrı ele alınmalıdır. Bunun nedeni, \(2^e\) modülündeki birim grubunun yapısının farklı olmasıdır.
Eğer
$$u=v_2(a-1)$$
ve \(a\equiv 1 \pmod 4\) ise
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e\le u,\\ 2^{e-u}, & e>u. \end{cases}$$
Eğer
$$w=v_2(a+1)$$
ve \(a\equiv 3 \pmod 4\) ise doğru formül
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e=1,\\ 2^{\max(1,e-w)}, & e\ge 2. \end{cases}$$
Bu problemde \(a=10^9+7\equiv 3 \pmod 4\) ve \(v_2(a+1)=3\) olduğu için, \(n!\) içindeki ikinin üssü \(e_2\) için yerel katkı \(2^{\max(1,e_2-3)}\) olur.
Tüm yerel mertebeler bilinse bile bunların EKOK'unu dev tamsayılar üzerinden tutmak istemeyiz. Daha temiz yöntem, her asal için görülen en büyük üssü saklamaktır.
Her \(r\le n\) asalı için
$$E_r=\max_{q\le n} v_r\!\left(\operatorname{ord}_{q^{e_q}}(a)\right)$$
olsun. O zaman
$$\operatorname{ord}_{n!}(a)=\prod_{r\le n} r^{E_r}$$
yazılır. Tek asal \(q\) durumunda \(t_q\)'nun asal çarpanları yalnızca \(q-1\)'den gelir; yükseltme adımı ise en fazla \(q\)'nun kendisinden ek kuvvet üretir. Bu yüzden maksimum üs tablosu yeterlidir.
Küçük örnek tüm mekanizmayı net biçimde gösterir:
$$12!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11.$$
Dolayısıyla sırasıyla \(2^{10}\), \(3^5\), \(5^2\), 7 ve 11 modüllerindeki mertebeleri bulmamız gerekir.
\(q=2\) için \(a\equiv 3 \pmod 4\) ve \(v_2(a+1)=3\) olduğundan
$$\operatorname{ord}_{2^{10}}(a)=2^{\max(1,10-3)}=2^7=128.$$
\(q=3\) için \(a\equiv -1 \pmod 3\), dolayısıyla \(t_3=2\). Ayrıca \(a\equiv -1 \pmod 9\), fakat \(27\) modunda artık 1 değildir; yani \(s_3=2\). Böylece
$$\operatorname{ord}_{3^5}(a)=2\cdot 3^{5-2}=54.$$
\(q=5\) için \(a\equiv 2 \pmod 5\) ve bu sayının mod 5'teki mertebesi \(t_5=4\)'tür. \(2^4-1=15\) olduğundan \(s_5=1\) ve
$$\operatorname{ord}_{5^2}(a)=4\cdot 5=20.$$
7 ve 11 modüllerindeki mertebeler sırasıyla 6 ve 10'u böler; dolayısıyla 128, 54 ve 20'de zaten bulunan asal kuvvetlerin ötesine geçmezler. O halde
$$\operatorname{ord}_{12!}(a)=\operatorname{lcm}(128,54,20)=2^7\cdot 3^3\cdot 5=17280.$$
Büyük örnekte yapılan işlem de aynıdır; sadece kapsanan asal sayısı çok daha fazladır.
C++, Python ve Java uygulamaları önce en küçük asal bölen süzgeci kurar. Bu tek adım hem tüm asal listesini çıkarır hem de \(q-1\) gibi sayıların çarpanlara ayrılmasını hızlandırır.
Her asal \(q\) için Legendre formülüyle \(e_q=v_q(n!)\) hesaplanır. Böylece incelenecek yerel modül hemen \(q^{e_q}\) olarak belirlenir.
Tek asal \(q\) için uygulama \(q-1\)'den başlayıp modüler üs alma testleriyle gerçek mertebe \(t_q\)'ya iner. Ardından aynı üssün \(q^2,q^3,\dots\) modlarında da işe yarayıp yaramadığı kontrol edilir; son başarılı seviye \(s_q\)'yu verir.
Böylece iki tür bilgi global tabloya yazılır: \(t_q\)'nun asal çarpanları ve gerekiyorsa yükseltmeden gelen ek \(q\) kuvveti. \(q=2\) olduğunda ise bu genel akış atlanır ve doğrudan \(2\)-adik formüller uygulanır.
Tüm yerel katkılar işlendiğinde elde yalnızca maksimum asal üsleri kalır. Son cevap
$$\prod_{r\le n} r^{E_r}\pmod a$$
şeklinde üretilir. C++ sürümü normal çarpımlarda 128 bit, daha derin kaldırma denemelerinde çok hassas tamsayı aritmetiği kullanır; Python doğal olarak büyük tamsayı destekler; Java sürümü de büyük tamsayılarla aynı işi yapar.
\(n=10^7\) için süzgeç \(O(n)\) zaman ve \(O(n)\) bellek gerektirir. En büyük bellek gideri, en küçük asal bölen dizisi ile maksimum üs tablosudur.
Her asal \(q\) için \(e_q\) hesabı \(O(\log_q n)\) maliyetlidir. \(q-1\)'in çarpanlara ayrılması süzgeç sayesinde hızlıdır; gerçek mertebeye inmek için de yalnızca birkaç modüler üs testi gerekir. Yükseltme aşaması da kongruans ilk kez bozulana kadar birkaç ek test daha yapar.
Dolayısıyla yöntem, doğrusal bir ön hazırlık ile her asal için görece küçük aritmetik işlemlerin birleşimi olarak görülebilir. En kritik nokta, algoritmanın hiçbir aşamada \(n!\)'i açıkça üretmemesi ve mertebeyi kör kuvvet denemeleriyle aramamasıdır.
La cantidad buscada es el orden multiplicativo de
$$a=10^9+7$$
módulo
$$n!=10{,}000{,}000!.$$
Es decir, hay que encontrar el menor entero positivo \(R\) tal que
$$a^R\equiv 1 \pmod{n!},$$
y después devolver \(R \bmod a\). Como \(a\) es mucho mayor que \(n\), no divide a \(n!\), así que el orden está bien definido.
Un ataque directo no tiene ninguna posibilidad. El módulo \(n!\) es gigantesco y el propio orden también puede ser enorme. La solución funciona porque \(n!\) tiene una descomposición en potencias primas muy rígida, y el orden multiplicativo se puede estudiar localmente en cada una de esas potencias.
La idea central es sustituir una congruencia enorme módulo \(n!\) por muchas congruencias locales módulo \(q^{e_q}\), resolver cada una y luego recomponer el resultado mediante un m.c.m.
Para cada primo \(q\le n\), definimos
$$e_q=v_q(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{q^j}\right\rfloor.$$
Esta es la fórmula de Legendre, y da exactamente el exponente de \(q\) en \(n!\). Por tanto,
$$n!=\prod_{q\le n} q^{e_q}.$$
Como esas potencias primas son coprimas entre sí, el teorema chino del resto implica
$$\operatorname{ord}_{n!}(a)=\operatorname{lcm}_{q\le n} \operatorname{ord}_{q^{e_q}}(a).$$
Así, el problema global se reduce a calcular \(\operatorname{ord}_{q^{e_q}}(a)\) para cada primo \(q\le n\).
Supongamos primero que \(q\) es impar. Definimos
$$t_q=\operatorname{ord}_q(a).$$
Por el pequeño teorema de Fermat, \(t_q\mid(q-1)\). Esa es la razón por la que las implementaciones comienzan con el candidato \(q-1\), lo factorizan y tratan de eliminar sus factores primos uno a uno: siempre que un exponente más pequeño siga satisfaciendo la congruencia módulo \(q\), el factor eliminado no era necesario. Al final queda el orden exacto módulo \(q\).
Después hay que entender qué ocurre al pasar de \(q\) a \(q^2,q^3,\dots,q^{e_q}\). Para eso se introduce
$$s_q=v_q(a^{t_q}-1).$$
Para un primo impar, el lema de elevación del exponente da
$$v_q\!\left(a^{t_q q^m}-1\right)=s_q+m \qquad (m\ge 0).$$
De ahí se concluye que
$$\operatorname{ord}_{q^{e_q}}(a)=t_q\,q^{\max(0,e_q-s_q)}.$$
Eso es exactamente lo que implementa el código: primero calcula \(t_q\), luego comprueba hasta qué potencia de \(q\) sigue siendo cierto que \(a^{t_q}\equiv 1\).
El caso \(q=2\) no sigue la misma pauta que los primos impares, así que se trata por separado.
Si
$$u=v_2(a-1)$$
y \(a\equiv 1 \pmod 4\), entonces
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e\le u,\\ 2^{e-u}, & e>u. \end{cases}$$
Si en cambio
$$w=v_2(a+1)$$
y \(a\equiv 3 \pmod 4\), la fórmula correcta es
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e=1,\\ 2^{\max(1,e-w)}, & e\ge 2. \end{cases}$$
En este problema concreto, \(a=10^9+7\equiv 3 \pmod 4\) y \(v_2(a+1)=3\). Por eso la parte correspondiente a la potencia de 2 dentro de \(n!\) viene dada por \(2^{\max(1,e_2-3)}\).
Incluso después de obtener todos los órdenes locales, no conviene formar el m.c.m. como un entero gigantesco. Lo correcto es guardar solo los máximos exponentes primos.
Para cada primo \(r\le n\), definimos
$$E_r=\max_{q\le n} v_r\!\left(\operatorname{ord}_{q^{e_q}}(a)\right).$$
Entonces
$$\operatorname{ord}_{n!}(a)=\prod_{r\le n} r^{E_r}.$$
Para un primo impar \(q\), los factores primos de \(t_q\) salen de \(q-1\), y la elevación a \(q^{e_q}\) solo puede añadir más potencia del propio \(q\). Por eso basta con mantener una tabla global de exponentes máximos.
El caso \(n=12\) ilustra toda la idea sin ocultar ningún paso:
$$12!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11.$$
Así que debemos estudiar los órdenes módulo \(2^{10}\), \(3^5\), \(5^2\), 7 y 11.
Para \(q=2\), como \(a\equiv 3 \pmod 4\) y \(v_2(a+1)=3\), obtenemos
$$\operatorname{ord}_{2^{10}}(a)=2^{\max(1,10-3)}=2^7=128.$$
Para \(q=3\), se tiene \(a\equiv -1 \pmod 3\), luego \(t_3=2\). Además, \(a\equiv -1 \pmod 9\) pero ya no módulo \(27\), así que \(s_3=2\). Por tanto,
$$\operatorname{ord}_{3^5}(a)=2\cdot 3^{5-2}=54.$$
Para \(q=5\), \(a\equiv 2 \pmod 5\), y el orden de 2 módulo 5 es \(t_5=4\). Como \(2^4-1=15\), resulta \(s_5=1\), y entonces
$$\operatorname{ord}_{5^2}(a)=4\cdot 5=20.$$
Los órdenes módulo 7 y 11 dividen 6 y 10 respectivamente, así que no añaden nuevas potencias primas más allá de las que ya aparecen en 128, 54 y 20. En consecuencia,
$$\operatorname{ord}_{12!}(a)=\operatorname{lcm}(128,54,20)=2^7\cdot 3^3\cdot 5=17280.$$
Ese mismo ensamblaje local-global es el que se usa en el caso real con \(n=10^7\).
Las implementaciones en C++, Python y Java construyen primero una criba del menor factor primo hasta \(n\). Esa estructura produce la lista completa de primos y, al mismo tiempo, permite factorizar rápidamente enteros como \(q-1\).
Para cada primo \(q\), la implementación calcula \(e_q=v_q(n!)\) mediante la fórmula de Legendre. Con eso ya queda fijado el módulo local \(q^{e_q}\) que hay que tratar.
Si \(q\) es impar, se parte de \(q-1\) y se lo reduce al orden exacto mediante pruebas de exponenciación modular. Luego se comprueba hasta qué potencia de \(q\) sigue valiendo la congruencia con ese mismo exponente, lo que determina \(s_q\).
La factorización prima de \(t_q\) actualiza directamente la tabla global de máximos, y la elevación añade, cuando corresponde, una potencia extra del propio \(q\). Cuando \(q=2\), se omite ese proceso y se aplican directamente las fórmulas \(2\)-ádicas.
En lugar de construir números locales gigantescos, la implementación solo conserva la máxima potencia observada para cada primo. Al final recompone la respuesta como
$$\prod_{r\le n} r^{E_r}\pmod a.$$
La versión en C++ usa aritmética de 128 bits para los productos modulares normales y multiprecisión cuando hay que probar potencias primas más profundas. Python dispone de enteros arbitrariamente grandes de manera natural, y Java utiliza enteros grandes integrados para esos mismos controles.
La criba hasta \(n=10^7\) cuesta \(O(n)\) tiempo y \(O(n)\) memoria. Ese también es el consumo dominante de espacio, porque tanto la tabla de menores factores primos como la tabla global de exponentes máximos están indexadas hasta \(n\).
Para cada primo \(q\le n\), calcular \(e_q\) cuesta \(O(\log_q n)\). Factorizar \(q-1\) es barato gracias a la criba, y reducir \(q-1\) hasta el orden real módulo \(q\) requiere solo unas pocas pruebas de exponenciación modular. La fase de elevación añade unas pocas pruebas más, hasta que la congruencia deja de cumplirse por primera vez.
En conjunto, el algoritmo es una combinación de preprocesamiento lineal y trabajo aritmético relativamente pequeño por primo. Lo esencial es que nunca intenta construir \(n!\) de forma explícita ni busca el orden probando exponentes uno a uno.
本题要求计算
$$a=10^9+7$$
在模
$$n!=10{,}000{,}000!$$
意义下的乘法阶。也就是说，我们要找出最小的正整数 \(R\)，使得
$$a^R\equiv 1 \pmod{n!},$$
然后输出 \(R \bmod a\)。由于 \(a\) 远大于 \(n\)，它不会整除 \(n!\)，所以这个乘法阶确实存在。
如果从“直接算”这个角度出发，问题几乎没有入口。\(n!\) 本身大得无法显式构造，真正的阶也不可能靠不断试乘来找到。可行的路线只有一条：利用 \(n!\) 的素数幂分解，把模 \(n!\) 的问题拆成模各个素数幂的局部问题，再把这些局部结果合并回来。
整道题的数学结构非常清晰：先把 \(n!\) 分解成互素的素数幂，再计算每个局部模数上的乘法阶，最后用最小公倍数把它们重新拼成整体答案。
对每个满足 \(q\le n\) 的素数 \(q\)，定义
$$e_q=v_q(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{q^j}\right\rfloor.$$
这就是 Legendre 公式，它给出了 \(q\) 在 \(n!\) 中的精确指数。因此
$$n!=\prod_{q\le n} q^{e_q}.$$
这些素数幂彼此互素，所以由中国剩余定理可知，模整个 \(n!\) 的乘法阶恰好等于所有局部乘法阶的最小公倍数：
$$\operatorname{ord}_{n!}(a)=\operatorname{lcm}_{q\le n} \operatorname{ord}_{q^{e_q}}(a).$$
于是问题被压缩成很多个独立的局部任务：对每个素数 \(q\)，求 \(\operatorname{ord}_{q^{e_q}}(a)\)。
先设 \(q\) 是奇素数。记
$$t_q=\operatorname{ord}_q(a).$$
根据费马小定理，\(t_q\) 一定整除 \(q-1\)。这正是实现中从 \(q-1\) 出发的原因：先把 \(q-1\) 分解质因数，然后尝试把其中的素因子逐个剥掉。只要剥掉之后仍满足对应的模 \(q\) 同余，说明这个因子并不是必须的。所有能删的都删完后，剩下的就是精确的 \(t_q\)。
接下来要解决的是“提升”问题：从模 \(q\) 提升到模 \(q^2,q^3,\dots,q^{e_q}\) 时，阶会怎样增长。定义
$$s_q=v_q(a^{t_q}-1).$$
对奇素数，LTE 引理给出
$$v_q\!\left(a^{t_q q^m}-1\right)=s_q+m \qquad (m\ge 0).$$
这意味着要想达到模 \(q^{e_q}\) 的同余，最小指数就是
$$\operatorname{ord}_{q^{e_q}}(a)=t_q\,q^{\max(0,e_q-s_q)}.$$
实现代码正是沿着这个公式工作的：先求 \(t_q\)，再检查 \(a^{t_q}\equiv 1\) 能在 \(q^2,q^3,\dots\) 这些更高幂次模数下持续到哪一层，最后那一层就是 \(s_q\)。
\(q=2\) 不能直接套用奇素数的思路，因为模 \(2^e\) 的单位群结构不同，所以代码专门使用显式的 \(2\)-进公式。
如果
$$u=v_2(a-1)$$
且 \(a\equiv 1 \pmod 4\)，那么
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e\le u,\\ 2^{e-u}, & e>u. \end{cases}$$
如果
$$w=v_2(a+1)$$
且 \(a\equiv 3 \pmod 4\)，那么正确公式是
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e=1,\\ 2^{\max(1,e-w)}, & e\ge 2. \end{cases}$$
对本题来说，\(a=10^9+7\equiv 3 \pmod 4\)，并且 \(v_2(a+1)=3\)。因此 \(n!\) 中 2 的幂次只会贡献出 \(2^{\max(1,e_2-3)}\) 这一部分。
就算所有局部阶都算出来了，也不应该真的去构造一个巨大的最小公倍数。更合理的做法是只记录每个素数在最终答案中出现的最大指数。
对每个素数 \(r\le n\)，定义
$$E_r=\max_{q\le n} v_r\!\left(\operatorname{ord}_{q^{e_q}}(a)\right).$$
那么
$$\operatorname{ord}_{n!}(a)=\prod_{r\le n} r^{E_r}.$$
对奇素数 \(q\) 来说，\(t_q\) 的质因子只可能来自 \(q-1\)，而从 \(q\) 提升到 \(q^{e_q}\) 只会额外增加若干个 \(q\) 本身。因此维护一张“全局最大指数表”就足够了。
用 \(n=12\) 可以把整个过程完整地走一遍。首先，
$$12!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11.$$
因此我们需要分别求模 \(2^{10}\)、\(3^5\)、\(5^2\)、7 和 11 的乘法阶。
对 \(q=2\)，因为 \(a\equiv 3 \pmod 4\) 且 \(v_2(a+1)=3\)，所以
$$\operatorname{ord}_{2^{10}}(a)=2^{\max(1,10-3)}=2^7=128.$$
对 \(q=3\)，有 \(a\equiv -1 \pmod 3\)，所以 \(t_3=2\)。同时 \(a\equiv -1 \pmod 9\)，但不再是模 \(27\) 的 1，因此 \(s_3=2\)。于是
$$\operatorname{ord}_{3^5}(a)=2\cdot 3^{5-2}=54.$$
对 \(q=5\)，\(a\equiv 2 \pmod 5\)，而 2 在模 5 下的阶为 \(t_5=4\)。由于 \(2^4-1=15\)，得到 \(s_5=1\)，于是
$$\operatorname{ord}_{5^2}(a)=4\cdot 5=20.$$
模 7 和模 11 的阶分别整除 6 和 10，不会再引入新的质因子指数。因此
$$\operatorname{ord}_{12!}(a)=\operatorname{lcm}(128,54,20)=2^7\cdot 3^3\cdot 5=17280.$$
真实题目只是在更大的 \(n\) 上重复同一套“局部计算，再全局合并”的过程。
C++、Python 和 Java 三个实现都会先建立一个最小素因子筛。这样既能得到全部素数列表，也能快速分解像 \(q-1\) 这样的整数。
随后对每个素数 \(q\)，利用 Legendre 公式求出 \(e_q=v_q(n!)\)。这一点直接确定了需要处理的局部模数 \(q^{e_q}\)。
若 \(q\) 是奇素数，实现会从 \(q-1\) 开始，用模幂测试把它缩减到真正的 \(t_q\)。然后再测试这个指数在 \(q^2,q^3,\dots\) 下是否仍然成立，以此确定提升深度 \(s_q\)。
之后，\(t_q\) 的质因数分解会更新全局最大指数表，而提升带来的那部分 \(q^{e_q-s_q}\) 也会在需要时加入同一张表。对于 \(q=2\)，实现直接走上面的 \(2\)-进分支，而不复用奇素数逻辑。
所有局部信息汇总完以后，代码并不显式构造巨大的整数，而是直接计算
$$\prod_{r\le n} r^{E_r}\pmod a.$$
C++ 版本在普通模乘上使用 128 位整数，并在更深的素数幂检查中切换到多精度整数；Python 天然支持任意精度；Java 版本则在这些深层检查里使用大整数。
筛到 \(n=10^7\) 需要 \(O(n)\) 时间和 \(O(n)\) 空间。空间上的主要开销就是最小素因子表以及全局最大指数表，它们都按 \(n\) 的规模建立。
对每个素数 \(q\le n\)，计算 \(e_q\) 的代价是 \(O(\log_q n)\)。分解 \(q-1\) 因为有筛表而很快，把 \(q-1\) 缩减成真正的阶只需要少量模幂测试。提升阶段再增加若干次模幂测试，直到同余第一次失败为止。
因此，整体上可以把算法看成“线性级别的预处理 + 每个素数上一点额外算术”。真正重要的是：算法从头到尾都不需要构造 \(n!\) 本身，也不需要靠顺次试探指数去找乘法阶。
В задаче требуется найти мультипликативный порядок числа
$$a=10^9+7$$
по модулю
$$n!=10{,}000{,}000!.$$
То есть нужно определить наименьшее положительное \(R\), для которого
$$a^R\equiv 1 \pmod{n!},$$
а затем вывести \(R \bmod a\). Поскольку \(a\) намного больше \(n\), оно не делит \(n!\), так что порядок определен корректно.
Лобовой подход здесь невозможен. Нельзя ни построить само число \(n!\), ни искать порядок последовательным перебором показателей. Рабочее решение опирается на точную структуру разложения \(n!\) на простые степени и на то, что порядок по модулю произведения взаимно простых модулей восстанавливается через НОК локальных порядков.
Вся математика сводится к локально-глобальному принципу: сначала решаем задачу для каждого простого степенного модуля, затем объединяем ответы.
Для каждого простого \(q\le n\) введем
$$e_q=v_q(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{q^j}\right\rfloor.$$
Это формула Лежандра. Она дает точную степень простого \(q\) в факторизации \(n!\). Следовательно,
$$n!=\prod_{q\le n} q^{e_q}.$$
Поскольку эти простые степени попарно взаимно просты, по китайской теореме об остатках получаем
$$\operatorname{ord}_{n!}(a)=\operatorname{lcm}_{q\le n} \operatorname{ord}_{q^{e_q}}(a).$$
Значит, глобальная задача распадается на вычисление \(\operatorname{ord}_{q^{e_q}}(a)\) для всех простых \(q\le n\).
Пусть \(q\) нечетное простое. Обозначим
$$t_q=\operatorname{ord}_q(a).$$
По малой теореме Ферма \(t_q\mid(q-1)\). Именно поэтому реализации начинают с числа \(q-1\), раскладывают его на множители и затем пытаются последовательно убрать лишние простые множители. Если меньший показатель все еще дает единицу по модулю \(q\), значит соответствующий множитель не нужен. После всех таких сокращений остается точный порядок modulo \(q\).
Дальше нужно понять, как этот порядок поднимается с \(q\) на \(q^2,q^3,\dots,q^{e_q}\). Для этого вводится величина
$$s_q=v_q(a^{t_q}-1).$$
Для нечетного простого \(q\) лемма LTE дает
$$v_q\!\left(a^{t_q q^m}-1\right)=s_q+m \qquad (m\ge 0).$$
Отсюда немедленно следует формула
$$\operatorname{ord}_{q^{e_q}}(a)=t_q\,q^{\max(0,e_q-s_q)}.$$
Именно эта схема реализована в коде: сначала находится \(t_q\), затем проверяется, до какой степени \(q\) сохраняется сравнение \(a^{t_q}\equiv 1\).
Для \(q=2\) структура иная, поэтому используется отдельная формула, а не общий шаблон для нечетных простых.
Если
$$u=v_2(a-1)$$
и \(a\equiv 1 \pmod 4\), то
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e\le u,\\ 2^{e-u}, & e>u. \end{cases}$$
Если же
$$w=v_2(a+1)$$
и \(a\equiv 3 \pmod 4\), то верна формула
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e=1,\\ 2^{\max(1,e-w)}, & e\ge 2. \end{cases}$$
В нашей задаче \(a=10^9+7\equiv 3 \pmod 4\) и \(v_2(a+1)=3\). Поэтому вклад двойки в локальный порядок определяется выражением \(2^{\max(1,e_2-3)}\).
Даже когда все локальные порядки известны, не хочется явно хранить их НОК как гигантское число. Гораздо удобнее работать только с простыми показателями.
Для каждого простого \(r\le n\) положим
$$E_r=\max_{q\le n} v_r\!\left(\operatorname{ord}_{q^{e_q}}(a)\right).$$
Тогда
$$\operatorname{ord}_{n!}(a)=\prod_{r\le n} r^{E_r}.$$
Для нечетного \(q\) простые делители \(t_q\) происходят из \(q-1\), а при подъеме на более высокие степени может добавиться только дополнительная степень самого \(q\). Поэтому достаточно поддерживать таблицу максимальных показателей.
На примере \(n=12\) хорошо видно, как работает вся конструкция. Сначала
$$12!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11.$$
Значит, нужно вычислить порядки modulo \(2^{10}\), \(3^5\), \(5^2\), 7 и 11.
Для \(q=2\): \(a\equiv 3 \pmod 4\) и \(v_2(a+1)=3\), поэтому
$$\operatorname{ord}_{2^{10}}(a)=2^{\max(1,10-3)}=2^7=128.$$
Для \(q=3\): \(a\equiv -1 \pmod 3\), значит \(t_3=2\). Кроме того, \(a\equiv -1 \pmod 9\), но уже не modulo \(27\), то есть \(s_3=2\). Следовательно,
$$\operatorname{ord}_{3^5}(a)=2\cdot 3^{5-2}=54.$$
Для \(q=5\): \(a\equiv 2 \pmod 5\), а порядок двойки modulo 5 равен \(t_5=4\). Так как \(2^4-1=15\), получаем \(s_5=1\), и поэтому
$$\operatorname{ord}_{5^2}(a)=4\cdot 5=20.$$
Порядки modulo 7 и 11 делят 6 и 10 соответственно, так что новых простых степеней они не добавляют. Итак,
$$\operatorname{ord}_{12!}(a)=\operatorname{lcm}(128,54,20)=2^7\cdot 3^3\cdot 5=17280.$$
В полном решении для \(n=10^7\) выполняется ровно тот же самый локально-глобальный расчет.
Реализации на C++, Python и Java сначала строят решето минимального простого делителя до \(n\). Это сразу дает и список всех простых, и быстрый способ раскладывать числа вида \(q-1\).
После этого для каждого простого \(q\) по формуле Лежандра вычисляется \(e_q=v_q(n!)\). Тем самым определяется локальный модуль \(q^{e_q}\), на котором надо считать порядок.
Для нечетного \(q\) реализация уменьшает исходный кандидат \(q-1\) до точного значения \(t_q\) с помощью проверок модульного возведения в степень. Затем проверяется, до какой степени \(q\) сохраняется сравнение с тем же показателем, что и дает глубину подъема \(s_q\).
Факторизация числа \(t_q\) сразу обновляет глобальные максимальные показатели. Если при подъеме требуется дополнительная степень самого \(q\), она тоже заносится туда же. Для \(q=2\) этот путь не используется: берется специальная \(2\)-адическая формула.
После обработки всех простых код хранит только таблицу максимальных простых показателей и восстанавливает ответ как
$$\prod_{r\le n} r^{E_r}\pmod a.$$
Версия на C++ использует 128-битную арифметику для обычных модульных произведений и многоточную арифметику для более глубоких проверок простых степеней. Python получает длинную арифметику автоматически, а Java использует встроенные большие целые.
Решето до \(n=10^7\) работает за \(O(n)\) времени и требует \(O(n)\) памяти. Это и есть основной расход памяти, поскольку и массив минимальных простых делителей, и таблица максимальных показателей индексируются до \(n\).
Для каждого простого \(q\le n\) вычисление \(e_q\) стоит \(O(\log_q n)\). Факторизация \(q-1\) дешева благодаря решету, а для сведения \(q-1\) к истинному порядку modulo \(q\) нужно лишь небольшое число проверок модульного возведения в степень. Фаза подъема добавляет еще несколько проверок, пока сравнение не перестанет выполняться.
Поэтому алгоритм лучше всего понимать как линейную подготовку плюс умеренный объем арифметики на каждый простой. Принципиально важно, что он нигде не строит \(n!\) явно и нигде не ищет порядок последовательным перебором степеней.
المطلوب في هذه المسألة هو إيجاد الرتبة الضربية للعدد
$$a=10^9+7$$
بترديد
$$n!=10{,}000{,}000!.$$
أي نبحث عن أصغر عدد صحيح موجب \(R\) يحقق
$$a^R\equiv 1 \pmod{n!},$$
ثم نعيد \(R \bmod a\). وبما أن \(a\) أكبر بكثير من \(n\)، فهو لا يقسم \(n!\)، ولذلك فالرتبة معرفة جيدًا.
المقاربة المباشرة غير واقعية تمامًا. لا يمكن بناء \(n!\) صراحة، ولا يمكن البحث عن الرتبة بتجريب الأسس واحدًا بعد آخر. الحل يعتمد على أن \(n!\) يتحلل إلى قوى أولية بطريقة دقيقة، وأن الرتبة الضربية يمكن حسابها محليًا على كل قوة أولية ثم جمع هذه المعلومات في النهاية.
الفكرة الأساسية هي تفكيك المسألة الكبيرة modulo \(n!\) إلى مسائل أصغر modulo \(q^{e_q}\) لكل أولي \(q\)، ثم إعادة تركيب الجواب عبر القاسم المشترك الأصغر.
لكل عدد أولي \(q\le n\)، نعرّف
$$e_q=v_q(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{q^j}\right\rfloor.$$
هذه هي صيغة ليجاندر، وهي تعطي الأس الدقيق لـ \(q\) داخل تحليل \(n!\). ومن ثم
$$n!=\prod_{q\le n} q^{e_q}.$$
وبما أن هذه القوى الأولية متباينة أوليًا، فإن مبرهنة البواقي الصينية تعطينا
$$\operatorname{ord}_{n!}(a)=\operatorname{lcm}_{q\le n} \operatorname{ord}_{q^{e_q}}(a).$$
إذن المسألة العالمية تختزل إلى حساب \(\operatorname{ord}_{q^{e_q}}(a)\) لكل أولي \(q\le n\).
لنفرض أولًا أن \(q\) أولي فردي. نكتب
$$t_q=\operatorname{ord}_q(a).$$
بفعل مبرهنة فيرما الصغرى، يقسم \(t_q\) العدد \(q-1\). لهذا تبدأ التطبيقات من \(q-1\)، ثم تحلله إلى عوامله الأولية، ثم تحاول حذف هذه العوامل واحدًا بعد آخر متى ظلّ الأس الأصغر يحقق التطابق modulo \(q\). بعد إزالة كل ما يمكن إزالته، يبقى الأس الصحيح modulo \(q\).
بعد ذلك نحتاج إلى معرفة كيف يرتفع هذا النظام عند الانتقال من \(q\) إلى \(q^2,q^3,\dots,q^{e_q}\). نعرّف
$$s_q=v_q(a^{t_q}-1).$$
وللأولي الفردي تعطينا لمّة رفع الأس
$$v_q\!\left(a^{t_q q^m}-1\right)=s_q+m \qquad (m\ge 0).$$
ومن هنا نحصل على الصيغة
$$\operatorname{ord}_{q^{e_q}}(a)=t_q\,q^{\max(0,e_q-s_q)}.$$
هذه هي الصيغة الفعلية التي تطبقها الشيفرات: تُحسب \(t_q\) أولًا، ثم يُفحص إلى أي درجة من قوى \(q\) يبقى التطابق \(a^{t_q}\equiv 1\) صحيحًا.
الحالة \(q=2\) لا تتبع السلوك نفسه، لذلك تُعالج على نحو منفصل.
إذا كان
$$u=v_2(a-1)$$
وكان \(a\equiv 1 \pmod 4\)، فإن
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e\le u,\\ 2^{e-u}, & e>u. \end{cases}$$
أما إذا كان
$$w=v_2(a+1)$$
وكان \(a\equiv 3 \pmod 4\)، فالصيغة الصحيحة هي
$$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e=1,\\ 2^{\max(1,e-w)}, & e\ge 2. \end{cases}$$
في هذه المسألة تحديدًا لدينا \(a=10^9+7\equiv 3 \pmod 4\) و\(v_2(a+1)=3\)، ولذلك فإن مساهمة قوة 2 داخل \(n!\) تحكمها العبارة \(2^{\max(1,e_2-3)}\).
حتى بعد معرفة جميع الرتب المحلية، لا نريد تكوين القاسم المشترك الأصغر كعدد عملاق. الأنظف هو حفظ أكبر أس أولي يظهر في النتيجة النهائية.
لكل أولي \(r\le n\)، نضع
$$E_r=\max_{q\le n} v_r\!\left(\operatorname{ord}_{q^{e_q}}(a)\right).$$
وعندئذٍ
$$\operatorname{ord}_{n!}(a)=\prod_{r\le n} r^{E_r}.$$
في حالة الأولي الفردي \(q\)، تأتي العوامل الأولية لـ \(t_q\) من تحليل \(q-1\)، أما الرفع إلى \(q^{e_q}\) فلا يضيف إلا قوة إضافية محتملة من \(q\) نفسه. لهذا تكفي تمامًا بنية بيانات تحتفظ بأكبر أس لكل أولي.
الحالة الصغيرة \(n=12\) تعرض الآلية كاملة. بدايةً
$$12!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11.$$
إذن نحتاج إلى الرتب modulo \(2^{10}\)، و\(3^5\)، و\(5^2\)، و7، و11.
بالنسبة إلى \(q=2\)، لدينا \(a\equiv 3 \pmod 4\) و\(v_2(a+1)=3\)، ومن ثم
$$\operatorname{ord}_{2^{10}}(a)=2^{\max(1,10-3)}=2^7=128.$$
وبالنسبة إلى \(q=3\)، فإن \(a\equiv -1 \pmod 3\)، لذا \(t_3=2\). كذلك \(a\equiv -1 \pmod 9\) لكنه لا يبقى كذلك modulo \(27\)، أي إن \(s_3=2\). وبالتالي
$$\operatorname{ord}_{3^5}(a)=2\cdot 3^{5-2}=54.$$
أما \(q=5\)، فلدينا \(a\equiv 2 \pmod 5\)، ورتبة 2 modulo 5 هي \(t_5=4\). وبما أن \(2^4-1=15\)، ينتج \(s_5=1\)، ومن ثم
$$\operatorname{ord}_{5^2}(a)=4\cdot 5=20.$$
الرتبتان modulo 7 و11 تقسمان 6 و10 على الترتيب، ولذلك لا تضيفان أي قوة أولية جديدة فوق ما هو موجود بالفعل في 128 و54 و20. إذن
$$\operatorname{ord}_{12!}(a)=\operatorname{lcm}(128,54,20)=2^7\cdot 3^3\cdot 5=17280.$$
هذا المثال الصغير يكرر تمامًا البنية نفسها التي تُستخدم في المسألة الكاملة عند \(n=10^7\).
تقوم التطبيقات في ++C وPython وJava أولًا ببناء غربال أصغر قاسم أولي حتى \(n\). هذا الغربال يعطي قائمة الأعداد الأولية كاملة، كما يسمح بتحليل أعداد من نوع \(q-1\) بسرعة كبيرة.
بعد ذلك، يُحسب \(e_q=v_q(n!)\) لكل أولي \(q\) باستخدام صيغة ليجاندر. وهكذا يصبح المودول المحلي \(q^{e_q}\) معلومًا مباشرة.
إذا كان \(q\) أوليًا فرديًا، تبدأ الشيفرة من \(q-1\) ثم تخفض هذا المرشح إلى \(t_q\) الحقيقي عبر اختبارات الرفع السريع modulo \(q\). وبعد ذلك تُفحص المراتب \(q^2,q^3,\dots\) لمعرفة عمق الرفع \(s_q\).
ثم تُحدَّث البنية العالمية بأُسس العوامل الأولية التي تظهر في \(t_q\)، ويُضاف أيضًا الأس الإضافي لـ \(q\) نفسه عندما تفرضه عملية الرفع. أما في حالة \(q=2\)، فتُستخدم الصيغ الثنائية-الأديكية مباشرة بدل هذا المسار العام.
في النهاية لا تحتفظ الشيفرة إلا بأكبر أس لكل أولي، ثم تعيد بناء النتيجة على الصورة
$$\prod_{r\le n} r^{E_r}\pmod a.$$
نسخة ++C تستخدم حسابات 128-بت للضرب المعياري العادي، وتنتقل إلى أعداد متعددة الدقة عندما تحتاج اختبارات الرفع إلى قوى أولية أكبر. Python تتعامل مع الأعداد الكبيرة بشكل طبيعي، أما Java فتستخدم الأعداد الصحيحة الكبيرة المدمجة لهذه المرحلة.
الغربال حتى \(n=10^7\) يحتاج إلى \(O(n)\) زمنًا و\(O(n)\) ذاكرة. وهذا هو العبء الأساسي على مستوى الذاكرة، لأن جدول أصغر قاسم أولي وجدول أكبر الأسس كلاهما مفهرسان حتى \(n\).
لكل أولي \(q\le n\)، حساب \(e_q\) يكلف \(O(\log_q n)\). تحليل \(q-1\) سريع بفضل الغربال، واختزال \(q-1\) إلى الرتبة الصحيحة modulo \(q\) لا يحتاج إلا إلى عدد صغير من اختبارات الرفع المعياري. ثم تضيف مرحلة الرفع بعض الاختبارات الأخرى إلى أن يفشل التطابق لأول مرة.
لذلك يمكن النظر إلى الخوارزمية على أنها تمهيد خطي ثم مقدار محدود من الحسابات لكل أولي. والنقطة الحاسمة أنها لا تبني \(n!\) صراحة ولا تبحث عن الرتبة بواسطة تجربة الأسس تباعًا.