Let \(\rho(n)\) be the number of residues \(x \pmod n\) satisfying
$$x^3\equiv1\pmod n.$$
The problem asks for the sum of all integers \(n\le10^{11}\) having exactly \(242\) nontrivial cube roots of unity. Since the trivial root \(x=1\) is always present, this is the same as asking for
$$\rho(n)=243=3^5.$$
The whole method starts from \(\rho(p^a)\).
For a prime \(p\neq3\), the unit group modulo \(p^a\) has order
$$\varphi(p^a)=p^{a-1}(p-1).$$
The equation \(u^3=1\) in a cyclic group has exactly \(\gcd(3,\varphi(p^a))\) solutions. Therefore:
1. if \(p\equiv2\pmod3\), then \(\gcd(3,\varphi(p^a))=1\), so \(\rho(p^a)=1\),
2. if \(p\equiv1\pmod3\), then \(\gcd(3,\varphi(p^a))=3\), so \(\rho(p^a)=3\).
The prime \(p=3\) is special. The code uses the standard fact
$$\rho(3)=1,\qquad \rho(3^a)=3\quad(a\ge2).$$
For example, modulo \(9\), the three roots are \(1,4,7\).
By the Chinese Remainder Theorem, \(\rho(n)\) is multiplicative across coprime factors. So if
$$n=\prod p_i^{a_i},$$
then
$$\rho(n)=\prod \rho(p_i^{a_i}).$$
That means the only factors that matter are:
1. distinct primes \(p\equiv1\pmod3\), each contributing one factor \(3\), regardless of exponent,
2. the prime \(3\), but only if its exponent is at least \(2\), contributing one factor \(3\).
The code encodes this with
$$\rho(n)=3^{s(n)},\qquad s(n)=\omega_1(n)+\mathbf 1_{v_3(n)\ge2},$$
where \(\omega_1(n)\) counts distinct prime divisors congruent to \(1\pmod3\).
Because \(243=3^5\), we need
$$s(n)=5.$$
This splits the search into two disjoint cases:
1. Case A: exactly five distinct primes \(p\equiv1\pmod3\), and \(v_3(n)<2\),
2. Case B: exactly four such primes, and \(v_3(n)\ge2\).
Those are the only possibilities, because every special contributor adds exactly one factor \(3\) to \(\rho(n)\).
Once the special contributors have been fixed, the rest of \(n\) must not create any new factor \(3\) in \(\rho(n)\).
So the remaining cofactor may contain only primes \(q\equiv2\pmod3\), because such primes contribute \(\rho(q^a)=1\).
There is one extra detail:
1. in Case A, a single factor \(3\) is allowed, since \(v_3(n)=1\) still contributes nothing extra,
2. in Case B, no additional factor \(3\) may appear in the cofactor, because the \(3^a\) contribution is already handled explicitly by taking \(a\ge2\).
A prime \(p\equiv1\pmod3\) contributes the same factor \(3\) to \(\rho(n)\) no matter whether it appears as \(p\), \(p^2\), or \(p^{17}\). Therefore the DFS must enumerate prime powers, not merely distinct primes.
The same phenomenon occurs for \(3\): once the exponent reaches \(2\), every larger power \(3^a\) still contributes only one factor \(3\) to \(\rho(n)\).
This is exactly why the recursion loops over
$$p,\;p^2,\;p^3,\dots$$
as long as the global product remains within the limit.
The code precomputes the function
$$F(M)=\sum_{\substack{m\le M\\ p\mid m\Rightarrow p\equiv2\pmod3}} m,$$
the sum of all integers up to \(M\) whose prime factors are all \(2\pmod3\).
This is stored as a prefix table prefix_allowed_sum_.
Then:
1. in Case B, the terminal contribution is just \(F(M)\),
2. in Case A, the cofactor may also include one extra factor \(3\), so the code uses
$$F(M)+3F(\lfloor M/3\rfloor).$$
That makes each leaf contribution \(O(1)\).
The search explores only primes \(p\equiv1\pmod3\). To avoid useless branches, the code precomputes min_prod_[r][i], the smallest possible product of \(r\) future special primes starting from index \(i\).
If even that minimal remaining product already exceeds the limit, the branch is abandoned immediately. This pruning is the reason the search is practical up to \(10^{11}\).
A number like
$$n=7\cdot13\cdot19\cdot31\cdot37$$
has exactly five special \(1\pmod3\) primes and no \(3^2\), so \(\rho(n)=3^5=243\) and it belongs to Case A.
A number like
$$n=9\cdot7\cdot13\cdot19\cdot31$$
has four special \(1\pmod3\) primes plus \(v_3(n)\ge2\), so again \(\rho(n)=3^5=243\); this is Case B.
In contrast, multiplying either example by a new prime such as \(43\equiv1\pmod3\) would push the root count to \(3^6\), which is too large.
The program checks three things before solving the full problem:
1. it verifies that modulo \(91\) there are exactly \(9\) cube roots of unity, so the nontrivial count is \(8\),
2. for every \(n\le2000\), it compares the formula-based root count against a brute-force count of solutions to \(x^3\equiv1\pmod n\),
3. up to \(5{,}000{,}000\), it compares the fast summation algorithm with a brute-force sum over all \(n\) having \(s(n)=5\).
These checkpoints validate both the arithmetic formula and the large-scale enumeration strategy.
special_factor_count computes \(s(n)\), the exponent of \(3\) in \(\rho(n)\).
build_special_primes generates all primes \(p\equiv1\pmod3\) that could possibly appear in a valid solution under the \(10^{11}\) limit.
build_cofactor_prefix precomputes the prefix sums for cofactors made only of primes \(2\pmod3\).
solve_case_without_9 handles Case A, and solve_case_with_9 handles Case B.
Each case uses DFS over special prime powers and aggregates whole blocks of remaining cofactors in constant time via the prefix table.
The algorithm is dominated by the number of reachable DFS nodes after pruning. That search space is vastly smaller than the naive set of all integers up to \(10^{11}\).
Terminal aggregation is \(O(1)\) because the cofactor sums are precomputed. So, in practice, the runtime is determined almost entirely by the number of viable special-factor branches.
Es sei \(\rho(n)\) die Anzahl der Lösungen von
$$x^3\equiv1\pmod n.$$
Gesucht ist die Summe aller \(n\le10^{11}\) mit genau \(242\) nichttrivialen Lösungen. Da \(x=1\) immer eine Lösung ist, entspricht das
$$\rho(n)=243=3^5.$$
Für \(p\neq3\) hat die Einheitengruppe modulo \(p^a\) die Ordnung \(\varphi(p^a)=p^{a-1}(p-1)\). Daher besitzt \(u^3=1\) genau \(\gcd(3,\varphi(p^a))\) Lösungen. Also:
1. bei \(p\equiv2\pmod3\) gilt \(\rho(p^a)=1\),
2. bei \(p\equiv1\pmod3\) gilt \(\rho(p^a)=3\).
Für \(p=3\) verwendet der Code den Sonderfall
$$\rho(3)=1,\qquad \rho(3^a)=3\;(a\ge2).$$
Wegen der Multiplikativität über teilerfremde Faktoren gilt
$$\rho(n)=3^{s(n)},\qquad s(n)=\omega_1(n)+\mathbf 1_{v_3(n)\ge2},$$
wobei \(\omega_1(n)\) die verschiedenen Primteiler \(p\equiv1\pmod3\) zählt.
Benötigt wird
$$s(n)=5.$$
Daraus ergeben sich genau zwei disjunkte Fälle:
1. Fall A: fünf verschiedene Primfaktoren \(1\bmod3\) und kein Beitrag von \(3^2\),
2. Fall B: vier solche Primfaktoren und zusätzlich \(v_3(n)\ge2\).
Der restliche Kofaktor darf keine weitere \(3\)-Potenz in \(\rho(n)\) erzeugen. Deshalb darf er nur Primfaktoren \(q\equiv2\pmod3\) enthalten.
Im Fall A ist zusätzlich genau ein einzelner Faktor \(3\) erlaubt, weil \(v_3(n)=1\) noch keinen Extra-Beitrag liefert. Im Fall B ist das nicht erlaubt, da der Beitrag von \(3^a\) mit \(a\ge2\) bereits separat berücksichtigt wird.
Ein Primfaktor \(p\equiv1\pmod3\) liefert denselben Beitrag \(3\), egal ob er mit Exponent \(1\) oder \(17\) vorkommt. Deshalb muss die DFS Primzahlpotenzen \(p,p^2,p^3,\dots\) durchsuchen und nicht nur verschiedene Primzahlen.
Dasselbe gilt für \(3\): ab Exponent \(2\) bleibt der Beitrag konstant gleich \(3\).
Der Code berechnet
$$F(M)=\sum_{\substack{m\le M\\ p\mid m\Rightarrow p\equiv2\pmod3}} m.$$
Dann ist die Kofaktor-Summe
1. im Fall B einfach \(F(M)\),
2. im Fall A gleich \(F(M)+3F(\lfloor M/3\rfloor)\).
Damit kostet ein Blatt der DFS nur \(O(1)\).
Die Suche läuft nur über Primzahlen \(p\equiv1\pmod3\). Mit min_prod_ hält der Code für jede Resttiefe das kleinstmögliche noch erreichbare Produkt fest. Wenn selbst dieses Minimum schon die Schranke verletzt, wird der Ast sofort abgeschnitten.
Die Zahl
$$n=7\cdot13\cdot19\cdot31\cdot37$$
liegt in Fall A, denn sie besitzt genau fünf spezielle Primfaktoren und kein \(3^2\). Also \(\rho(n)=3^5\).
Dagegen liegt
$$n=9\cdot7\cdot13\cdot19\cdot31$$
in Fall B: vier spezielle Primfaktoren plus \(v_3(n)\ge2\), also ebenfalls \(\rho(n)=3^5\).
Der Code prüft:
1. modulo \(91\) gibt es genau \(9\) Kubikwurzeln von \(1\),
2. für alle \(n\le2000\) stimmt die Formel mit einem Brute-Force-Zähler überein,
3. bis \(5{,}000{,}000\) stimmt die schnelle Summation mit einer vollständigen Brute-Force-Summe überein.
special_factor_count berechnet \(s(n)\). build_special_primes erzeugt alle relevanten Primzahlen \(1\bmod3\). build_cofactor_prefix baut die Präfixsummen für zulässige Kofaktoren auf.
solve_case_without_9 behandelt Fall A, solve_case_with_9 Fall B. Beide verwenden DFS über Primzahlpotenzen und fassen die restlichen Kofaktoren per Präfixsummen in \(O(1)\) zusammen.
Die praktische Laufzeit wird von der Zahl der nach dem Pruning verbleibenden DFS-Knoten bestimmt. Diese ist viel kleiner als ein naiver Durchlauf bis \(10^{11}\). An jedem Endknoten erfolgt die Aggregation konstant schnell.
\(\rho(n)\),
$$x^3\equiv1\pmod n$$
denkleminin çözüm sayısı olsun. Problem, \(n\le10^{11}\) için trivial olmayan çözüm sayısı 242 olan, yani toplam çözüm sayısı
$$\rho(n)=243=3^5$$
olan tüm sayıların toplamını ister.
\(p\neq3\) için mod \(p^a\) birim grubu \(\varphi(p^a)=p^{a-1}(p-1)\) mertebelidir. Çevrimsel bir grupta \(u^3=1\) denkleminin çözüm sayısı \(\gcd(3,\varphi(p^a))\) olur. Bu yüzden:
1. \(p\equiv2\pmod3\) ise \(\rho(p^a)=1\),
2. \(p\equiv1\pmod3\) ise \(\rho(p^a)=3\).
\(p=3\) özel durumunda ise
$$\rho(3)=1,\qquad \rho(3^a)=3\;(a\ge2)$$
kullanılır. Örneğin mod \(9\)'daki üç kök \(1,4,7\)'dir.
CRT nedeniyle kök sayısı, aralarında asal çarpanlar üzerinde çarpımsaldır. Bu yüzden
$$\rho(n)=3^{s(n)},\qquad s(n)=\omega_1(n)+\mathbf 1_{v_3(n)\ge2}$$
şeklinde yazılabilir. Burada \(\omega_1(n)\), \(1\pmod3\) olan farklı asal bölen sayısıdır.
Gereken şey
$$s(n)=5$$
olduğundan tam iki ayrık durum vardır:
1. Durum A: tam 5 farklı \(p\equiv1\pmod3\) asal katkısı ve \(v_3(n)<2\),
2. Durum B: tam 4 böyle katkı ve ayrıca \(v_3(n)\ge2\).
Özel katkılar seçildikten sonra geri kalan çarpanların \(\rho(n)\)'ye yeni bir 3 katsayısı eklememesi gerekir. Bu yüzden kofaktör yalnızca \(q\equiv2\pmod3\) olan asallardan oluşabilir.
Tek ayrıntı şudur:
1. Durum A'da tek bir \(3\) çarpanı serbesttir; çünkü \(v_3(n)=1\) henüz ekstra katkı üretmez,
2. Durum B'de bu serbest değildir; çünkü \(3^a\) katkısı zaten \(a\ge2\) olarak ayrı sayılmıştır.
\(p\equiv1\pmod3\) olan bir asal, üssü ne olursa olsun \(\rho(n)\)'ye yalnızca tek bir 3 çarpanı getirir. Bu nedenle DFS yalnızca “hangi asallar seçildi?” sorusunu değil, her biri için
$$p,\;p^2,\;p^3,\dots$$
şeklindeki asal kuvvet seçeneklerini de gezmek zorundadır. Aynı mantık \(3\) için de geçerlidir: üs \(2\)'ye ulaştıktan sonra daha büyük tüm üsler de aynı tek katkıyı verir.
Kod şu fonksiyonu önden hesaplar:
$$F(M)=\sum_{\substack{m\le M\\ p\mid m\Rightarrow p\equiv2\pmod3}} m.$$
Böylece yaprakta kalan kofaktör toplamı:
1. Durum B için doğrudan \(F(M)\),
2. Durum A için ise
$$F(M)+3F(\lfloor M/3\rfloor)$$
olur. Böylece her terminal dal \(O(1)\) zamanda toplanır.
Arama yalnızca \(p\equiv1\pmod3\) olan asallar üzerinde yapılır. min_prod_ tablosu, belirli bir indeksten başlayarak geriye kalan \(r\) özel asalın alabileceği en küçük çarpımı tutar. Eğer bu en küçük olası devam bile üst sınırı aşıyorsa dal anında kesilir.
Mesela
$$n=7\cdot13\cdot19\cdot31\cdot37$$
Durum A'ya girer; beş özel asal vardır ve \(3^2\) katkısı yoktur, dolayısıyla \(\rho(n)=3^5\).
Buna karşılık
$$n=9\cdot7\cdot13\cdot19\cdot31$$
Durum B örneğidir; dört özel asal ve \(v_3(n)\ge2\) birlikte yine \(\rho(n)=3^5\) verir.
Program tam çözüme geçmeden önce üç test yapar:
1. mod \(91\) için toplam kök sayısının \(9\) olduğunu doğrular,
2. \(n\le2000\) için formülle hesaplanan \(\rho(n)\) değerini brute-force ile karşılaştırır,
3. \(5{,}000{,}000\)'a kadar hızlı toplam algoritmasını brute-force toplam ile karşılaştırır.
special_factor_count, \(s(n)\) değerini hesaplar.
build_special_primes, sınır altında işe yarayabilecek tüm \(1\pmod3\) asallarını çıkarır.
build_cofactor_prefix, normal kofaktörler için prefix toplam tablosunu hazırlar.
solve_case_without_9 Durum A'yı, solve_case_with_9 ise Durum B'yi çözer. Her ikisi de özel asal kuvvetleri DFS ile gezer ve yaprakta prefix toplamları kullanır.
Pratik maliyeti belirleyen şey, budama sonrası kalan DFS düğümlerinin sayısıdır. Bu sayı, \(10^{11}\)'e kadar tüm sayıları tek tek taramaya kıyasla çok küçüktür. Yaprakta toplama \(O(1)\) olduğundan terminal maliyet ihmal edilebilir düzeydedir.
Sea \(\rho(n)\) el número de residuos \(x\pmod n\) tales que
$$x^3\equiv1\pmod n.$$
Se pide sumar todos los \(n\le10^{11}\) con exactamente \(242\) raíces no triviales. Como la raíz trivial \(x=1\) siempre existe, esto equivale a imponer
$$\rho(n)=243=3^5.$$
Para \(p\neq3\), el grupo de unidades módulo \(p^a\) tiene tamaño \(\varphi(p^a)=p^{a-1}(p-1)\). En un grupo cíclico, la ecuación \(u^3=1\) tiene \(\gcd(3,\varphi(p^a))\) soluciones. Por tanto:
1. si \(p\equiv2\pmod3\), entonces \(\rho(p^a)=1\),
2. si \(p\equiv1\pmod3\), entonces \(\rho(p^a)=3\).
Para \(p=3\), el código usa
$$\rho(3)=1,\qquad \rho(3^a)=3\;(a\ge2).$$
Por CRT, \(\rho(n)\) es multiplicativa en factores coprimos. Así,
$$\rho(n)=3^{s(n)},\qquad s(n)=\omega_1(n)+\mathbf 1_{v_3(n)\ge2},$$
donde \(\omega_1(n)\) cuenta los primos distintos congruentes con \(1\pmod3\).
Necesitamos
$$s(n)=5.$$
Eso produce exactamente dos casos disjuntos:
1. Caso A: cinco primos distintos \(1\bmod3\) y sin contribución de \(3^2\),
2. Caso B: cuatro tales primos y además \(v_3(n)\ge2\).
Una vez fijados los factores especiales, el resto de \(n\) no debe añadir otra potencia de \(3\) a \(\rho(n)\). Por eso el cofactor solo puede usar primos \(q\equiv2\pmod3\).
Hay un matiz:
1. en el Caso A se permite un único factor \(3\), porque \(v_3(n)=1\) aún no aporta nada extra,
2. en el Caso B no se permite ese factor adicional, porque la contribución de \(3^a\) con \(a\ge2\) ya está incorporada.
Un primo \(p\equiv1\pmod3\) aporta el mismo factor \(3\) a \(\rho(n)\) tanto si aparece como \(p\) como si aparece como \(p^{20}\). Por eso la DFS debe recorrer
$$p,\;p^2,\;p^3,\dots$$
y no solo la presencia o ausencia del primo.
El programa precalcula
$$F(M)=\sum_{\substack{m\le M\\ p\mid m\Rightarrow p\equiv2\pmod3}} m.$$
Entonces:
1. en el Caso B, la contribución terminal es \(F(M)\),
2. en el Caso A, como puede haber un único factor \(3\), se usa
$$F(M)+3F(\lfloor M/3\rfloor).$$
La búsqueda recorre solo los primos \(1\pmod3\). La tabla min_prod_ guarda el menor producto posible de los factores especiales que faltan; si ni siquiera ese mínimo cabe bajo el límite, la rama se poda inmediatamente.
El número
$$n=7\cdot13\cdot19\cdot31\cdot37$$
pertenece al Caso A, porque tiene cinco primos especiales y no contiene \(3^2\). En consecuencia, \(\rho(n)=3^5\).
En cambio,
$$n=9\cdot7\cdot13\cdot19\cdot31$$
pertenece al Caso B: cuatro primos especiales más \(v_3(n)\ge2\), y de nuevo \(\rho(n)=3^5\).
El programa comprueba tres cosas:
1. que módulo \(91\) hay exactamente \(9\) raíces cúbicas de la unidad,
2. que para todo \(n\le2000\) la fórmula coincide con un conteo brute-force,
3. que hasta \(5{,}000{,}000\) la suma rápida coincide con una suma brute-force sobre \(s(n)=5\).
special_factor_count calcula \(s(n)\).
build_special_primes genera los primos \(1\pmod3\) relevantes bajo el límite.
build_cofactor_prefix construye la tabla de prefijos para cofatores ordinarios.
solve_case_without_9 resuelve el Caso A y solve_case_with_9 el Caso B. Ambos recorren potencias primas especiales por DFS y agregan el resto en tiempo constante.
El coste práctico viene dado por el número de nodos DFS que sobreviven a la poda. Ese número es muy inferior a un barrido ingenuo hasta \(10^{11}\). En cada hoja, la agregación es \(O(1)\) gracias a los prefijos precomputados.
记 \(\rho(n)\) 为满足
$$x^3\equiv1\pmod n$$
的剩余类个数。题目要求把所有 \(n\le10^{11}\) 且恰有 \(242\) 个非平凡解的整数加起来。由于平凡根 \(x=1\) 总是存在，这就等价于
$$\rho(n)=243=3^5.$$
对 \(p\neq3\)，模 \(p^a\) 的单位群大小为 \(\varphi(p^a)=p^{a-1}(p-1)\)。在循环群中，方程 \(u^3=1\) 的解数等于 \(\gcd(3,\varphi(p^a))\)。因此：
1. 若 \(p\equiv2\pmod3\)，则 \(\rho(p^a)=1\)，
2. 若 \(p\equiv1\pmod3\)，则 \(\rho(p^a)=3\)。
对 \(p=3\)，代码使用的事实是
$$\rho(3)=1,\qquad \rho(3^a)=3\;(a\ge2).$$
由中国剩余定理可知，\(\rho(n)\) 在互素因子上是乘法性的，因此
$$\rho(n)=3^{s(n)},\qquad s(n)=\omega_1(n)+\mathbf 1_{v_3(n)\ge2},$$
其中 \(\omega_1(n)\) 表示 \(n\) 中不同的 \(1\pmod3\) 素因子个数。
我们需要
$$s(n)=5.$$
因此只有两个互不重叠的情况：
1. A 类：恰有 5 个不同的 \(1\bmod3\) 素因子，且 \(v_3(n)<2\)，
2. B 类：恰有 4 个这样的素因子，并且 \(v_3(n)\ge2\)。
一旦“特殊”贡献已经选定，剩余因子就不能再给 \(\rho(n)\) 额外乘上一个 \(3\)。因此剩余 cofactor 只能含有 \(q\equiv2\pmod3\) 的素因子。
唯一的细节是：
1. 在 A 类中，可以再附带一个单独的因子 \(3\)，因为 \(v_3(n)=1\) 还不会带来额外贡献，
2. 在 B 类中，不允许这样做，因为 \(3^a\)（\(a\ge2\)）的贡献已经单独计入了。
一个 \(p\equiv1\pmod3\) 的素数，无论出现为 \(p\)、\(p^2\) 还是 \(p^{50}\)，对 \(\rho(n)\) 的贡献都只是一个因子 \(3\)。所以 DFS 不能只枚举“选不选这个素数”，而必须枚举
$$p,\;p^2,\;p^3,\dots$$
这些可能的幂次。
程序预先构造
$$F(M)=\sum_{\substack{m\le M\\ p\mid m\Rightarrow p\equiv2\pmod3}} m.$$
于是：
1. 在 B 类里，终端贡献就是 \(F(M)\)，
2. 在 A 类里，因为允许额外一个因子 \(3\)，所以使用
$$F(M)+3F(\lfloor M/3\rfloor).$$
这样每个 DFS 叶子都能在 \(O(1)\) 时间内完成汇总。
搜索只在 \(p\equiv1\pmod3\) 的素数上进行。表 min_prod_ 记录了从某个位置开始、剩余若干个特殊素数所能达到的最小乘积。若连这个最小乘积都超出上界，该分支就立刻剪掉。
例如
$$n=7\cdot13\cdot19\cdot31\cdot37$$
属于 A 类，因为它正好有 5 个特殊素因子且没有 \(3^2\)，因此 \(\rho(n)=3^5\)。
而
$$n=9\cdot7\cdot13\cdot19\cdot31$$
属于 B 类：4 个特殊素因子加上 \(v_3(n)\ge2\)，同样得到 \(\rho(n)=3^5\)。
程序在正式求解前会验证三件事：
1. 模 \(91\) 的三次单位根总数确实是 \(9\)，
2. 对所有 \(n\le2000\)，公式计数与 brute-force 计数一致，
3. 在 \(5{,}000{,}000\) 范围内，快速求和与 brute-force 求和一致。
special_factor_count 计算 \(s(n)\)。
build_special_primes 构造所有可能参与答案的 \(1\pmod3\) 素数。
build_cofactor_prefix 预处理普通 cofactor 的前缀和表。
solve_case_without_9 负责 A 类，solve_case_with_9 负责 B 类。两者都用 DFS 枚举特殊素数幂，并在叶子节点用前缀表常数时间汇总剩余部分。
实际复杂度主要由剪枝后仍然保留下来的 DFS 节点数决定，它远小于把 \(1\) 到 \(10^{11}\) 全部枚举一遍。由于叶子汇总是 \(O(1)\)，终端开销很小。
Пусть \(\rho(n)\) — число решений сравнения
$$x^3\equiv1\pmod n.$$
Нужно просуммировать все \(n\le10^{11}\), у которых ровно \(242\) нетривиальных решения. Так как тривиальный корень \(x=1\) существует всегда, это равносильно условию
$$\rho(n)=243=3^5.$$
Для \(p\neq3\) группа единиц modulo \(p^a\) имеет порядок \(\varphi(p^a)=p^{a-1}(p-1)\). В циклической группе уравнение \(u^3=1\) имеет \(\gcd(3,\varphi(p^a))\) решений. Следовательно:
1. при \(p\equiv2\pmod3\) имеем \(\rho(p^a)=1\),
2. при \(p\equiv1\pmod3\) имеем \(\rho(p^a)=3\).
Для числа \(3\) используется отдельный факт:
$$\rho(3)=1,\qquad \rho(3^a)=3\;(a\ge2).$$
По КТО функция \(\rho(n)\) мультипликативна по взаимно простым множителям, поэтому
$$\rho(n)=3^{s(n)},\qquad s(n)=\omega_1(n)+\mathbf 1_{v_3(n)\ge2},$$
где \(\omega_1(n)\) считает различные простые делители \(p\equiv1\pmod3\).
Нужно, чтобы
$$s(n)=5.$$
Значит, возможны ровно два случая:
1. Случай A: пять различных специальных простых \(1\bmod3\) и отсутствие вклада от \(3^2\),
2. Случай B: четыре таких простых и дополнительно \(v_3(n)\ge2\).
После выбора специальных множителей оставшаяся часть числа не должна добавлять ещё один множитель \(3\) в \(\rho(n)\). Поэтому кофактор может состоять только из простых \(q\equiv2\pmod3\).
Есть одно уточнение:
1. в случае A допустим ещё один одиночный множитель \(3\), поскольку \(v_3(n)=1\) не даёт дополнительного вклада,
2. в случае B это запрещено, потому что вклад \(3^a\) при \(a\ge2\) уже учтён отдельно.
Простой \(p\equiv1\pmod3\) даёт один и тот же вклад \(3\) в \(\rho(n)\) независимо от того, входит ли он как \(p\), \(p^2\) или \(p^{20}\). Поэтому DFS обязана перечислять степени
$$p,\;p^2,\;p^3,\dots$$
а не только сам факт наличия простого.
Код предвычисляет функцию
$$F(M)=\sum_{\substack{m\le M\\ p\mid m\Rightarrow p\equiv2\pmod3}} m.$$
Тогда вклад оставшегося кофактора равен:
1. в случае B — просто \(F(M)\),
2. в случае A —
$$F(M)+3F(\lfloor M/3\rfloor).$$
Поиск идёт только по простым \(p\equiv1\pmod3\). Таблица min_prod_ хранит минимально возможное произведение ещё не выбранных специальных множителей. Если даже оно уже превышает предел, ветвь отсекается сразу.
Число
$$n=7\cdot13\cdot19\cdot31\cdot37$$
попадает в случай A: здесь ровно пять специальных простых и нет \(3^2\), значит \(\rho(n)=3^5\).
Число
$$n=9\cdot7\cdot13\cdot19\cdot31$$
попадает в случай B: четыре специальных простых плюс \(v_3(n)\ge2\), и снова \(\rho(n)=3^5\).
Программа подтверждает:
1. что по модулю \(91\) существует ровно \(9\) кубических корней единицы,
2. что для всех \(n\le2000\) формула совпадает с brute-force подсчётом,
3. что до \(5{,}000{,}000\) быстрая сумма совпадает с полной brute-force суммой.
special_factor_count вычисляет \(s(n)\). build_special_primes строит список нужных простых \(1\pmod3\). build_cofactor_prefix формирует префиксные суммы для обычных кофакторов.
solve_case_without_9 реализует случай A, а solve_case_with_9 — случай B. В обоих случаях DFS перебирает специальные простые степени, а оставшаяся часть суммируется за \(O(1)\) с помощью префиксной таблицы.
Практическое время работы определяется количеством DFS-узлов, оставшихся после отсечений. Это число намного меньше полного перебора до \(10^{11}\). На листе вклад считается за константное время.
لتكن \(\rho(n)\) عدد البواقي التي تحقق
$$x^3\equiv1\pmod n.$$
المطلوب هو جمع كل \(n\le10^{11}\) التي لها \(242\) جذرًا غير بديهي. وبما أن الجذر البديهي \(x=1\) موجود دائمًا، فهذا يكافئ الشرط
$$\rho(n)=243=3^5.$$
إذا كان \(p\neq3\)، فإن زمرة الوحدات modulo \(p^a\) رتبتها \(\varphi(p^a)=p^{a-1}(p-1)\). وفي زمرة دورية يكون عدد حلول \(u^3=1\) مساويًا لـ \(\gcd(3,\varphi(p^a))\). لذلك:
1. إذا كان \(p\equiv2\pmod3\) فلدينا \(\rho(p^a)=1\)،
2. وإذا كان \(p\equiv1\pmod3\) فلدينا \(\rho(p^a)=3\).
أما عند \(p=3\) فيستخدم الكود الحقيقة
$$\rho(3)=1,\qquad \rho(3^a)=3\;(a\ge2).$$
بفضل نظرية البواقي الصينية تكون \(\rho(n)\) دالة ضربية على العوامل المتباينة أوليًا، ومن ثم
$$\rho(n)=3^{s(n)},\qquad s(n)=\omega_1(n)+\mathbf 1_{v_3(n)\ge2},$$
حيث \(\omega_1(n)\) تعدّ العوامل الأولية المختلفة التي تحقق \(1\pmod3\).
نحتاج إلى
$$s(n)=5.$$
وهذا يعطي حالتين منفصلتين تمامًا:
1. الحالة A: خمسة أوليات مختلفة من النوع \(1\bmod3\) ومن دون مساهمة من \(3^2\)،
2. الحالة B: أربعة أوليات من هذا النوع مع \(v_3(n)\ge2\).
بعد تثبيت العوامل الخاصة، يجب ألا يضيف باقي العدد عاملًا جديدًا من \(3\) إلى \(\rho(n)\). ولذلك لا يجوز أن يحتوي المرافق إلا على أوليات \(q\equiv2\pmod3\).
لكن هناك تفصيلًا واحدًا:
1. في الحالة A يُسمح بعامل \(3\) واحد فقط، لأن \(v_3(n)=1\) لا يضيف مساهمة جديدة،
2. في الحالة B لا يُسمح بذلك، لأن مساهمة \(3^a\) مع \(a\ge2\) قد حُسبت أصلًا على نحو مستقل.
الأولي \(p\equiv1\pmod3\) يعطي العامل نفسه \(3\) في \(\rho(n)\) سواء ظهر على صورة \(p\) أو \(p^2\) أو \(p^{20}\). لهذا السبب لا يكفي تعداد الأوليات المختلفة فقط، بل يجب تعداد القوى
$$p,\;p^2,\;p^3,\dots$$
ما دامت تحت الحد.
يبني البرنامج مسبقًا الدالة
$$F(M)=\sum_{\substack{m\le M\\ p\mid m\Rightarrow p\equiv2\pmod3}} m.$$
وعندها يكون مجموع المرافق:
1. في الحالة B هو \(F(M)\)،
2. وفي الحالة A هو
$$F(M)+3F(\lfloor M/3\rfloor).$$
وبذلك تصبح مساهمة كل ورقة في DFS ذات كلفة ثابتة.
البحث يسير فقط على الأوليات \(1\pmod3\). ويخزن الجدول min_prod_ أصغر جداء ممكن لما تبقى من العوامل الخاصة. فإذا كان هذا الحد الأدنى نفسه يتجاوز السقف، تُقطع الشجرة مباشرة.
العدد
$$n=7\cdot13\cdot19\cdot31\cdot37$$
ينتمي إلى الحالة A، لأن فيه خمسة أوليات خاصة ولا يحتوي \(3^2\)، ولذلك \(\rho(n)=3^5\).
أما
$$n=9\cdot7\cdot13\cdot19\cdot31$$
فينتمي إلى الحالة B: أربعة أوليات خاصة مع \(v_3(n)\ge2\)، ومن ثم أيضًا \(\rho(n)=3^5\).
يتحقق البرنامج من ثلاث نقاط:
1. أن عدد الجذور modulo \(91\) هو \(9\)،
2. أن الصيغة توافق العدّ brute-force لكل \(n\le2000\)،
3. أن المجموع السريع حتى \(5{,}000{,}000\) يوافق المجموع brute-force.
special_factor_count يحسب \(s(n)\). وتبني الدالة build_special_primes جميع الأوليات \(1\pmod3\) ذات الصلة. أما build_cofactor_prefix فتبني الجداول البادئة للمرافق العادي.
وتعالج solve_case_without_9 الحالة A، بينما تعالج solve_case_with_9 الحالة B. وفي كلتا الحالتين تُعدَّد القوى الخاصة عبر DFS ثم يُجمع باقي المرافق في \(O(1)\) عند الورقة.
الزمن العملي تحدده عقد DFS التي تبقى بعد التقليم، وهذا أصغر بكثير من التعداد الخام حتى \(10^{11}\). أما عند النهايات فالتجميع ثابت الزمن بفضل الجداول البادئة.