For each pair of consecutive primes \(p_1, p_2\) with \(5 \le p_1 \le 10^6\), let \(S(p_1,p_2)\) be the smallest positive integer that is divisible by \(p_2\) and whose decimal expansion ends with the digits of \(p_1\). The task is to sum \(S(p_1,p_2)\) over all such consecutive prime pairs.
A brute-force scan through multiples of \(p_2\) would be wasteful. The suffix condition is really a congruence modulo a power of ten, so every prime pair can be solved by one modular inverse and one multiplication.
Let \(d\) be the number of decimal digits of \(p_1\), and set \(M = 10^d\). Saying that a number ends with the digits of \(p_1\) is equivalent to saying that it is congruent to \(p_1\) modulo \(M\).
If \(n\) is divisible by \(p_2\), then \(n = p_2 k\) for some positive integer \(k\). The suffix requirement becomes
$$p_2 k \equiv p_1 \pmod{M}.$$
This is the central congruence used by the implementations. It solves directly for the multiplier \(k\), and then reconstructs \(n\) as \(p_2 k\).
Because \(p_1 \ge 5\) and \(p_2\) is the next prime, we always have \(p_2 \ge 7\). Therefore \(p_2\) is not divisible by 2 or 5, while \(M = 10^d\) has no prime factors other than 2 and 5. Hence
$$\gcd(p_2, M) = 1,$$
so \(p_2\) has a unique multiplicative inverse modulo \(M\). Multiplying the congruence by that inverse gives
$$k \equiv p_1 \, p_2^{-1} \pmod{M}.$$
Let \(k_0\) be the least positive residue of \(p_1 p_2^{-1}\) modulo \(M\). Then every valid multiplier has the form
$$k = k_0 + tM \qquad (t \ge 0),$$
and every valid number has the form
$$n = p_2(k_0 + tM) = p_2 k_0 + t(p_2 M).$$
Since the step size \(p_2 M\) is positive, the smallest valid number is obtained at \(t = 0\). Therefore
$$\boxed{S(p_1,p_2) = p_2 \left( (p_1 p_2^{-1}) \bmod M \right).}$$
This is exactly the value accumulated by the C++, Python, and Java implementations.
Here \(d = 2\), so \(M = 100\). We need
$$23k \equiv 19 \pmod{100}.$$
The inverse of \(23\) modulo \(100\) is \(87\), because \(23 \cdot 87 = 2001 \equiv 1 \pmod{100}\). Hence
$$k_0 \equiv 19 \cdot 87 \equiv 53 \pmod{100},$$
so the smallest valid number is
$$S(19,23) = 23 \cdot 53 = 1219.$$
And indeed \(1219\) is divisible by \(23\) and ends in the digits \(19\).
One can also write \(n = p_1 + Mt\) and solve
$$Mt \equiv -p_1 \pmod{p_2}.$$
That version uses the inverse of \(M\) modulo \(p_2\). It is mathematically equivalent, but the implementations choose the dual viewpoint above because they already represent the answer as a multiple of \(p_2\).
The implementations first generate primes beyond \(10^6\), not merely up to \(10^6\), because every prime \(p_1\) below the bound needs its consecutive successor \(p_2\). They then scan the prime list pair by pair and stop once \(p_1\) reaches the limit.
For each pair, the implementation computes \(M = 10^d\) by counting the decimal digits of \(p_1\). Since \(p_1 \lt 10^6\), we only need \(d \le 6\). It then computes the inverse of \(p_2 \bmod M\): the C++ version does this with the extended Euclidean algorithm, the Python version uses built-in modular inversion, and the Java version uses big-integer modular inversion.
After that, the implementation forms the least residue \(k_0 = (p_1 p_2^{-1}) \bmod M\), multiplies by \(p_2\), and adds the result to the running sum. No candidate values are tested, and no repeated multiples are scanned.
If the sieve bound is \(L\), prime generation costs \(O(L \log \log L)\) time and \(O(L)\) memory. After the sieve, each consecutive prime pair requires only a digit count and one modular inverse modulo \(10^d\), so the per-pair work is \(O(\log M)\) with \(M \le 10^6\), effectively very small here.
In practice the sieve dominates the runtime, while the arithmetic for each pair is tiny. The total sum also fits comfortably in signed 64-bit arithmetic for the stated bound, which is why the fixed-width implementations can accumulate it directly.
Für jedes Paar aufeinanderfolgender Primzahlen \(p_1, p_2\) mit \(5 \le p_1 \le 10^6\) sei \(S(p_1,p_2)\) die kleinste positive Zahl, die durch \(p_2\) teilbar ist und in ihrer Dezimalschreibweise mit den Ziffern von \(p_1\) endet. Gesucht ist die Summe dieser Werte über alle solchen Primzahlpaare.
Ein direktes Durchprobieren der Vielfachen von \(p_2\) wäre unnötig langsam. Die Endziffernbedingung ist in Wahrheit nur eine Kongruenz modulo einer Zehnerpotenz, also reduziert sich jedes Paar auf eine modulare Inversion und eine Multiplikation.
Sei \(d\) die Anzahl der Dezimalziffern von \(p_1\), und setze \(M = 10^d\). Dass eine Zahl mit den Ziffern von \(p_1\) endet, ist äquivalent zu
$$n \equiv p_1 \pmod{M}.$$
Ist \(n\) durch \(p_2\) teilbar, so gilt \(n = p_2 k\) für ein positives ganzzahliges \(k\). Die Bedingung an die Endziffern wird damit zu
$$p_2 k \equiv p_1 \pmod{M}.$$
Genau diese Kongruenz lösen die Implementierungen. Sie bestimmen also zuerst den passenden Multiplikator \(k\) und setzen danach \(n = p_2 k\).
Da \(p_1 \ge 5\) und \(p_2\) die nächste Primzahl ist, gilt immer \(p_2 \ge 7\). Also ist \(p_2\) weder durch 2 noch durch 5 teilbar, während \(M = 10^d\) nur die Primfaktoren 2 und 5 besitzt. Deshalb
$$\gcd(p_2, M) = 1,$$
und \(p_2\) besitzt ein eindeutiges multiplikatives Inverses modulo \(M\). Multipliziert man die Kongruenz damit, erhält man
$$k \equiv p_1 \, p_2^{-1} \pmod{M}.$$
Sei \(k_0\) der kleinste positive Rest von \(p_1 p_2^{-1}\) modulo \(M\). Dann hat jeder gültige Multiplikator die Form
$$k = k_0 + tM \qquad (t \ge 0),$$
und jede gültige Zahl die Form
$$n = p_2(k_0 + tM) = p_2 k_0 + t(p_2 M).$$
Da die Schrittweite \(p_2 M\) positiv ist, entsteht die kleinste Lösung bei \(t = 0\). Also
$$\boxed{S(p_1,p_2) = p_2 \left( (p_1 p_2^{-1}) \bmod M \right).}$$
Genau diesen Ausdruck akkumulieren die Implementierungen.
Hier ist \(d = 2\), also \(M = 100\). Gesucht ist
$$23k \equiv 19 \pmod{100}.$$
Das Inverse von \(23\) modulo \(100\) ist \(87\), denn \(23 \cdot 87 = 2001 \equiv 1 \pmod{100}\). Daher
$$k_0 \equiv 19 \cdot 87 \equiv 53 \pmod{100},$$
und damit
$$S(19,23) = 23 \cdot 53 = 1219.$$
Tatsächlich ist \(1219\) durch \(23\) teilbar und endet auf \(19\).
Man kann auch \(n = p_1 + Mt\) setzen und
$$Mt \equiv -p_1 \pmod{p_2}$$
lösen. Das verwendet das Inverse von \(M\) modulo \(p_2\). Mathematisch ist das völlig gleichwertig, aber die Implementierungen wählen die obige duale Formulierung, weil sie die Antwort ohnehin als Vielfaches von \(p_2\) schreiben.
Die Implementierungen erzeugen zuerst Primzahlen über \(10^6\) hinaus, nicht nur bis \(10^6\), denn zu jeder Primzahl \(p_1\) unterhalb der Schranke wird auch die unmittelbar folgende Primzahl \(p_2\) benötigt. Anschließend laufen sie die Primzahlliste paarweise durch und brechen ab, sobald \(p_1\) die Grenze erreicht.
Für jedes Paar wird \(M = 10^d\) aus der Ziffernzahl von \(p_1\) aufgebaut. Da \(p_1 \lt 10^6\), reicht stets \(d \le 6\). Danach wird das Inverse von \(p_2 \bmod M\) berechnet: in C++ mit dem erweiterten euklidischen Algorithmus, in Python mit eingebauter modularer Inversion und in Java mit modularer Inversion auf Basis großer Ganzzahlen.
Dann bildet die Implementierung den kleinsten Rest \(k_0 = (p_1 p_2^{-1}) \bmod M\), multipliziert mit \(p_2\) und addiert das Ergebnis zur Summe. Es werden keine Kandidaten getestet und keine Vielfachen nacheinander abgesucht.
Ist \(L\) die Siebgrenze, dann kostet die Primzahlerzeugung \(O(L \log \log L)\) Zeit und \(O(L)\) Speicher. Danach benötigt jedes aufeinanderfolgende Primzahlpaar nur eine Ziffernzählung und eine modulare Inversion modulo \(10^d\), also \(O(\log M)\) Arbeit mit \(M \le 10^6\), was hier sehr klein ist.
In der Praxis dominiert also das Sieb, während die Rechnung pro Paar fast vernachlässigbar ist. Auch die Endsumme bleibt für die vorgegebene Schranke bequem innerhalb von vorzeichenbehafteten 64-Bit-Ganzzahlen, weshalb die Implementierungen mit fester Breite direkt akkumulieren können.
\(5 \le p_1 \le 10^6\) koşulunu sağlayan her ardışık asal çifti \(p_1, p_2\) için, \(p_2\)'ye tam bölünen ve ondalık yazımı \(p_1\)'in rakamlarıyla biten en küçük pozitif sayıyı \(S(p_1,p_2)\) olarak tanımlayalım. İstenen, bu değerlerin tüm çiftler üzerindeki toplamıdır.
\(p_2\)'nin katlarını tek tek denemek gereksizdir. Son basamak koşulu aslında yalnızca bir on kuvvetine göre kongruenstir; bu yüzden her çift tek bir modüler ters ve tek bir çarpma ile çözülebilir.
\(p_1\)'in ondalık basamak sayısı \(d\) olsun ve \(M = 10^d\) tanımlayalım. Bir sayının sonundaki \(d\) basamağın \(p_1\) olması tam olarak
$$n \equiv p_1 \pmod{M}$$
demektir.
Eğer \(n\), \(p_2\)'ye bölünüyorsa \(n = p_2 k\) biçimindedir. O zaman son basamak koşulu
$$p_2 k \equiv p_1 \pmod{M}$$
şeklini alır. Uygulamalar tam olarak bu kongruensi çözer. Yani önce uygun çarpan \(k\) bulunur, sonra cevap \(n = p_2 k\) olarak elde edilir.
\(p_1 \ge 5\) ve \(p_2\), \(p_1\)'den sonraki asal olduğundan daima \(p_2 \ge 7\) olur. Dolayısıyla \(p_2\), 2'ye de 5'e de bölünmez; buna karşılık \(M = 10^d\) yalnızca 2 ve 5 asal çarpanlarına sahiptir. Bu yüzden
$$\gcd(p_2, M) = 1$$
ve \(p_2\)'nin \(M\) modundaki çarpımsal tersi vardır. Kongruensi bu ters ile çarparsanız
$$k \equiv p_1 \, p_2^{-1} \pmod{M}$$
sonucuna ulaşırsınız.
\(p_1 p_2^{-1}\)'in \(M\) modundaki en küçük pozitif kalanı \(k_0\) olsun. O zaman bütün geçerli çarpanlar
$$k = k_0 + tM \qquad (t \ge 0)$$
biçimindedir. Buna karşılık tüm geçerli sayılar
$$n = p_2(k_0 + tM) = p_2 k_0 + t(p_2 M)$$
şeklinde yazılır. Artış miktarı \(p_2 M\) pozitif olduğundan en küçük çözüm \(t = 0\) iken elde edilir. Sonuç olarak
$$\boxed{S(p_1,p_2) = p_2 \left( (p_1 p_2^{-1}) \bmod M \right).}$$
C++, Python ve Java uygulamalarının topladığı değer tam olarak budur.
Burada \(d = 2\) olduğundan \(M = 100\) olur. Çözmemiz gereken kongruens
$$23k \equiv 19 \pmod{100}$$
şeklindedir. \(23\)'ün \(100\) modundaki tersi \(87\)'dir; çünkü \(23 \cdot 87 = 2001 \equiv 1 \pmod{100}\). Dolayısıyla
$$k_0 \equiv 19 \cdot 87 \equiv 53 \pmod{100},$$
ve en küçük geçerli sayı
$$S(19,23) = 23 \cdot 53 = 1219$$
olur. Gerçekten de \(1219\), 23'e bölünür ve son iki basamağı 19'dur.
İstenirse \(n = p_1 + Mt\) yazılıp
$$Mt \equiv -p_1 \pmod{p_2}$$
de çözülebilir. Bu yaklaşım \(M\)'in \(p_2\) modundaki tersini kullanır. Matematik aynı olsa da uygulamalar yukarıdaki ikili bakışı tercih eder; çünkü cevabı zaten \(p_2\)'nin bir katı olarak kurarlar.
Uygulamalar önce \(10^6\)'nın biraz ötesine kadar asal üretir; yalnızca \(10^6\)'ya kadar üretmek yetmez, çünkü sınırın altındaki her \(p_1\) için ondan sonraki asal \(p_2\) de gerekir. Daha sonra asal listesi ardışık çiftler halinde dolaşılır ve \(p_1\) limite ulaştığında durulur.
Her çiftte önce \(p_1\)'in basamak sayısından \(M = 10^d\) hesaplanır. \(p_1 \lt 10^6\) olduğu için burada daima \(d \le 6\) yeterlidir. Sonra \(p_2 \bmod M\)'nin tersi bulunur: C++ sürümü bunu genişletilmiş Öklid algoritmasıyla, Python sürümü yerleşik modüler ters alma özelliğiyle, Java sürümü ise büyük tamsayıların modüler tersiyle yapar.
Ardından \(k_0 = (p_1 p_2^{-1}) \bmod M\) oluşturulur, \(p_2\) ile çarpılır ve toplama eklenir. Hiçbir aday sayı test edilmez; ardışık katlar üzerinde tarama yapılmaz.
Süzgeç üst sınırı \(L\) ise asal üretimi \(O(L \log \log L)\) zamanda ve \(O(L)\) bellekte yapılır. Bundan sonra her ardışık asal çifti için yalnızca bir basamak sayımı ve \(10^d\) modunda bir modüler ters gerekir; yani çift başına iş yükü \(M \le 10^6\) olmak üzere \(O(\log M)\) düzeyindedir ve pratikte çok küçüktür.
Dolayısıyla çalışma süresini asıl belirleyen kısım süzgeçtir; çift başına aritmetik çok hafiftir. Toplam sonuç da verilen sınır için işaretli 64 bit aralığına rahatça sığdığı için sabit genişlikli uygulamalar doğrudan toplama yapabilir.
Para cada par de primos consecutivos \(p_1, p_2\) con \(5 \le p_1 \le 10^6\), definimos \(S(p_1,p_2)\) como el menor entero positivo divisible por \(p_2\) cuya escritura decimal termina con los dígitos de \(p_1\). El objetivo es sumar \(S(p_1,p_2)\) sobre todos esos pares consecutivos.
Probar múltiplos de \(p_2\) uno por uno sería innecesario. La condición sobre el sufijo decimal es simplemente una congruencia módulo una potencia de diez, de modo que cada par se resuelve con una sola inversa modular y una sola multiplicación.
Sea \(d\) el número de cifras decimales de \(p_1\), y definamos \(M = 10^d\). Que un número termine en los dígitos de \(p_1\) equivale a decir que
$$n \equiv p_1 \pmod{M}.$$
Si \(n\) es divisible por \(p_2\), entonces \(n = p_2 k\) para algún entero positivo \(k\). La condición del sufijo se transforma en
$$p_2 k \equiv p_1 \pmod{M}.$$
Esta es la congruencia central que usan las implementaciones. Primero resuelven el multiplicador \(k\) y luego reconstruyen \(n\) como \(p_2 k\).
Como \(p_1 \ge 5\) y \(p_2\) es el primo siguiente, siempre se tiene \(p_2 \ge 7\). Por tanto \(p_2\) no es divisible ni por 2 ni por 5, mientras que \(M = 10^d\) solo contiene factores primos 2 y 5. En consecuencia,
$$\gcd(p_2, M) = 1,$$
y \(p_2\) posee una inversa multiplicativa módulo \(M\). Multiplicando la congruencia anterior por esa inversa obtenemos
$$k \equiv p_1 \, p_2^{-1} \pmod{M}.$$
Sea \(k_0\) el menor residuo positivo de \(p_1 p_2^{-1}\) módulo \(M\). Entonces todos los multiplicadores válidos son de la forma
$$k = k_0 + tM \qquad (t \ge 0),$$
y todos los números válidos son
$$n = p_2(k_0 + tM) = p_2 k_0 + t(p_2 M).$$
Como el incremento \(p_2 M\) es positivo, la menor solución corresponde a \(t = 0\). Por tanto,
$$\boxed{S(p_1,p_2) = p_2 \left( (p_1 p_2^{-1}) \bmod M \right).}$$
Esa es exactamente la cantidad que acumulan las implementaciones.
Aquí \(d = 2\), así que \(M = 100\). Debemos resolver
$$23k \equiv 19 \pmod{100}.$$
La inversa de \(23\) módulo \(100\) es \(87\), porque \(23 \cdot 87 = 2001 \equiv 1 \pmod{100}\). Entonces
$$k_0 \equiv 19 \cdot 87 \equiv 53 \pmod{100},$$
y el menor número válido es
$$S(19,23) = 23 \cdot 53 = 1219.$$
En efecto, \(1219\) es múltiplo de \(23\) y termina en \(19\).
También se puede escribir \(n = p_1 + Mt\) y resolver
$$Mt \equiv -p_1 \pmod{p_2}.$$
Esa versión usa la inversa de \(M\) módulo \(p_2\). Es completamente equivalente, pero las implementaciones prefieren la formulación dual anterior porque ya expresan la respuesta como un múltiplo de \(p_2\).
Las implementaciones generan primero primos más allá de \(10^6\), no solo hasta \(10^6\), porque cada primo \(p_1\) por debajo del límite necesita conocer su sucesor consecutivo \(p_2\). Después recorren la lista primo a primo y se detienen cuando \(p_1\) alcanza el límite.
Para cada par, la implementación calcula \(M = 10^d\) contando las cifras decimales de \(p_1\). Como \(p_1 \lt 10^6\), siempre basta con \(d \le 6\). Luego calcula la inversa de \(p_2 \bmod M\): en C++ mediante el algoritmo extendido de Euclides, en Python con inversión modular incorporada y en Java con inversión modular sobre enteros grandes.
Después forma \(k_0 = (p_1 p_2^{-1}) \bmod M\), multiplica por \(p_2\) y añade el resultado a la suma acumulada. No se prueban candidatos y no se recorren múltiplos repetidos.
Si \(L\) es el límite del tamiz, generar los primos cuesta \(O(L \log \log L)\) en tiempo y \(O(L)\) en memoria. Una vez hecho eso, cada par consecutivo requiere solo un conteo de cifras y una inversa modular módulo \(10^d\), así que el costo por par es \(O(\log M)\) con \(M \le 10^6\), muy pequeño en este problema.
En la práctica domina el tamiz, mientras que la aritmética por par es mínima. La suma total además cabe sin problemas en enteros con signo de 64 bits para este límite, lo que explica que las implementaciones de anchura fija acumulen directamente el resultado.
对每一对相邻素数 \(p_1, p_2\)，其中 \(5 \le p_1 \le 10^6\)，定义 \(S(p_1,p_2)\) 为满足以下两个条件的最小正整数：它能被 \(p_2\) 整除，而且它的十进制末尾恰好是 \(p_1\) 的数字。题目要求把所有这样的 \(S(p_1,p_2)\) 相加。
如果按顺序去枚举 \(p_2\) 的倍数，虽然概念上简单，但完全没有必要。真正起作用的是“末尾等于 \(p_1\)”这一条件，它本质上只是一个关于十的幂的同余式，因此每一对素数都可以化成一次模逆运算。
设 \(d\) 是 \(p_1\) 的十进制位数，并记 \(M = 10^d\)。一个整数的最后 \(d\) 位等于 \(p_1\)，等价于说这个整数满足
$$n \equiv p_1 \pmod{M}.$$
实现采用的做法不是直接求 \(n\)，而是先把 \(n\) 写成 \(p_2\) 的倍数，再去解对应的乘子。
因为要求 \(n\) 能被 \(p_2\) 整除，所以可以写成
$$n = p_2 k,$$
其中 \(k\) 是正整数。把这个表达式代入后，末尾条件立刻变成
$$p_2 k \equiv p_1 \pmod{M}.$$
这就是三个实现真正求解的核心同余式。先求出合适的 \(k\)，再用 \(n = p_2 k\) 还原答案。
由于 \(p_1 \ge 5\)，而 \(p_2\) 是紧随其后的下一个素数，所以总有 \(p_2 \ge 7\)。这意味着 \(p_2\) 不会被 2 或 5 整除。另一方面，\(M = 10^d\) 的全部素因子只可能是 2 和 5。因此
$$\gcd(p_2, M) = 1.$$
既然 \(p_2\) 与 \(M\) 互素，\(p_2\) 在模 \(M\) 下就一定存在乘法逆元。于是把上面的同余式两边同时乘以 \(p_2^{-1}\)，得到
$$k \equiv p_1 \, p_2^{-1} \pmod{M}.$$
这样问题就从“找一个特殊的整数 \(n\)”变成了“找一个特定的剩余类 \(k\)”。
记 \(k_0\) 为 \(p_1 p_2^{-1}\) 在模 \(M\) 下的最小正剩余。那么所有满足条件的乘子都可以写成
$$k = k_0 + tM \qquad (t \ge 0).$$
对应的所有合法整数就是
$$n = p_2(k_0 + tM) = p_2 k_0 + t(p_2 M).$$
由于每增加 1 个 \(t\)，数值都会增加正量 \(p_2 M\)，所以最小解必然在 \(t = 0\) 处取得。于是有
$$\boxed{S(p_1,p_2) = p_2 \left( (p_1 p_2^{-1}) \bmod M \right).}$$
这不是抽象推导后的附加结论，而正是实现里对每一对素数实际计算和累加的量。
当 \(p_1 = 19\) 时，位数 \(d = 2\)，因此 \(M = 100\)。我们需要解
$$23k \equiv 19 \pmod{100}.$$
\(23\) 在模 \(100\) 下的逆元是 \(87\)，因为
$$23 \cdot 87 = 2001 \equiv 1 \pmod{100}.$$
所以
$$k_0 \equiv 19 \cdot 87 \equiv 53 \pmod{100}.$$
最小答案就是
$$S(19,23) = 23 \cdot 53 = 1219.$$
检查一下就知道这个结果完全正确：\(1219\) 能被 \(23\) 整除，而且最后两位正好是 \(19\)。
也可以从另一侧切入，把答案写成
$$n = p_1 + Mt,$$
然后解
$$Mt \equiv -p_1 \pmod{p_2}.$$
这会用到 \(M\) 在模 \(p_2\) 下的逆元。它与上面的推导完全等价，只是实现没有选择这条路线，因为程序本来就把目标数看成“\(p_2\) 的某个最小合适倍数”。
实现不会只筛到 \(10^6\) 为止，而是会继续向后筛出一段范围。原因很直接：对于每个 \(p_1 \lt 10^6\)，都必须知道它后面的那个相邻素数 \(p_2\)。如果只保留界内素数，就无法处理最靠近上界的那些对。
拿到一对 \((p_1,p_2)\) 后，程序先通过十进制位数得到 \(M = 10^d\)。因为这里始终有 \(p_1 \lt 10^6\)，所以只会出现 \(d \le 6\) 的情况。接着计算 \(p_2 \bmod M\) 的逆元：C++ 版本使用扩展欧几里得算法，Python 版本直接调用语言内置的模逆能力，Java 版本则用大整数提供的模逆运算。
随后程序形成最小正剩余 \(k_0 = (p_1 p_2^{-1}) \bmod M\)，再计算 \(p_2 k_0\) 并加入总和。整个过程中没有枚举候选答案，也没有沿着 \(p_2\) 的倍数链向上试探。
如果把筛法上界记为 \(L\)，那么生成素数的时间复杂度是 \(O(L \log \log L)\)，空间复杂度是 \(O(L)\)。筛完之后，对每一对相邻素数所做的工作只包括位数统计和一次模 \(10^d\) 的逆元计算，因此单对成本是 \(O(\log M)\)，而这里 \(M \le 10^6\)，所以这部分非常小。
实际运行时，主要耗时来自筛法，而不是后面的数论计算。总和在这个数据范围内也可以安全放进有符号 64 位整数，因此定长整数实现可以直接累计，不需要额外的大数求和逻辑。
Для каждой пары последовательных простых чисел \(p_1, p_2\), где \(5 \le p_1 \le 10^6\), обозначим через \(S(p_1,p_2)\) наименьшее положительное число, которое делится на \(p_2\) и оканчивается в десятичной записи цифрами числа \(p_1\). Нужно просуммировать все такие значения \(S(p_1,p_2)\).
Перебирать кратные \(p_2\) одно за другим не нужно. Условие на последние цифры есть обычное сравнение по модулю степени десяти, поэтому каждая пара простых сводится к одной модульной обратной и одному умножению.
Пусть \(d\) — число десятичных цифр в \(p_1\), а \(M = 10^d\). Тогда требование «число оканчивается цифрами \(p_1\)» означает
$$n \equiv p_1 \pmod{M}.$$
Реализации идут не от самого \(n\), а от его представления как кратного следующему простому.
Если \(n\) делится на \(p_2\), то
$$n = p_2 k$$
для некоторого положительного целого \(k\). Подставляя это в условие на суффикс, получаем
$$p_2 k \equiv p_1 \pmod{M}.$$
Именно эту конгруэнцию и решают реализации. Сначала находится подходящий множитель \(k\), а затем ответ восстанавливается как \(n = p_2 k\).
Так как \(p_1 \ge 5\), а \(p_2\) — следующий после него простой, всегда выполняется \(p_2 \ge 7\). Значит, \(p_2\) не делится ни на 2, ни на 5. В то же время \(M = 10^d\) имеет только простые множители 2 и 5. Следовательно,
$$\gcd(p_2, M) = 1,$$
и у числа \(p_2\) существует мультипликативный обратный по модулю \(M\). Умножая конгруэнцию на этот обратный элемент, получаем
$$k \equiv p_1 \, p_2^{-1} \pmod{M}.$$
Обозначим через \(k_0\) наименьший положительный остаток числа \(p_1 p_2^{-1}\) по модулю \(M\). Тогда все допустимые множители имеют вид
$$k = k_0 + tM \qquad (t \ge 0),$$
а все допустимые числа — вид
$$n = p_2(k_0 + tM) = p_2 k_0 + t(p_2 M).$$
Поскольку шаг \(p_2 M\) положителен, наименьшее допустимое число получается при \(t = 0\). Отсюда
$$\boxed{S(p_1,p_2) = p_2 \left( (p_1 p_2^{-1}) \bmod M \right).}$$
Именно эту величину суммируют реализации на C++, Python и Java.
Здесь \(d = 2\), значит \(M = 100\). Нужно решить
$$23k \equiv 19 \pmod{100}.$$
Обратный к \(23\) по модулю \(100\) равен \(87\), потому что
$$23 \cdot 87 = 2001 \equiv 1 \pmod{100}.$$
Следовательно,
$$k_0 \equiv 19 \cdot 87 \equiv 53 \pmod{100},$$
и минимальный ответ равен
$$S(19,23) = 23 \cdot 53 = 1219.$$
Проверка проста: \(1219\) делится на \(23\) и оканчивается цифрами \(19\).
Можно пойти и с другой стороны, записав
$$n = p_1 + Mt$$
и решая
$$Mt \equiv -p_1 \pmod{p_2}.$$
Тогда используется обратный элемент к \(M\) по модулю \(p_2\). Это полностью эквивалентно, но реализации выбирают предыдущую форму, потому что в ней ответ сразу представляется как кратное \(p_2\).
Сначала реализации строят таблицу простых чисел не только до \(10^6\), но и немного дальше. Причина в том, что для каждого \(p_1\) ниже границы нужен следующий за ним простой \(p_2\). После этого список просматривается попарно, и цикл останавливается, когда \(p_1\) достигает заданного предела.
Для каждой пары программа определяет \(M = 10^d\), подсчитывая число десятичных цифр в \(p_1\). Поскольку \(p_1 \lt 10^6\), всегда достаточно \(d \le 6\). Затем вычисляется обратный элемент к \(p_2 \bmod M\): в C++ через расширенный алгоритм Евклида, в Python через встроенную модульную инверсию, а в Java через модульную инверсию больших целых.
После этого программа берет \(k_0 = (p_1 p_2^{-1}) \bmod M\), умножает на \(p_2\) и прибавляет результат к общей сумме. Никакого перебора кандидатов и никакого сканирования последовательных кратных не требуется.
Если верхняя граница решета равна \(L\), то построение простых чисел требует \(O(L \log \log L)\) времени и \(O(L)\) памяти. После этого для каждой последовательной пары простых выполняются лишь подсчет цифр и одна модульная обратная по модулю \(10^d\), то есть \(O(\log M)\) операций при \(M \le 10^6\), что здесь очень мало.
Следовательно, реальное время работы определяется решетом, а не арифметикой по парам. Итоговая сумма тоже уверенно помещается в знаковый 64-битный тип для данного диапазона, поэтому реализации с фиксированной разрядностью могут накапливать ее напрямую.
لكل زوج من الأعداد الأولية المتتالية \(p_1, p_2\) بحيث \(5 \le p_1 \le 10^6\)، نعرّف \(S(p_1,p_2)\) بأنه أصغر عدد صحيح موجب يقبل القسمة على \(p_2\) وينتهي تمثيله العشري برقمَي أو أرقام \(p_1\). المطلوب هو جمع هذه القيم على جميع الأزواج المتتالية الممكنة.
ليس من الحكمة فحص مضاعفات \(p_2\) واحدًا بعد الآخر. شرط النهاية العشرية ليس إلا علاقة توافق بترديد قوة من قوى العشرة، ولذلك يمكن حل كل زوج بأخذ معكوس معياري واحد ثم إجراء ضرب واحد.
ليكن \(d\) هو عدد الخانات العشرية في \(p_1\)، ولنعرف \(M = 10^d\). القول بأن عددًا ما ينتهي بأرقام \(p_1\) يكافئ الشرط
$$n \equiv p_1 \pmod{M}.$$
التنفيذ لا يبدأ من \(n\) مباشرة، بل يعيد كتابة \(n\) على صورة مضاعف للعدد الأولي التالي \(p_2\).
إذا كان \(n\) يقبل القسمة على \(p_2\)، فلابد أن
$$n = p_2 k$$
لبعض العدد الصحيح الموجب \(k\). عند التعويض في شرط النهاية نحصل على
$$p_2 k \equiv p_1 \pmod{M}.$$
هذه هي علاقة التوافق الأساسية التي تحلها التطبيقات. أي أن البرنامج يبحث أولًا عن المضاعِف \(k\)، ثم يبني الجواب في النهاية بوصفه \(n = p_2 k\).
بما أن \(p_1 \ge 5\) و\(p_2\) هو العدد الأولي التالي له، فإن \(p_2 \ge 7\) دائمًا. لذلك لا يمكن أن يكون \(p_2\) قابلًا للقسمة على 2 أو 5، بينما \(M = 10^d\) لا يملك إلا العاملين الأوليين 2 و5. ومن ثم
$$\gcd(p_2, M) = 1.$$
وحين يكون العددان متباينين نسبيًا يوجد معكوس ضربي لـ \(p_2\) بترديد \(M\). وبضرب طرفي علاقة التوافق في هذا المعكوس نحصل على
$$k \equiv p_1 \, p_2^{-1} \pmod{M}.$$
لنرمز بـ \(k_0\) إلى أصغر باقي موجب لـ \(p_1 p_2^{-1}\) بترديد \(M\). عندئذٍ تكون جميع المضاعِفات الصحيحة الموافقة
$$k = k_0 + tM \qquad (t \ge 0),$$
وجميع الأعداد الصالحة هي
$$n = p_2(k_0 + tM) = p_2 k_0 + t(p_2 M).$$
بما أن الزيادة في كل خطوة تساوي \(p_2 M\) وهي كمية موجبة، فإن أصغر قيمة ممكنة تتحقق عندما \(t = 0\). لذلك
$$\boxed{S(p_1,p_2) = p_2 \left( (p_1 p_2^{-1}) \bmod M \right).}$$
وهذه بالضبط هي الصيغة التي تجمعها تطبيقات C++ وPython وJava.
في هذا المثال \(d = 2\)، ومن ثم \(M = 100\). نحتاج إلى حل
$$23k \equiv 19 \pmod{100}.$$
المعكوس المعياري لـ \(23\) بترديد \(100\) هو \(87\)، لأن
$$23 \cdot 87 = 2001 \equiv 1 \pmod{100}.$$
إذن
$$k_0 \equiv 19 \cdot 87 \equiv 53 \pmod{100},$$
ومن ثم
$$S(19,23) = 23 \cdot 53 = 1219.$$
والتحقق مباشر: \(1219\) يقبل القسمة على \(23\)، وينتهي فعلًا بالرقمين \(19\).
يمكن أيضًا كتابة
$$n = p_1 + Mt$$
ثم حل
$$Mt \equiv -p_1 \pmod{p_2}.$$
هذه الصياغة تستعمل معكوس \(M\) بترديد \(p_2\). وهي مكافئة تمامًا من الناحية الرياضية، لكن التنفيذ يفضّل الصياغة السابقة لأنه ينظر إلى الجواب أساسًا بوصفه أصغر مضاعف مناسب لـ \(p_2\).
تبدأ التطبيقات ببناء جدول للأعداد الأولية يتجاوز \(10^6\)، وليس فقط حتى \(10^6\). والسبب أن كل \(p_1\) أصغر من الحد يحتاج إلى معرفة العدد الأولي التالي له \(p_2\). بعد ذلك تُفحص القائمة على شكل أزواج متتالية، ويتوقف المرور عندما يصل \(p_1\) إلى الحد المطلوب.
لكل زوج، تُحسب أولًا القيمة \(M = 10^d\) عبر عدّ الخانات العشرية في \(p_1\). وبما أن \(p_1 \lt 10^6\)، فلا نحتاج إلا إلى \(d \le 6\). ثم يُحسب معكوس \(p_2 \bmod M\): نسخة C++ تستخدم خوارزمية إقليدس الموسعة، ونسخة Python تستخدم المعكوس المعياري المدمج، ونسخة Java تستخدم معكوسًا معياريًا على أعداد صحيحة كبيرة.
بعد ذلك تُكوَّن القيمة \(k_0 = (p_1 p_2^{-1}) \bmod M\)، ثم تُضرب في \(p_2\) وتُضاف إلى المجموع. لا يوجد أي تعداد لمرشحين، ولا أي مسح متكرر لمضاعفات \(p_2\).
إذا رمزنا إلى حد الغربلة بـ \(L\)، فإن توليد الأعداد الأولية يكلف \(O(L \log \log L)\) زمنًا و\(O(L)\) ذاكرة. بعد ذلك، يحتاج كل زوج متتالٍ من الأعداد الأولية فقط إلى حساب عدد الخانات وأخذ معكوس معياري بترديد \(10^d\)، أي \(O(\log M)\) مع \(M \le 10^6\)، وهي تكلفة صغيرة جدًا هنا.
عمليًا، الجزء الغالب في الزمن هو الغربلة، أما الحساب العددي لكل زوج فهو خفيف للغاية. كما أن المجموع النهائي يبقى ضمن مجال الأعداد الصحيحة الموقعة ذات 64 بت لهذا الحد، ولهذا تستطيع التطبيقات ذات العرض الثابت تجميع النتيجة مباشرة.