For each subset \(A \subseteq \{1,2,\dots,n\}\), call an element \(x \in A\) an elevisor if \(x\) divides at least one other element of \(A\). The problem asks for the total sum of all elevisors over all subsets of \(\{1,\dots,n\}\) when \(n=10^{14}\), modulo \(M=1234567891\).
Enumerating subsets is hopeless because there are \(2^n\) of them. The key move is to reverse the order of summation: instead of looping over subsets, fix a value \(x\) and count how many subsets make that specific \(x\) an elevisor.
If \(E(A)\) denotes the set of elevisors of \(A\), then the desired quantity is
\[ S(n)=\sum_{A\subseteq \{1,\dots,n\}} \sum_{x\in E(A)} x \pmod M. \]
Fix \(x\). Let
\[ q=\left\lfloor \frac{n}{x} \right\rfloor. \]
Then the multiples of \(x\) inside \(\{1,\dots,n\}\) are \(x,2x,\dots,qx\), so there are exactly \(q\) of them.
For \(x\) to be an elevisor of a subset \(A\), two conditions are necessary and sufficient: \(x\) itself must be chosen, and at least one of the other \(q-1\) multiples of \(x\) must also be chosen. Every non-multiple of \(x\) may be chosen freely.
Therefore the number of subsets in which \(x\) is an elevisor is
\[ 2^{n-q}\left(2^{q-1}-1\right). \]
This can be rewritten in the more convenient form
\[ 2^{n-q}\left(2^{q-1}-1\right)=2^{n-1}-2^{n-q}. \]
The interpretation is simple: \(2^{n-1}\) counts all subsets containing \(x\), and \(2^{n-q}\) removes the subsets where \(x\) is present but no other multiple of \(x\) is present.
Now sum the contribution of each possible elevisor separately. By linearity,
\[ S(n)=\sum_{x=1}^{n} x\left(2^{n-1}-2^{n-\left\lfloor n/x\right\rfloor}\right). \]
This is exactly the formula used by the C++, Python, and Java implementations. Splitting off the easy part gives
\[ S(n)=2^{n-1}\sum_{x=1}^{n} x-\sum_{x=1}^{n} x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
Since \(\sum_{x=1}^{n}x=n(n+1)/2\), all of the real work is concentrated in the weighted sum
\[ W(n)=\sum_{x=1}^{n} x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
The quotient \(\left\lfloor n/x\right\rfloor\) stays constant on long intervals. If
\[ q=\left\lfloor \frac{n}{x} \right\rfloor, \]
then the corresponding values of \(x\) are exactly those in
\[ \left\lfloor \frac{n}{q+1} \right\rfloor+1 \le x \le \left\lfloor \frac{n}{q} \right\rfloor. \]
On such an interval the power of 2 is constant, so the whole block contributes
\[ 2^{n-q}\sum_{x=l}^{r}x = 2^{n-q}\frac{(l+r)(r-l+1)}{2}. \]
This turns many consecutive terms of \(W(n)\) into one arithmetic-progression calculation.
Take \(x=2\). Then \(q=\lfloor 10/2\rfloor=5\), and the relevant multiples are \(2,4,6,8,10\). To make 2 an elevisor, we must include 2, include at least one of \(\{4,6,8,10\}\), and choose any subset of the five non-multiples \(\{1,3,5,7,9\}\). Hence 2 is an elevisor in
\[ 2^{5}(2^{4}-1)=480 \]
subsets, contributing \(2\cdot 480=960\) to \(S(10)\).
The quotient grouping is visible in the same example. For \(W(10)\), the quotient \(q=1\) occurs for \(x=6,7,8,9,10\), so that whole block contributes
\[ 2^{10-1}(6+7+8+9+10)=2^{9}\cdot 40. \]
This is the exact compression used on the large-\(x\) side of the final algorithm.
The implementations choose a fixed cutoff \(B=3{,}000{,}000\). Values \(x\le B\) are handled directly, while values \(x>B\) are regrouped by the quotient \(q=\lfloor n/x\rfloor\).
Because \(x>B\) implies \(q\le \lfloor n/(B+1)\rfloor\), the remaining quotients are relatively small. The resulting decomposition is
\[ W(n) = \sum_{x=1}^{B} x\,2^{n-\left\lfloor n/x\right\rfloor} + \sum_{q=1}^{\left\lfloor n/(B+1)\right\rfloor} 2^{n-q} \sum_{x=\max\left(B+1,\left\lfloor \frac{n}{q+1}\right\rfloor+1\right)}^{\left\lfloor n/q\right\rfloor} x. \]
This is not merely a conceptual derivation; it is the exact formula evaluated by the code.
The implementation first computes \(2^{n-1}\bmod M\), because it appears in the closed form of the easy summand. It also evaluates arithmetic-progression sums modulo \(M\) so that a whole interval \([l,r]\) can be handled without iterating through every integer in that interval.
The first pass runs through \(x=1,2,\dots,\min(n,B)\). For each \(x\), it forms \(q=\lfloor n/x\rfloor\), computes \(2^{n-q}\bmod M\) by binary exponentiation, multiplies by \(x\), and adds the result to the running value of \(W(n)\).
The second pass runs through \(q=1,2,\dots,\lfloor n/(B+1)\rfloor\). For each quotient it reconstructs the interval of values \(x>B\) satisfying \(\lfloor n/x\rfloor=q\), evaluates the interval sum, and multiplies by the common factor \(2^{n-q}\).
At this stage the implementation maintains a useful invariant: at the beginning of the iteration for a given \(q\), the stored power is exactly \(2^{n-q}\bmod M\). Moving to the next quotient therefore only requires multiplication by \(2^{-1}\bmod M\). Since \(M\) is odd, \(2^{-1}\equiv (M+1)/2 \pmod M\).
After \(W(n)\) has been computed, the programs evaluate \(2^{n-1}\cdot n(n+1)/2 \bmod M\) and subtract \(W(n)\) modulo \(M\). The C++ and Java implementations also perform small sanity checks, including \(S(1)=0\) and \(S(10)=4927\), before printing the value for \(n=10^{14}\).
Let \(B=3{,}000{,}000\). The direct pass performs \(B\) iterations, and each one computes a modular power by repeated squaring, so this part costs \(O(B\log n)\).
The block pass performs \(\lfloor n/(B+1)\rfloor\) iterations, each with constant-time arithmetic, so it costs \(O(n/B)\). Therefore the implemented algorithm runs in
\[ O(B\log n+n/B) \]
time and uses \(O(1)\) extra memory. For the target value \(n=10^{14}\), this is practical while still computing the exact mathematical sum.
Für jede Teilmenge \(A \subseteq \{1,2,\dots,n\}\) nennen wir ein Element \(x \in A\) einen Elevisor, wenn \(x\) mindestens ein anderes Element von \(A\) teilt. Gesucht ist die Gesamtsumme aller Elevisoren über alle Teilmengen von \(\{1,\dots,n\}\) für \(n=10^{14}\), modulo \(M=1234567891\).
Ein Durchlauf über alle Teilmengen ist unmöglich, denn es gibt \(2^n\) davon. Der entscheidende Schritt ist deshalb ein Summenwechsel: Statt Teilmengen zu erzeugen, fixiert man einen Wert \(x\) und zählt, in wie vielen Teilmengen genau dieses \(x\) ein Elevisor ist.
Bezeichne mit \(E(A)\) die Menge der Elevisoren von \(A\). Dann ist die gesuchte Größe
\[ S(n)=\sum_{A\subseteq \{1,\dots,n\}} \sum_{x\in E(A)} x \pmod M. \]
Fixiere \(x\) und setze
\[ q=\left\lfloor \frac{n}{x} \right\rfloor. \]
Dann sind \(x,2x,\dots,qx\) genau die Vielfachen von \(x\) innerhalb von \(\{1,\dots,n\}\); es gibt also genau \(q\) Stück.
Damit \(x\) in einer Teilmenge \(A\) ein Elevisor ist, muss \(x\) selbst ausgewählt werden, und zusätzlich muss mindestens eines der übrigen \(q-1\) Vielfachen ebenfalls ausgewählt werden. Alle Nichtvielfachen von \(x\) sind frei wählbar.
Daraus folgt sofort, dass die Anzahl passender Teilmengen gleich
\[ 2^{n-q}\left(2^{q-1}-1\right) \]
ist. Praktischer ist die äquivalente Form
\[ 2^{n-q}\left(2^{q-1}-1\right)=2^{n-1}-2^{n-q}. \]
Hier zählt \(2^{n-1}\) alle Teilmengen, die \(x\) enthalten, und \(2^{n-q}\) entfernt genau die Fälle, in denen zwar \(x\) gewählt wurde, aber kein weiteres Vielfaches von \(x\).
Nun summiert man die Beiträge aller möglichen Elevisoren getrennt. Wegen der Linearität erhält man
\[ S(n)=\sum_{x=1}^{n} x\left(2^{n-1}-2^{n-\left\lfloor n/x\right\rfloor}\right). \]
Genau diese Formel verwenden die drei Implementierungen. Den einfachen Teil kann man sofort abspalten:
\[ S(n)=2^{n-1}\sum_{x=1}^{n}x-\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
Da \(\sum_{x=1}^{n}x=n(n+1)/2\) gilt, konzentriert sich die gesamte Schwierigkeit auf
\[ W(n)=\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
Der Ausdruck \(\left\lfloor n/x\right\rfloor\) bleibt auf ganzen Intervallen konstant. Gilt
\[ q=\left\lfloor \frac{n}{x} \right\rfloor, \]
dann sind genau die \(x\) aus dem Bereich
\[ \left\lfloor \frac{n}{q+1} \right\rfloor+1 \le x \le \left\lfloor \frac{n}{q} \right\rfloor \]
zugehörig. Auf einem solchen Intervall ist der Zweierpotenzfaktor konstant, also liefert der ganze Block
\[ 2^{n-q}\sum_{x=l}^{r}x = 2^{n-q}\frac{(l+r)(r-l+1)}{2}. \]
Damit ersetzt man viele aufeinanderfolgende Summanden durch eine einzige Summe einer arithmetischen Folge.
Betrachte \(x=2\). Dann ist \(q=\lfloor 10/2\rfloor=5\), also sind die relevanten Vielfachen \(2,4,6,8,10\). Damit 2 ein Elevisor ist, muss 2 gewählt werden, mindestens eines aus \(\{4,6,8,10\}\) gewählt werden, und aus den fünf Nichtvielfachen \(\{1,3,5,7,9\}\) darf beliebig gewählt werden. Also tritt 2 in
\[ 2^{5}(2^{4}-1)=480 \]
passenden Teilmengen als Elevisor auf und trägt daher \(2\cdot 480=960\) zu \(S(10)\) bei.
Dasselbe Beispiel zeigt die Quotientenblock-Idee. In \(W(10)\) gehört der Quotient \(q=1\) zu \(x=6,7,8,9,10\), also ist der gesamte Blockbeitrag
\[ 2^{10-1}(6+7+8+9+10)=2^{9}\cdot 40. \]
Genau diese Bündelung wird auf der großen-\(x\)-Seite des Algorithmus ausgenutzt.
Die Implementierungen wählen den festen Grenzwert \(B=3{,}000{,}000\). Für \(x\le B\) wird direkt summiert, für \(x>B\) wird nach dem Quotienten \(q=\lfloor n/x\rfloor\) gruppiert.
Aus \(x>B\) folgt \(q\le \lfloor n/(B+1)\rfloor\), also bleiben im zweiten Teil nur kleine Quotientenwerte übrig. Damit lautet die tatsächlich ausgewertete Zerlegung
\[ W(n) = \sum_{x=1}^{B}x\,2^{n-\left\lfloor n/x\right\rfloor} + \sum_{q=1}^{\left\lfloor n/(B+1)\right\rfloor} 2^{n-q} \sum_{x=\max\left(B+1,\left\lfloor \frac{n}{q+1}\right\rfloor+1\right)}^{\left\lfloor n/q\right\rfloor}x. \]
Das ist nicht nur eine Herleitung auf dem Papier, sondern genau die Formel, die der Code auswertet.
Die Implementierung berechnet zuerst \(2^{n-1}\bmod M\), weil dieser Faktor im geschlossenen Ausdruck des einfachen Summanden vorkommt. Außerdem wird die Summenformel für arithmetische Folgen modulo \(M\) verwendet, damit ein ganzes Intervall \([l,r]\) ohne Einzelschleife verarbeitet werden kann.
Im ersten Durchgang werden die Werte \(x=1,2,\dots,\min(n,B)\) bearbeitet. Für jedes \(x\) wird \(q=\lfloor n/x\rfloor\) bestimmt, dann \(2^{n-q}\bmod M\) per binärer Exponentiation berechnet, mit \(x\) multipliziert und zum laufenden Wert von \(W(n)\) addiert.
Im zweiten Durchgang läuft die Implementierung über \(q=1,2,\dots,\lfloor n/(B+1)\rfloor\). Für jeden Quotienten wird das Intervall der Werte \(x>B\) mit \(\lfloor n/x\rfloor=q\) rekonstruiert, die Intervallsumme berechnet und mit dem gemeinsamen Faktor \(2^{n-q}\) multipliziert.
Dabei bleibt eine einfache Invariante erhalten: Zu Beginn der Iteration für ein bestimmtes \(q\) ist die gespeicherte Potenz genau \(2^{n-q}\bmod M\). Für den Übergang zu \(q+1\) genügt also eine Multiplikation mit \(2^{-1}\bmod M\). Da \(M\) ungerade ist, gilt \(2^{-1}\equiv (M+1)/2 \pmod M\).
Nachdem \(W(n)\) feststeht, berechnen die Programme \(2^{n-1}\cdot n(n+1)/2 \bmod M\) und subtrahieren \(W(n)\) modulo \(M\). Die C++- und Java-Implementierungen prüfen vorher noch kleine Testfälle, darunter \(S(1)=0\) und \(S(10)=4927\), bevor der Zielwert für \(n=10^{14}\) ausgegeben wird.
Sei \(B=3{,}000{,}000\). Der direkte Teil benötigt \(B\) Iterationen, und in jeder davon wird eine modulare Potenz per wiederholtem Quadrieren berechnet. Dieser Abschnitt kostet also \(O(B\log n)\).
Der Blockteil benötigt \(\lfloor n/(B+1)\rfloor\) Iterationen mit jeweils nur konstanter Arithmetik und kostet daher \(O(n/B)\). Insgesamt läuft der implementierte Algorithmus also in
\[ O(B\log n+n/B) \]
Zeit und verwendet \(O(1)\) zusätzlichen Speicher. Für \(n=10^{14}\) ist das praktisch genug und bleibt dennoch exakt.
\(\{1,2,\dots,n\}\) kümesinin her altkümesi \(A\) için, \(A\) içindeki bir \(x\) elemanına, \(A\) içindeki kendisinden farklı en az bir başka elemanı bölüyorsa elevisor diyelim. Problem, \(n=10^{14}\) için bütün altkümeler üzerindeki tüm elevisorların toplamını \(M=1234567891\) modunda bulmayı istiyor.
Bunu altkümeleri tek tek gezerek yapmak imkansızdır; çünkü toplam \(2^n\) tane altküme vardır. Temel fikir, toplamın yönünü değiştirmektir: altkümeler üzerinden gitmek yerine bir \(x\) sabitlenir ve bu belirli \(x\)'in kaç altkümede elevisor olduğu sayılır.
\(E(A)\), \(A\) kümesinin elevisorlar kümesi olsun. Aranan nicelik
\[ S(n)=\sum_{A\subseteq \{1,\dots,n\}} \sum_{x\in E(A)} x \pmod M \]
şeklindedir.
Bir \(x\) değeri sabitlensin ve
\[ q=\left\lfloor \frac{n}{x} \right\rfloor \]
olsun. O zaman \(\{1,\dots,n\}\) içinde \(x\)'in katları tam olarak \(x,2x,\dots,qx\) sayılarıdır; yani toplam \(q\) tane kat vardır.
\(x\)'in bir altkümede elevisor olabilmesi için iki koşul gerekir ve yeterlidir: \(x\)'in kendisi seçilmiş olmalıdır ve kalan \(q-1\) katın en az biri de seçilmiş olmalıdır. \(x\)'in katı olmayan sayılar ise tamamen serbesttir.
Bu nedenle \(x\)'in elevisor olduğu altküme sayısı
\[ 2^{n-q}\left(2^{q-1}-1\right) \]
olur. Bunu
\[ 2^{n-q}\left(2^{q-1}-1\right)=2^{n-1}-2^{n-q} \]
biçiminde yazmak daha kullanışlıdır. Burada \(2^{n-1}\), \(x\)'i içeren bütün altkümeleri sayar; \(2^{n-q}\) ise \(x\) seçildiği halde başka hiçbir katının seçilmediği durumları çıkarır.
Artık her olası elevisorun katkısını ayrı ayrı toplayabiliriz. Doğrusallıktan dolayı
\[ S(n)=\sum_{x=1}^{n}x\left(2^{n-1}-2^{n-\left\lfloor n/x\right\rfloor}\right) \]
elde edilir. C++, Python ve Java uygulamalarının hesapladığı temel formül tam olarak budur. Kolay kısmı ayırırsak
\[ S(n)=2^{n-1}\sum_{x=1}^{n}x-\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor} \]
olur. \(\sum_{x=1}^{n}x=n(n+1)/2\) olduğundan, asıl zor terim
\[ W(n)=\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor} \]
toplamıdır.
\(\left\lfloor n/x\right\rfloor\) ifadesi tek tek her \(x\) için farklı davranmak zorunda değildir; uzun aralıklarda sabit kalır. Eğer
\[ q=\left\lfloor \frac{n}{x} \right\rfloor \]
ise, bu aynı bölüme sahip bütün \(x\) değerleri
\[ \left\lfloor \frac{n}{q+1} \right\rfloor+1 \le x \le \left\lfloor \frac{n}{q} \right\rfloor \]
aralığındadır. Bu aralıkta 2'nin üssü değişmediği için blok katkısı
\[ 2^{n-q}\sum_{x=l}^{r}x = 2^{n-q}\frac{(l+r)(r-l+1)}{2} \]
olur. Böylece ardışık birçok terim tek bir aritmetik dizi toplamına indirgenir.
\(x=2\) alalım. Bu durumda \(q=\lfloor 10/2\rfloor=5\) ve ilgili katlar \(2,4,6,8,10\) olur. 2'nin elevisor olması için 2 mutlaka seçilmeli, \(\{4,6,8,10\}\) içinden en az biri seçilmeli ve kat olmayan \(\{1,3,5,7,9\}\) sayılarından herhangi bir altküme alınabilmelidir. Dolayısıyla 2, tam
\[ 2^{5}(2^{4}-1)=480 \]
altkümede elevisordur; bu da \(S(10)\) toplamına \(2\cdot 480=960\) katkı verir.
Aynı örnek bölüm gruplamasını da gösterir. \(W(10)\) içinde \(q=1\) değeri \(x=6,7,8,9,10\) için geçerlidir; bu yüzden tüm blok tek seferde
\[ 2^{10-1}(6+7+8+9+10)=2^{9}\cdot 40 \]
olarak hesaplanır.
Uygulamalar sabit bir eşik olarak \(B=3{,}000{,}000\) seçer. \(x\le B\) için terimler doğrudan toplanır; \(x>B\) içinse toplam, \(q=\lfloor n/x\rfloor\) değerine göre bloklara ayrılır.
\(x>B\) olduğunda \(q\le \lfloor n/(B+1)\rfloor\) olur; yani ikinci aşamada yalnızca küçük bölüm değerleri kalır. Kodun kullandığı ayrışım tam olarak
\[ W(n) = \sum_{x=1}^{B}x\,2^{n-\left\lfloor n/x\right\rfloor} + \sum_{q=1}^{\left\lfloor n/(B+1)\right\rfloor} 2^{n-q} \sum_{x=\max\left(B+1,\left\lfloor \frac{n}{q+1}\right\rfloor+1\right)}^{\left\lfloor n/q\right\rfloor}x \]
formülüdür. Bu, yalnızca sezgisel bir açıklama değil, doğrudan uygulanan matematiksel parçalamadır.
Önce \(2^{n-1}\bmod M\) hesaplanır; çünkü kolay terimin kapalı formunda bu çarpan yer alır. Ayrıca \([l,r]\) aralığındaki sayıların toplamı modulo \(M\) altında aritmetik dizi formülüyle hesaplanır; böylece blok içindeki her sayıyı tek tek dolaşmaya gerek kalmaz.
İlk geçişte \(x=1,2,\dots,\min(n,B)\) değerleri ele alınır. Her \(x\) için \(q=\lfloor n/x\rfloor\) bulunur, \(2^{n-q}\bmod M\) ikili üs alma ile hesaplanır, \(x\) ile çarpılır ve \(W(n)\)'in biriken değerine eklenir.
İkinci geçiş \(q=1,2,\dots,\lfloor n/(B+1)\rfloor\) üzerinde çalışır. Her bölüm için \(\lfloor n/x\rfloor=q\) koşulunu sağlayan \(x>B\) aralığı yeniden kurulur, aralık toplamı hesaplanır ve ortak \(2^{n-q}\) katsayısıyla çarpılır.
Burada önemli bir değişmez korunur: belirli bir \(q\) için iterasyonun başında elde tutulan üs değeri tam olarak \(2^{n-q}\bmod M\)'dir. Bir sonraki bölüme geçmek için yalnızca \(2^{-1}\bmod M\) ile çarpmak yeterlidir. \(M\) tek sayı olduğu için \(2^{-1}\equiv (M+1)/2 \pmod M\) olur.
\(W(n)\) elde edildikten sonra programlar \(2^{n-1}\cdot n(n+1)/2 \bmod M\) değerini hesaplayıp bundan \(W(n)\)'i modüler olarak çıkarır. C++ ve Java sürümleri, \(n=10^{14}\) için sonucu yazdırmadan önce \(S(1)=0\) ve \(S(10)=4927\) gibi küçük doğrulamaları da kontrol eder.
\(B=3{,}000{,}000\) olsun. Doğrudan geçiş \(B\) adım sürer ve her adımda tekrar eden kareleme ile bir modüler üs hesaplandığı için bu bölümün maliyeti \(O(B\log n)\)'dir.
Blok geçişi ise \(\lfloor n/(B+1)\rfloor\) adım içerir ve her adımda yalnızca sabit sayıda aritmetik işlem yapar; dolayısıyla bu bölüm \(O(n/B)\) zaman alır. Sonuç olarak uygulanan algoritma
\[ O(B\log n+n/B) \]
zamanda çalışır ve \(O(1)\) ek bellek kullanır. \(n=10^{14}\) için bu yaklaşım hem pratik hem de tam doğrudur.
Para cada subconjunto \(A \subseteq \{1,2,\dots,n\}\), llamemos elevisor a un elemento \(x \in A\) si \(x\) divide al menos a otro elemento de \(A\). El problema pide la suma total de todos los elevisores sobre todos los subconjuntos de \(\{1,\dots,n\}\) cuando \(n=10^{14}\), módulo \(M=1234567891\).
Recorrer todos los subconjuntos es imposible porque hay \(2^n\) de ellos. La idea decisiva es cambiar el orden de la suma: en vez de iterar por subconjuntos, fijamos un valor \(x\) y contamos en cuántos subconjuntos ese \(x\) concreto actúa como elevisor.
Si \(E(A)\) denota el conjunto de elevisores de \(A\), entonces la cantidad buscada es
\[ S(n)=\sum_{A\subseteq \{1,\dots,n\}} \sum_{x\in E(A)} x \pmod M. \]
Fijemos \(x\) y definamos
\[ q=\left\lfloor \frac{n}{x} \right\rfloor. \]
Entonces los múltiplos de \(x\) dentro de \(\{1,\dots,n\}\) son \(x,2x,\dots,qx\), así que hay exactamente \(q\) múltiplos.
Para que \(x\) sea un elevisor de un subconjunto \(A\), deben cumplirse dos condiciones: \(x\) tiene que estar en \(A\), y al menos uno de los otros \(q-1\) múltiplos de \(x\) también tiene que estar en \(A\). Los números que no son múltiplos de \(x\) pueden elegirse libremente.
Por tanto, el número de subconjuntos en los que \(x\) es elevisor es
\[ 2^{n-q}\left(2^{q-1}-1\right). \]
Conviene escribirlo como
\[ 2^{n-q}\left(2^{q-1}-1\right)=2^{n-1}-2^{n-q}. \]
La lectura combinatoria es clara: \(2^{n-1}\) cuenta todos los subconjuntos que contienen a \(x\), y \(2^{n-q}\) resta aquellos en los que \(x\) aparece pero no aparece ningún otro múltiplo suyo.
Ahora sumamos por separado la contribución de cada posible elevisor. Por linealidad, obtenemos
\[ S(n)=\sum_{x=1}^{n}x\left(2^{n-1}-2^{n-\left\lfloor n/x\right\rfloor}\right). \]
Ésta es exactamente la fórmula que calculan las implementaciones en C++, Python y Java. Separando la parte sencilla, queda
\[ S(n)=2^{n-1}\sum_{x=1}^{n}x-\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
Como \(\sum_{x=1}^{n}x=n(n+1)/2\), toda la dificultad real está en
\[ W(n)=\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
El valor \(\left\lfloor n/x\right\rfloor\) permanece constante en intervalos largos. Si
\[ q=\left\lfloor \frac{n}{x} \right\rfloor, \]
entonces los \(x\) que producen ese mismo cociente son exactamente los del intervalo
\[ \left\lfloor \frac{n}{q+1} \right\rfloor+1 \le x \le \left\lfloor \frac{n}{q} \right\rfloor. \]
En ese bloque la potencia de 2 es constante, así que la contribución total es
\[ 2^{n-q}\sum_{x=l}^{r}x = 2^{n-q}\frac{(l+r)(r-l+1)}{2}. \]
Así, muchos términos consecutivos se comprimen en una sola suma de progresión aritmética.
Tomemos \(x=2\). Entonces \(q=\lfloor 10/2\rfloor=5\), y los múltiplos relevantes son \(2,4,6,8,10\). Para que 2 sea elevisor, debemos incluir 2, incluir al menos uno de \(\{4,6,8,10\}\), y escoger libremente cualquier subconjunto de los cinco no múltiplos \(\{1,3,5,7,9\}\). Por eso 2 es elevisor en
\[ 2^{5}(2^{4}-1)=480 \]
subconjuntos, con una contribución total de \(2\cdot 480=960\) a \(S(10)\).
El mismo ejemplo muestra la agrupación por cociente. En \(W(10)\), el valor \(q=1\) corresponde a \(x=6,7,8,9,10\), así que todo ese bloque aporta
\[ 2^{10-1}(6+7+8+9+10)=2^{9}\cdot 40. \]
Ésa es exactamente la compresión utilizada en la fase de valores grandes de \(x\).
Las implementaciones fijan un umbral \(B=3{,}000{,}000\). Los valores \(x\le B\) se suman de forma directa; los valores \(x>B\) se reagrupan por el cociente \(q=\lfloor n/x\rfloor\).
Como \(x>B\) implica \(q\le \lfloor n/(B+1)\rfloor\), en la segunda fase sólo quedan cocientes relativamente pequeños. La descomposición evaluada por el código es
\[ W(n) = \sum_{x=1}^{B}x\,2^{n-\left\lfloor n/x\right\rfloor} + \sum_{q=1}^{\left\lfloor n/(B+1)\right\rfloor} 2^{n-q} \sum_{x=\max\left(B+1,\left\lfloor \frac{n}{q+1}\right\rfloor+1\right)}^{\left\lfloor n/q\right\rfloor}x. \]
No es una descripción genérica: es la fórmula exacta que implementan los tres programas.
La implementación calcula primero \(2^{n-1}\bmod M\), porque ese factor aparece en la parte cerrada de la fórmula. También usa la suma de una progresión aritmética módulo \(M\) para evaluar cualquier intervalo \([l,r]\) sin recorrerlo elemento por elemento.
La primera pasada recorre \(x=1,2,\dots,\min(n,B)\). Para cada \(x\), calcula \(q=\lfloor n/x\rfloor\), obtiene \(2^{n-q}\bmod M\) mediante exponenciación binaria, multiplica por \(x\) y acumula el resultado en \(W(n)\).
La segunda pasada recorre \(q=1,2,\dots,\lfloor n/(B+1)\rfloor\). Para cada cociente, reconstruye el intervalo de valores \(x>B\) que satisfacen \(\lfloor n/x\rfloor=q\), calcula la suma del intervalo y la multiplica por el factor común \(2^{n-q}\).
Aquí se mantiene un invariante sencillo: al empezar la iteración del cociente \(q\), la potencia almacenada vale exactamente \(2^{n-q}\bmod M\). Pasar al siguiente cociente sólo requiere multiplicar por \(2^{-1}\bmod M\). Como \(M\) es impar, se tiene \(2^{-1}\equiv (M+1)/2 \pmod M\).
Una vez calculado \(W(n)\), los programas evalúan \(2^{n-1}\cdot n(n+1)/2 \bmod M\) y restan \(W(n)\) módulo \(M\). Las versiones en C++ y Java además comprueban casos pequeños, entre ellos \(S(1)=0\) y \(S(10)=4927\), antes de imprimir la respuesta para \(n=10^{14}\).
Sea \(B=3{,}000{,}000\). La pasada directa realiza \(B\) iteraciones, y en cada una calcula una potencia modular por exponenciación rápida, así que su coste es \(O(B\log n)\).
La pasada por bloques realiza \(\lfloor n/(B+1)\rfloor\) iteraciones con sólo aritmética constante en cada una, por lo que cuesta \(O(n/B)\). En consecuencia, el algoritmo implementado funciona en
\[ O(B\log n+n/B) \]
tiempo y usa \(O(1)\) memoria adicional. Para \(n=10^{14}\), este coste es totalmente manejable.
对每个子集 \(A \subseteq \{1,2,\dots,n\}\)，如果 \(x \in A\) 并且 \(x\) 能整除 \(A\) 中另一个不同的元素，就称 \(x\) 是这个子集的一个 elevisor。题目要求在 \(n=10^{14}\) 时，把 \(\{1,\dots,n\}\) 的所有子集中的全部 elevisor 加总，并对 \(M=1234567891\) 取模。
显然不能按子集暴力枚举，因为子集总数是 \(2^n\)。真正的突破点是把求和顺序反过来：不是先枚举子集，再找其中的 elevisor，而是先固定一个数 \(x\)，统计它在多少个子集中会成为 elevisor。
设 \(E(A)\) 表示子集 \(A\) 中所有 elevisor 的集合，那么目标量就是
\[ S(n)=\sum_{A\subseteq \{1,\dots,n\}} \sum_{x\in E(A)} x \pmod M. \]
先固定某个 \(x\)，记
\[ q=\left\lfloor \frac{n}{x} \right\rfloor. \]
那么在 \(\{1,\dots,n\}\) 中，\(x\) 的倍数正好是 \(x,2x,\dots,qx\)，总共有 \(q\) 个。
要让 \(x\) 在某个子集 \(A\) 中成为 elevisor，条件恰好有两个：第一，\(x\) 自己必须被选进 \(A\)；第二，其余 \(q-1\) 个倍数里至少还要选进一个。至于不是 \(x\) 倍数的数，选不选完全自由。
因此，使 \(x\) 成为 elevisor 的子集个数为
\[ 2^{n-q}\left(2^{q-1}-1\right). \]
把它改写成
\[ 2^{n-q}\left(2^{q-1}-1\right)=2^{n-1}-2^{n-q} \]
会更方便理解。前一项 \(2^{n-1}\) 表示所有包含 \(x\) 的子集；后一项 \(2^{n-q}\) 则对应“选了 \(x\)，但一个额外的 \(x\) 倍数都没选”的坏情况，需要把它们删掉。
现在可以把每个可能的 elevisor 分开累加。根据求和的线性性，有
\[ S(n)=\sum_{x=1}^{n}x\left(2^{n-1}-2^{n-\left\lfloor n/x\right\rfloor}\right). \]
这正是三份实现真正计算的公式。把容易的部分拆出来，可得
\[ S(n)=2^{n-1}\sum_{x=1}^{n}x-\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
由于 \(\sum_{x=1}^{n}x=n(n+1)/2\)，问题的难点完全集中在
\[ W(n)=\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor} \]
这个加权和上。
\(\left\lfloor n/x\right\rfloor\) 并不是每次只变化一个点，它会在整段区间内保持不变。若
\[ q=\left\lfloor \frac{n}{x} \right\rfloor, \]
则所有满足这个商的 \(x\) 恰好构成区间
\[ \left\lfloor \frac{n}{q+1} \right\rfloor+1 \le x \le \left\lfloor \frac{n}{q} \right\rfloor. \]
在这样一个区间里，2 的幂次完全相同，因此整块贡献可以一次写成
\[ 2^{n-q}\sum_{x=l}^{r}x = 2^{n-q}\frac{(l+r)(r-l+1)}{2}. \]
这一步非常关键，因为它把许多连续项压缩成一次等差数列求和。
取 \(x=2\)。这时 \(q=\lfloor 10/2\rfloor=5\)，相关倍数是 \(2,4,6,8,10\)。要让 2 成为 elevisor，必须选中 2，必须在 \(\{4,6,8,10\}\) 中至少再选一个，同时 \(\{1,3,5,7,9\}\) 这五个非倍数元素可以任意取舍。所以 2 成为 elevisor 的子集总数是
\[ 2^{5}(2^{4}-1)=480. \]
因此 2 对 \(S(10)\) 的贡献是 \(2\cdot 480=960\)。
同一个例子也能看出分块的作用。在 \(W(10)\) 中，商 \(q=1\) 对应 \(x=6,7,8,9,10\)，于是这一整块可以直接写成
\[ 2^{10-1}(6+7+8+9+10)=2^{9}\cdot 40. \]
这就是实现处理大 \(x\) 时所利用的压缩方式。
代码选取固定分界 \(B=3{,}000{,}000\)。当 \(x\le B\) 时直接逐项累加；当 \(x>B\) 时，则改为按商 \(q=\lfloor n/x\rfloor\) 分块。
因为 \(x>B\) 会推出 \(q\le \lfloor n/(B+1)\rfloor\)，第二阶段只需要处理较小的商值。于是代码实际计算的就是
\[ W(n) = \sum_{x=1}^{B}x\,2^{n-\left\lfloor n/x\right\rfloor} + \sum_{q=1}^{\left\lfloor n/(B+1)\right\rfloor} 2^{n-q} \sum_{x=\max\left(B+1,\left\lfloor \frac{n}{q+1}\right\rfloor+1\right)}^{\left\lfloor n/q\right\rfloor}x. \]
这不是抽象的优化思路，而是实现逐字遵循的数学分解。
实现首先算出 \(2^{n-1}\bmod M\)，因为封闭形式里的第一项要用到它。同时，区间 \([l,r]\) 的和使用等差数列公式在模 \(M\) 下直接计算，这样就不需要真的把整个区间遍历一遍。
第一段循环遍历 \(x=1,2,\dots,\min(n,B)\)。对每个 \(x\)，先求 \(q=\lfloor n/x\rfloor\)，再用二进制快速幂算出 \(2^{n-q}\bmod M\)，乘上 \(x\) 之后加到 \(W(n)\) 中。
第二段循环遍历 \(q=1,2,\dots,\lfloor n/(B+1)\rfloor\)。对于每个商值，程序反推出所有满足 \(\lfloor n/x\rfloor=q\) 且 \(x>B\) 的整数区间，计算这个区间的整数和，再乘上公共因子 \(2^{n-q}\)。
这一段维护着一个很重要的不变量：当循环准备处理某个 \(q\) 时，当前保存的幂恰好是 \(2^{n-q}\bmod M\)。因此从 \(q\) 走到 \(q+1\) 时，只需要再乘一次 \(2^{-1}\bmod M\)。因为 \(M\) 是奇数，所以 \(2^{-1}\equiv (M+1)/2 \pmod M\)。
求出 \(W(n)\) 之后，程序再计算 \(2^{n-1}\cdot n(n+1)/2 \bmod M\)，然后减去 \(W(n)\) 得到答案。C++ 和 Java 版本还会先验证若干小例子，例如 \(S(1)=0\) 和 \(S(10)=4927\)，再输出 \(n=10^{14}\) 的结果。
令 \(B=3{,}000{,}000\)。第一阶段有 \(B\) 次迭代，每次都要做一次快速幂，因此这一部分的时间复杂度是 \(O(B\log n)\)。
第二阶段有 \(\lfloor n/(B+1)\rfloor\) 次迭代，而每次只做常数次模运算和区间求和，所以复杂度是 \(O(n/B)\)。因此整份实现的总时间复杂度为
\[ O(B\log n+n/B), \]
额外空间复杂度为 \(O(1)\)。对于目标规模 \(n=10^{14}\)，这个代价是完全可接受的。
Для каждого подмножества \(A \subseteq \{1,2,\dots,n\}\) будем называть элемент \(x \in A\) эливизором, если \(x\) делит хотя бы один другой элемент из \(A\). Требуется найти сумму всех эливизоров по всем подмножествам множества \(\{1,\dots,n\}\) при \(n=10^{14}\) по модулю \(M=1234567891\).
Перебирать подмножества напрямую невозможно, потому что их \(2^n\). Поэтому решение меняет порядок суммирования: вместо перебора подмножеств фиксируется число \(x\), и считается, в скольких подмножествах именно это \(x\) становится эливизором.
Пусть \(E(A)\) обозначает множество эливизоров подмножества \(A\). Тогда искомая величина равна
\[ S(n)=\sum_{A\subseteq \{1,\dots,n\}} \sum_{x\in E(A)} x \pmod M. \]
Зафиксируем \(x\) и положим
\[ q=\left\lfloor \frac{n}{x} \right\rfloor. \]
Тогда кратные числа \(x\) внутри \(\{1,\dots,n\}\) имеют вид \(x,2x,\dots,qx\), то есть их ровно \(q\).
Чтобы \(x\) был эливизором в некотором подмножестве \(A\), нужно и достаточно двух условий: само \(x\) должно входить в \(A\), и хотя бы одно из остальных \(q-1\) кратных тоже должно входить в \(A\). Все числа, не кратные \(x\), можно выбирать произвольно.
Отсюда число подходящих подмножеств равно
\[ 2^{n-q}\left(2^{q-1}-1\right). \]
Удобнее пользоваться эквивалентной записью
\[ 2^{n-q}\left(2^{q-1}-1\right)=2^{n-1}-2^{n-q}. \]
Слагаемое \(2^{n-1}\) считает все подмножества, содержащие \(x\), а \(2^{n-q}\) вычитает те случаи, где \(x\) выбрано, но никакое другое кратное ему число не выбрано.
Теперь можно суммировать вклад каждого возможного эливизора отдельно. По линейности получаем
\[ S(n)=\sum_{x=1}^{n}x\left(2^{n-1}-2^{n-\left\lfloor n/x\right\rfloor}\right). \]
Именно эту формулу вычисляют реализации на C++, Python и Java. Выделяя простую часть, имеем
\[ S(n)=2^{n-1}\sum_{x=1}^{n}x-\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
Так как \(\sum_{x=1}^{n}x=n(n+1)/2\), вся трудность сосредоточена в сумме
\[ W(n)=\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
Выражение \(\left\lfloor n/x\right\rfloor\) остаётся постоянным на целых интервалах. Если
\[ q=\left\lfloor \frac{n}{x} \right\rfloor, \]
то все \(x\), дающие этот же частный, лежат ровно в интервале
\[ \left\lfloor \frac{n}{q+1} \right\rfloor+1 \le x \le \left\lfloor \frac{n}{q} \right\rfloor. \]
На таком интервале степень двойки одинакова, поэтому вклад всего блока равен
\[ 2^{n-q}\sum_{x=l}^{r}x = 2^{n-q}\frac{(l+r)(r-l+1)}{2}. \]
Это и есть основное сжатие суммы: множество подряд идущих членов заменяется одной формулой для арифметической прогрессии.
Возьмём \(x=2\). Тогда \(q=\lfloor 10/2\rfloor=5\), и нужные кратные равны \(2,4,6,8,10\). Чтобы 2 было эливизором, надо выбрать 2, выбрать хотя бы одно число из \(\{4,6,8,10\}\), а из пяти некратных чисел \(\{1,3,5,7,9\}\) можно выбрать что угодно. Поэтому число подходящих подмножеств равно
\[ 2^{5}(2^{4}-1)=480, \]
а вклад числа 2 в \(S(10)\) равен \(2\cdot 480=960\).
Тот же пример показывает блочное суммирование. В сумме \(W(10)\) значение \(q=1\) соответствует \(x=6,7,8,9,10\), значит весь блок даёт
\[ 2^{10-1}(6+7+8+9+10)=2^{9}\cdot 40. \]
Именно так реализуется обработка больших значений \(x\).
В реализациях выбирается фиксированная граница \(B=3{,}000{,}000\). Значения \(x\le B\) обрабатываются напрямую, а значения \(x>B\) группируются по частному \(q=\lfloor n/x\rfloor\).
Из условия \(x>B\) следует \(q\le \lfloor n/(B+1)\rfloor\), поэтому во второй фазе остаются только сравнительно малые частные. В точности вычисляется разложение
\[ W(n) = \sum_{x=1}^{B}x\,2^{n-\left\lfloor n/x\right\rfloor} + \sum_{q=1}^{\left\lfloor n/(B+1)\right\rfloor} 2^{n-q} \sum_{x=\max\left(B+1,\left\lfloor \frac{n}{q+1}\right\rfloor+1\right)}^{\left\lfloor n/q\right\rfloor}x. \]
Это не общая схема на словах, а именно та формула, которую вычисляет программа.
Сначала реализация вычисляет \(2^{n-1}\bmod M\), поскольку этот множитель нужен в замкнутой формуле для простой части ответа. Кроме того, суммы по отрезкам \([l,r]\) считаются как суммы арифметической прогрессии по модулю \(M\), чтобы не перебирать каждое число внутри блока.
В первой фазе перебираются \(x=1,2,\dots,\min(n,B)\). Для каждого значения находится \(q=\lfloor n/x\rfloor\), затем двоичным возведением в степень вычисляется \(2^{n-q}\bmod M\), после чего результат умножается на \(x\) и прибавляется к текущему значению \(W(n)\).
Во второй фазе перебираются \(q=1,2,\dots,\lfloor n/(B+1)\rfloor\). Для каждого такого частного восстанавливается интервал значений \(x>B\), удовлетворяющих \(\lfloor n/x\rfloor=q\), вычисляется сумма по интервалу и умножается на общий множитель \(2^{n-q}\).
Здесь поддерживается важный инвариант: в начале итерации для данного \(q\) сохранённая степень равна ровно \(2^{n-q}\bmod M\). Поэтому переход к следующему частному требует только умножения на \(2^{-1}\bmod M\). Так как \(M\) нечётно, имеем \(2^{-1}\equiv (M+1)/2 \pmod M\).
После вычисления \(W(n)\) программы находят \(2^{n-1}\cdot n(n+1)/2 \bmod M\) и вычитают из этого \(W(n)\) по модулю \(M\). Реализации на C++ и Java также проверяют несколько малых случаев, в частности \(S(1)=0\) и \(S(10)=4927\), перед выводом ответа для \(n=10^{14}\).
Пусть \(B=3{,}000{,}000\). Прямая фаза состоит из \(B\) итераций, и в каждой вычисляется модульная степень быстрым возведением, так что её стоимость равна \(O(B\log n)\).
Блочная фаза содержит \(\lfloor n/(B+1)\rfloor\) итераций, в каждой из которых выполняется только постоянное число арифметических действий. Следовательно, эта часть стоит \(O(n/B)\). Полная сложность реализованного алгоритма равна
\[ O(B\log n+n/B), \]
а дополнительная память составляет \(O(1)\). Для целевого значения \(n=10^{14}\) этого более чем достаточно.
لكل مجموعة جزئية \(A \subseteq \{1,2,\dots,n\}\)، سنسمي العنصر \(x \in A\) elevisor إذا كان \(x\) يقسم عنصرًا آخر مختلفًا داخل \(A\). المطلوب هو مجموع جميع الـ elevisors عبر كل المجموعات الجزئية لـ \(\{1,\dots,n\}\) عندما \(n=10^{14}\)، وذلك بترديد \(M=1234567891\).
المرور على جميع المجموعات الجزئية مستحيل عمليًا لأن عددها \(2^n\). الفكرة الحاسمة هي قلب ترتيب الجمع: بدلًا من تثبيت مجموعة جزئية ثم البحث عن elevisors بداخلها، نثبت عددًا واحدًا \(x\) ونحسب في كم مجموعة جزئية يصبح هذا \(x\) نفسه elevisor.
إذا رمزنا إلى مجموعة elevisors الخاصة بـ \(A\) بالرمز \(E(A)\)، فإن الكمية المطلوبة هي
\[ S(n)=\sum_{A\subseteq \{1,\dots,n\}} \sum_{x\in E(A)} x \pmod M. \]
ثبّت عددًا \(x\)، ولْنكتب
\[ q=\left\lfloor \frac{n}{x} \right\rfloor. \]
عندئذ تكون مضاعفات \(x\) داخل \(\{1,\dots,n\}\) هي \(x,2x,\dots,qx\)، وبالتالي يوجد بالضبط \(q\) مضاعفات.
لكي يكون \(x\) elevisor داخل مجموعة جزئية \(A\)، يجب أن يتحقق شرطان معًا: أن يكون \(x\) نفسه مختارًا، وأن يكون واحد على الأقل من المضاعفات الأخرى وعددها \(q-1\) مختارًا أيضًا. أما الأعداد غير القابلة للقسمة على \(x\)، فيمكن اختيارها بحرية كاملة.
إذن عدد المجموعات الجزئية التي تجعل \(x\) elevisor هو
\[ 2^{n-q}\left(2^{q-1}-1\right). \]
ومن المفيد إعادة كتابته على الصورة
\[ 2^{n-q}\left(2^{q-1}-1\right)=2^{n-1}-2^{n-q}. \]
فالحد \(2^{n-1}\) يعد جميع المجموعات التي تحتوي \(x\)، ثم نطرح \(2^{n-q}\) لأنها تمثل الحالات التي اختير فيها \(x\) لكن لم يُختر أي مضاعف آخر له.
الآن يمكن جمع مساهمة كل elevisor محتمل على حدة. وبخطية الجمع نحصل على
\[ S(n)=\sum_{x=1}^{n}x\left(2^{n-1}-2^{n-\left\lfloor n/x\right\rfloor}\right). \]
وهذه هي الصيغة التي تحسبها تنفيذات C++ وPython وJava حرفيًا. وإذا فصلنا الجزء السهل نحصل على
\[ S(n)=2^{n-1}\sum_{x=1}^{n}x-\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
وبما أن \(\sum_{x=1}^{n}x=n(n+1)/2\)، فإن العبء الحقيقي كله يتركز في المجموع الموزون
\[ W(n)=\sum_{x=1}^{n}x\,2^{n-\left\lfloor n/x\right\rfloor}. \]
القيمة \(\left\lfloor n/x\right\rfloor\) لا تتغير عند كل \(x\) على حدة، بل تبقى ثابتة على فترات كاملة. فإذا كان
\[ q=\left\lfloor \frac{n}{x} \right\rfloor, \]
فإن جميع قيم \(x\) التي تعطي هذا الخارج تقع تمامًا في الفترة
\[ \left\lfloor \frac{n}{q+1} \right\rfloor+1 \le x \le \left\lfloor \frac{n}{q} \right\rfloor. \]
داخل هذه الفترة تكون قوة 2 ثابتة، ولذلك تساوي مساهمة الكتلة كلها
\[ 2^{n-q}\sum_{x=l}^{r}x = 2^{n-q}\frac{(l+r)(r-l+1)}{2}. \]
هذه هي خطوة الضغط الأساسية: عدد كبير من الحدود المتتالية يتحول إلى مجموع متتالية حسابية واحد.
خذ \(x=2\). عندئذ \(q=\lfloor 10/2\rfloor=5\)، والمضاعفات المعنية هي \(2,4,6,8,10\). لكي يصبح 2 elevisor يجب أن نختار 2، وأن نختار عنصرًا واحدًا على الأقل من \(\{4,6,8,10\}\)، بينما يمكن اختيار أي مجموعة من غير المضاعفات \(\{1,3,5,7,9\}\). لذلك يكون 2 elevisor في
\[ 2^{5}(2^{4}-1)=480 \]
مجموعة جزئية، وتكون مساهمته في \(S(10)\) مساوية لـ \(2\cdot 480=960\).
ويُظهر المثال نفسه فكرة التجميع. ففي \(W(10)\) نجد أن \(q=1\) يقابل القيم \(x=6,7,8,9,10\)، ومن ثم تساوي مساهمة هذه الكتلة كلها
\[ 2^{10-1}(6+7+8+9+10)=2^{9}\cdot 40. \]
وهذا هو بالضبط النوع من التجميع الذي تستغله الخوارزمية عند القيم الكبيرة لـ \(x\).
تعتمد التنفيذات حدًا ثابتًا هو \(B=3{,}000{,}000\). فإذا كان \(x\le B\) نحسب الحد مباشرة، وإذا كان \(x>B\) نعيد تنظيم الجمع بحسب خارج القسمة \(q=\lfloor n/x\rfloor\).
ومن الشرط \(x>B\) ينتج أن \(q\le \lfloor n/(B+1)\rfloor\)، أي إن المرحلة الثانية لا تتعامل إلا مع قيم صغيرة نسبيًا من \(q\). وعندها تصبح الصيغة المحسوبة فعلًا هي
\[ W(n) = \sum_{x=1}^{B}x\,2^{n-\left\lfloor n/x\right\rfloor} + \sum_{q=1}^{\left\lfloor n/(B+1)\right\rfloor} 2^{n-q} \sum_{x=\max\left(B+1,\left\lfloor \frac{n}{q+1}\right\rfloor+1\right)}^{\left\lfloor n/q\right\rfloor}x. \]
هذه ليست مجرد فكرة تفسيرية، بل هي التفكيك الرياضي نفسه الذي تنفذه الشيفرة.
تبدأ الشيفرة بحساب \(2^{n-1}\bmod M\)، لأن هذا العامل يظهر في الصيغة المغلقة للجزء السهل. كما تستعمل صيغة مجموع المتتالية الحسابية تحت الترديد \(M\) حتى يمكن معالجة أي فترة \([l,r]\) دفعة واحدة من دون المرور على كل قيمة بداخلها.
في المرحلة الأولى تُعالَج القيم \(x=1,2,\dots,\min(n,B)\). ولكل قيمة منها يُحسب \(q=\lfloor n/x\rfloor\)، ثم تُحسب \(2^{n-q}\bmod M\) بالأس السريع الثنائي، ثم يُضرب الناتج في \(x\) ويضاف إلى \(W(n)\).
في المرحلة الثانية تمر الشيفرة على \(q=1,2,\dots,\lfloor n/(B+1)\rfloor\). ولكل \(q\) تعيد بناء الفترة الخاصة بكل \(x>B\) الذي يحقق \(\lfloor n/x\rfloor=q\)، ثم تحسب مجموع تلك الفترة وتضربه في العامل المشترك \(2^{n-q}\).
وهنا تُحافِظ الشيفرة على ثابت مهم: في بداية تكرار قيمة معينة من \(q\)، تكون القوة المخزنة مساوية تمامًا لـ \(2^{n-q}\bmod M\). لذلك فإن الانتقال إلى القيمة التالية من \(q\) يحتاج فقط إلى الضرب في \(2^{-1}\bmod M\). وبما أن \(M\) عدد فردي، فإن \(2^{-1}\equiv (M+1)/2 \pmod M\).
بعد الحصول على \(W(n)\)، تحسب البرامج القيمة \(2^{n-1}\cdot n(n+1)/2 \bmod M\) ثم تطرح منها \(W(n)\) بترديد \(M\). كما أن تنفيذي C++ وJava يتحققان من حالات صغيرة مثل \(S(1)=0\) و\(S(10)=4927\) قبل طباعة الجواب النهائي عند \(n=10^{14}\).
لنأخذ \(B=3{,}000{,}000\). المرحلة المباشرة تحتوي على \(B\) تكرارات، وفي كل تكرار توجد عملية أس معياري سريع، لذا فكلفتها \(O(B\log n)\).
أما المرحلة الكتلية فتحتوي على \(\lfloor n/(B+1)\rfloor\) تكرارات، وكل تكرار يستخدم عددًا ثابتًا من العمليات الحسابية فقط، ولذلك تكلفتها \(O(n/B)\). إذن التعقيد الزمني الكلي للخوارزمية المنفذة هو
\[ O(B\log n+n/B), \]
بينما الذاكرة الإضافية هي \(O(1)\). وهذا يجعل الحساب عمليًا حتى عند \(n=10^{14}\).