Let \(p_1,p_2,\dots,p_m\) be the first \(m\) primes strictly larger than a huge starting value \(A\). The task is to compute
$$\sum_{i=1}^{m}F_{p_i}\pmod{M},$$
where \(F_n\) is the Fibonacci sequence and the official parameters are extremely large.
The primes we need live near \(A\approx 10^{14}\). A naive primality test for each number in that region would be far too slow, and a full sieve up to \(A\) is impossible in memory. The right tool is a segmented sieve.
We scan blocks
$$[L,H],$$
and mark composites inside that block using all base primes up to \(\sqrt{H}\).
If \(x\in [L,H]\) is composite, then \(x=ab\) with \(1<a\le b\). Hence
$$a\le \sqrt{x}\le \sqrt{H}.$$
So every composite in the segment has a prime divisor not exceeding \(\sqrt{H}\). Therefore, after marking multiples of all primes \(p\le \sqrt{H}\), every remaining unmarked number in the segment is prime.
For a fixed base prime \(p\), the first multiple of \(p\) inside the current segment is
$$\left\lceil\frac{L}{p}\right\rceil p.$$
But we must also avoid marking the prime \(p\) itself when \(p\in[L,H]\). Therefore the correct starting point is
$$\max\!\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right).$$
This is exactly what the code computes before it walks through the segment in steps of \(p\).
Once the prime indices \(p_i\) are known, we still cannot generate Fibonacci numbers linearly up to index \(10^{14}\). The code instead computes \((F_n,F_{n+1})\) with fast doubling.
Using the addition formulas
$$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n,$$
and substituting \(m=n=k\), one obtains the standard doubling identities
$$F_{2k}=F_k(2F_{k+1}-F_k),$$
$$F_{2k+1}=F_k^2+F_{k+1}^2.$$
Thus from \((F_k,F_{k+1})\) we can compute \((F_{2k},F_{2k+1})\), and then decide whether \(n\) is even or odd. Each recursive step halves the index, so the running time is \(O(\log n)\).
All arithmetic is needed only modulo \(M\). Since Fibonacci recurrences use only addition, subtraction, and multiplication, we may reduce after every operation:
$$F_n \bmod M$$
can be computed without ever forming the enormous exact integer \(F_n\). This is why the solution remains fast even though the indices are gigantic.
The C++ code contains a cross-check on a much smaller range:
$$A=1000,\qquad m=30,\qquad M=10^9+7.$$
The first few primes after \(1000\) are
$$1009,\ 1013,\ 1019,\ 1021,\ 1031,\dots$$
and the corresponding Fibonacci residues begin as
$$F_{1009}\equiv 529241575,\qquad F_{1013}\equiv 613716502,\qquad F_{1019}\equiv 506824938\pmod{10^9+7}.$$
For the first \(30\) such primes, the checkpoint sum is
$$\sum_{i=1}^{30}F_{p_i}\equiv 682050181\pmod{10^9+7}.$$
The program compares its segmented-sieve result with a brute-force prime search on that small input.
Because the main search scans segments whose upper endpoint is roughly \(A+\text{segment\_size}\), it is enough to precompute base primes up to a safe constant slightly larger than
$$\sqrt{A+\text{segment\_size}}.$$
For \(A\approx 10^{14}\), this is about \(10^7\), which explains the base-prime sieve limit used in the implementations.
The solver has three clean stages:
1. generate base primes with an ordinary sieve up to a safe square-root bound;
2. run a segmented sieve to extract the first \(m\) primes after \(A\);
3. compute each \(F_{p_i}\bmod M\) by fast doubling and accumulate the sum modulo \(M\).
The helper fib_pair_mod(n, mod) returns \((F_n,F_{n+1})\), so each prime index is handled independently in logarithmic time.
The segmented sieve is essentially linear in the total length of the scanned blocks, up to the usual harmonic marking cost from small primes. The Fibonacci part costs
$$O(m\log A),$$
because each of the \(m\) prime indices needs one logarithmic fast-doubling evaluation. Memory usage is modest: one segment bitmap plus the base-prime list.
Seien \(p_1,p_2,\dots,p_m\) die ersten \(m\) Primzahlen, die strikt größer als ein sehr großes \(A\) sind. Gesucht ist
$$\sum_{i=1}^{m}F_{p_i}\pmod{M},$$
wobei \(F_n\) die Fibonacci-Folge bezeichnet.
Die gesuchten Primzahlen liegen in der Nähe von \(A\approx 10^{14}\). Einzelne Primzahltests in dieser Region wären zu langsam, und ein vollständiges Sieb bis \(A\) wäre speichertechnisch unmöglich. Deshalb verwendet man ein segmentiertes Sieb.
Man durchsucht Blöcke
$$[L,H]$$
und markiert in jedem Block die zusammengesetzten Zahlen mit Hilfe aller Basisprimzahlen bis \(\sqrt{H}\).
Ist \(x\in[L,H]\) zusammengesetzt, dann gilt \(x=ab\) mit \(1<a\le b\). Also
$$a\le \sqrt{x}\le \sqrt{H}.$$
Jede zusammengesetzte Zahl des Segments besitzt also einen Primteiler \(\le \sqrt{H}\). Nach dem Markieren aller Vielfachen solcher Primzahlen bleibt deshalb genau die Menge der Primzahlen unmarkiert.
Für eine feste Basisprimzahl \(p\) ist das erste Vielfache im aktuellen Segment
$$\left\lceil\frac{L}{p}\right\rceil p.$$
Allerdings darf man \(p\) selbst nicht markieren, falls \(p\in[L,H]\) liegt. Daher ist der richtige Startpunkt
$$\max\!\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right).$$
Genau diesen Ausdruck verwendet der Code, bevor er mit Schrittweite \(p\) durch den Block läuft.
Sobald die Primindizes \(p_i\) bekannt sind, kann man die Fibonacci-Zahlen trotzdem nicht linear bis Index \(10^{14}\) erzeugen. Deshalb berechnet der Code \((F_n,F_{n+1})\) mit Fast Doubling.
Aus den Additionsformeln
$$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$$
folgen für \(m=n=k\) die Standardidentitäten
$$F_{2k}=F_k(2F_{k+1}-F_k),$$
$$F_{2k+1}=F_k^2+F_{k+1}^2.$$
Damit lässt sich aus \((F_k,F_{k+1})\) das Paar \((F_{2k},F_{2k+1})\) bestimmen; anschließend entscheidet man je nach Parität von \(n\). Jeder Schritt halbiert den Index, also kostet eine Auswertung nur \(O(\log n)\).
Benötigt werden nur Werte modulo \(M\). Da die Fibonacci-Rekursionen ausschließlich Addition, Subtraktion und Multiplikation verwenden, darf man nach jeder Operation reduzieren. So kann
$$F_n \bmod M$$
berechnet werden, ohne jemals die gigantische exakte Zahl \(F_n\) aufzubauen.
Der C++-Code enthält einen Quercheck auf einem kleinen Beispiel:
$$A=1000,\qquad m=30,\qquad M=10^9+7.$$
Die ersten Primzahlen nach \(1000\) sind
$$1009,\ 1013,\ 1019,\ 1021,\ 1031,\dots$$
und die zugehörigen Fibonacci-Reste beginnen mit
$$F_{1009}\equiv 529241575,\qquad F_{1013}\equiv 613716502,\qquad F_{1019}\equiv 506824938\pmod{10^9+7}.$$
Für die ersten \(30\) solchen Primzahlen lautet die Prüfsumme
$$\sum_{i=1}^{30}F_{p_i}\equiv 682050181\pmod{10^9+7}.$$
Das Programm vergleicht hier das segmentierte Sieb mit einer Brute-Force-Primzahlprüfung.
Da die Hauptsuche Segmente mit oberer Grenze ungefähr \(A+\text{segment\_size}\) betrachtet, genügt es, Basisprimzahlen bis zu einer sicheren Konstante etwas oberhalb von
$$\sqrt{A+\text{segment\_size}}$$
vorzuberechnen. Für \(A\approx 10^{14}\) liegt das in der Größenordnung \(10^7\), was die in den Implementierungen gewählte Siebgrenze erklärt.
Der Solver zerfällt in drei Stufen:
1. Basisprimzahlen mit einem gewöhnlichen Sieb bis zu einer sicheren Wurzelgrenze erzeugen;
2. mit einem segmentierten Sieb die ersten \(m\) Primzahlen nach \(A\) extrahieren;
3. für jedes \(p_i\) den Wert \(F_{p_i}\bmod M\) per Fast Doubling berechnen und modulo \(M\) aufsummieren.
Die Hilfsfunktion fib_pair_mod(n, mod) gibt \((F_n,F_{n+1})\) zurück, sodass jeder Primindex unabhängig in logarithmischer Zeit behandelt wird.
Das segmentierte Sieb ist im Wesentlichen linear in der Gesamtlänge der gescannten Blöcke, abgesehen vom üblichen harmonischen Markierungsaufwand kleiner Primzahlen. Der Fibonacci-Teil kostet
$$O(m\log A),$$
weil für jeden der \(m\) Primindizes genau eine logarithmische Fast-Doubling-Auswertung nötig ist. Der Speicherbedarf bleibt moderat: ein Segment-Bitfeld plus Liste der Basisprimzahlen.
\(p_1,p_2,\dots,p_m\), çok büyük bir \(A\) değerinden sonra gelen ilk \(m\) asal olsun. Hesaplanmak istenen ifade
$$\sum_{i=1}^{m}F_{p_i}\pmod{M}$$
şeklindedir; burada \(F_n\) Fibonacci dizisidir.
Aradığımız asallar \(A\approx 10^{14}\) civarındadır. Bu bölgede her sayı için tek tek asal testi yapmak çok pahalıdır; \(A\)'ya kadar tam sieve yapmak ise bellek açısından imkânsızdır. Bu yüzden doğru araç segmentli sieve'dir.
Arama bloklar halinde yapılır:
$$[L,H].$$
Her blokta, \(\sqrt{H}\)'e kadar olan temel asalların katları işaretlenir.
Eğer \(x\in[L,H]\) bileşik ise \(x=ab\) olacak şekilde \(1<a\le b\) yazılabilir. O hâlde
$$a\le \sqrt{x}\le \sqrt{H}.$$
Yani segment içindeki her bileşik sayının \(\sqrt{H}\)'den büyük olmayan bir asal böleni vardır. Dolayısıyla \(p\le \sqrt{H}\) tüm asalların katları işaretlenince, işaretsiz kalanlar tam olarak asallardır.
Sabit bir temel asal \(p\) için, segment içindeki ilk kat
$$\left\lceil\frac{L}{p}\right\rceil p$$
olur. Ancak \(p\) kendisi segmentin içindeyse onu yanlışlıkla bileşik diye işaretlememek gerekir. Bu yüzden doğru başlangıç noktası
$$\max\!\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right)$$
şeklindedir. Kod tam olarak bu formülü kullanıp sonra \(p\) adımlarıyla ilerler.
Asal indisler \(p_i\) bulunsa bile, Fibonacci dizisini \(10^{14}\) mertebesine kadar doğrusal üretmek mümkün değildir. Bunun yerine kod \((F_n,F_{n+1})\) çiftini fast doubling ile hesaplar.
Toplama özdeşliği
$$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$$
kullanılıp \(m=n=k\) yazılınca standart ikiye katlama formülleri elde edilir:
$$F_{2k}=F_k(2F_{k+1}-F_k),$$
$$F_{2k+1}=F_k^2+F_{k+1}^2.$$
Böylece \((F_k,F_{k+1})\)'den \((F_{2k},F_{2k+1})\) bulunur; sonra \(n\)'nin tek/çift oluşuna göre doğru çift seçilir. Her adım indeksi ikiye böldüğü için karmaşıklık \(O(\log n)\)'dir.
Bize yalnızca mod \(M\) sonucu gerekir. Fibonacci bağıntılarında sadece toplama, çıkarma ve çarpma vardır; bu yüzden her işlemden sonra mod alınabilir. Yani
$$F_n \bmod M$$
değeri, devasa tam sayı \(F_n\)'yi hiç oluşturmadan hesaplanabilir.
C++ kodu daha küçük bir örnekte brute-force karşılaştırması yapar:
$$A=1000,\qquad m=30,\qquad M=10^9+7.$$
\(1000\)'den sonraki ilk birkaç asal
$$1009,\ 1013,\ 1019,\ 1021,\ 1031,\dots$$
şeklindedir ve bunların Fibonacci kalıntıları şu şekilde başlar:
$$F_{1009}\equiv 529241575,\qquad F_{1013}\equiv 613716502,\qquad F_{1019}\equiv 506824938\pmod{10^9+7}.$$
Bu aralıkta ilk \(30\) asal için toplam checkpoint değeri
$$\sum_{i=1}^{30}F_{p_i}\equiv 682050181\pmod{10^9+7}$$
olur. Kod, segmentli sieve sonucunu küçük aralıkta brute-force asal bulmayla karşılaştırır.
Ana arama, üst ucu yaklaşık \(A+\text{segment\_size}\) olan segmentleri gezdiği için, temel asalları biraz güvenli pay bırakarak
$$\sqrt{A+\text{segment\_size}}$$
üstüne kadar üretmek yeterlidir. \(A\approx10^{14}\) için bu değer yaklaşık \(10^7\) mertebesindedir; implementasyonlardaki base-prime sınırı bu yüzden o büyüklüktedir.
Çözüm üç temiz aşamadan oluşur:
1. güvenli karekök sınırına kadar normal sieve ile temel asalları üretmek;
2. segmentli sieve ile \(A\)'dan sonraki ilk \(m\) asalı çıkarmak;
3. her \(p_i\) için \(F_{p_i}\bmod M\) değerini fast doubling ile hesaplayıp toplamı mod \(M\) altında biriktirmek.
fib_pair_mod(n, mod) yardımcı fonksiyonu \((F_n,F_{n+1})\) döndürdüğü için her asal indis bağımsız ve logaritmik sürede işlenir.
Segmentli sieve, küçük asalların harmonik işaretleme maliyeti dışında toplam taranan blok uzunluğuna göre esasen doğrusaldır. Fibonacci kısmı ise
$$O(m\log A)$$
maliyetlidir; çünkü \(m\) asal indisin her biri için bir adet logaritmik fast-doubling hesabı yapılır. Bellek kullanımı düşüktür: bir segmentlik bit dizisi ve temel asal listesi.
Sean \(p_1,p_2,\dots,p_m\) los primeros \(m\) primos estrictamente mayores que un valor enorme \(A\). Hay que calcular
$$\sum_{i=1}^{m}F_{p_i}\pmod{M},$$
donde \(F_n\) es la sucesión de Fibonacci.
Los primos buscados viven cerca de \(A\approx 10^{14}\). Probar primalidad uno por uno en esa zona sería demasiado lento, y una criba completa hasta \(A\) sería imposible en memoria. Por eso se usa una criba segmentada.
Se recorren bloques
$$[L,H],$$
y dentro de cada bloque se marcan los compuestos usando todos los primos base hasta \(\sqrt{H}\).
Si \(x\in[L,H]\) es compuesto, entonces \(x=ab\) con \(1<a\le b\). Por tanto,
$$a\le \sqrt{x}\le \sqrt{H}.$$
Así, todo compuesto del segmento tiene un divisor primo no mayor que \(\sqrt{H}\). Después de marcar los múltiplos de todos los primos \(p\le \sqrt{H}\), lo que queda sin marcar en el bloque son exactamente los primos.
Para un primo base fijo \(p\), el primer múltiplo de \(p\) dentro del segmento actual es
$$\left\lceil\frac{L}{p}\right\rceil p.$$
Pero además hay que evitar marcar al propio \(p\) si cae dentro del bloque. Por eso el punto de inicio correcto es
$$\max\!\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right).$$
Eso es exactamente lo que calcula el código antes de avanzar de \(p\) en \(p\).
Una vez conocidos los índices primos \(p_i\), todavía no podemos generar Fibonacci linealmente hasta \(10^{14}\). En su lugar, el código calcula \((F_n,F_{n+1})\) con fast doubling.
A partir de la fórmula de suma
$$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n,$$
y poniendo \(m=n=k\), se obtienen las identidades estándar
$$F_{2k}=F_k(2F_{k+1}-F_k),$$
$$F_{2k+1}=F_k^2+F_{k+1}^2.$$
Así, a partir de \((F_k,F_{k+1})\) se calcula \((F_{2k},F_{2k+1})\), y luego se decide según la paridad de \(n\). Cada paso divide el índice entre dos, así que el coste es \(O(\log n)\).
Solo necesitamos el resultado módulo \(M\). Como las recurrencias de Fibonacci usan suma, resta y multiplicación, podemos reducir tras cada operación. En otras palabras,
$$F_n \bmod M$$
se puede obtener sin construir nunca el entero gigantesco \(F_n\).
El código C++ contiene una verificación en una instancia pequeña:
$$A=1000,\qquad m=30,\qquad M=10^9+7.$$
Los primeros primos después de \(1000\) son
$$1009,\ 1013,\ 1019,\ 1021,\ 1031,\dots$$
y los residuos de Fibonacci correspondientes comienzan con
$$F_{1009}\equiv 529241575,\qquad F_{1013}\equiv 613716502,\qquad F_{1019}\equiv 506824938\pmod{10^9+7}.$$
Para los primeros \(30\) primos de ese rango, la suma de control es
$$\sum_{i=1}^{30}F_{p_i}\equiv 682050181\pmod{10^9+7}.$$
El programa compara ahí la salida de la criba segmentada con una búsqueda de primos por fuerza bruta.
Como la búsqueda principal examina segmentos cuyo extremo superior es aproximadamente \(A+\text{segment\_size}\), basta con precomputar primos base hasta una cota segura un poco mayor que
$$\sqrt{A+\text{segment\_size}}.$$
Para \(A\approx 10^{14}\), esto está en torno a \(10^7\), lo que explica el límite de criba elegido en las implementaciones.
El solver tiene tres etapas claras:
1. generar primos base con una criba ordinaria hasta una cota segura de raíz cuadrada;
2. usar una criba segmentada para extraer los primeros \(m\) primos después de \(A\);
3. calcular cada \(F_{p_i}\bmod M\) mediante fast doubling y acumular la suma módulo \(M\).
La función auxiliar fib_pair_mod(n, mod) devuelve \((F_n,F_{n+1})\), por lo que cada índice primo se procesa de manera independiente en tiempo logarítmico.
La criba segmentada es esencialmente lineal en la longitud total de los bloques recorridos, salvo el coste armónico habitual de marcar con primos pequeños. La parte Fibonacci cuesta
$$O(m\log A),$$
porque cada uno de los \(m\) índices primos requiere una evaluación fast-doubling logarítmica. El uso de memoria es moderado: un bitmap de segmento y la lista de primos base.
设 \(p_1,p_2,\dots,p_m\) 为严格大于某个巨大起点 \(A\) 的前 \(m\) 个素数。要求计算
$$\sum_{i=1}^{m}F_{p_i}\pmod{M},$$
其中 \(F_n\) 是 Fibonacci 数列。
我们需要的素数位于 \(A\approx 10^{14}\) 附近。在这个量级上，对每个数单独做素性测试太慢，而把筛法直接开到 \(A\) 又完全不现实。正确做法是分段筛。
也就是分块扫描区间
$$[L,H],$$
并用所有不超过 \(\sqrt{H}\) 的基素数去标记这一块中的合数。
如果 \(x\in[L,H]\) 是合数，那么 \(x=ab\)，其中 \(1<a\le b\)。因此
$$a\le \sqrt{x}\le \sqrt{H}.$$
这说明，段内每个合数都至少有一个不超过 \(\sqrt{H}\) 的素因子。所以当我们把所有 \(p\le \sqrt{H}\) 的倍数都标掉后，剩下未标记的数就一定是素数。
对固定基素数 \(p\)，当前段内第一个 \(p\) 的倍数是
$$\left\lceil\frac{L}{p}\right\rceil p.$$
但如果 \(p\) 本身落在区间 \([L,H]\) 内，就不能把它误标为合数。因此真正的起点应取
$$\max\!\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right).$$
代码正是这样做的，然后按步长 \(p\) 一路标记下去。
即使已经知道了素数下标 \(p_i\)，也不能线性地把 Fibonacci 一直推到 \(10^{14}\)。所以代码改为用 fast doubling 计算 \((F_n,F_{n+1})\)。
由加法恒等式
$$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$$
令 \(m=n=k\)，可得到标准倍增公式
$$F_{2k}=F_k(2F_{k+1}-F_k),$$
$$F_{2k+1}=F_k^2+F_{k+1}^2.$$
因此从 \((F_k,F_{k+1})\) 可以直接得到 \((F_{2k},F_{2k+1})\)，再根据 \(n\) 的奇偶决定结果。每一步都把下标减半，所以复杂度是 \(O(\log n)\)。
我们只关心模 \(M\) 的结果。由于 Fibonacci 递推里只出现加法、减法和乘法，所以每一步都可以直接取模。也就是说，
$$F_n \bmod M$$
可以在从不显式构造巨大整数 \(F_n\) 的情况下算出来。
C++ 代码里放了一个小范围的交叉校验：
$$A=1000,\qquad m=30,\qquad M=10^9+7.$$
\(1000\) 之后的前几个素数是
$$1009,\ 1013,\ 1019,\ 1021,\ 1031,\dots$$
对应的 Fibonacci 模值开头是
$$F_{1009}\equiv 529241575,\qquad F_{1013}\equiv 613716502,\qquad F_{1019}\equiv 506824938\pmod{10^9+7}.$$
对前 \(30\) 个这样的素数，校验和为
$$\sum_{i=1}^{30}F_{p_i}\equiv 682050181\pmod{10^9+7}.$$
程序在这个小例子上把分段筛的结果与暴力找素数的结果进行比较。
因为主过程扫描的段上端大致在 \(A+\text{segment\_size}\) 附近，所以只需要把基素数预处理到一个略大于
$$\sqrt{A+\text{segment\_size}}$$
的安全常数即可。对 \(A\approx 10^{14}\) 来说，这个数量级约为 \(10^7\)，这就是实现中基筛上界的来源。
整个求解分成三个清晰步骤：
1. 先用普通筛法生成到安全平方根上界为止的基素数；
2. 再用分段筛提取 \(A\) 之后的前 \(m\) 个素数；
3. 对每个 \(p_i\) 用 fast doubling 计算 \(F_{p_i}\bmod M\)，并把结果在模 \(M\) 下累加。
辅助函数 fib_pair_mod(n, mod) 返回 \((F_n,F_{n+1})\)，因此每个素数下标都能独立地在对数时间里处理。
分段筛的时间基本与所扫描区间总长度线性相关，只额外带有小素数标记的调和级开销。Fibonacci 部分的复杂度为
$$O(m\log A),$$
因为每个素数下标都要做一次对数级 fast doubling 计算。空间消耗较小：一块段数组加上一张基素数表即可。
Пусть \(p_1,p_2,\dots,p_m\) — первые \(m\) простых чисел, строго больших огромного значения \(A\). Нужно вычислить
$$\sum_{i=1}^{m}F_{p_i}\pmod{M},$$
где \(F_n\) — последовательность Фибоначчи.
Нужные простые находятся около \(A\approx 10^{14}\). Проверять каждое число на простоту в этой области слишком дорого, а полное решето до \(A\) невозможно по памяти. Поэтому используется сегментированное решето.
Мы просматриваем блоки
$$[L,H]$$
и в каждом блоке помечаем составные числа с помощью всех базовых простых до \(\sqrt{H}\).
Если \(x\in[L,H]\) составно, то \(x=ab\) при \(1<a\le b\). Тогда
$$a\le \sqrt{x}\le \sqrt{H}.$$
Значит, каждое составное число сегмента имеет простой делитель не больше \(\sqrt{H}\). Следовательно, после пометки кратных всех простых \(p\le \sqrt{H}\) непомеченными останутся ровно простые числа.
Для фиксированного базового простого \(p\) первым кратным внутри текущего сегмента является
$$\left\lceil\frac{L}{p}\right\rceil p.$$
Но если сам \(p\) попадает в отрезок \([L,H]\), его нельзя пометить как составное. Поэтому правильная стартовая позиция равна
$$\max\!\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right).$$
Именно это выражение использует код, после чего идёт по сегменту шагом \(p\).
Даже зная простые индексы \(p_i\), нельзя линейно досчитать Фибоначчи до уровня \(10^{14}\). Поэтому код вычисляет пару \((F_n,F_{n+1})\) методом быстрого удвоения.
Из формулы сложения
$$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$$
при подстановке \(m=n=k\) получаются стандартные тождества
$$F_{2k}=F_k(2F_{k+1}-F_k),$$
$$F_{2k+1}=F_k^2+F_{k+1}^2.$$
То есть из \((F_k,F_{k+1})\) можно получить \((F_{2k},F_{2k+1})\), а затем выбрать нужный случай по чётности \(n\). На каждом шаге индекс делится пополам, поэтому время работы равно \(O(\log n)\).
Нужен только результат по модулю \(M\). Поскольку рекурсии Фибоначчи используют лишь сложение, вычитание и умножение, можно уменьшать по модулю после каждой операции. То есть
$$F_n \bmod M$$
вычисляется без построения огромного точного числа \(F_n\).
В C++-коде есть перекрёстная проверка на маленьком диапазоне:
$$A=1000,\qquad m=30,\qquad M=10^9+7.$$
Первые простые после \(1000\):
$$1009,\ 1013,\ 1019,\ 1021,\ 1031,\dots$$
а соответствующие остатки Фибоначчи начинаются так:
$$F_{1009}\equiv 529241575,\qquad F_{1013}\equiv 613716502,\qquad F_{1019}\equiv 506824938\pmod{10^9+7}.$$
Для первых \(30\) таких простых контрольная сумма равна
$$\sum_{i=1}^{30}F_{p_i}\equiv 682050181\pmod{10^9+7}.$$
На этом маленьком входе программа сравнивает сегментированное решето с brute-force поиском простых.
Так как основной проход смотрит сегменты с верхней границей примерно \(A+\text{segment\_size}\), достаточно заранее построить базовые простые до безопасной константы, немного превышающей
$$\sqrt{A+\text{segment\_size}}.$$
Для \(A\approx 10^{14}\) это порядка \(10^7\), что и объясняет выбранную в реализациях границу базового решета.
Решение делится на три этапа:
1. обычным решетом построить базовые простые до безопасной корневой границы;
2. сегментированным решетом извлечь первые \(m\) простых после \(A\);
3. для каждого \(p_i\) вычислить \(F_{p_i}\bmod M\) методом fast doubling и накопить сумму по модулю \(M\).
Вспомогательная функция fib_pair_mod(n, mod) возвращает \((F_n,F_{n+1})\), поэтому каждый простой индекс обрабатывается независимо за логарифмическое время.
Сегментированное решето по сути линейно по суммарной длине просмотренных блоков, с обычным гармоническим накладным расходом на пометки малыми простыми. Fibonacci-часть стоит
$$O(m\log A),$$
поскольку для каждого из \(m\) индексов требуется одна логарифмическая fast-doubling-оценка. Память остаётся небольшой: один сегментный массив и список базовых простых.
لتكن \(p_1,p_2,\dots,p_m\) أول \(m\) أعداد أولية أكبر من قيمة ضخمة \(A\). المطلوب حساب
$$\sum_{i=1}^{m}F_{p_i}\pmod{M},$$
حيث \(F_n\) هي متتالية فيبوناتشي.
الأعداد الأولية المطلوبة تقع قرب \(A\approx 10^{14}\). اختبار كل عدد هناك على حدة سيكون بطيئًا جدًا، أما بناء غربال كامل حتى \(A\) فغير ممكن من ناحية الذاكرة. لذلك نستخدم الغربال المقطعي.
نمسح المقاطع
$$[L,H],$$
وفي كل مقطع نعلّم الأعداد المركبة باستعمال جميع الأعداد الأولية الأساسية حتى \(\sqrt{H}\).
إذا كان \(x\in[L,H]\) عددًا مركبًا، فلدينا \(x=ab\) مع \(1<a\le b\). ومن ثم
$$a\le \sqrt{x}\le \sqrt{H}.$$
إذًا كل عدد مركب داخل المقطع يملك قاسمًا أوليًا لا يتجاوز \(\sqrt{H}\). لذلك، بعد تعليم مضاعفات جميع الأعداد الأولية \(p\le \sqrt{H}\)، فإن كل ما يبقى غير معلّم داخل المقطع يكون أوليًا.
بالنسبة إلى عدد أولي أساسي ثابت \(p\)، فإن أول مضاعف له داخل المقطع الحالي هو
$$\left\lceil\frac{L}{p}\right\rceil p.$$
لكن يجب أيضًا ألا نعلّم \(p\) نفسه إذا كان يقع داخل \([L,H]\). ولذلك تكون نقطة البداية الصحيحة
$$\max\!\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right).$$
وهذا هو بالضبط ما يحسبه الكود قبل أن يسير بخطوة \(p\) عبر المقطع.
حتى بعد معرفة الفهارس الأولية \(p_i\)، لا يمكننا توليد فيبوناتشي خطيًا حتى الرتبة \(10^{14}\). لذلك يحسب الكود الزوج \((F_n,F_{n+1})\) بطريقة Fast Doubling.
من صيغة الجمع
$$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$$
وبوضع \(m=n=k\) نحصل على الهويتين القياسيتين
$$F_{2k}=F_k(2F_{k+1}-F_k),$$
$$F_{2k+1}=F_k^2+F_{k+1}^2.$$
وبذلك يمكن الانتقال من \((F_k,F_{k+1})\) إلى \((F_{2k},F_{2k+1})\)، ثم نختار الحالة المناسبة بحسب زوجية \(n\). وكل خطوة تقسم الفهرس إلى النصف، ولذلك يكون الزمن \(O(\log n)\).
ما نحتاجه في النهاية هو النتيجة modulo \(M\) فقط. وبما أن علاقات فيبوناتشي تستخدم الجمع والطرح والضرب فقط، فيمكننا الاختزال modulo \(M\) بعد كل عملية. أي إن
$$F_n \bmod M$$
يمكن حسابه دون بناء العدد الضخم \(F_n\) نفسه.
يحتوي كود ++C على فحص تقاطعي في مثال أصغر:
$$A=1000,\qquad m=30,\qquad M=10^9+7.$$
وأول الأعداد الأولية بعد \(1000\) هي
$$1009,\ 1013,\ 1019,\ 1021,\ 1031,\dots$$
وتبدأ بواقي فيبوناتشي الموافقة لها كما يلي:
$$F_{1009}\equiv 529241575,\qquad F_{1013}\equiv 613716502,\qquad F_{1019}\equiv 506824938\pmod{10^9+7}.$$
أما مجموع أول \(30\) عددًا أوليًا من هذا النوع فيساوي
$$\sum_{i=1}^{30}F_{p_i}\equiv 682050181\pmod{10^9+7}.$$
وهنا يقارن البرنامج نتيجة الغربال المقطعي مع بحث brute-force عن الأعداد الأولية في هذا النطاق الصغير.
بما أن البحث الرئيسي يمسح مقاطع يكون حدها الأعلى تقريبًا \(A+\text{segment\_size}\)، فإنه يكفي تجهيز الأعداد الأولية الأساسية حتى ثابت آمن أكبر قليلًا من
$$\sqrt{A+\text{segment\_size}}.$$
وبالنسبة إلى \(A\approx 10^{14}\)، يكون هذا من رتبة \(10^7\)، ولهذا تظهر حدود الغربال الأساسية بهذا الحجم في التنفيذات.
ينقسم الحل إلى ثلاث مراحل واضحة:
1. توليد الأعداد الأولية الأساسية بغربال عادي حتى حد جذري آمن؛
2. استعمال الغربال المقطعي لاستخراج أول \(m\) عدد أولي بعد \(A\)؛
3. حساب \(F_{p_i}\bmod M\) لكل \(p_i\) بطريقة Fast Doubling ثم جمع النتائج modulo \(M\).
وتعيد الدالة المساعدة fib_pair_mod(n, mod) الزوج \((F_n,F_{n+1})\)، لذا يمكن معالجة كل فهرس أولي بشكل مستقل في زمن لوغاريتمي.
الغربال المقطعي شبه خطي في الطول الكلي للمقاطع المفحوصة، مع الكلفة التوافقية المعتادة لتعليم مضاعفات الأعداد الأولية الصغيرة. أما جزء فيبوناتشي فيكلف
$$O(m\log A),$$
لأن كل واحد من \(m\) الفهارس الأولية يحتاج إلى تقييم Fast Doubling لوغاريتمي واحد. استهلاك الذاكرة معتدل: مصفوفة مقطع واحدة وقائمة الأعداد الأولية الأساسية.