For a positive integer \(n\), let \(a=\sqrt{n}\) and define a recursion by
$$g_a(x)=\begin{cases} 1, & x<a,\\ g_a(x-1)+g_a(x-a), & x\ge a. \end{cases}$$
The quantity of interest is \(G(n)=g_a(n)\) with \(a=\sqrt n\). Problem 517 asks for
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ prime}}} G(p)\pmod{10^9+7}.$$
A naive recursive evaluation would branch explosively, so the solution turns the recursion into a direct combinatorial formula and then evaluates that formula for every prime in the interval.
The key observation is that every recursive branch corresponds to a sequence of jumps of size \(1\) and \(\sqrt n\). Counting leaves of the recursion tree is therefore the same as counting valid ordered jump patterns.
Start with remainder \(x=n\). Every recursive call replaces \(x\) by either \(x-1\) or \(x-\sqrt n\), and the branch stops as soon as the new remainder is \(<\sqrt n\).
Thus each leaf is an ordered sequence of two move types:
$$1\text{-step}: x\mapsto x-1,\qquad \sqrt n\text{-step}: x\mapsto x-\sqrt n.$$
If a branch uses \(k\) steps of size \(\sqrt n\), then automatically
$$k\sqrt n\le n,$$
so only
$$0\le k\le \left\lfloor\sqrt n\right\rfloor$$
can contribute.
Fix a branch using exactly \(k\) steps of size \(\sqrt n\). For \(r=1,\dots,k\), let \(s_r\) be the number of \(1\)-steps that have already occurred before the \(r\)-th \(\sqrt n\)-step is taken.
These numbers satisfy
$$0\le s_1\le s_2\le \cdots \le s_k,$$
because the total number of \(1\)-steps seen so far can only increase.
Before taking the \(r\)-th \(\sqrt n\)-step, the current remainder is
$$n-s_r-(r-1)\sqrt n.$$
That step is legal only if the recursion has not stopped yet, namely if this remainder is at least \(\sqrt n\). Therefore
$$n-s_r-(r-1)\sqrt n\ge \sqrt n,$$
so
$$s_r\le n-r\sqrt n.$$
Since \(s_r\) is an integer, this becomes
$$s_r\le \left\lfloor n-r\sqrt n\right\rfloor.$$
For prime \(n\), the number \(\sqrt n\) is irrational, hence \(r\sqrt n\notin \mathbb Z\) for every \(r\ge1\), and we may rewrite the bound as
$$s_r\le n-\left\lceil r\sqrt n\right\rceil.$$
Because these upper bounds decrease as \(r\) increases, the single strongest condition is the last one:
$$s_k\le T_k:=n-\left\lceil k\sqrt n\right\rceil.$$
Once the nondecreasing \(k\)-tuple \((s_1,\dots,s_k)\) is fixed, the whole branch is determined:
take \(s_1\) steps of size \(1\), then one step of size \(\sqrt n\); then \(s_2-s_1\) more \(1\)-steps, then another \(\sqrt n\)-step; continue in the same way until the \(k\)-th \(\sqrt n\)-step; after that, only \(1\)-steps remain until the remainder drops below \(\sqrt n\).
Conversely, every leaf with exactly \(k\) steps of size \(\sqrt n\) produces exactly one such tuple. So the problem is now:
How many tuples satisfy
$$0\le s_1\le s_2\le \cdots \le s_k\le T_k\ ?$$
This is the classical count of multisets of size \(k\) chosen from \(T_k+1\) values. Hence
$$\#\{\text{branches with exactly }k\text{ }\sqrt n\text{-steps}\}=\binom{T_k+k}{k}.$$
Substituting \(T_k=n-\lceil k\sqrt n\rceil\) gives
$$\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
Adding the contributions of all admissible \(k\) yields
$$G(n)=\sum_{k=0}^{\lfloor\sqrt n\rfloor}\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
This is the closed form used by the implementations. It replaces an exponential recursion tree with only \(O(\sqrt n)\) binomial terms.
Notice that the term for \(k=0\) is
$$\binom{n}{0}=1,$$
which corresponds to the unique branch that uses only \(1\)-steps until the stopping condition is reached.
The required modulus is
$$M=10^9+7,$$
which is prime. Therefore each binomial coefficient can be evaluated as
$$\binom{m}{k}\equiv m!\,(k!)^{-1}\,((m-k)!)^{-1}\pmod M.$$
After factorials and inverse factorials have been precomputed once, every summand of \(G(n)\) is obtained in constant time.
The overall Project Euler sum is then
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ prime}}}\ \sum_{k=0}^{\lfloor\sqrt p\rfloor}\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod M.$$
Here \(a=\sqrt5\approx 2.236\), so \(k\) can only be \(0\), \(1\), or \(2\).
For \(k=0\), the contribution is
$$\binom{5}{0}=1.$$
This is the single branch that repeatedly subtracts \(1\):
$$5\to 4\to 3\to 2,<\sqrt5.$$
For \(k=1\), we have
$$T_1=5-\lceil \sqrt5\rceil=5-3=2,$$
so \(s_1\) can be \(0\), \(1\), or \(2\). That gives the three branches
$$\sqrt5,1;\qquad 1,\sqrt5;\qquad 1,1,\sqrt5,$$
hence the contribution
$$\binom{2+1}{1}=3.$$
For \(k=2\),
$$T_2=5-\lceil 2\sqrt5\rceil=5-5=0,$$
so only \((s_1,s_2)=(0,0)\) is possible, corresponding to the branch
$$\sqrt5,\sqrt5,$$
and the contribution is
$$\binom{0+2}{2}=1.$$
Therefore
$$G(5)=1+3+1=5.$$
The C++, Python, and Java implementations all follow the same pipeline.
First, they precompute factorials and inverse factorials modulo \(10^9+7\) up to the largest integer that can appear in a binomial coefficient. This makes each later combination lookup constant time.
Next, they generate all primes in the interval \(10^7<p<10^7+10^4\) with a segmented sieve. Because the window width is only \(10^4\), this is much cheaper than sieving the entire range from \(1\) up to \(10^7+10^4\).
For each prime \(p\), the implementation loops over
$$0\le k\le \lfloor\sqrt p\rfloor$$
and evaluates the summand
$$\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod{10^9+7}.$$
The only delicate quantity is \(\lceil k\sqrt p\rceil\). Rather than simulating the original real recursion, the implementations compute this ceiling numerically from \(\sqrt{k^2p}\), then form the corresponding binomial term and add it to \(G(p)\).
Finally, all prime contributions are accumulated modulo \(10^9+7\) to produce the required answer.
Let \(U=10^7+10^4-1\), let \(W=10^4\) be the width of the prime interval, and let \(P\) be the number of primes in that interval.
Precomputing factorials and inverse factorials up to \(U\) costs \(O(U)\) time and \(O(U)\) memory. The segmented sieve needs only the base primes up to \(\sqrt U\), so prime generation over the target window is roughly \(O(\sqrt U\log\log U+W\log\log U)\) time and \(O(W)\) extra memory.
For each prime \(p\), evaluating \(G(p)\) requires \(\lfloor\sqrt p\rfloor+1\) summands, so that phase costs \(O(\sqrt p)\) per prime. Overall the running time is therefore
$$O\!\left(U+P\sqrt U\right),$$
with memory dominated by the factorial tables:
$$O(U).$$
Für eine positive ganze Zahl \(n\) setzen wir \(a=\sqrt n\) und definieren die Rekursion
$$g_a(x)=\begin{cases} 1, & x<a,\\ g_a(x-1)+g_a(x-a), & x\ge a. \end{cases}$$
Gesucht ist \(G(n)=g_a(n)\) mit \(a=\sqrt n\). Problem 517 verlangt dann die Summe
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ prim}}} G(p)\pmod{10^9+7}.$$
Direkte Rekursion wäre viel zu groß, deshalb ersetzt die Lösung den vollständigen Verzweigungsbaum durch eine geschlossene kombinatorische Formel.
Jeder Rekursionszweig entspricht einer geordneten Folge von Sprüngen der Länge \(1\) und \(\sqrt n\). Statt Zustände rekursiv auszuwerten, zählen wir daher diese zulässigen Folgen direkt.
Man startet mit dem Restwert \(x=n\). Jeder Rekursionsschritt ersetzt \(x\) durch \(x-1\) oder \(x-\sqrt n\), und der Zweig endet genau dann, wenn der neue Rest \(<\sqrt n\) ist.
Jedes Blatt des Rekursionsbaums ist also eine endliche Folge aus
$$1\text{-Schritt}: x\mapsto x-1,\qquad \sqrt n\text{-Schritt}: x\mapsto x-\sqrt n.$$
Verwendet ein Zweig genau \(k\) Schritte der Länge \(\sqrt n\), dann muss
$$k\sqrt n\le n$$
gelten. Also kommen nur
$$0\le k\le \left\lfloor\sqrt n\right\rfloor$$
in Frage.
Fixieren wir einen Zweig mit genau \(k\) Schritten der Länge \(\sqrt n\). Für \(r=1,\dots,k\) sei \(s_r\) die Anzahl der bereits ausgeführten \(1\)-Schritte, bevor der \(r\)-te \(\sqrt n\)-Schritt genommen wird.
Dann gilt automatisch
$$0\le s_1\le s_2\le \cdots \le s_k,$$
denn die Zahl der schon gesehenen \(1\)-Schritte wächst nur.
Vor dem \(r\)-ten \(\sqrt n\)-Schritt ist der aktuelle Rest
$$n-s_r-(r-1)\sqrt n.$$
Damit dieser Schritt überhaupt erlaubt ist, muss die Rekursion dort noch nicht gestoppt haben; also braucht man
$$n-s_r-(r-1)\sqrt n\ge \sqrt n.$$
Daraus folgt
$$s_r\le n-r\sqrt n.$$
Da \(s_r\) ganzzahlig ist, schreiben wir
$$s_r\le \left\lfloor n-r\sqrt n\right\rfloor.$$
Für primzahlige \(n\) ist \(\sqrt n\) irrational, also \(r\sqrt n\notin\mathbb Z\) für jedes \(r\ge1\). Daher ist dies äquivalent zu
$$s_r\le n-\left\lceil r\sqrt n\right\rceil.$$
Weil diese Schranken mit wachsendem \(r\) kleiner werden, genügt die stärkste Bedingung
$$s_k\le T_k:=n-\left\lceil k\sqrt n\right\rceil.$$
Ist das nichtfallende \(k\)-Tupel \((s_1,\dots,s_k)\) gegeben, dann ist der gesamte Zweig festgelegt:
zuerst \(s_1\) viele \(1\)-Schritte, dann ein \(\sqrt n\)-Schritt; danach \(s_2-s_1\) weitere \(1\)-Schritte, dann wieder ein \(\sqrt n\)-Schritt; und so weiter. Nach dem \(k\)-ten \(\sqrt n\)-Schritt bleiben nur noch \(1\)-Schritte, bis der Rest unter \(\sqrt n\) fällt.
Umgekehrt erzeugt jedes Blatt mit genau \(k\) \(\sqrt n\)-Schritten genau ein solches Tupel. Also müssen wir nur die Lösungen von
$$0\le s_1\le s_2\le \cdots \le s_k\le T_k$$
zählen.
Das ist genau die klassische Multimengen-Anzahl, also
$$\#\{\text{Zweige mit genau }k\text{ }\sqrt n\text{-Schritten}\}=\binom{T_k+k}{k}.$$
Mit \(T_k=n-\lceil k\sqrt n\rceil\) wird daraus
$$\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
Durch Summation über alle zulässigen \(k\) erhält man
$$G(n)=\sum_{k=0}^{\lfloor\sqrt n\rfloor}\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
Das ist exakt die geschlossene Form, die in den Implementierungen verwendet wird. Die exponentielle Rekursion wird dadurch auf nur \(O(\sqrt n)\) Summanden reduziert.
Für \(k=0\) erhält man den Term
$$\binom{n}{0}=1,$$
also genau den einen Zweig, der nur aus \(1\)-Schritten besteht, bis die Abbruchbedingung erreicht ist.
Das geforderte Modul ist
$$M=10^9+7,$$
also eine Primzahl. Deshalb kann jeder Binomialkoeffizient als
$$\binom{m}{k}\equiv m!\,(k!)^{-1}\,((m-k)!)^{-1}\pmod M$$
berechnet werden.
Nach einmaliger Vorberechnung von Fakultäten und inversen Fakultäten kostet damit jeder Summand von \(G(n)\) nur noch konstante Zeit.
Die endgültige Euler-Summe lautet also
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ prim}}}\ \sum_{k=0}^{\lfloor\sqrt p\rfloor}\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod M.$$
Hier ist \(a=\sqrt5\approx 2{,}236\), also kommen nur \(k=0\), \(1\) oder \(2\) vor.
Für \(k=0\) ist der Beitrag
$$\binom{5}{0}=1.$$
Das ist der einzige Zweig mit lauter \(1\)-Schritten:
$$5\to 4\to 3\to 2,<\sqrt5.$$
Für \(k=1\) gilt
$$T_1=5-\lceil \sqrt5\rceil=5-3=2,$$
also sind \(s_1=0,1,2\) möglich. Das liefert die drei Zweige
$$\sqrt5,1;\qquad 1,\sqrt5;\qquad 1,1,\sqrt5,$$
und somit den Beitrag
$$\binom{2+1}{1}=3.$$
Für \(k=2\) folgt
$$T_2=5-\lceil 2\sqrt5\rceil=5-5=0,$$
also bleibt nur \((s_1,s_2)=(0,0)\), entsprechend dem Zweig
$$\sqrt5,\sqrt5,$$
mit Beitrag
$$\binom{0+2}{2}=1.$$
Insgesamt also
$$G(5)=1+3+1=5.$$
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf.
Zuerst werden Fakultäten und inverse Fakultäten modulo \(10^9+7\) bis zur größten benötigten Zahl vorab berechnet. Dadurch wird jede spätere Binomialauswertung zu einem konstanten Tabellenzugriff.
Anschließend erzeugt ein segmentiertes Sieb alle Primzahlen im Intervall \(10^7<p<10^7+10^4\). Weil die Fensterbreite nur \(10^4\) beträgt, ist das deutlich günstiger als ein vollständiges Sieb bis \(10^7+10^4\).
Für jede Primzahl \(p\) läuft die Implementierung dann über
$$0\le k\le \lfloor\sqrt p\rfloor$$
und addiert den Summanden
$$\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod{10^9+7}.$$
Der einzige heikle Ausdruck ist \(\lceil k\sqrt p\rceil\). Statt die ursprüngliche Rekursion über reelle Zahlen zu simulieren, bestimmen die Implementierungen diesen Deckenwert numerisch aus \(\sqrt{k^2p}\) und setzen ihn direkt in den Binomialterm ein.
Zum Schluss werden alle Beiträge der Primzahlen modulo \(10^9+7\) aufaddiert.
Sei \(U=10^7+10^4-1\), \(W=10^4\) die Breite des Primzahlintervalls und \(P\) die Anzahl der Primzahlen darin.
Die Vorberechnung von Fakultäten und inversen Fakultäten bis \(U\) kostet \(O(U)\) Zeit und \(O(U)\) Speicher. Das segmentierte Sieb benötigt nur die Basisprimzahlen bis \(\sqrt U\), daher kostet die Primzahlerzeugung über dem Zielfenster ungefähr \(O(\sqrt U\log\log U+W\log\log U)\) Zeit und \(O(W)\) zusätzlichen Speicher.
Für jede Primzahl \(p\) braucht die Auswertung von \(G(p)\) genau \(\lfloor\sqrt p\rfloor+1\) Summanden, also \(O(\sqrt p)\) Zeit pro Primzahl. Insgesamt ergibt sich damit
$$O\!\left(U+P\sqrt U\right)$$
Zeit und, dominiert von den Fakultätstabellen,
$$O(U)$$
Speicher.
Pozitif bir \(n\) tamsayısı için \(a=\sqrt n\) olsun ve şu özyinelemeyi tanımlayalım:
$$g_a(x)=\begin{cases} 1, & x<a,\\ g_a(x-1)+g_a(x-a), & x\ge a. \end{cases}$$
İlgilendiğimiz büyüklük \(a=\sqrt n\) için \(G(n)=g_a(n)\) değeridir. Problem 517,
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ asal}}} G(p)\pmod{10^9+7}$$
toplamını ister. Doğrudan özyineleme çok hızlı dallandığı için çözüm, bütün ağacı gezmek yerine kapalı bir kombinatorik formül kurar.
Temel fikir şudur: Özyineleme ağacındaki her yaprak, uzunluğu \(1\) ve \(\sqrt n\) olan adımlardan oluşan sıralı bir diziye karşılık gelir. Böylece problem, geçerli adım dizilerini saymaya dönüşür.
Başlangıçta kalan değer \(x=n\) olur. Her çağrıda ya \(x-1\) ya da \(x-\sqrt n\) durumuna geçilir. Yeni kalan değer \(<\sqrt n\) olur olmaz dal biter.
Dolayısıyla her yaprak şu iki hamle türünden oluşan sıralı bir dizi verir:
$$1\text{-adımı}: x\mapsto x-1,\qquad \sqrt n\text{-adımı}: x\mapsto x-\sqrt n.$$
Eğer bir dal tam \(k\) tane \(\sqrt n\)-adımı kullanıyorsa
$$k\sqrt n\le n$$
olmalıdır. Bu yüzden yalnızca
$$0\le k\le \left\lfloor\sqrt n\right\rfloor$$
değerleri katkı verebilir.
Şimdi tam \(k\) tane \(\sqrt n\)-adımı içeren bir dalı sabitleyelim. \(r=1,\dots,k\) için \(s_r\), \(r\)-inci \(\sqrt n\)-adımı atılmadan önce gerçekleştirilmiş \(1\)-adımı sayısı olsun.
Bu sayılar için
$$0\le s_1\le s_2\le \cdots \le s_k$$
olur; çünkü şimdiye kadar atılan \(1\)-adımı sayısı sadece artabilir.
\(r\)-inci \(\sqrt n\)-adımından hemen önce kalan değer
$$n-s_r-(r-1)\sqrt n$$
olur. Bu adımın yasal olabilmesi için özyinelemenin henüz durmamış olması gerekir, yani
$$n-s_r-(r-1)\sqrt n\ge \sqrt n.$$
Buradan
$$s_r\le n-r\sqrt n$$
ve tam sayı olduğu için
$$s_r\le \left\lfloor n-r\sqrt n\right\rfloor$$
elde edilir.
Asal \(n\) için \(\sqrt n\) irrasyoneldir; dolayısıyla \(r\sqrt n\) hiçbir pozitif \(r\) için tam sayı değildir. Bu yüzden sınırı
$$s_r\le n-\left\lceil r\sqrt n\right\rceil$$
şeklinde yazabiliriz. Bu üst sınırlar \(r\) arttıkça küçüldüğü için en güçlü koşul sonuncusudur:
$$s_k\le T_k:=n-\left\lceil k\sqrt n\right\rceil.$$
Azalmayan \(k\)-lisi \((s_1,\dots,s_k)\) verildiğinde tüm dal belirlenir:
önce \(s_1\) tane \(1\)-adımı, sonra bir \(\sqrt n\)-adımı; ardından \(s_2-s_1\) tane daha \(1\)-adımı, sonra bir \(\sqrt n\)-adımı; bu süreç böyle devam eder. \(k\)-inci \(\sqrt n\)-adımından sonra ise kalan değer \(\sqrt n\)'nin altına düşünceye kadar sadece \(1\)-adımları kalır.
Tersi de doğrudur: tam \(k\) tane \(\sqrt n\)-adımı içeren her yaprak tam bir böyle \(k\)-li verir. O halde saymamız gereken nesneler
$$0\le s_1\le s_2\le \cdots \le s_k\le T_k$$
koşulunu sağlayan dizilerdir.
Bu da klasik multiset sayımıdır. Sonuç:
$$\#\{\text{tam }k\text{ adet }\sqrt n\text{-adımı içeren dallar}\}=\binom{T_k+k}{k}.$$
\(T_k=n-\lceil k\sqrt n\rceil\) yerine yazarsak
$$\binom{n-\lceil k\sqrt n\rceil+k}{k}$$
elde edilir.
Böylece
$$G(n)=\sum_{k=0}^{\lfloor\sqrt n\rfloor}\binom{n-\lceil k\sqrt n\rceil+k}{k}$$
sonucuna ulaşırız. Uygulamanın kullandığı kapalı form tam olarak budur. Üstel büyüyen özyineleme ağacı, yalnızca \(O(\sqrt n)\) terimlik bir toplama indirgenmiş olur.
\(k=0\) terimi
$$\binom{n}{0}=1$$
olup, durma koşuluna kadar yalnızca \(1\)-adımı kullanan tek dala karşılık gelir.
İstenen modül
$$M=10^9+7$$
asal olduğu için her binom katsayısı
$$\binom{m}{k}\equiv m!\,(k!)^{-1}\,((m-k)!)^{-1}\pmod M$$
şeklinde hesaplanabilir.
Faktöriyel ve ters faktöriyel tabloları bir kez hazırlandıktan sonra \(G(n)\) içindeki her terim sabit zamanda bulunur.
Böylece istenen toplam
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ asal}}}\ \sum_{k=0}^{\lfloor\sqrt p\rfloor}\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod M$$
şeklini alır.
Burada \(a=\sqrt5\approx 2.236\) olduğundan yalnızca \(k=0\), \(1\) ve \(2\) mümkündür.
\(k=0\) için katkı
$$\binom{5}{0}=1$$
olur. Bu, sadece \(1\)-adımlarıyla ilerleyen tek daldır:
$$5\to 4\to 3\to 2,<\sqrt5.$$
\(k=1\) için
$$T_1=5-\lceil \sqrt5\rceil=5-3=2$$
olduğundan \(s_1=0,1,2\) mümkündür. Bunlar şu üç dala karşılık gelir:
$$\sqrt5,1;\qquad 1,\sqrt5;\qquad 1,1,\sqrt5,$$
ve katkı
$$\binom{2+1}{1}=3$$
eder.
\(k=2\) için
$$T_2=5-\lceil 2\sqrt5\rceil=5-5=0$$
olur; dolayısıyla yalnızca \((s_1,s_2)=(0,0)\) mümkündür. Bu da
$$\sqrt5,\sqrt5$$
dalını verir ve katkı
$$\binom{0+2}{2}=1$$
olur.
Sonuç olarak
$$G(5)=1+3+1=5.$$
C++, Python ve Java uygulamaları aynı iskeleti izler.
Önce \(10^9+7\) modunda, gereken en büyük sayıya kadar faktöriyel ve ters faktöriyel tabloları hazırlanır. Böylece her binom katsayısı daha sonra sabit zamanda okunabilir.
Ardından segmentli asal eleği ile \(10^7<p<10^7+10^4\) aralığındaki tüm asallar üretilir. Pencere genişliği yalnızca \(10^4\) olduğu için bu adım tüm aralığı baştan elemekten çok daha ucuzdur.
Her asal \(p\) için uygulama
$$0\le k\le \lfloor\sqrt p\rfloor$$
değerleri üzerinde döner ve
$$\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod{10^9+7}$$
terimini toplar.
Buradaki hassas nokta \(\lceil k\sqrt p\rceil\) ifadesidir. Gerçek sayılı özyinelemeyi canlandırmak yerine uygulamalar bu değeri \(\sqrt{k^2p}\) üzerinden sayısal olarak hesaplar, sonra doğrudan binom terimine yerleştirir.
Son aşamada tüm asal katkıları mod \(10^9+7\) altında biriktirilir.
\(U=10^7+10^4-1\), asal aralığının genişliği \(W=10^4\) ve bu aralıktaki asal sayısı \(P\) olsun.
\(U\)'ya kadar faktöriyel ve ters faktöriyel ön hesabı \(O(U)\) zaman ve \(O(U)\) bellek ister. Segmentli eleğin taban asalları yalnızca \(\sqrt U\)'ya kadar gerektiğinden, hedef penceredeki asal üretimi yaklaşık \(O(\sqrt U\log\log U+W\log\log U)\) zaman ve \(O(W)\) ek bellek kullanır.
Her asal \(p\) için \(G(p)\) hesabı \(\lfloor\sqrt p\rfloor+1\) terim içerir; yani asal başına \(O(\sqrt p)\) zaman gerekir. Toplam çalışma süresi bu nedenle
$$O\!\left(U+P\sqrt U\right)$$
olur. Bellek kullanımı ise faktöriyel tablolarının baskın olması nedeniyle
$$O(U)$$
mertebesindedir.
Para un entero positivo \(n\), definimos \(a=\sqrt n\) y la recursión
$$g_a(x)=\begin{cases} 1, & x<a,\\ g_a(x-1)+g_a(x-a), & x\ge a. \end{cases}$$
La cantidad relevante es \(G(n)=g_a(n)\) con \(a=\sqrt n\). El problema 517 pide calcular
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ primo}}} G(p)\pmod{10^9+7}.$$
La recursión directa se dispara demasiado rápido, así que la solución sustituye el árbol recursivo por una fórmula combinatoria cerrada.
La observación central es que cada hoja del árbol recursivo corresponde a una secuencia ordenada de saltos de longitud \(1\) y \(\sqrt n\). Por tanto, basta contar directamente esas secuencias válidas.
Comenzamos con residuo \(x=n\). Cada llamada recursiva reemplaza \(x\) por \(x-1\) o por \(x-\sqrt n\), y la rama termina en cuanto el nuevo residuo es \(<\sqrt n\).
Cada hoja es entonces una secuencia finita formada por
$$1\text{-paso}: x\mapsto x-1,\qquad \sqrt n\text{-paso}: x\mapsto x-\sqrt n.$$
Si una rama usa exactamente \(k\) pasos de longitud \(\sqrt n\), necesariamente
$$k\sqrt n\le n,$$
de modo que solo pueden aparecer
$$0\le k\le \left\lfloor\sqrt n\right\rfloor.$$
Fijemos una rama con exactamente \(k\) pasos de longitud \(\sqrt n\). Para \(r=1,\dots,k\), sea \(s_r\) el número de pasos de longitud \(1\) ya realizados antes del \(r\)-ésimo paso de longitud \(\sqrt n\).
Entonces
$$0\le s_1\le s_2\le \cdots \le s_k,$$
porque el número acumulado de pasos de longitud \(1\) solo puede aumentar.
Antes del \(r\)-ésimo paso de longitud \(\sqrt n\), el residuo es
$$n-s_r-(r-1)\sqrt n.$$
Para que ese salto sea legal, la recursión aún no debe haber terminado, así que necesitamos
$$n-s_r-(r-1)\sqrt n\ge \sqrt n.$$
Por tanto,
$$s_r\le n-r\sqrt n.$$
Como \(s_r\) es entero, esto equivale a
$$s_r\le \left\lfloor n-r\sqrt n\right\rfloor.$$
Cuando \(n\) es primo, \(\sqrt n\) es irracional, de modo que \(r\sqrt n\notin\mathbb Z\) para todo \(r\ge1\), y podemos reescribir la cota como
$$s_r\le n-\left\lceil r\sqrt n\right\rceil.$$
Estas cotas decrecen con \(r\), así que la condición más fuerte es la última:
$$s_k\le T_k:=n-\left\lceil k\sqrt n\right\rceil.$$
Una vez fijada la \(k\)-tupla no decreciente \((s_1,\dots,s_k)\), la rama completa queda determinada:
primero se hacen \(s_1\) pasos de longitud \(1\), luego un paso de longitud \(\sqrt n\); después \(s_2-s_1\) pasos adicionales de longitud \(1\), luego otro paso de longitud \(\sqrt n\); y así sucesivamente. Tras el \(k\)-ésimo paso de longitud \(\sqrt n\), solo quedan pasos de longitud \(1\) hasta que el residuo cae por debajo de \(\sqrt n\).
Recíprocamente, cada hoja con exactamente \(k\) pasos de longitud \(\sqrt n\) produce una única \(k\)-tupla de este tipo. Por lo tanto, solo hay que contar las soluciones de
$$0\le s_1\le s_2\le \cdots \le s_k\le T_k.$$
Ese es el conteo clásico de multiconjuntos, y da
$$\#\{\text{ramas con exactamente }k\text{ pasos }\sqrt n\}=\binom{T_k+k}{k}.$$
Sustituyendo \(T_k=n-\lceil k\sqrt n\rceil\), obtenemos
$$\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
Al sumar todas las contribuciones aparece la fórmula cerrada
$$G(n)=\sum_{k=0}^{\lfloor\sqrt n\rfloor}\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
Esa es exactamente la expresión usada por las implementaciones. El árbol recursivo exponencial queda reemplazado por solo \(O(\sqrt n)\) términos binomiales.
El término con \(k=0\) vale
$$\binom{n}{0}=1,$$
y representa la única rama formada exclusivamente por pasos de longitud \(1\) hasta alcanzar la condición de parada.
El módulo pedido es
$$M=10^9+7,$$
que es primo. Por ello, cada coeficiente binomial puede calcularse como
$$\binom{m}{k}\equiv m!\,(k!)^{-1}\,((m-k)!)^{-1}\pmod M.$$
Después de precomputar factoriales e inversos factoriales una sola vez, cada sumando de \(G(n)\) cuesta tiempo constante.
La suma final de Project Euler toma la forma
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ primo}}}\ \sum_{k=0}^{\lfloor\sqrt p\rfloor}\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod M.$$
Aquí \(a=\sqrt5\approx 2.236\), así que solo pueden aparecer \(k=0\), \(1\) y \(2\).
Para \(k=0\), la contribución es
$$\binom{5}{0}=1.$$
Corresponde a la única rama que solo resta \(1\):
$$5\to 4\to 3\to 2,<\sqrt5.$$
Para \(k=1\), tenemos
$$T_1=5-\lceil \sqrt5\rceil=5-3=2,$$
de modo que \(s_1\) puede ser \(0\), \(1\) o \(2\). Eso produce las tres ramas
$$\sqrt5,1;\qquad 1,\sqrt5;\qquad 1,1,\sqrt5,$$
y por tanto la contribución
$$\binom{2+1}{1}=3.$$
Para \(k=2\),
$$T_2=5-\lceil 2\sqrt5\rceil=5-5=0,$$
así que solo es posible \((s_1,s_2)=(0,0)\), lo que corresponde a la rama
$$\sqrt5,\sqrt5,$$
con contribución
$$\binom{0+2}{2}=1.$$
En consecuencia,
$$G(5)=1+3+1=5.$$
Las implementaciones en C++, Python y Java siguen el mismo esquema general.
Primero precomputan factoriales e inversos factoriales módulo \(10^9+7\) hasta el mayor valor que puede intervenir en un coeficiente binomial. Así, cada combinación posterior se obtiene con consultas de tiempo constante.
Después generan todos los primos del intervalo \(10^7<p<10^7+10^4\) mediante una criba segmentada. Como la ventana solo tiene anchura \(10^4\), esta etapa es mucho más barata que cribar todo el rango desde \(1\).
Para cada primo \(p\), la implementación recorre
$$0\le k\le \lfloor\sqrt p\rfloor$$
y acumula el término
$$\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod{10^9+7}.$$
La única cantidad delicada es \(\lceil k\sqrt p\rceil\). En lugar de simular la recursión real original, las implementaciones calculan ese techo numéricamente a partir de \(\sqrt{k^2p}\), forman el binomial correspondiente y lo añaden a \(G(p)\).
Al final se suman todas las contribuciones primas módulo \(10^9+7\).
Sea \(U=10^7+10^4-1\), sea \(W=10^4\) la anchura de la ventana de primos y sea \(P\) el número de primos en ese intervalo.
La precomputación de factoriales e inversos factoriales hasta \(U\) cuesta \(O(U)\) tiempo y \(O(U)\) memoria. La criba segmentada solo necesita primos base hasta \(\sqrt U\), de modo que la generación de primos sobre la ventana objetivo requiere aproximadamente \(O(\sqrt U\log\log U+W\log\log U)\) tiempo y \(O(W)\) memoria adicional.
Para cada primo \(p\), evaluar \(G(p)\) necesita \(\lfloor\sqrt p\rfloor+1\) sumandos, es decir, \(O(\sqrt p)\) tiempo por primo. En conjunto, el tiempo total es
$$O\!\left(U+P\sqrt U\right),$$
mientras que la memoria está dominada por las tablas factoriales:
$$O(U).$$
对于正整数 \(n\)，令 \(a=\sqrt n\)，并定义递归
$$g_a(x)=\begin{cases} 1, & x<a,\\ g_a(x-1)+g_a(x-a), & x\ge a. \end{cases}$$
我们关心的量是当 \(a=\sqrt n\) 时的 \(G(n)=g_a(n)\)。第 517 题要求计算
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ 为素数}}} G(p)\pmod{10^9+7}.$$
如果直接按递归定义展开，分支数量会迅速爆炸，因此必须把递归树转换成一个可以直接求值的组合公式。
核心观察是：递归树中的每一片叶子，都对应于一串按顺序执行的两种操作，长度分别为 \(1\) 和 \(\sqrt n\)。于是我们不再递归搜索，而是直接统计这些合法操作序列的数量。
初始剩余量是 \(x=n\)。每一步递归都会把 \(x\) 变成 \(x-1\) 或 \(x-\sqrt n\)。一旦新的剩余量小于 \(\sqrt n\)，该分支立即结束并贡献 \(1\)。
因此，每一条叶子分支都可以看成由以下两类跳跃组成：
$$1\text{ 步}: x\mapsto x-1,\qquad \sqrt n\text{ 步}: x\mapsto x-\sqrt n.$$
如果某条分支一共使用了 \(k\) 次长度为 \(\sqrt n\) 的跳跃，那么显然必须满足
$$k\sqrt n\le n,$$
所以只有
$$0\le k\le \left\lfloor\sqrt n\right\rfloor$$
这些 \(k\) 才可能出现。
现在固定一条恰好使用 \(k\) 次 \(\sqrt n\) 跳跃的分支。对每个 \(r=1,\dots,k\)，令 \(s_r\) 表示在第 \(r\) 次 \(\sqrt n\) 跳跃发生之前，已经执行了多少次长度为 \(1\) 的跳跃。
由于这个计数只会增加，所以必然有
$$0\le s_1\le s_2\le \cdots \le s_k.$$
在进行第 \(r\) 次 \(\sqrt n\) 跳跃之前，当前剩余量为
$$n-s_r-(r-1)\sqrt n.$$
为了让这一步仍然合法，递归在此之前不能已经停止，因此必须满足
$$n-s_r-(r-1)\sqrt n\ge \sqrt n.$$
整理得到
$$s_r\le n-r\sqrt n.$$
而 \(s_r\) 是整数，所以实际上可以写成
$$s_r\le \left\lfloor n-r\sqrt n\right\rfloor.$$
在题目真正需要的输入中，\(n\) 是素数，因此 \(\sqrt n\) 不可能是整数；于是对所有 \(r\ge1\)，\(r\sqrt n\) 也不是整数。这样上式就可以改写为
$$s_r\le n-\left\lceil r\sqrt n\right\rceil.$$
这些上界随着 \(r\) 的增大而变小，因此最强的限制恰好是最后一个：
$$s_k\le T_k:=n-\left\lceil k\sqrt n\right\rceil.$$
一旦非降 \(k\) 元组 \((s_1,\dots,s_k)\) 固定，整条分支就被唯一决定了：
先走 \(s_1\) 次长度为 \(1\) 的跳跃，再走一次 \(\sqrt n\) 跳跃；然后再走 \(s_2-s_1\) 次长度为 \(1\) 的跳跃，再走下一次 \(\sqrt n\) 跳跃；如此继续。完成第 \(k\) 次 \(\sqrt n\) 跳跃之后，就只剩下长度为 \(1\) 的跳跃，直到剩余量第一次小于 \(\sqrt n\) 为止。
反过来，任何一条恰好包含 \(k\) 次 \(\sqrt n\) 跳跃的叶子分支，也都会唯一对应到这样一个非降 \(k\) 元组。因此我们真正需要统计的是
$$0\le s_1\le s_2\le \cdots \le s_k\le T_k$$
的解数。
这正是经典的“可重复选取”的组合计数，也就是多重组合。结果为
$$\#\{\text{恰好有 }k\text{ 次 }\sqrt n\text{ 跳跃的分支}\}=\binom{T_k+k}{k}.$$
把 \(T_k=n-\lceil k\sqrt n\rceil\) 代入，就得到
$$\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
把所有允许的 \(k\) 的贡献加起来，就得到闭式
$$G(n)=\sum_{k=0}^{\lfloor\sqrt n\rfloor}\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
这正是程序真正计算的公式。原来指数级增长的递归树，被压缩成了只有 \(O(\sqrt n)\) 项的求和。
其中 \(k=0\) 时的项是
$$\binom{n}{0}=1,$$
对应于那条只执行长度为 \(1\) 的跳跃、直到触发终止条件的唯一分支。
题目要求的模数是
$$M=10^9+7,$$
它是一个素数。因此每个二项式系数都可以写成
$$\binom{m}{k}\equiv m!\,(k!)^{-1}\,((m-k)!)^{-1}\pmod M.$$
只要把阶乘和逆阶乘预处理好，之后 \(G(n)\) 的每一项都能在常数时间内算出。
于是最终需要的欧拉和就变成了
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ 为素数}}}\ \sum_{k=0}^{\lfloor\sqrt p\rfloor}\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod M.$$
此时 \(a=\sqrt5\approx 2.236\)，所以 \(k\) 只可能是 \(0\)、\(1\)、\(2\)。
当 \(k=0\) 时，贡献为
$$\binom{5}{0}=1.$$
它对应唯一一条只减 \(1\) 的分支：
$$5\to 4\to 3\to 2,<\sqrt5.$$
当 \(k=1\) 时，
$$T_1=5-\lceil \sqrt5\rceil=5-3=2,$$
所以 \(s_1\) 可以取 \(0,1,2\)。这给出三条分支：
$$\sqrt5,1;\qquad 1,\sqrt5;\qquad 1,1,\sqrt5,$$
对应贡献
$$\binom{2+1}{1}=3.$$
当 \(k=2\) 时，
$$T_2=5-\lceil 2\sqrt5\rceil=5-5=0,$$
因此只有 \((s_1,s_2)=(0,0)\) 这一种情况，对应分支
$$\sqrt5,\sqrt5,$$
贡献为
$$\binom{0+2}{2}=1.$$
最终得到
$$G(5)=1+3+1=5.$$
C++、Python 和 Java 三个实现使用的是同一条计算路线。
第一步，先在模 \(10^9+7\) 下预处理到所需上界的阶乘表和逆阶乘表。这样后面的每个二项式系数都可以用常数时间取出。
第二步，用分段筛生成区间 \(10^7<p<10^7+10^4\) 内的所有素数。由于窗口宽度只有 \(10^4\)，这一阶段远比从 \(1\) 一直筛到上界要便宜。
第三步，对每个素数 \(p\)，枚举
$$0\le k\le \lfloor\sqrt p\rfloor$$
并累加
$$\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod{10^9+7}.$$
这里唯一需要小心的是 \(\lceil k\sqrt p\rceil\) 的计算。实现并不去模拟原始的实数递归，而是从 \(\sqrt{k^2p}\) 数值地得到这个上取整值，再构造对应的二项式项。
最后，把所有素数的贡献在模 \(10^9+7\) 下累加起来即可。
设 \(U=10^7+10^4-1\)，设窗口宽度 \(W=10^4\)，设该区间内素数个数为 \(P\)。
预处理到 \(U\) 的阶乘和逆阶乘需要 \(O(U)\) 时间和 \(O(U)\) 空间。分段筛只需要 \(\sqrt U\) 以内的基素数，因此在目标窗口上生成素数大约需要 \(O(\sqrt U\log\log U+W\log\log U)\) 时间，以及 \(O(W)\) 的额外空间。
对于每个素数 \(p\)，计算 \(G(p)\) 需要 \(\lfloor\sqrt p\rfloor+1\) 项，所以单个素数的代价是 \(O(\sqrt p)\)。总时间因此为
$$O\!\left(U+P\sqrt U\right),$$
而空间则由阶乘表主导，为
$$O(U).$$
Для положительного целого \(n\) положим \(a=\sqrt n\) и определим рекурсию
$$g_a(x)=\begin{cases} 1, & x<a,\\ g_a(x-1)+g_a(x-a), & x\ge a. \end{cases}$$
Нас интересует величина \(G(n)=g_a(n)\) при \(a=\sqrt n\). В задаче 517 требуется вычислить
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ простое}}} G(p)\pmod{10^9+7}.$$
Прямое разворачивание рекурсии слишком дорого, поэтому решение заменяет рекурсивное дерево явной комбинаторной формулой.
Главное наблюдение состоит в том, что каждый лист рекурсивного дерева соответствует упорядоченной последовательности шагов длины \(1\) и \(\sqrt n\). Значит, вместо рекурсивного перебора можно просто посчитать такие допустимые последовательности.
Стартуем с остатка \(x=n\). Каждый рекурсивный вызов заменяет \(x\) на \(x-1\) или на \(x-\sqrt n\). Ветка завершается, как только новый остаток становится меньше \(\sqrt n\).
Следовательно, каждый лист можно рассматривать как конечную последовательность двух типов шагов:
$$1\text{-шаг}: x\mapsto x-1,\qquad \sqrt n\text{-шаг}: x\mapsto x-\sqrt n.$$
Если ветка использует ровно \(k\) шагов длины \(\sqrt n\), то обязательно
$$k\sqrt n\le n,$$
поэтому возможны только
$$0\le k\le \left\lfloor\sqrt n\right\rfloor.$$
Рассмотрим ветку, в которой ровно \(k\) шагов длины \(\sqrt n\). Для \(r=1,\dots,k\) обозначим через \(s_r\) количество уже сделанных шагов длины \(1\) перед тем, как выполняется \(r\)-й шаг длины \(\sqrt n\).
Тогда автоматически
$$0\le s_1\le s_2\le \cdots \le s_k,$$
потому что число уже сделанных единичных шагов не может уменьшаться.
Перед \(r\)-м шагом длины \(\sqrt n\) текущий остаток равен
$$n-s_r-(r-1)\sqrt n.$$
Чтобы этот шаг был допустим, рекурсия ещё не должна была остановиться, то есть нужно
$$n-s_r-(r-1)\sqrt n\ge \sqrt n.$$
Отсюда
$$s_r\le n-r\sqrt n.$$
Так как \(s_r\) целое, это эквивалентно
$$s_r\le \left\lfloor n-r\sqrt n\right\rfloor.$$
Для простого \(n\) число \(\sqrt n\) иррационально, поэтому \(r\sqrt n\notin\mathbb Z\) при любом \(r\ge1\), и ограничение можно переписать в виде
$$s_r\le n-\left\lceil r\sqrt n\right\rceil.$$
Эти верхние границы убывают при росте \(r\), так что самое сильное условие даёт последний индекс:
$$s_k\le T_k:=n-\left\lceil k\sqrt n\right\rceil.$$
Как только неубывающий \(k\)-кортеж \((s_1,\dots,s_k)\) зафиксирован, вся ветка определяется однозначно:
сначала делаем \(s_1\) единичных шагов, потом один шаг длины \(\sqrt n\); затем \(s_2-s_1\) новых единичных шагов, потом ещё один шаг длины \(\sqrt n\); и так далее. После \(k\)-го шага длины \(\sqrt n\) остаются только единичные шаги, пока остаток впервые не станет меньше \(\sqrt n\).
Обратно, каждая ветка с ровно \(k\) шагами длины \(\sqrt n\) порождает ровно один такой кортеж. Значит, надо посчитать решения системы
$$0\le s_1\le s_2\le \cdots \le s_k\le T_k.$$
Это стандартный подсчёт мультимножеств, и результат равен
$$\#\{\text{ветви с ровно }k\text{ шагами }\sqrt n\}=\binom{T_k+k}{k}.$$
Подставляя \(T_k=n-\lceil k\sqrt n\rceil\), получаем
$$\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
Сумма по всем возможным \(k\) даёт закрытую формулу
$$G(n)=\sum_{k=0}^{\lfloor\sqrt n\rfloor}\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
Именно её вычисляют программы. Экспоненциальное рекурсивное дерево заменяется суммой всего из \(O(\sqrt n)\) биномиальных членов.
Член при \(k=0\) равен
$$\binom{n}{0}=1,$$
и соответствует единственной ветке, состоящей только из шагов длины \(1\) до момента остановки.
Используемый модуль равен
$$M=10^9+7,$$
а это простое число. Поэтому каждый биномиальный коэффициент можно вычислять как
$$\binom{m}{k}\equiv m!\,(k!)^{-1}\,((m-k)!)^{-1}\pmod M.$$
После однократного предвычисления факториалов и обратных факториалов каждый член суммы для \(G(n)\) находится за постоянное время.
Итоговая сумма задачи принимает вид
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ простое}}}\ \sum_{k=0}^{\lfloor\sqrt p\rfloor}\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod M.$$
Здесь \(a=\sqrt5\approx 2.236\), так что возможны только \(k=0\), \(1\) и \(2\).
Для \(k=0\) вклад равен
$$\binom{5}{0}=1.$$
Это единственная ветка, в которой выполняются только единичные шаги:
$$5\to 4\to 3\to 2,<\sqrt5.$$
Для \(k=1\) имеем
$$T_1=5-\lceil \sqrt5\rceil=5-3=2,$$
поэтому \(s_1\) может принимать значения \(0\), \(1\) или \(2\). Это даёт три ветви
$$\sqrt5,1;\qquad 1,\sqrt5;\qquad 1,1,\sqrt5,$$
и вклад
$$\binom{2+1}{1}=3.$$
Для \(k=2\)
$$T_2=5-\lceil 2\sqrt5\rceil=5-5=0,$$
значит возможен только кортеж \((s_1,s_2)=(0,0)\), соответствующий ветви
$$\sqrt5,\sqrt5,$$
с вкладом
$$\binom{0+2}{2}=1.$$
Итак,
$$G(5)=1+3+1=5.$$
Реализации на C++, Python и Java используют один и тот же вычислительный конвейер.
Сначала они предвычисляют факториалы и обратные факториалы по модулю \(10^9+7\) вплоть до наибольшего значения, которое может встретиться в биномиальном коэффициенте. После этого любая комбинация извлекается за постоянное время.
Далее с помощью сегментированного решета находятся все простые числа в интервале \(10^7<p<10^7+10^4\). Поскольку ширина окна равна всего \(10^4\), этот шаг намного дешевле полного решета до верхней границы.
Для каждого простого \(p\) программа перебирает
$$0\le k\le \lfloor\sqrt p\rfloor$$
и добавляет член
$$\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod{10^9+7}.$$
Единственная тонкость состоит в вычислении \(\lceil k\sqrt p\rceil\). Вместо моделирования исходной рекурсии над вещественными числами реализации находят этот потолок численно через \(\sqrt{k^2p}\), а затем подставляют его в биномиальный член.
В конце все вклады простых чисел суммируются по модулю \(10^9+7\).
Пусть \(U=10^7+10^4-1\), \(W=10^4\) — ширина окна по простым, а \(P\) — число простых в этом окне.
Предвычисление факториалов и обратных факториалов до \(U\) требует \(O(U)\) времени и \(O(U)\) памяти. Сегментированное решето использует базовые простые только до \(\sqrt U\), поэтому генерация простых в целевом окне занимает примерно \(O(\sqrt U\log\log U+W\log\log U)\) времени и \(O(W)\) дополнительной памяти.
Для каждого простого \(p\) вычисление \(G(p)\) требует \(\lfloor\sqrt p\rfloor+1\) слагаемых, то есть \(O(\sqrt p)\) времени на одно простое. В итоге общая асимптотика равна
$$O\!\left(U+P\sqrt U\right),$$
а память определяется таблицами факториалов и имеет порядок
$$O(U).$$
لعدد صحيح موجب \(n\)، نضع \(a=\sqrt n\) ونعرّف العلاقة العودية
$$g_a(x)=\begin{cases} 1, & x<a,\\ g_a(x-1)+g_a(x-a), & x\ge a. \end{cases}$$
والكمية المطلوبة هي \(G(n)=g_a(n)\) عندما يكون \(a=\sqrt n\). تطلب المسألة 517 حساب
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ prime}}} G(p)\pmod{10^9+7}.$$
التقييم العودي المباشر يتشعب بسرعة كبيرة، لذلك يستبدل الحل شجرة الاستدعاءات كاملة بصيغة توافقية مغلقة قابلة للحساب مباشرة.
الفكرة الأساسية هي أن كل ورقة في شجرة العودية تقابل سلسلة مرتبة من خطوات طولها \(1\) وخطوات طولها \(\sqrt n\). لذلك يمكننا عدّ هذه السلاسل المسموح بها بدلًا من محاكاة العودية نفسها.
نبدأ من الباقي \(x=n\). في كل استدعاء عودي نستبدل \(x\) إما بـ \(x-1\) أو بـ \(x-\sqrt n\). وتنتهي الشعبة بمجرد أن يصبح الباقي الجديد أصغر من \(\sqrt n\).
إذًا كل ورقة تمثل سلسلة من نوعين من الخطوات:
$$1\text{-step}: x\mapsto x-1,\qquad \sqrt n\text{-step}: x\mapsto x-\sqrt n.$$
إذا استخدمت شعبة ما عددًا يساوي \(k\) من خطوات \(\sqrt n\)، فلا بد أن
$$k\sqrt n\le n,$$
ولذلك فإن القيم الممكنة هي فقط
$$0\le k\le \left\lfloor\sqrt n\right\rfloor.$$
ثبّت الآن شعبة فيها بالضبط \(k\) خطوة من النوع \(\sqrt n\). ولـ \(r=1,\dots,k\)، ليكن \(s_r\) هو عدد الخطوات ذات الطول \(1\) المنفذة قبل الخطوة رقم \(r\) من النوع \(\sqrt n\).
عندئذٍ لدينا بالضرورة
$$0\le s_1\le s_2\le \cdots \le s_k,$$
لأن عدد الخطوات ذات الطول \(1\) المنجزة حتى تلك اللحظة لا يمكن إلا أن يزداد.
قبل تنفيذ الخطوة \(r\) من النوع \(\sqrt n\)، يكون الباقي الحالي
$$n-s_r-(r-1)\sqrt n.$$
ولكي تكون هذه الخطوة قانونية يجب ألا تكون العودية قد توقفت بعد، أي لا بد من تحقق
$$n-s_r-(r-1)\sqrt n\ge \sqrt n.$$
ومنها نحصل على
$$s_r\le n-r\sqrt n.$$
وبما أن \(s_r\) عدد صحيح، يمكن كتابة ذلك على الصورة
$$s_r\le \left\lfloor n-r\sqrt n\right\rfloor.$$
ولأن \(n\) في المسألة الفعلية عدد أولي، فإن \(\sqrt n\) غير نسبي، وبالتالي \(r\sqrt n\) ليس عددًا صحيحًا لأي \(r\ge1\). لذا يمكن إعادة كتابة القيد بالشكل
$$s_r\le n-\left\lceil r\sqrt n\right\rceil.$$
وهذه الحدود العليا تتناقص كلما ازداد \(r\)، لذا يكون القيد الأقوى هو الأخير:
$$s_k\le T_k:=n-\left\lceil k\sqrt n\right\rceil.$$
بمجرد تثبيت المتتالية غير المتناقصة \((s_1,\dots,s_k)\)، تصبح الشعبة محددة بالكامل:
ننفيذ أولًا \(s_1\) من خطوات الطول \(1\)، ثم خطوة واحدة من النوع \(\sqrt n\)؛ بعد ذلك ننفذ \(s_2-s_1\) خطوة إضافية من الطول \(1\)، ثم خطوة أخرى من النوع \(\sqrt n\)؛ ونستمر بهذا النمط. بعد الخطوة رقم \(k\) من النوع \(\sqrt n\)، لا يبقى إلا خطوات الطول \(1\) حتى يهبط الباقي لأول مرة تحت \(\sqrt n\).
وبالعكس، كل ورقة تحتوي بالضبط على \(k\) خطوات من النوع \(\sqrt n\) تعطي متتالية وحيدة من هذا الشكل. إذن ما نحتاج إلى عده هو حلول
$$0\le s_1\le s_2\le \cdots \le s_k\le T_k.$$
وهذا هو عدّ متعددات العناصر الكلاسيكي، ومن ثم
$$\#\{\text{branches with exactly }k\text{ }\sqrt n\text{-steps}\}=\binom{T_k+k}{k}.$$
وبالتعويض عن \(T_k=n-\lceil k\sqrt n\rceil\) نحصل على
$$\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
بجمع المساهمات على كل القيم المسموح بها لـ \(k\) نحصل على الصيغة المغلقة
$$G(n)=\sum_{k=0}^{\lfloor\sqrt n\rfloor}\binom{n-\lceil k\sqrt n\rceil+k}{k}.$$
وهذه هي بالضبط الصيغة التي تعتمدها التطبيقات. لقد تحولت شجرة العودية ذات النمو الأسي إلى مجموع يحوي فقط \(O(\sqrt n)\) حدًا.
أما الحد الموافق لـ \(k=0\) فهو
$$\binom{n}{0}=1,$$
ويمثل الشعبة الوحيدة التي تستعمل خطوات الطول \(1\) فقط حتى الوصول إلى شرط التوقف.
الترديد المطلوب هو
$$M=10^9+7,$$
وهو عدد أولي. لذلك يمكن حساب كل معامل ثنائي الحد وفق
$$\binom{m}{k}\equiv m!\,(k!)^{-1}\,((m-k)!)^{-1}\pmod M.$$
وبعد تجهيز جداول المضروب ومقلوباته مرة واحدة، يصبح حساب كل حد من حدود \(G(n)\) بزمن ثابت.
وعليه تصبح القيمة النهائية المطلوبة هي
$$\sum_{\substack{10^7<p<10^7+10^4\\ p\text{ prime}}}\ \sum_{k=0}^{\lfloor\sqrt p\rfloor}\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod M.$$
هنا \(a=\sqrt5\approx 2.236\)، ولذلك فإن القيم الممكنة لـ \(k\) هي فقط \(0\) و\(1\) و\(2\).
عندما \(k=0\)، تكون المساهمة
$$\binom{5}{0}=1.$$
وهي تمثل الشعبة الوحيدة التي تطرح \(1\) فقط:
$$5\to 4\to 3\to 2,<\sqrt5.$$
وعندما \(k=1\)، نجد أن
$$T_1=5-\lceil \sqrt5\rceil=5-3=2,$$
ومن ثم يمكن أن تكون \(s_1\) مساوية لـ \(0\) أو \(1\) أو \(2\). وهذا يعطي الشعب الثلاث
$$\sqrt5,1;\qquad 1,\sqrt5;\qquad 1,1,\sqrt5,$$
وبالتالي المساهمة
$$\binom{2+1}{1}=3.$$
وعندما \(k=2\)، نحصل على
$$T_2=5-\lceil 2\sqrt5\rceil=5-5=0,$$
لذا لا يوجد إلا الخيار \((s_1,s_2)=(0,0)\)، وهو يقابل الشعبة
$$\sqrt5,\sqrt5,$$
ومساهمتها
$$\binom{0+2}{2}=1.$$
إذن
$$G(5)=1+3+1=5.$$
التنفيذات بلغة C++ وPython وJava تتبع جميعًا المسار نفسه.
في البداية تُحضَّر جداول المضروب ومقلوب المضروب بترديد \(10^9+7\) حتى أكبر قيمة قد تظهر داخل معامل ثنائي الحد. بعد ذلك يصبح استخراج أي قيمة توافقية عملية بزمن ثابت.
بعدها تُولَّد جميع الأعداد الأولية في المجال \(10^7<p<10^7+10^4\) باستخدام مصفاة مجزأة. ولأن عرض النافذة هو \(10^4\) فقط، فإن هذه المرحلة أرخص بكثير من بناء مصفاة كاملة حتى الحد الأعلى.
لكل عدد أولي \(p\)، يدور التنفيذ على
$$0\le k\le \lfloor\sqrt p\rfloor$$
ويجمع الحد
$$\binom{p-\lceil k\sqrt p\rceil+k}{k}\pmod{10^9+7}.$$
والكمية الحساسة الوحيدة هي \(\lceil k\sqrt p\rceil\). بدلًا من محاكاة العودية الحقيقية على الأعداد الفعلية، يحسب التنفيذ هذا السقف عدديًا من \(\sqrt{k^2p}\)، ثم يبني الحد التوافقي الموافق مباشرة.
وفي النهاية تُجمع مساهمات جميع الأعداد الأولية بترديد \(10^9+7\).
لنكتب \(U=10^7+10^4-1\)، ولنرمز إلى عرض نافذة الأعداد الأولية بـ \(W=10^4\)، وإلى عدد الأعداد الأولية داخلها بـ \(P\).
التحضير المسبق للمضاريب ومقلوباتها حتى \(U\) يكلّف \(O(U)\) زمنًا و\(O(U)\) ذاكرة. والمصفاة المجزأة تحتاج فقط إلى الأعداد الأولية الأساسية حتى \(\sqrt U\)، ولذلك فإن توليد الأعداد الأولية داخل النافذة الهدف يكلّف تقريبًا \(O(\sqrt U\log\log U+W\log\log U)\) زمنًا و\(O(W)\) ذاكرة إضافية.
أما حساب \(G(p)\) لكل عدد أولي \(p\)، فيحتاج إلى \(\lfloor\sqrt p\rfloor+1\) حدود، أي \(O(\sqrt p)\) زمنًا لكل عدد أولي. وبذلك يصبح الزمن الكلي
$$O\!\left(U+P\sqrt U\right),$$
بينما تظل الذاكرة محكومة بجداول المضاريب، أي
$$O(U).$$