For fixed positive integers \(a\) and \(b\), consider the two sequences
$$u_n=n^3+b,\qquad v_n=(n+a)^3+b.$$
Define
$$M(a,b)=\max_{n\ge 0}\gcd(u_n,v_n).$$
Then \(G(a,b)\) is the smallest nonnegative integer \(n\) for which \(\gcd(u_n,v_n)=M(a,b)\). The final target is
$$H(m,n)=\sum_{a=1}^{m}\sum_{b=1}^{n}G(a,b).$$
The C++, Python, and Java implementations do not search \(n\) directly. Instead, they determine the largest prime-power contribution that can occur in the gcd, then reconstruct the smallest index that realizes all of those local maxima simultaneously.
For any prime power \(p^k\), the statement \(p^k\mid \gcd(u_n,v_n)\) is equivalent to the pair of congruences
$$n^3+b\equiv 0\pmod{p^k},\qquad (n+a)^3+b\equiv 0\pmod{p^k}.$$
So the problem is local at each prime: we need to know for which primes and exponents the two cubics have a common residue class.
If two integer polynomials have a common root modulo a prime \(p\), then \(p\) must divide their resultant. For
$$f(x)=x^3+b,\qquad g(x)=(x+a)^3+b,$$
a direct Sylvester-determinant computation gives
$$\operatorname{Res}_x(f,g)=a^3(a^6+27b^2).$$
Therefore every prime that can appear in the maximal gcd must divide \(a^3(a^6+27b^2)\). This is why the implementation factors \(a^6+27b^2\) for each pair \((a,b)\) and then adds three times the prime exponents coming from \(a\).
Subtract the two congruences:
$$0\equiv (n+a)^3-n^3=a(3n^2+3an+a^2)\pmod{p^k}.$$
When \(p\nmid a\), this forces
$$3n^2+3an+a^2\equiv 0\pmod{p}.$$
For odd primes \(p>5\), we may complete the square:
$$4(3n^2+3an+a^2)=3(2n+a)^2+a^2,$$
hence
$$ (2n+a)^2\equiv -\frac{a^2}{3}\pmod{p}. $$
This reduces the base search modulo \(p\) to a modular square-root problem. The implementation computes the square root when possible, converts it into up to two candidate residues, and then verifies those candidates in the original cubic congruences. For small primes and degenerate cases with \(p\mid a\), it safely enumerates all residues modulo \(p\) instead of relying on the quadratic shortcut.
Suppose \(r\) is a simultaneous solution modulo \(p^t\). Any lift to the next power must have the form
$$n=r+u\,p^t,\qquad u\in\{0,1,\dots,p-1\}.$$
The implementation tests all \(p\) descendants and keeps only those that still satisfy both cubic congruences modulo \(p^{t+1}\). Repeating this determines the largest exponent \(k_p\) for which simultaneous roots still exist. If lifting fails at the next stage, then \(p^{k_p}\) is the largest power of \(p\) that can divide the gcd.
Let \(p^{e_p}\) be the exponent of \(p\) in the resultant, and let \(k_p\le e_p\) be the highest exponent actually reached by the lifting process. Then every value \(\gcd(u_n,v_n)\) has \(p\)-adic valuation at most \(k_p\), so
$$M(a,b)\le \prod_p p^{k_p}.$$
Conversely, choose one lifted residue class for each surviving prime. Different prime powers are coprime, so the Chinese remainder theorem merges them into a unique class modulo
$$Q(a,b)=\prod_p p^{k_p}.$$
Every \(n\) in that class makes both sequences divisible by \(p^{k_p}\) for every surviving prime, so
$$\boxed{M(a,b)=Q(a,b).}$$
Thus \(G(a,b)\) is simply the smallest nonnegative integer in the CRT-merged residue classes.
For \((a,b)=(1,1)\), the resultant is
$$1^3(1^6+27\cdot 1^2)=28=2^2\cdot 7.$$
There is no simultaneous root modulo \(2\), while modulo \(7\) the unique solution is \(n\equiv 5\pmod{7}\). Hence the maximal gcd is \(7\), and the first index that attains it is
$$G(1,1)=5.$$
A lifting example is \((a,b)=(1,5)\). Here
$$1^3(1^6+27\cdot 5^2)=676=2^2\cdot 13^2.$$
The only surviving prime is \(13\). The residue \(n\equiv 5\pmod{13}\) lifts further to \(n\equiv 161\pmod{169}\), so the maximal gcd is \(13^2=169\) and
$$G(1,5)=161.$$
The implementations first build a reusable prime table, precompute the values \(a^6\), \(27b^2\), and the prime factorization of each allowed \(a\). For each pair \((a,b)\), they factor \(a^6+27b^2\), add the prime exponents contributed by \(a^3\), and process each candidate prime separately.
For every prime block, the implementation finds the simultaneous residues modulo \(p\), lifts them as far as possible, and stores the highest modulus that still has solutions. The prime blocks are then ordered by the number of local residues, which keeps the CRT merge smaller in practice. Every merged residue achieves the maximal gcd, and the smallest merged residue is returned as \(G(a,b)\).
Finally, the values are summed over the full \((a,b)\)-grid. Since every pair is independent, the C++, Python, and Java implementations parallelize this outer accumulation. Their published checkpoints are
$$G(1,1)=5,\qquad H(5,5)=128878,\qquad H(10,10)=32936544.$$
For one pair \((a,b)\), the first cost is factoring \(a^6+27b^2\) with the precomputed prime list. Then each candidate prime needs a local search modulo \(p\), followed by at most one lifting stage for each additional exponent. If the surviving residue counts are \(r_1,r_2,\dots,r_s\), then the CRT phase examines \(r_1r_2\cdots r_s\) combinations in the worst case.
So the runtime is dominated by three ingredients: factoring the resultant part, lifting prime-power roots, and merging local residue classes. Over the full rectangle \(1\le a\le m\), \(1\le b\le n\), the total runtime is roughly linear in the number of parameter pairs, multiplied by the average local arithmetic cost. Memory usage is modest and is dominated by the temporary residue lists carried through lifting and CRT.
Für feste positive ganze Zahlen \(a\) und \(b\) betrachten wir die beiden Folgen
$$u_n=n^3+b,\qquad v_n=(n+a)^3+b.$$
Definiere
$$M(a,b)=\max_{n\ge 0}\gcd(u_n,v_n).$$
Dann ist \(G(a,b)\) das kleinste nichtnegative \(n\), für das \(\gcd(u_n,v_n)=M(a,b)\) gilt. Gesucht ist schließlich
$$H(m,n)=\sum_{a=1}^{m}\sum_{b=1}^{n}G(a,b).$$
Die Implementierungen durchsuchen also nicht alle \(n\) direkt, sondern bestimmen zuerst die größte an jeder Primzahl erreichbare Primzahlpotenz im ggT und rekonstruieren danach per chinesischem Restsatz das kleinste \(n\), das all diese lokalen Maxima gleichzeitig realisiert.
Für eine Primzahlpotenz \(p^k\) ist die Aussage \(p^k\mid \gcd(u_n,v_n)\) äquivalent zu
$$n^3+b\equiv 0\pmod{p^k},\qquad (n+a)^3+b\equiv 0\pmod{p^k}.$$
Damit zerfällt das Problem in lokale Fragen: Für welche Primzahlen und Exponenten besitzen die beiden kubischen Ausdrücke dieselbe Restklasse als gemeinsame Nullstelle?
Haben zwei ganzzahlige Polynome modulo einer Primzahl \(p\) eine gemeinsame Nullstelle, dann teilt \(p\) ihre Resultante. Für
$$f(x)=x^3+b,\qquad g(x)=(x+a)^3+b$$
liefert die Sylvester-Determinante
$$\operatorname{Res}_x(f,g)=a^3(a^6+27b^2).$$
Also kann jede Primzahl, die im maximalen ggT vorkommt, nur aus \(a^3(a^6+27b^2)\) stammen. Genau deshalb faktorisieren die Implementierungen für jedes Paar \((a,b)\) den Ausdruck \(a^6+27b^2\) und addieren danach die dreifachen Exponenten aus \(a\).
Subtrahiert man die beiden Kongruenzen, verschwindet \(b\):
$$0\equiv (n+a)^3-n^3=a(3n^2+3an+a^2)\pmod{p^k}.$$
Falls \(p\nmid a\), folgt insbesondere
$$3n^2+3an+a^2\equiv 0\pmod{p}.$$
Für ungerade Primzahlen \(p>5\) kann man quadratisch ergänzen:
$$4(3n^2+3an+a^2)=3(2n+a)^2+a^2,$$
also
$$ (2n+a)^2\equiv -\frac{a^2}{3}\pmod{p}. $$
Die Basissuche modulo \(p\) reduziert sich damit auf eine modulare Quadratwurzel. Die Implementierung berechnet diese, erzeugt daraus höchstens zwei Kandidaten und prüft sie anschließend noch in den ursprünglichen kubischen Kongruenzen. Für kleine Primzahlen und entartete Fälle mit \(p\mid a\) wird stattdessen robust modulo \(p\) durchprobiert.
Ist \(r\) eine simultane Lösung modulo \(p^t\), dann hat jede Fortsetzung modulo \(p^{t+1}\) die Form
$$n=r+u\,p^t,\qquad u\in\{0,1,\dots,p-1\}.$$
Die Implementierung testet alle \(p\) Nachfolger und behält nur diejenigen, die beide kubischen Kongruenzen weiterhin modulo \(p^{t+1}\) erfüllen. So erhält man den größten Exponenten \(k_p\), für den noch gemeinsame Nullstellen existieren. Scheitert der Lift in der nächsten Stufe, dann ist \(p^{k_p}\) bereits die größte mögliche \(p\)-Potenz im ggT.
Sei \(p^{e_p}\) der Exponent von \(p\) in der Resultante und \(k_p\le e_p\) der tatsächlich erreichte Lift-Exponent. Dann besitzt jeder Wert \(\gcd(u_n,v_n)\) höchstens die \(p\)-adische Bewertung \(k_p\), also
$$M(a,b)\le \prod_p p^{k_p}.$$
Umgekehrt wählen wir für jede überlebende Primzahl eine geliftete Restklasse. Da verschiedene Primzahlpotenzen teilerfremd sind, kann der chinesische Restsatz sie zu genau einer Klasse modulo
$$Q(a,b)=\prod_p p^{k_p}$$
zusammenführen. Jedes \(n\) in dieser Klasse macht beide Folgen für jede überlebende Primzahl durch \(p^{k_p}\) teilbar. Deshalb gilt
$$\boxed{M(a,b)=Q(a,b).}$$
Somit ist \(G(a,b)\) einfach das kleinste nichtnegative Element der zusammengeführten CRT-Restklassen.
Für \((a,b)=(1,1)\) ist die Resultante
$$1^3(1^6+27\cdot 1^2)=28=2^2\cdot 7.$$
Modulo \(2\) gibt es keine simultane Lösung, modulo \(7\) dagegen die eindeutige Lösung \(n\equiv 5\pmod{7}\). Daher ist der maximale ggT gleich \(7\), und der erste Index mit diesem Wert ist
$$G(1,1)=5.$$
Ein Beispiel mit Heben ist \((a,b)=(1,5)\). Hier gilt
$$1^3(1^6+27\cdot 5^2)=676=2^2\cdot 13^2.$$
Nur die Primzahl \(13\) überlebt. Die Restklasse \(n\equiv 5\pmod{13}\) hebt sich weiter zu \(n\equiv 161\pmod{169}\), also ist der maximale ggT \(13^2=169\) und
$$G(1,5)=161.$$
Die C++-, Python- und Java-Implementierungen bauen zuerst eine wiederverwendbare Primzahlliste auf und berechnen anschließend die Werte \(a^6\), \(27b^2\) sowie die Primfaktorzerlegung jedes zulässigen \(a\) vor. Für jedes Paar \((a,b)\) wird dann \(a^6+27b^2\) faktorisiert, die Beiträge aus \(a^3\) werden ergänzt, und jede Kandidatenprimzahl wird separat behandelt.
Für jeden Primzahlblock sucht die Implementierung simultane Restklassen modulo \(p\), hebt sie so weit wie möglich an und speichert den größten Modul, für den noch Lösungen existieren. Danach werden die Blöcke nach der Anzahl lokaler Restklassen sortiert; das verkleinert in der Praxis das kartesische Produkt bei der CRT-Zusammenführung. Jede zusammengeführte Restklasse erreicht den maximalen ggT, und die kleinste davon ist \(G(a,b)\).
Zum Schluss werden alle Werte über das komplette \((a,b)\)-Gitter aufsummiert. Weil die Paare unabhängig sind, parallelisieren alle drei Implementierungen diesen äußeren Summationsschritt. Die Kontrollwerte lauten
$$G(1,1)=5,\qquad H(5,5)=128878,\qquad H(10,10)=32936544.$$
Für ein einzelnes Paar \((a,b)\) ist der erste Kostenfaktor die Faktorisierung von \(a^6+27b^2\) mit der vorab berechneten Primzahlliste. Danach benötigt jede Kandidatenprimzahl eine lokale Suche modulo \(p\) und für jeden weiteren Exponenten höchstens eine Lift-Stufe. Haben die überlebenden Blöcke die Restklassenzahlen \(r_1,r_2,\dots,r_s\), dann betrachtet die CRT-Phase im schlechtesten Fall \(r_1r_2\cdots r_s\) Kombinationen.
Die Laufzeit wird also von drei Teilen bestimmt: Faktorisierung, Heben auf Primzahlpotenzen und Zusammenführung lokaler Restklassen. Über das gesamte Rechteck \(1\le a\le m\), \(1\le b\le n\) wächst der Aufwand näherungsweise linear mit der Anzahl der Parameterpaare, multipliziert mit den mittleren lokalen Rechenkosteen. Der Speicherbedarf bleibt klein und wird im Wesentlichen von den temporären Restklassenlisten während Lift und CRT bestimmt.
Sabit pozitif \(a\) ve \(b\) için şu iki diziye bakıyoruz:
$$u_n=n^3+b,\qquad v_n=(n+a)^3+b.$$
Şunu tanımlayalım:
$$M(a,b)=\max_{n\ge 0}\gcd(u_n,v_n).$$
Ardından \(G(a,b)\), \(\gcd(u_n,v_n)=M(a,b)\) eşitliğini sağlayan en küçük negatif olmayan \(n\) olsun. Nihai hedef
$$H(m,n)=\sum_{a=1}^{m}\sum_{b=1}^{n}G(a,b)$$
toplamını bulmaktır. C++, Python ve Java uygulamaları \(n\) değerlerini doğrudan taramaz; bunun yerine, gcd içinde ortaya çıkabilecek en büyük asal kuvvetleri yerel olarak hesaplar ve sonra bu yerel maksimumları aynı anda sağlayan en küçük indeksi CRT ile yeniden kurar.
Bir asal kuvvet \(p^k\) için \(p^k\mid \gcd(u_n,v_n)\) olması şu iki kongruansla eşdeğerdir:
$$n^3+b\equiv 0\pmod{p^k},\qquad (n+a)^3+b\equiv 0\pmod{p^k}.$$
Dolayısıyla problem asal bazında ayrışır: hangi asallar ve hangi üsler için bu iki kübik ifade aynı kalanı ortak kök olarak paylaşabiliyor?
İki tam katsayılı polinom bir asal \(p\) modunda ortak köke sahipse, \(p\) bu iki polinomun resultant’ını bölmek zorundadır. Burada
$$f(x)=x^3+b,\qquad g(x)=(x+a)^3+b$$
için Sylvester determinantı
$$\operatorname{Res}_x(f,g)=a^3(a^6+27b^2)$$
sonucunu verir. Bu yüzden maksimum gcd içinde yer alabilecek her asal mutlaka \(a^3(a^6+27b^2)\) sayısını böler. Uygulamanın her \((a,b)\) çifti için \(a^6+27b^2\) değerini çarpanlara ayırıp daha sonra \(a\)’dan gelen üsleri üç kat eklemesinin nedeni tam olarak budur.
İki kongruansı birbirinden çıkaralım:
$$0\equiv (n+a)^3-n^3=a(3n^2+3an+a^2)\pmod{p^k}.$$
Eğer \(p\nmid a\) ise özellikle
$$3n^2+3an+a^2\equiv 0\pmod{p}$$
elde edilir. Tek asal \(p>5\) için kare tamamlayabiliriz:
$$4(3n^2+3an+a^2)=3(2n+a)^2+a^2,$$
dolayısıyla
$$ (2n+a)^2\equiv -\frac{a^2}{3}\pmod{p}. $$
Böylece mod \(p\) taban araması modüler karekök problemine indirgenir. Uygulama karekök varsa onu hesaplar, oradan en fazla iki aday kalıntı üretir ve sonra bu adayları asıl kübik kongruanslarda doğrular. Küçük asallar ve \(p\mid a\) gibi yoz durumlarda ise güvenli yöntem olarak tüm kalıntılar doğrudan denenir.
\(r\) kalıntısı mod \(p^t\) için eşzamanlı çözüm olsun. Bir üst kuvvete geçiş ancak
$$n=r+u\,p^t,\qquad u\in\{0,1,\dots,p-1\}$$
şeklinde olabilir. Uygulama bu \(p\) olası torunu test eder ve yalnızca her iki kübik kongruansı da mod \(p^{t+1}\) sağlayanları tutar. Bu işlem tekrar edilerek ortak kökün yaşayabildiği en büyük üs \(k_p\) bulunur. Bir sonraki aşamada lift başarısız olursa, gcd içindeki en büyük \(p\)-katkısı tam olarak \(p^{k_p}\) olur.
\(p^{e_p}\), resultant içindeki üs; \(k_p\le e_p\) ise lift sonunda gerçekten ulaşılabilen en büyük üs olsun. O halde her \(\gcd(u_n,v_n)\) değeri için \(p\)-adik değer en fazla \(k_p\) olabilir; yani
$$M(a,b)\le \prod_p p^{k_p}.$$
Tersi yönde, her yaşayan asal için bir lift edilmiş kalıntı sınıfı seçelim. Farklı asal kuvvetler aralarında asal olduğundan, Çin Kalan Teoremi bunları
$$Q(a,b)=\prod_p p^{k_p}$$
modülünde tek bir sınıfta birleştirir. Bu sınıftaki her \(n\), her yaşayan asal için her iki diziyi de \(p^{k_p}\) ile bölünebilir yapar. Böylece
$$\boxed{M(a,b)=Q(a,b).}$$
Sonuç olarak \(G(a,b)\), CRT ile birleşen kalıntı sınıflarının en küçük negatif olmayan elemanıdır.
\((a,b)=(1,1)\) için resultant
$$1^3(1^6+27\cdot 1^2)=28=2^2\cdot 7$$
olur. Mod \(2\) için eşzamanlı kök yoktur; mod \(7\) için tek çözüm \(n\equiv 5\pmod{7}\) gelir. Bu yüzden maksimum gcd değeri \(7\), bu değeri veren en küçük indis ise
$$G(1,1)=5$$
olur. Lift örneği olarak \((a,b)=(1,5)\) alınırsa
$$1^3(1^6+27\cdot 5^2)=676=2^2\cdot 13^2$$
elde edilir. Yalnızca \(13\) hayatta kalır. \(n\equiv 5\pmod{13}\) kalıntısı daha sonra \(n\equiv 161\pmod{169}\) biçimine lift olur; dolayısıyla maksimum gcd \(13^2=169\) ve
$$G(1,5)=161$$
çıkar.
Uygulamalar önce tekrar kullanılabilir bir asal tablosu kurar; sonra \(a^6\), \(27b^2\) ve izin verilen her \(a\) değerinin asal çarpanlarına ayrılışını önceden hesaplar. Her \((a,b)\) çifti için \(a^6+27b^2\) çarpanlara ayrılır, \(a^3\)’ten gelen üs katkıları eklenir ve her aday asal ayrı ayrı işlenir.
Her asal blok için önce mod \(p\) üzerindeki eşzamanlı kalıntılar bulunur, sonra bunlar mümkün olduğu kadar yukarı lift edilir ve hâlâ çözüm bulunan en büyük modül saklanır. Ardından bloklar, sahip oldukları yerel kalıntı sayısına göre sıralanır; bu, CRT birleşimindeki Kartezyen çarpımın pratik maliyetini düşürür. Birleştirilen her kalıntı maksimum gcd değerini verir; bunların en küçüğü \(G(a,b)\)’dir.
Son aşamada tüm değerler \((a,b)\) ızgarası üzerinde toplanır. Her çift bağımsız olduğundan C++, Python ve Java sürümleri bu dış toplamı paralel yürütür. Kontrol noktaları şunlardır:
$$G(1,1)=5,\qquad H(5,5)=128878,\qquad H(10,10)=32936544.$$
Tek bir \((a,b)\) çifti için ilk maliyet, önceden hesaplanmış asal listesiyle \(a^6+27b^2\) değerini çarpanlara ayırmaktır. Sonra her aday asal için mod \(p\) taban araması ve her ek üs için en fazla bir lift aşaması gerekir. Yaşayan blokların kalıntı sayıları \(r_1,r_2,\dots,r_s\) ise, CRT aşaması en kötü durumda \(r_1r_2\cdots r_s\) birleşimi inceler.
Dolayısıyla çalışma süresi üç ana parçadan oluşur: faktorizasyon, asal kuvvet lift işlemleri ve yerel kalıntı sınıflarının birleştirilmesi. Tüm \(1\le a\le m\), \(1\le b\le n\) dikdörtgeni üzerinde toplam süre, çift sayısıyla yaklaşık doğrusal biçimde büyür ve buna ortalama yerel aritmetik maliyet çarpan olarak eklenir. Bellek kullanımı düşüktür; baskın pay, lift ve CRT sırasında tutulan geçici kalıntı listeleridir.
Para enteros positivos fijos \(a\) y \(b\), consideramos las dos sucesiones
$$u_n=n^3+b,\qquad v_n=(n+a)^3+b.$$
Definimos
$$M(a,b)=\max_{n\ge 0}\gcd(u_n,v_n).$$
Entonces \(G(a,b)\) es el menor entero no negativo \(n\) para el cual \(\gcd(u_n,v_n)=M(a,b)\). El objetivo final es
$$H(m,n)=\sum_{a=1}^{m}\sum_{b=1}^{n}G(a,b).$$
Las implementaciones en C++, Python y Java no recorren directamente todos los valores de \(n\). Primero determinan la mayor potencia prima que puede aparecer en el mcd para cada primo, y después reconstruyen con CRT el menor índice que alcanza simultáneamente todos esos máximos locales.
Para una potencia prima \(p^k\), la condición \(p^k\mid \gcd(u_n,v_n)\) es equivalente a
$$n^3+b\equiv 0\pmod{p^k},\qquad (n+a)^3+b\equiv 0\pmod{p^k}.$$
Así, el problema se vuelve local en cada primo: necesitamos saber para qué primos y exponentes las dos cúbicas comparten una clase residual común.
Si dos polinomios enteros tienen una raíz común módulo un primo \(p\), entonces \(p\) debe dividir su resultante. Para
$$f(x)=x^3+b,\qquad g(x)=(x+a)^3+b,$$
el determinante de Sylvester da
$$\operatorname{Res}_x(f,g)=a^3(a^6+27b^2).$$
Por lo tanto, cualquier primo que pueda aparecer en el mcd máximo debe dividir \(a^3(a^6+27b^2)\). Por eso la implementación factoriza \(a^6+27b^2\) para cada par \((a,b)\) y luego añade los exponentes triplicados procedentes de \(a\).
Restando las dos congruencias desaparece \(b\):
$$0\equiv (n+a)^3-n^3=a(3n^2+3an+a^2)\pmod{p^k}.$$
Si \(p\nmid a\), esto implica
$$3n^2+3an+a^2\equiv 0\pmod{p}.$$
Para primos impares \(p>5\), completamos el cuadrado:
$$4(3n^2+3an+a^2)=3(2n+a)^2+a^2,$$
y obtenemos
$$ (2n+a)^2\equiv -\frac{a^2}{3}\pmod{p}. $$
Esto reduce la búsqueda base módulo \(p\) a un problema de raíz cuadrada modular. La implementación calcula esa raíz cuando existe, la convierte en hasta dos candidatos y luego comprueba esos candidatos en las congruencias cúbicas originales. Para primos pequeños y casos degenerados con \(p\mid a\), se enumeran directamente todas las clases módulo \(p\).
Supongamos que \(r\) es solución simultánea módulo \(p^t\). Cualquier elevación a \(p^{t+1}\) debe ser de la forma
$$n=r+u\,p^t,\qquad u\in\{0,1,\dots,p-1\}.$$
La implementación prueba los \(p\) descendientes posibles y conserva solo los que siguen satisfaciendo ambas congruencias cúbicas módulo \(p^{t+1}\). Repitiendo el proceso se obtiene el mayor exponente \(k_p\) para el que aún existen raíces simultáneas. Si la elevación falla en el siguiente nivel, entonces \(p^{k_p}\) es exactamente la mayor potencia de \(p\) que puede dividir al mcd.
Sea \(p^{e_p}\) el exponente de \(p\) en el resultante, y sea \(k_p\le e_p\) el mayor exponente alcanzado por la elevación. Entonces cualquier valor \(\gcd(u_n,v_n)\) tiene valoración \(p\)-ádica a lo sumo \(k_p\), de modo que
$$M(a,b)\le \prod_p p^{k_p}.$$
En sentido inverso, elijamos una clase residual elevada para cada primo superviviente. Como las potencias primas distintas son coprimas, el teorema chino del resto las combina en una clase única módulo
$$Q(a,b)=\prod_p p^{k_p}.$$
Cualquier \(n\) de esa clase hace que ambas sucesiones sean divisibles por \(p^{k_p}\) para todos los primos supervivientes. Por tanto,
$$\boxed{M(a,b)=Q(a,b).}$$
Así, \(G(a,b)\) no es más que el menor entero no negativo dentro de las clases residuales fusionadas por CRT.
Para \((a,b)=(1,1)\), el resultante vale
$$1^3(1^6+27\cdot 1^2)=28=2^2\cdot 7.$$
No hay raíz simultánea módulo \(2\), mientras que módulo \(7\) aparece la solución única \(n\equiv 5\pmod{7}\). En consecuencia, el mcd máximo es \(7\) y el primer índice que lo alcanza es
$$G(1,1)=5.$$
Un ejemplo de elevación es \((a,b)=(1,5)\). Aquí
$$1^3(1^6+27\cdot 5^2)=676=2^2\cdot 13^2.$$
Solo sobrevive el primo \(13\). La clase \(n\equiv 5\pmod{13}\) se eleva a \(n\equiv 161\pmod{169}\), por lo que el mcd máximo es \(13^2=169\) y
$$G(1,5)=161.$$
Las implementaciones construyen primero una tabla reutilizable de primos y precalculan los valores \(a^6\), \(27b^2\) y la factorización prima de cada \(a\) permitido. Para cada par \((a,b)\), se factoriza \(a^6+27b^2\), se añaden las contribuciones de \(a^3\) y se procesa cada primo candidato por separado.
Para cada bloque primo, la implementación encuentra las clases residuales simultáneas módulo \(p\), las eleva todo lo posible y guarda el mayor módulo que aún admite soluciones. Después, los bloques se ordenan por número de residuos locales para reducir en la práctica el coste del producto cartesiano durante la fusión CRT. Cada residuo fusionado alcanza el mcd máximo y el menor de ellos se devuelve como \(G(a,b)\).
Al final, los valores se suman sobre toda la malla de \((a,b)\). Como cada par es independiente, las versiones en C++, Python y Java paralelizan esta acumulación exterior. Los puntos de control publicados son
$$G(1,1)=5,\qquad H(5,5)=128878,\qquad H(10,10)=32936544.$$
Para un par \((a,b)\), el primer coste es factorizar \(a^6+27b^2\) con la lista de primos precalculada. Después, cada primo candidato requiere una búsqueda local módulo \(p\) y, para cada exponente adicional, como mucho una fase de elevación. Si los bloques supervivientes tienen \(r_1,r_2,\dots,r_s\) residuos, la etapa CRT examina en el peor caso \(r_1r_2\cdots r_s\) combinaciones.
En consecuencia, el tiempo total viene dominado por tres tareas: factorizar la parte del resultante, elevar raíces a potencias primas y combinar clases residuales locales. Sobre todo el rectángulo \(1\le a\le m\), \(1\le b\le n\), el coste crece aproximadamente de forma lineal con el número de pares de parámetros, multiplicado por el coste aritmético medio de cada caso. El uso de memoria es pequeño y está dominado por las listas temporales de residuos generadas durante la elevación y la fusión CRT.
对固定的正整数 \(a\) 和 \(b\)，考虑两列数
$$u_n=n^3+b,\qquad v_n=(n+a)^3+b.$$
定义
$$M(a,b)=\max_{n\ge 0}\gcd(u_n,v_n).$$
然后令 \(G(a,b)\) 为使 \(\gcd(u_n,v_n)=M(a,b)\) 的最小非负整数 \(n\)。最终要求的是
$$H(m,n)=\sum_{a=1}^{m}\sum_{b=1}^{n}G(a,b).$$
C++、Python 和 Java 实现并不是直接枚举 \(n\)，而是先求出 gcd 在每个素数上的最大可达素数幂，再用中国剩余定理把这些局部最大值同时拼接起来，从而得到最小的对应下标。
对任意素数幂 \(p^k\)，条件 \(p^k\mid \gcd(u_n,v_n)\) 等价于
$$n^3+b\equiv 0\pmod{p^k},\qquad (n+a)^3+b\equiv 0\pmod{p^k}.$$
因此整个问题可以拆成按素数分别处理的局部问题：对于哪些素数以及哪些指数，这两个三次式会拥有共同的剩余类根。
如果两个整系数多项式在模素数 \(p\) 的意义下有公共根，那么 \(p\) 必须整除它们的结果式。这里
$$f(x)=x^3+b,\qquad g(x)=(x+a)^3+b,$$
其 Sylvester 行列式计算结果为
$$\operatorname{Res}_x(f,g)=a^3(a^6+27b^2).$$
所以，能够出现在最大 gcd 中的素数，必然来自 \(a^3(a^6+27b^2)\) 的素因子。这正是实现中对每个 \((a,b)\) 分解 \(a^6+27b^2\)，再把 \(a\) 的素因子指数乘以 3 加进去的原因。
把两条同余相减，\(b\) 会消掉：
$$0\equiv (n+a)^3-n^3=a(3n^2+3an+a^2)\pmod{p^k}.$$
当 \(p\nmid a\) 时，必有
$$3n^2+3an+a^2\equiv 0\pmod{p}.$$
对奇素数 \(p>5\)，可以配方得到
$$4(3n^2+3an+a^2)=3(2n+a)^2+a^2,$$
于是
$$ (2n+a)^2\equiv -\frac{a^2}{3}\pmod{p}. $$
这样，模 \(p\) 的初始搜索就化成了一个模平方根问题。实现会先求这个平方根，得到至多两个候选剩余类，再把它们代回原来的两个三次同余中做最终验证。对小素数以及 \(p\mid a\) 这样的退化情况，实现直接枚举模 \(p\) 的所有剩余类，以保证稳健性。
假设 \(r\) 是模 \(p^t\) 的一个同时解，那么模 \(p^{t+1}\) 的任何提升都必须写成
$$n=r+u\,p^t,\qquad u\in\{0,1,\dots,p-1\}.$$
实现会测试这 \(p\) 个后继，只保留仍然满足两个三次同余模 \(p^{t+1}\) 的那些。不断重复后，就得到仍然存在共同根的最高指数 \(k_p\)。如果再往上一层已经没有可行提升，那么 gcd 中关于 \(p\) 的最大贡献就恰好是 \(p^{k_p}\)。
设 \(p^{e_p}\) 是结果式中 \(p\) 的指数，\(k_p\le e_p\) 是提升过程真正达到的最高指数。那么任意 \(\gcd(u_n,v_n)\) 的 \(p\)-进赋值都不会超过 \(k_p\)，因此
$$M(a,b)\le \prod_p p^{k_p}.$$
反过来，对每个仍然存活的素数选取一个提升后的剩余类。不同素数幂彼此互素，所以中国剩余定理可以把它们合并成模
$$Q(a,b)=\prod_p p^{k_p}$$
下唯一的一个剩余类。这个类中的任何 \(n\) 都会让两个序列同时被每个 \(p^{k_p}\) 整除，于是
$$\boxed{M(a,b)=Q(a,b).}$$
因此 \(G(a,b)\) 就是这些合并后剩余类中的最小非负整数。
当 \((a,b)=(1,1)\) 时，结果式为
$$1^3(1^6+27\cdot 1^2)=28=2^2\cdot 7.$$
模 \(2\) 没有同时根，而模 \(7\) 有唯一解 \(n\equiv 5\pmod{7}\)。所以最大 gcd 是 \(7\)，最先达到它的下标为
$$G(1,1)=5.$$
再看一个提升例子 \((a,b)=(1,5)\)。此时
$$1^3(1^6+27\cdot 5^2)=676=2^2\cdot 13^2.$$
只有素数 \(13\) 保留下来。剩余类 \(n\equiv 5\pmod{13}\) 会继续提升为 \(n\equiv 161\pmod{169}\)，因此最大 gcd 为 \(13^2=169\)，并且
$$G(1,5)=161.$$
这些实现先构造一张可复用的素数表，并预计算所有允许范围内的 \(a^6\)、\(27b^2\) 以及每个 \(a\) 的素因子分解。对每个 \((a,b)\)，先分解 \(a^6+27b^2\)，再补上 \(a^3\) 提供的指数贡献，然后逐个处理候选素数。
对于每个素数块，实现先找出模 \(p\) 的同时剩余类，再尽可能向更高素数幂提升，并记录仍然有解的最大模数。随后，各个素数块会按“局部剩余类个数”从小到大排序，这能减少 CRT 合并时的笛卡尔积规模。每个合并后的剩余类都会达到最大 gcd，其中最小的一个就是 \(G(a,b)\)。
最后，对整个 \((a,b)\) 网格求和即可。由于各个参数对彼此独立，C++、Python 和 Java 实现都把这一步做成了并行累加。公开校验点为
$$G(1,1)=5,\qquad H(5,5)=128878,\qquad H(10,10)=32936544.$$
对单个 \((a,b)\) 而言，第一部分开销是用预先生成的素数表分解 \(a^6+27b^2\)。随后，每个候选素数都需要一次模 \(p\) 的局部搜索，并对每个额外指数做至多一次提升过程。若存活的局部块对应的剩余类数量为 \(r_1,r_2,\dots,r_s\)，那么 CRT 合并阶段在最坏情况下需要考察 \(r_1r_2\cdots r_s\) 种组合。
所以总时间主要由三部分决定：结果式相关部分的因式分解、素数幂根的提升，以及局部剩余类的 CRT 合并。放到整个矩形 \(1\le a\le m\)、\(1\le b\le n\) 上看，总体运行时间大致与参数对数量成线性关系，再乘上平均每对参数的局部算术代价。内存占用不大，主要来自提升与 CRT 合并过程中暂时保存的剩余类列表。
Для фиксированных положительных целых \(a\) и \(b\) рассматриваются две последовательности
$$u_n=n^3+b,\qquad v_n=(n+a)^3+b.$$
Определим
$$M(a,b)=\max_{n\ge 0}\gcd(u_n,v_n).$$
Тогда \(G(a,b)\) — это наименьшее неотрицательное \(n\), для которого \(\gcd(u_n,v_n)=M(a,b)\). Требуется вычислить
$$H(m,n)=\sum_{a=1}^{m}\sum_{b=1}^{n}G(a,b).$$
Реализации на C++, Python и Java не перебирают \(n\) напрямую. Сначала они находят наибольшую степень каждого простого, которая вообще может войти в максимальный НОД, а затем с помощью китайской теоремы об остатках восстанавливают минимальный индекс, достигающий всех этих локальных максимумов одновременно.
Для любой степени простого \(p^k\) условие \(p^k\mid \gcd(u_n,v_n)\) эквивалентно двум сравнениям
$$n^3+b\equiv 0\pmod{p^k},\qquad (n+a)^3+b\equiv 0\pmod{p^k}.$$
Следовательно, задача локализуется по простым: нужно понять, для каких простых и каких показателей обе кубики имеют общий класс вычетов.
Если два целочисленных полинома имеют общий корень по модулю простого \(p\), то \(p\) обязан делить их результант. Для
$$f(x)=x^3+b,\qquad g(x)=(x+a)^3+b$$
вычисление по матрице Сильвестра дает
$$\operatorname{Res}_x(f,g)=a^3(a^6+27b^2).$$
Значит, любой простой, который может входить в максимальный НОД, должен делить число \(a^3(a^6+27b^2)\). Именно поэтому реализация факторизует \(a^6+27b^2\) для каждой пары \((a,b)\), а затем добавляет утроенные показатели простых из разложения числа \(a\).
Вычтем одно сравнение из другого:
$$0\equiv (n+a)^3-n^3=a(3n^2+3an+a^2)\pmod{p^k}.$$
Если \(p\nmid a\), то отсюда следует
$$3n^2+3an+a^2\equiv 0\pmod{p}.$$
Для нечетных простых \(p>5\) можно дополнить до квадрата:
$$4(3n^2+3an+a^2)=3(2n+a)^2+a^2,$$
поэтому
$$ (2n+a)^2\equiv -\frac{a^2}{3}\pmod{p}. $$
Тем самым базовый поиск по модулю \(p\) сводится к задаче о модульном квадратном корне. Реализация находит этот корень, если он существует, получает из него не более двух кандидатов и затем проверяет их в исходных кубических сравнениях. Для малых простых и вырожденных случаев с \(p\mid a\) программа просто перебирает все вычеты по модулю \(p\).
Пусть \(r\) — совместное решение по модулю \(p^t\). Тогда любое продолжение на модуль \(p^{t+1}\) обязано иметь вид
$$n=r+u\,p^t,\qquad u\in\{0,1,\dots,p-1\}.$$
Реализация проверяет все \(p\) потомков и оставляет только те, которые по-прежнему удовлетворяют обеим кубическим сравнениям по модулю \(p^{t+1}\). Повторяя этот шаг, она находит наибольший показатель \(k_p\), для которого совместные корни еще существуют. Если на следующем уровне подъем уже невозможен, значит максимальный вклад простого \(p\) в НОД равен именно \(p^{k_p}\).
Пусть \(p^{e_p}\) — показатель простого \(p\) в результанте, а \(k_p\le e_p\) — наибольший показатель, реально достигнутый при подъеме. Тогда \(p\)-адическая оценка любого значения \(\gcd(u_n,v_n)\) не превосходит \(k_p\), следовательно
$$M(a,b)\le \prod_p p^{k_p}.$$
С другой стороны, выберем по одному поднятому классу вычетов для каждого выжившего простого. Разные степени простых взаимно просты, поэтому китайская теорема об остатках склеивает их в единственный класс по модулю
$$Q(a,b)=\prod_p p^{k_p}.$$
Любое \(n\) из этого класса делает обе последовательности делимыми на \(p^{k_p}\) для каждого выжившего простого. Значит,
$$\boxed{M(a,b)=Q(a,b).}$$
Следовательно, \(G(a,b)\) — это просто наименьший неотрицательный представитель объединенного CRT-класса.
Для \((a,b)=(1,1)\) результант равен
$$1^3(1^6+27\cdot 1^2)=28=2^2\cdot 7.$$
По модулю \(2\) совместного корня нет, а по модулю \(7\) существует единственное решение \(n\equiv 5\pmod{7}\). Поэтому максимальный НОД равен \(7\), а первый индекс, на котором он достигается, равен
$$G(1,1)=5.$$
Пример с подъемом: \((a,b)=(1,5)\). Здесь
$$1^3(1^6+27\cdot 5^2)=676=2^2\cdot 13^2.$$
Выживает только простой \(13\). Класс \(n\equiv 5\pmod{13}\) поднимается до \(n\equiv 161\pmod{169}\), поэтому максимальный НОД равен \(13^2=169\), и
$$G(1,5)=161.$$
Сначала реализации строят переиспользуемую таблицу простых чисел и заранее вычисляют значения \(a^6\), \(27b^2\), а также разложения каждого допустимого \(a\) на простые множители. Для каждой пары \((a,b)\) факторизуется число \(a^6+27b^2\), затем к показателям добавляется вклад из \(a^3\), и каждый кандидатный простой разбирается отдельно.
Для каждого простого блока программа находит совместные классы по модулю \(p\), поднимает их настолько высоко, насколько это возможно, и запоминает наибольший модуль, где решения еще существуют. Затем блоки сортируются по числу локальных вычетов; это уменьшает практическую стоимость декартова произведения на этапе CRT-склейки. Каждый склеенный вычет достигает максимального НОД, а минимальный из них возвращается как \(G(a,b)\).
В конце значения суммируются по всей сетке \((a,b)\). Поскольку разные пары независимы, C++, Python и Java параллелят именно этот внешний этап. Контрольные значения таковы:
$$G(1,1)=5,\qquad H(5,5)=128878,\qquad H(10,10)=32936544.$$
Для одной пары \((a,b)\) первая составляющая стоимости — факторизация числа \(a^6+27b^2\) с помощью заранее построенного списка простых. Затем для каждого кандидатного простого выполняется локальный поиск по модулю \(p\) и, для каждого следующего показателя, не более одного этапа подъема. Если у выживших блоков числа локальных вычетов равны \(r_1,r_2,\dots,r_s\), то CRT-этап в худшем случае рассматривает \(r_1r_2\cdots r_s\) комбинаций.
Итак, время работы определяется тремя компонентами: факторизацией результантной части, подъемом корней на степени простых и объединением локальных классов вычетов. На всем прямоугольнике \(1\le a\le m\), \(1\le b\le n\) общая трудоемкость примерно линейна по числу пар параметров с дополнительным множителем, равным средней локальной арифметической стоимости. Память требуется небольшая; основной вклад дают временные списки вычетов, используемые при подъеме и CRT-склейке.
لعددين صحيحين موجبين ثابتين \(a\) و\(b\)، ننظر إلى المتتاليتين
$$u_n=n^3+b,\qquad v_n=(n+a)^3+b.$$
ونعرّف
$$M(a,b)=\max_{n\ge 0}\gcd(u_n,v_n).$$
ثم يكون \(G(a,b)\) هو أصغر عدد صحيح غير سالب \(n\) يحقق \(\gcd(u_n,v_n)=M(a,b)\). والمطلوب في النهاية هو
$$H(m,n)=\sum_{a=1}^{m}\sum_{b=1}^{n}G(a,b).$$
لا تقوم تطبيقات C++ وPython وJava بمسح كل قيم \(n\) مباشرة. بدلًا من ذلك، تحسب أولًا أكبر قوة أولية يمكن أن تظهر في القاسم المشترك الأكبر لكل عدد أولي، ثم تعيد بناء أصغر فهرس يحقق جميع هذه القيم المحلية العظمى معًا بواسطة مبرهنة الباقي الصيني.
لكل قوة أولية \(p^k\)، فإن الشرط \(p^k\mid \gcd(u_n,v_n)\) يكافئ
$$n^3+b\equiv 0\pmod{p^k},\qquad (n+a)^3+b\equiv 0\pmod{p^k}.$$
إذن المسألة محلية بالنسبة إلى كل عدد أولي: نريد أن نعرف لأي الأعداد الأولية ولأي أسس تمتلك كثيرات الحدود التكعيبية هاتان جذرًا مشتركًا في نفس فئة البواقي.
إذا كان لكثيري حدود صحيحَي المعاملات جذر مشترك بترديد أولي \(p\)، فلا بد أن يقسم \(p\) ناتجهما. في حالتنا
$$f(x)=x^3+b,\qquad g(x)=(x+a)^3+b,$$
ويعطي محدد سيلفستر
$$\operatorname{Res}_x(f,g)=a^3(a^6+27b^2).$$
إذًا أي عدد أولي يمكن أن يظهر في gcd الأعظمي لا بد أن يقسم \(a^3(a^6+27b^2)\). ولهذا السبب بالضبط تقوم التطبيقات بتحليل \(a^6+27b^2\) إلى عوامله الأولية لكل زوج \((a,b)\)، ثم تضيف بعد ذلك الأسس الثلاثية القادمة من \(a\).
بطرح التوافقين يختفي الحد \(b\):
$$0\equiv (n+a)^3-n^3=a(3n^2+3an+a^2)\pmod{p^k}.$$
وعندما يكون \(p\nmid a\)، ينتج من ذلك
$$3n^2+3an+a^2\equiv 0\pmod{p}.$$
وللأعداد الأولية الفردية \(p>5\) نستطيع إكمال المربع:
$$4(3n^2+3an+a^2)=3(2n+a)^2+a^2,$$
ومن ثم
$$ (2n+a)^2\equiv -\frac{a^2}{3}\pmod{p}. $$
وهذا يحول البحث الأساسي بترديد \(p\) إلى مسألة جذر تربيعي معياري. تحسب التطبيقات هذا الجذر عندما يكون موجودًا، وتحوّله إلى مرشحين اثنين على الأكثر، ثم تتحقق من كل مرشح داخل التوافقين التكعيبيين الأصليين. أما للأعداد الأولية الصغيرة والحالات المنحلة التي فيها \(p\mid a\)، فتجري تجربة مباشرة على جميع البواقي بترديد \(p\).
إذا كان \(r\) حلًا متزامنًا بترديد \(p^t\)، فإن أي رفع إلى \(p^{t+1}\) يجب أن يكون من الشكل
$$n=r+u\,p^t,\qquad u\in\{0,1,\dots,p-1\}.$$
تختبر التطبيقات جميع الأبناء الممكنين وعددهم \(p\)، وتحتفظ فقط بمن يحقق التوافقين التكعيبيين أيضًا بترديد \(p^{t+1}\). وبتكرار هذه العملية نحصل على أكبر أس \(k_p\) ما زالت توجد معه جذور مشتركة. فإذا فشل الرفع في المستوى التالي، كانت \(p^{k_p}\) هي أكبر قوة من \(p\) يمكن أن تدخل في gcd.
ليكن \(p^{e_p}\) أس \(p\) في الناتج، وليكن \(k_p\le e_p\) أكبر أس نجح الوصول إليه أثناء الرفع. عندئذ تكون \(p\)-الأدبية لأي قيمة من \(\gcd(u_n,v_n)\) محصورة من الأعلى بـ \(k_p\)، وبالتالي
$$M(a,b)\le \prod_p p^{k_p}.$$
وبالعكس، إذا اخترنا فئة بواقي مرفوعة لكل عدد أولي باقٍ، فإن قوى الأعداد الأولية المختلفة متباينة أوليًا، ولذلك تجمعها مبرهنة الباقي الصيني في فئة واحدة بترديد
$$Q(a,b)=\prod_p p^{k_p}.$$
وأي \(n\) داخل هذه الفئة يجعل كلتا المتتاليتين قابلتين للقسمة على \(p^{k_p}\) لكل عدد أولي باقٍ، ومن ثم
$$\boxed{M(a,b)=Q(a,b).}$$
إذًا \(G(a,b)\) ليس إلا أصغر عنصر غير سالب في فئات البواقي المجمعة بواسطة CRT.
بالنسبة إلى \((a,b)=(1,1)\)، يكون الناتج
$$1^3(1^6+27\cdot 1^2)=28=2^2\cdot 7.$$
لا يوجد جذر متزامن بترديد \(2\)، بينما يوجد حل وحيد بترديد \(7\) هو \(n\equiv 5\pmod{7}\). لذلك يكون gcd الأعظمي مساويًا لـ \(7\)، وأصغر فهرس يحققه هو
$$G(1,1)=5.$$
ومثال الرفع هو \((a,b)=(1,5)\). في هذه الحالة
$$1^3(1^6+27\cdot 5^2)=676=2^2\cdot 13^2.$$
يبقى العدد الأولي \(13\) فقط. وترتفع الفئة \(n\equiv 5\pmod{13}\) إلى \(n\equiv 161\pmod{169}\)، ولذلك يكون gcd الأعظمي هو \(13^2=169\)، ومن ثم
$$G(1,5)=161.$$
تبدأ التطبيقات ببناء جدول قابل لإعادة الاستخدام للأعداد الأولية، ثم تحسب مسبقًا القيم \(a^6\) و\(27b^2\) وتحليل كل قيمة مسموحة من \(a\) إلى عواملها الأولية. لكل زوج \((a,b)\)، يجري تحليل \(a^6+27b^2\)، ثم تُضاف مساهمات \(a^3\)، وبعد ذلك يُعالَج كل عدد أولي مرشح على حدة.
لكل كتلة أولية، تجد التطبيقات فئات البواقي المتزامنة بترديد \(p\)، ثم ترفعها ما أمكن وتحفظ أكبر قوة أولية ما تزال عندها حلول مشتركة. وبعد ذلك تُرتب الكتل بحسب عدد بواقيها المحلية لتقليل كلفة الضرب الديكارتي أثناء الدمج بواسطة CRT. كل باقٍ مدمج يحقق gcd الأعظمي، وأصغر هذه البواقي هو القيمة \(G(a,b)\).
وفي النهاية تُجمع القيم على كامل شبكة \((a,b)\). وبما أن كل زوج مستقل عن غيره، فإن تطبيقات C++ وPython وJava توازي هذه العملية الخارجية. ونقاط التحقق المنشورة هي
$$G(1,1)=5,\qquad H(5,5)=128878,\qquad H(10,10)=32936544.$$
لكل زوج \((a,b)\)، تكون الكلفة الأولى هي تحليل \(a^6+27b^2\) باستخدام قائمة الأعداد الأولية المحسوبة مسبقًا. بعد ذلك يحتاج كل عدد أولي مرشح إلى بحث محلي بترديد \(p\)، ومع كل أس إضافي تظهر مرحلة رفع واحدة على الأكثر. وإذا كانت أعداد البواقي في الكتل الباقية هي \(r_1,r_2,\dots,r_s\)، فإن مرحلة CRT تفحص في أسوأ الحالات \(r_1r_2\cdots r_s\) تركيبًا مختلفًا.
وعليه، فإن الزمن الكلي تحكمه ثلاث مهام رئيسية: تحليل الجزء الناتج من النواتج الجبرية، ورفع الجذور على قوى الأعداد الأولية، ودمج فئات البواقي المحلية. وعلى كامل المستطيل \(1\le a\le m\)، \(1\le b\le n\)، ينمو الزمن تقريبًا خطيًا مع عدد أزواج المعلمات، مضروبًا في متوسط الكلفة الحسابية المحلية لكل زوج. أما الذاكرة فتبقى متواضعة، ويأتي معظمها من قوائم البواقي المؤقتة أثناء الرفع والدمج.