Let \(a=17^p\), \(b=19^p\), and \(c=23^p\). The task is to compute the sum of all positive integers that cannot be written in the form
$$n=ax+by+cz,\qquad x,y,z\in \mathbb{Z}_{>0},$$
for the target case \(p=6\), with the final result reduced modulo \(10^9+7\). Since \(a\), \(b\), and \(c\) are pairwise coprime, there are only finitely many unreachable integers, so the problem becomes a finite numerical-semigroup calculation rather than an infinite search.
The solution converts the positive-coefficient representation problem into a statement about gaps of a numerical semigroup. Those gaps are then recovered from the Apéry set with respect to the smallest generator.
Define the numerical semigroup
$$S=\langle a,b,c\rangle=\{ia+jb+kc:i,j,k\in \mathbb{Z}_{\ge 0}\}.$$
Also let
$$s=a+b+c.$$
If \(x,y,z\ge 1\), then
$$ax+by+cz=s+\bigl(a(x-1)+b(y-1)+c(z-1)\bigr).$$
So a positive integer \(n\) is representable with all three coefficients positive exactly when
$$n-s\in S.$$
This means the unreachable positive integers consist of two parts:
$$1,2,\dots,s-1,$$
and all integers of the form
$$s+g,$$
where \(g\) is a gap of \(S\), meaning \(g\notin S\).
If \(g(S)\) denotes the number of gaps of \(S\), and \(\sigma(S)\) denotes the sum of those gaps, then the required quantity is
$$U(p)=\frac{s(s-1)}{2}+s\,g(S)+\sigma(S).$$
Because \(a=17^p\) is the smallest generator, working modulo \(a\) gives the smallest state space. For each residue \(r\in\{0,1,\dots,a-1\}\), define
$$w_r=\min\{m\in S:m\equiv r\pmod a\}.$$
The set \(\{w_0,\dots,w_{a-1}\}\) is the Apéry set of \(S\) with respect to \(a\). Once \(w_r\) is known, every reachable number in residue class \(r\) is
$$w_r,\ w_r+a,\ w_r+2a,\dots,$$
and every smaller nonnegative number in the same residue class is unreachable.
Construct a directed graph on the residue classes modulo \(a\). From residue \(u\), add two edges
$$u\to u+b\pmod a,\qquad u\to u+c\pmod a.$$
The two edge weights are \(b\) and \(c\), respectively.
Any path from \(0\) to residue \(r\) represents a value \(jb+kc\) with that residue, and its path length is exactly that value. Therefore the shortest-path distance from \(0\) to \(r\) is the smallest semigroup element in that residue class.
No separate edge for \(+a\) is needed. Adding \(a\) does not change the residue and only increases the total value, so it can never improve a minimal representative. Hence Dijkstra's algorithm returns precisely the values \(w_r\).
Write each Apéry element as
$$w_r=r+a q_r,\qquad q_r\in \mathbb{Z}_{\ge 0}.$$
Then the gaps in residue class \(r\) are
$$r,\ r+a,\ r+2a,\dots,r+(q_r-1)a,$$
so that residue class contributes exactly \(q_r\) gaps. Summing over all residue classes gives
$$g(S)=\sum_{r=0}^{a-1} q_r=\frac{1}{a}\sum_{r=0}^{a-1} w_r-\frac{a-1}{2}.$$
If we define
$$W_1=\sum_{r=0}^{a-1} w_r,$$
then
$$g(S)=\frac{W_1}{a}-\frac{a-1}{2}.$$
The gaps in one residue class form an arithmetic progression, so their sum is
$$q_r r+\frac{a q_r(q_r-1)}{2}.$$
Substituting \(q_r=(w_r-r)/a\) and simplifying yields the standard Apéry identity
$$\sigma(S)=\frac{1}{2a}\sum_{r=0}^{a-1} w_r^2-\frac12\sum_{r=0}^{a-1} w_r+\frac{a^2-1}{12}.$$
With
$$W_2=\sum_{r=0}^{a-1} w_r^2,$$
this becomes
$$\sigma(S)=\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}.$$
Combining the shift argument with the two Apéry identities gives
$$\boxed{U(p)=\frac{s(s-1)}{2}+s\left(\frac{W_1}{a}-\frac{a-1}{2}\right)+\left(\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}\right).}$$
This is exactly the quantity evaluated modulo \(10^9+7\) by the implementations.
For \(p=1\), we have \(a=17\), \(b=19\), \(c=23\), and \(s=59\). The full Apéry set modulo \(17\) is
$$\left(w_0,\dots,w_{16}\right)=\left(0,69,19,88,38,107,23,92,42,111,61,130,46,115,65,134,84\right).$$
Therefore
$$W_1=1224,\qquad W_2=114036.$$
The number of gaps of \(S\) is
$$g(S)=\frac{1224}{17}-\frac{16}{2}=72-8=64,$$
and the sum of the gaps is
$$\sigma(S)=\frac{114036}{34}-\frac{1224}{2}+\frac{17^2-1}{12}=3354-612+24=2766.$$
Hence
$$U(1)=\frac{59\cdot 58}{2}+59\cdot 64+2766=1711+3776+2766=8253,$$
which matches the small checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same pipeline. They first compute the three powers \(17^p\), \(19^p\), and \(23^p\), choose the smallest one as the modulus, and run Dijkstra's algorithm on the residue graph from Step 3.
The resulting distance table is the Apéry set. The implementation then accumulates the two moment sums \(W_1=\sum w_r\) and \(W_2=\sum w_r^2\), reducing everything modulo \(10^9+7\).
The formulas for \(g(S)\), \(\sigma(S)\), and \(U(p)\) contain division by \(2\), \(12\), and \(a\). Since the modulus is prime and coprime to those values, the code performs those divisions by modular inverses.
The same logic reproduces the checkpoints \(U(1)=8253\) and \(U(2)=60258000\) before evaluating the target case \(p=6\).
The residue graph has \(a=17^p\) vertices and exactly two outgoing edges from each vertex. With a binary heap, Dijkstra's algorithm runs in \(O(a\log a)\) time and uses \(O(a)\) memory. The post-processing pass that forms \(W_1\) and \(W_2\) is linear, so the total complexity remains \(O(a\log a)\) time and \(O(a)\) space.
Sei \(a=17^p\), \(b=19^p\) und \(c=23^p\). Gesucht ist die Summe aller positiven ganzen Zahlen, die sich nicht in der Form
$$n=ax+by+cz,\qquad x,y,z\in \mathbb{Z}_{>0},$$
darstellen lassen, und zwar für den Zielwert \(p=6\), modulo \(10^9+7\). Da \(a\), \(b\) und \(c\) paarweise teilerfremd sind, gibt es nur endlich viele unerreichbare Zahlen. Deshalb lässt sich das Problem als endliche Rechnung in einer numerischen Halbgruppe formulieren.
Die Lösung übersetzt die Darstellung mit positiven Koeffizienten zunächst in eine Frage über Lücken einer numerischen Halbgruppe. Diese Lücken werden anschließend aus der Apéry-Menge bezüglich des kleinsten Erzeugers rekonstruiert.
Definiere die numerische Halbgruppe
$$S=\langle a,b,c\rangle=\{ia+jb+kc:i,j,k\in \mathbb{Z}_{\ge 0}\}.$$
Außerdem setzen wir
$$s=a+b+c.$$
Für \(x,y,z\ge 1\) gilt dann
$$ax+by+cz=s+\bigl(a(x-1)+b(y-1)+c(z-1)\bigr).$$
Eine positive ganze Zahl \(n\) ist also genau dann mit strikt positiven Koeffizienten darstellbar, wenn
$$n-s\in S.$$
Die unerreichbaren positiven Zahlen bestehen daher aus zwei Teilen:
$$1,2,\dots,s-1,$$
sowie allen Zahlen der Form
$$s+g,$$
wobei \(g\) eine Lücke von \(S\) ist, also \(g\notin S\).
Bezeichnet \(g(S)\) die Anzahl der Lücken und \(\sigma(S)\) ihre Summe, dann lautet die gesuchte Größe
$$U(p)=\frac{s(s-1)}{2}+s\,g(S)+\sigma(S).$$
Da \(a=17^p\) der kleinste Erzeuger ist, liefert die Arbeit modulo \(a\) den kleinsten Zustandsraum. Für jede Restklasse \(r\in\{0,1,\dots,a-1\}\) definieren wir
$$w_r=\min\{m\in S:m\equiv r\pmod a\}.$$
Die Menge \(\{w_0,\dots,w_{a-1}\}\) ist die Apéry-Menge von \(S\) bezüglich \(a\). Sobald \(w_r\) bekannt ist, sind alle erreichbaren Zahlen in dieser Restklasse
$$w_r,\ w_r+a,\ w_r+2a,\dots,$$
und jede kleinere nichtnegative Zahl mit demselben Rest ist eine Lücke.
Man konstruiert einen gerichteten Graphen auf den Restklassen modulo \(a\). Von einem Rest \(u\) gehen zwei Kanten aus:
$$u\to u+b\pmod a,\qquad u\to u+c\pmod a.$$
Die beiden Kantengewichte sind entsprechend \(b\) und \(c\).
Jeder Weg von \(0\) zu einer Restklasse \(r\) steht für einen Wert \(jb+kc\) mit genau diesem Rest; die Weglänge ist gleich diesem Wert. Also liefert der kürzeste Weg nach \(r\) das kleinste Halbgruppenelement in dieser Restklasse.
Eine zusätzliche Kante für \(+a\) ist nicht nötig. Das Addieren von \(a\) ändert den Rest nicht und vergrößert nur den Wert, kann also einen Minimalrepräsentanten niemals verbessern. Daher gibt Dijkstra exakt die Werte \(w_r\) zurück.
Schreibe jedes Apéry-Element als
$$w_r=r+a q_r,\qquad q_r\in \mathbb{Z}_{\ge 0}.$$
Dann sind die Lücken in Restklasse \(r\)
$$r,\ r+a,\ r+2a,\dots,r+(q_r-1)a,$$
also trägt diese Restklasse genau \(q_r\) Lücken bei. Summiert über alle Restklassen ergibt das
$$g(S)=\sum_{r=0}^{a-1} q_r=\frac{1}{a}\sum_{r=0}^{a-1} w_r-\frac{a-1}{2}.$$
Mit
$$W_1=\sum_{r=0}^{a-1} w_r$$
folgt also
$$g(S)=\frac{W_1}{a}-\frac{a-1}{2}.$$
Die Lücken einer Restklasse bilden eine arithmetische Folge, also ist ihre Summe
$$q_r r+\frac{a q_r(q_r-1)}{2}.$$
Setzt man \(q_r=(w_r-r)/a\) ein und vereinfacht, erhält man die Standardformel
$$\sigma(S)=\frac{1}{2a}\sum_{r=0}^{a-1} w_r^2-\frac12\sum_{r=0}^{a-1} w_r+\frac{a^2-1}{12}.$$
Mit
$$W_2=\sum_{r=0}^{a-1} w_r^2$$
wird daraus
$$\sigma(S)=\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}.$$
Kombiniert man die Verschiebung aus Schritt 1 mit den beiden Apéry-Identitäten, erhält man
$$\boxed{U(p)=\frac{s(s-1)}{2}+s\left(\frac{W_1}{a}-\frac{a-1}{2}\right)+\left(\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}\right).}$$
Genau diese Größe berechnen die Implementierungen modulo \(10^9+7\).
Für \(p=1\) gilt \(a=17\), \(b=19\), \(c=23\) und \(s=59\). Die vollständige Apéry-Menge modulo \(17\) ist
$$\left(w_0,\dots,w_{16}\right)=\left(0,69,19,88,38,107,23,92,42,111,61,130,46,115,65,134,84\right).$$
Daraus folgen
$$W_1=1224,\qquad W_2=114036.$$
Die Anzahl der Lücken von \(S\) ist
$$g(S)=\frac{1224}{17}-\frac{16}{2}=72-8=64,$$
und ihre Summe ist
$$\sigma(S)=\frac{114036}{34}-\frac{1224}{2}+\frac{17^2-1}{12}=3354-612+24=2766.$$
Damit erhält man
$$U(1)=\frac{59\cdot 58}{2}+59\cdot 64+2766=1711+3776+2766=8253,$$
genau den kleinen Kontrollwert aus den Implementierungen.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst werden die drei Potenzen \(17^p\), \(19^p\) und \(23^p\) gebildet, dann wird der kleinste Erzeuger als Modulus gewählt, und schließlich läuft Dijkstra auf dem Restklassengraphen aus Schritt 3.
Die entstehende Distanztafel ist die Apéry-Menge. Daraus akkumuliert die Implementierung die beiden Momentsummen \(W_1=\sum w_r\) und \(W_2=\sum w_r^2\), jeweils modulo \(10^9+7\).
In den Formeln für \(g(S)\), \(\sigma(S)\) und \(U(p)\) tauchen Divisionen durch \(2\), \(12\) und \(a\) auf. Weil der Modulus prim ist und zu diesen Zahlen teilerfremd ist, werden diese Divisionen per modularen Inversen ausgeführt.
Mit derselben Mathematik erhält man vor dem Zielwert \(p=6\) auch die Kontrollwerte \(U(1)=8253\) und \(U(2)=60258000\).
Der Restklassengraph besitzt \(a=17^p\) Knoten und genau zwei ausgehende Kanten pro Knoten. Mit einem Binär-Heap läuft Dijkstra in \(O(a\log a)\) Zeit und benötigt \(O(a)\) Speicher. Der anschließende Durchlauf zur Bildung von \(W_1\) und \(W_2\) ist linear und ändert die Gesamtkosten daher nicht.
\(a=17^p\), \(b=19^p\) ve \(c=23^p\) olsun. Amaç,
$$n=ax+by+cz,\qquad x,y,z\in \mathbb{Z}_{>0},$$
biçiminde yazılamayan tüm pozitif tamsayıların toplamını, hedef durum olan \(p=6\) için \(10^9+7\) modunda bulmaktır. \(a\), \(b\) ve \(c\) aralarında asal olduğu için erişilemeyen sayıların kümesi sonludur; dolayısıyla problem sonsuz bir tarama değil, sonlu bir sayısal yarıgrup hesabı olarak ele alınabilir.
Çözüm önce pozitif katsayılı gösterim problemini bir sayısal yarıgrubun boşlukları problemine dönüştürür. Ardından bu boşluklar, en küçük üretece göre tanımlanan Apéry kümesinden çıkarılır.
Şu sayısal yarıgrubu tanımlayalım:
$$S=\langle a,b,c\rangle=\{ia+jb+kc:i,j,k\in \mathbb{Z}_{\ge 0}\}.$$
Ayrıca
$$s=a+b+c$$
olsun. \(x,y,z\ge 1\) ise
$$ax+by+cz=s+\bigl(a(x-1)+b(y-1)+c(z-1)\bigr)$$
yazılır. O halde bir pozitif tamsayı \(n\), tüm katsayılar pozitif olacak şekilde ancak ve ancak
$$n-s\in S$$
ise temsil edilebilir.
Buna göre erişilemeyen pozitif sayılar iki parçadan oluşur:
$$1,2,\dots,s-1,$$
ve
$$s+g$$
biçimindeki sayılar; burada \(g\), \(S\)'nin bir boşluğudur, yani \(g\notin S\).
\(g(S)\) boşluk sayısını, \(\sigma(S)\) ise boşlukların toplamını göstersin. Aranan büyüklük
$$U(p)=\frac{s(s-1)}{2}+s\,g(S)+\sigma(S)$$
olur.
\(a=17^p\) en küçük üreteç olduğu için, mod \(a\) çalışmak en küçük durum uzayını verir. Her \(r\in\{0,1,\dots,a-1\}\) kalıntısı için
$$w_r=\min\{m\in S:m\equiv r\pmod a\}$$
tanımını yapalım. \(\{w_0,\dots,w_{a-1}\}\) kümesi, \(S\)'nin \(a\)'ya göre Apéry kümesidir.
\(w_r\) bilindiğinde bu kalıntı sınıfındaki tüm erişilebilir sayılar
$$w_r,\ w_r+a,\ w_r+2a,\dots$$
şeklindedir; aynı sınıftaki daha küçük tüm negatif olmayan sayılar ise boşluktur.
Mod \(a\) kalıntıları üzerinde yönlü bir grafik kurulur. Kalıntı \(u\)'dan iki kenar çıkar:
$$u\to u+b\pmod a,\qquad u\to u+c\pmod a.$$
Bu iki kenarın ağırlıkları sırasıyla \(b\) ve \(c\)'dir.
\(0\)'dan \(r\)'ye giden her yol, kalıntısı \(r\) olan bir \(jb+kc\) değerine karşılık gelir ve yol uzunluğu tam olarak bu değerdir. Bu yüzden \(0\)'dan \(r\)'ye en kısa yol, o kalıntı sınıfındaki en küçük yarıgrup elemanını verir.
\(+a\) için ayrı bir kenara gerek yoktur. Çünkü \(a\) eklemek kalıntıyı değiştirmez, sadece sayıyı büyütür. Dolayısıyla minimal temsilci ararken asla faydalı olmaz. Sonuç olarak Dijkstra algoritması doğrudan \(w_r\) değerlerini üretir.
Her Apéry elemanını
$$w_r=r+a q_r,\qquad q_r\in \mathbb{Z}_{\ge 0}$$
şeklinde yazalım. O zaman \(r\) kalıntı sınıfındaki boşluklar
$$r,\ r+a,\ r+2a,\dots,r+(q_r-1)a$$
olur; yani bu sınıf tam \(q_r\) boşluk katkısı yapar. Tüm kalıntılar üzerinde toplayınca
$$g(S)=\sum_{r=0}^{a-1} q_r=\frac{1}{a}\sum_{r=0}^{a-1} w_r-\frac{a-1}{2}$$
elde edilir. Eğer
$$W_1=\sum_{r=0}^{a-1} w_r$$
dersek,
$$g(S)=\frac{W_1}{a}-\frac{a-1}{2}$$
olur.
Tek bir kalıntı sınıfındaki boşluklar bir aritmetik dizi oluşturduğu için toplamları
$$q_r r+\frac{a q_r(q_r-1)}{2}$$
şeklindedir. Burada \(q_r=(w_r-r)/a\) yazıp sadeleştirince standart Apéry özdeşliği çıkar:
$$\sigma(S)=\frac{1}{2a}\sum_{r=0}^{a-1} w_r^2-\frac12\sum_{r=0}^{a-1} w_r+\frac{a^2-1}{12}.$$
Eğer
$$W_2=\sum_{r=0}^{a-1} w_r^2$$
olarak tanımlarsak, bu ifade
$$\sigma(S)=\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}$$
haline gelir.
Birinci adımdaki kaydırma ile iki Apéry özdeşliğini birleştirince
$$\boxed{U(p)=\frac{s(s-1)}{2}+s\left(\frac{W_1}{a}-\frac{a-1}{2}\right)+\left(\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}\right)}$$
elde edilir. Uygulamalar tam olarak bu büyüklüğü \(10^9+7\) modunda hesaplar.
\(p=1\) için \(a=17\), \(b=19\), \(c=23\) ve \(s=59\) olur. Mod \(17\) için tam Apéry kümesi
$$\left(w_0,\dots,w_{16}\right)=\left(0,69,19,88,38,107,23,92,42,111,61,130,46,115,65,134,84\right)$$
şeklindedir. Dolayısıyla
$$W_1=1224,\qquad W_2=114036.$$
Boşluk sayısı
$$g(S)=\frac{1224}{17}-\frac{16}{2}=72-8=64,$$
boşlukların toplamı ise
$$\sigma(S)=\frac{114036}{34}-\frac{1224}{2}+\frac{17^2-1}{12}=3354-612+24=2766$$
olur. Böylece
$$U(1)=\frac{59\cdot 58}{2}+59\cdot 64+2766=1711+3776+2766=8253,$$
ve bu değer uygulamalardaki küçük doğrulama sonucuyla aynıdır.
C++, Python ve Java uygulamalarının akışı aynıdır. Önce \(17^p\), \(19^p\) ve \(23^p\) hesaplanır; sonra en küçük üreteç modül olarak seçilir ve 3. adımdaki kalıntı grafiği üzerinde Dijkstra çalıştırılır.
Elde edilen uzaklık tablosu Apéry kümesidir. Ardından uygulama \(W_1=\sum w_r\) ve \(W_2=\sum w_r^2\) moment toplamlarını toplar ve tüm işlemleri \(10^9+7\) modunda tutar.
\(g(S)\), \(\sigma(S)\) ve \(U(p)\) formüllerinde \(2\), \(12\) ve \(a\) ile bölmeler bulunduğu için, asal modül altında bu bölmeler modüler ters kullanılarak yapılır.
Aynı yöntem, hedef durum olan \(p=6\) öncesinde \(U(1)=8253\) ve \(U(2)=60258000\) kontrol sonuçlarını da verir.
Kalıntı grafiğinde \(a=17^p\) düğüm vardır ve her düğümden tam iki çıkış kenarı bulunur. İkili yığın kullanıldığında Dijkstra algoritması \(O(a\log a)\) zamanda ve \(O(a)\) bellekte çalışır. \(W_1\) ile \(W_2\)'yi toplamak için yapılan son geçiş doğrusal olduğu için toplam karmaşıklık değişmez.
Sea \(a=17^p\), \(b=19^p\) y \(c=23^p\). Hay que calcular la suma de todos los enteros positivos que no pueden escribirse como
$$n=ax+by+cz,\qquad x,y,z\in \mathbb{Z}_{>0},$$
en el caso objetivo \(p=6\), tomando el resultado final módulo \(10^9+7\). Como \(a\), \(b\) y \(c\) son coprimos dos a dos, el conjunto de enteros inalcanzables es finito, así que el problema se reduce a estudiar los huecos de un semigrupo numérico.
La idea es transformar la condición de coeficientes estrictamente positivos en un problema de huecos de semigrupo, y luego reconstruir esos huecos a partir del conjunto de Apéry respecto del generador más pequeño.
Definimos el semigrupo numérico
$$S=\langle a,b,c\rangle=\{ia+jb+kc:i,j,k\in \mathbb{Z}_{\ge 0}\}.$$
También ponemos
$$s=a+b+c.$$
Si \(x,y,z\ge 1\), entonces
$$ax+by+cz=s+\bigl(a(x-1)+b(y-1)+c(z-1)\bigr).$$
Por tanto, un entero positivo \(n\) es representable con los tres coeficientes positivos si y solo si
$$n-s\in S.$$
Los enteros positivos inalcanzables son entonces dos familias:
$$1,2,\dots,s-1,$$
y todos los números de la forma
$$s+g,$$
donde \(g\) es un hueco de \(S\), es decir, \(g\notin S\).
Si \(g(S)\) es el número de huecos y \(\sigma(S)\) su suma, la cantidad pedida es
$$U(p)=\frac{s(s-1)}{2}+s\,g(S)+\sigma(S).$$
Como \(a=17^p\) es el menor generador, trabajar módulo \(a\) minimiza el tamaño del grafo. Para cada residuo \(r\in\{0,1,\dots,a-1\}\), definimos
$$w_r=\min\{m\in S:m\equiv r\pmod a\}.$$
El conjunto \(\{w_0,\dots,w_{a-1}\}\) es el conjunto de Apéry de \(S\) respecto de \(a\). Una vez conocido \(w_r\), todos los enteros alcanzables en esa clase residual son
$$w_r,\ w_r+a,\ w_r+2a,\dots,$$
y todos los menores no negativos con el mismo residuo son huecos.
Se construye un grafo dirigido sobre las clases de residuos módulo \(a\). Desde el residuo \(u\) salen dos aristas:
$$u\to u+b\pmod a,\qquad u\to u+c\pmod a.$$
Los pesos de estas dos aristas son \(b\) y \(c\), respectivamente.
Cada camino desde \(0\) hasta \(r\) representa un valor \(jb+kc\) con ese residuo, y la longitud del camino coincide exactamente con dicho valor. Por eso, la distancia mínima hasta \(r\) es el menor elemento del semigrupo en esa clase residual.
No hace falta una arista adicional de coste \(a\). Sumar \(a\) no cambia el residuo y solo aumenta el valor, así que nunca mejora un representante mínimo. En consecuencia, el algoritmo de Dijkstra devuelve precisamente los valores \(w_r\).
Escribimos cada elemento de Apéry como
$$w_r=r+a q_r,\qquad q_r\in \mathbb{Z}_{\ge 0}.$$
Entonces los huecos de la clase residual \(r\) son
$$r,\ r+a,\ r+2a,\dots,r+(q_r-1)a,$$
de modo que esa clase aporta exactamente \(q_r\) huecos. Sumando todas las clases se obtiene
$$g(S)=\sum_{r=0}^{a-1} q_r=\frac{1}{a}\sum_{r=0}^{a-1} w_r-\frac{a-1}{2}.$$
Si definimos
$$W_1=\sum_{r=0}^{a-1} w_r,$$
entonces
$$g(S)=\frac{W_1}{a}-\frac{a-1}{2}.$$
Los huecos de una clase residual forman una progresión aritmética, así que su suma es
$$q_r r+\frac{a q_r(q_r-1)}{2}.$$
Sustituyendo \(q_r=(w_r-r)/a\) y simplificando se llega a la identidad clásica de Apéry
$$\sigma(S)=\frac{1}{2a}\sum_{r=0}^{a-1} w_r^2-\frac12\sum_{r=0}^{a-1} w_r+\frac{a^2-1}{12}.$$
Con
$$W_2=\sum_{r=0}^{a-1} w_r^2,$$
queda
$$\sigma(S)=\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}.$$
Juntando el corrimiento del Paso 1 con las dos identidades de Apéry, resulta
$$\boxed{U(p)=\frac{s(s-1)}{2}+s\left(\frac{W_1}{a}-\frac{a-1}{2}\right)+\left(\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}\right).}$$
Esa es exactamente la cantidad que calculan las implementaciones módulo \(10^9+7\).
Cuando \(p=1\), tenemos \(a=17\), \(b=19\), \(c=23\) y \(s=59\). El conjunto de Apéry completo módulo \(17\) es
$$\left(w_0,\dots,w_{16}\right)=\left(0,69,19,88,38,107,23,92,42,111,61,130,46,115,65,134,84\right).$$
Por tanto,
$$W_1=1224,\qquad W_2=114036.$$
El número de huecos de \(S\) es
$$g(S)=\frac{1224}{17}-\frac{16}{2}=72-8=64,$$
y la suma de los huecos es
$$\sigma(S)=\frac{114036}{34}-\frac{1224}{2}+\frac{17^2-1}{12}=3354-612+24=2766.$$
Entonces
$$U(1)=\frac{59\cdot 58}{2}+59\cdot 64+2766=1711+3776+2766=8253,$$
que coincide con la comprobación pequeña usada por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero calculan \(17^p\), \(19^p\) y \(23^p\), eligen el menor generador como módulo y ejecutan Dijkstra sobre el grafo de residuos descrito en el Paso 3.
La tabla de distancias resultante es precisamente el conjunto de Apéry. A partir de ella, la implementación acumula los dos momentos \(W_1=\sum w_r\) y \(W_2=\sum w_r^2\), siempre reduciendo módulo \(10^9+7\).
Las fórmulas de \(g(S)\), \(\sigma(S)\) y \(U(p)\) contienen divisiones por \(2\), \(12\) y \(a\). Como el módulo es primo y coprimo con esos valores, el código realiza esas divisiones mediante inversos modulares.
La misma lógica reproduce las comprobaciones \(U(1)=8253\) y \(U(2)=60258000\) antes de evaluar el caso objetivo \(p=6\).
El grafo de residuos tiene \(a=17^p\) vértices y exactamente dos aristas salientes por vértice. Con un montículo binario, el algoritmo de Dijkstra cuesta \(O(a\log a)\) en tiempo y \(O(a)\) en memoria. El recorrido final para formar \(W_1\) y \(W_2\) es lineal, así que no cambia el orden asintótico total.
设 \(a=17^p\)、\(b=19^p\)、\(c=23^p\)。题目要求在目标情形 \(p=6\) 下，求所有不能写成
$$n=ax+by+cz,\qquad x,y,z\in \mathbb{Z}_{>0}$$
的正整数之和，并对 \(10^9+7\) 取模。由于 \(a\)、\(b\)、\(c\) 两两互素，不可达的正整数只有有限多个，所以问题本质上是一个有限的数值半群缺口求和问题。
核心思路分成两层。第一层把“系数必须都为正”改写成一个普通数值半群的缺口问题。第二层通过相对于最小生成元的 Apéry 集来恢复缺口的个数与缺口和。
定义数值半群
$$S=\langle a,b,c\rangle=\{ia+jb+kc:i,j,k\in \mathbb{Z}_{\ge 0}\}.$$
再记
$$s=a+b+c.$$
如果 \(x,y,z\ge 1\)，那么
$$ax+by+cz=s+\bigl(a(x-1)+b(y-1)+c(z-1)\bigr).$$
因此，一个正整数 \(n\) 能够用三个正系数表示，当且仅当
$$n-s\in S.$$
这就说明，不可达的正整数恰好由两部分组成：
$$1,2,\dots,s-1,$$
以及所有形如
$$s+g$$
的数，其中 \(g\) 是半群 \(S\) 的缺口，也就是 \(g\notin S\)。
如果用 \(g(S)\) 表示缺口个数，用 \(\sigma(S)\) 表示所有缺口的总和，那么题目要求的量就是
$$U(p)=\frac{s(s-1)}{2}+s\,g(S)+\sigma(S).$$
因为 \(a=17^p\) 是三个生成元里最小的一个，所以对 \(a\) 取模会得到最小的状态空间。对每个余数 \(r\in\{0,1,\dots,a-1\}\)，定义
$$w_r=\min\{m\in S:m\equiv r\pmod a\}.$$
\(\{w_0,\dots,w_{a-1}\}\) 就是半群 \(S\) 相对于 \(a\) 的 Apéry 集。一旦知道了 \(w_r\)，同一余数类中所有可达的非负整数就正好是
$$w_r,\ w_r+a,\ w_r+2a,\dots,$$
而比 \(w_r\) 更小、又与它同余的非负整数全部都是缺口。
在模 \(a\) 的余数类上建立一个有向图。对任意余数 \(u\)，连出两条边：
$$u\to u+b\pmod a,\qquad u\to u+c\pmod a.$$
这两条边的权值分别是 \(b\) 和 \(c\)。
从余数 \(0\) 走到余数 \(r\) 的任意一条路径，都对应某个值 \(jb+kc\)，而路径总权值恰好就是这个值本身。因此，从 \(0\) 到 \(r\) 的最短路长度，就是该余数类里最小的半群元素。
这里不需要额外加入一条“加上 \(a\)”的边，因为加 \(a\) 不改变余数，只会让数值更大，对寻找最小代表没有帮助。于是 Dijkstra 算法算出来的距离表，正好就是全部 \(w_r\)。
把每个 Apéry 元素写成
$$w_r=r+a q_r,\qquad q_r\in \mathbb{Z}_{\ge 0}.$$
那么余数类 \(r\) 中的缺口正好是
$$r,\ r+a,\ r+2a,\dots,r+(q_r-1)a,$$
所以这一类一共贡献 \(q_r\) 个缺口。对所有余数求和得到
$$g(S)=\sum_{r=0}^{a-1} q_r=\frac{1}{a}\sum_{r=0}^{a-1} w_r-\frac{a-1}{2}.$$
如果记
$$W_1=\sum_{r=0}^{a-1} w_r,$$
那么就有
$$g(S)=\frac{W_1}{a}-\frac{a-1}{2}.$$
同一个余数类里的缺口构成等差数列，因此它们的和为
$$q_r r+\frac{a q_r(q_r-1)}{2}.$$
再把 \(q_r=(w_r-r)/a\) 代回去并化简，就得到标准的 Apéry 恒等式
$$\sigma(S)=\frac{1}{2a}\sum_{r=0}^{a-1} w_r^2-\frac12\sum_{r=0}^{a-1} w_r+\frac{a^2-1}{12}.$$
若记
$$W_2=\sum_{r=0}^{a-1} w_r^2,$$
则上式可写成
$$\sigma(S)=\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}.$$
把第一步的平移关系与上面两个 Apéry 公式合并，可得
$$\boxed{U(p)=\frac{s(s-1)}{2}+s\left(\frac{W_1}{a}-\frac{a-1}{2}\right)+\left(\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}\right).}$$
实现所做的事情，就是把这个表达式在模 \(10^9+7\) 下高效地算出来。
当 \(p=1\) 时，有 \(a=17\)、\(b=19\)、\(c=23\)、\(s=59\)。模 \(17\) 的完整 Apéry 集为
$$\left(w_0,\dots,w_{16}\right)=\left(0,69,19,88,38,107,23,92,42,111,61,130,46,115,65,134,84\right).$$
于是
$$W_1=1224,\qquad W_2=114036.$$
半群缺口个数为
$$g(S)=\frac{1224}{17}-\frac{16}{2}=72-8=64,$$
缺口总和为
$$\sigma(S)=\frac{114036}{34}-\frac{1224}{2}+\frac{17^2-1}{12}=3354-612+24=2766.$$
因此
$$U(1)=\frac{59\cdot 58}{2}+59\cdot 64+2766=1711+3776+2766=8253,$$
这与实现中使用的小规模校验结果完全一致。
C++、Python 和 Java 三个实现使用的是同一条计算流水线。首先计算 \(17^p\)、\(19^p\)、\(23^p\)，然后选最小的生成元作为模数，在步骤 3 的余数图上运行 Dijkstra 算法。
得到的距离数组就是 Apéry 集。接着实现累加两个矩量和 \(W_1=\sum w_r\) 与 \(W_2=\sum w_r^2\)，并把所有运算都保持在 \(10^9+7\) 模下。
由于 \(g(S)\)、\(\sigma(S)\) 和 \(U(p)\) 的公式中含有除以 \(2\)、\(12\) 和 \(a\) 的步骤，而模数是质数且与这些数互素，所以实现通过模逆元完成这些除法。
同一套方法先给出 \(U(1)=8253\) 和 \(U(2)=60258000\) 这两个校验值，再计算目标情形 \(p=6\)。
余数图有 \(a=17^p\) 个顶点，每个顶点恰好有两条出边。使用二叉堆时，Dijkstra 的时间复杂度为 \(O(a\log a)\)，空间复杂度为 \(O(a)\)。之后计算 \(W_1\) 和 \(W_2\) 的遍历只是线性的，因此不会改变总体复杂度。
Положим \(a=17^p\), \(b=19^p\), \(c=23^p\). Требуется найти сумму всех положительных целых чисел, которые нельзя представить в виде
$$n=ax+by+cz,\qquad x,y,z\in \mathbb{Z}_{>0},$$
для целевого случая \(p=6\), по модулю \(10^9+7\). Так как \(a\), \(b\) и \(c\) попарно взаимно просты, множество недостижимых чисел конечно. Поэтому задача сводится к анализу пробелов числовой полугруппы.
Сначала условие о строго положительных коэффициентах переводится в задачу о пробелах обычной числовой полугруппы. Затем число пробелов и их сумма выражаются через множество Апери относительно наименьшего образующего.
Рассмотрим числовую полугруппу
$$S=\langle a,b,c\rangle=\{ia+jb+kc:i,j,k\in \mathbb{Z}_{\ge 0}\}.$$
Также обозначим
$$s=a+b+c.$$
Если \(x,y,z\ge 1\), то
$$ax+by+cz=s+\bigl(a(x-1)+b(y-1)+c(z-1)\bigr).$$
Следовательно, положительное число \(n\) представимо со всеми положительными коэффициентами тогда и только тогда, когда
$$n-s\in S.$$
Отсюда недостижимые положительные числа состоят из двух частей:
$$1,2,\dots,s-1,$$
и всех чисел вида
$$s+g,$$
где \(g\) является пробелом полугруппы \(S\), то есть \(g\notin S\).
Если \(g(S)\) обозначает число пробелов, а \(\sigma(S)\) их сумму, то искомая величина равна
$$U(p)=\frac{s(s-1)}{2}+s\,g(S)+\sigma(S).$$
Так как \(a=17^p\) является наименьшим образующим, работа по модулю \(a\) даёт минимальное число состояний. Для каждого вычета \(r\in\{0,1,\dots,a-1\}\) определим
$$w_r=\min\{m\in S:m\equiv r\pmod a\}.$$
Множество \(\{w_0,\dots,w_{a-1}\}\) есть множество Апери полугруппы \(S\) относительно \(a\). Как только найдено \(w_r\), все достижимые числа в классе вычетов \(r\) имеют вид
$$w_r,\ w_r+a,\ w_r+2a,\dots,$$
а все меньшие неотрицательные числа с тем же вычетом являются пробелами.
Строится ориентированный граф на классах вычетов по модулю \(a\). Из вершины \(u\) выходят две дуги:
$$u\to u+b\pmod a,\qquad u\to u+c\pmod a.$$
Вес этих двух дуг равен \(b\) и \(c\) соответственно.
Любой путь из \(0\) в вычет \(r\) соответствует некоторому числу \(jb+kc\) с этим вычетом, причём длина пути точно равна самому числу. Поэтому расстояние кратчайшего пути от \(0\) до \(r\) есть минимальный элемент полугруппы в данном классе вычетов.
Отдельная дуга для прибавления \(a\) не нужна. Добавление \(a\) не меняет вычет и только увеличивает значение, значит, при поиске минимального представителя такая операция бесполезна. Следовательно, алгоритм Дейкстры возвращает ровно значения \(w_r\).
Запишем каждый элемент множества Апери в виде
$$w_r=r+a q_r,\qquad q_r\in \mathbb{Z}_{\ge 0}.$$
Тогда пробелы в классе вычетов \(r\) равны
$$r,\ r+a,\ r+2a,\dots,r+(q_r-1)a,$$
то есть этот класс даёт ровно \(q_r\) пробелов. Суммируя по всем вычетам, получаем
$$g(S)=\sum_{r=0}^{a-1} q_r=\frac{1}{a}\sum_{r=0}^{a-1} w_r-\frac{a-1}{2}.$$
Если обозначить
$$W_1=\sum_{r=0}^{a-1} w_r,$$
то
$$g(S)=\frac{W_1}{a}-\frac{a-1}{2}.$$
Пробелы внутри одного класса вычетов образуют арифметическую прогрессию, поэтому их сумма равна
$$q_r r+\frac{a q_r(q_r-1)}{2}.$$
Подставляя \(q_r=(w_r-r)/a\) и упрощая, получаем стандартную формулу для множества Апери:
$$\sigma(S)=\frac{1}{2a}\sum_{r=0}^{a-1} w_r^2-\frac12\sum_{r=0}^{a-1} w_r+\frac{a^2-1}{12}.$$
Если ввести обозначение
$$W_2=\sum_{r=0}^{a-1} w_r^2,$$
то формула перепишется как
$$\sigma(S)=\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}.$$
Объединяя сдвиг из шага 1 и две формулы для множества Апери, получаем
$$\boxed{U(p)=\frac{s(s-1)}{2}+s\left(\frac{W_1}{a}-\frac{a-1}{2}\right)+\left(\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}\right).}$$
Именно это значение и вычисляют реализации по модулю \(10^9+7\).
При \(p=1\) имеем \(a=17\), \(b=19\), \(c=23\), \(s=59\). Полное множество Апери по модулю \(17\) равно
$$\left(w_0,\dots,w_{16}\right)=\left(0,69,19,88,38,107,23,92,42,111,61,130,46,115,65,134,84\right).$$
Отсюда
$$W_1=1224,\qquad W_2=114036.$$
Число пробелов равно
$$g(S)=\frac{1224}{17}-\frac{16}{2}=72-8=64,$$
а их сумма равна
$$\sigma(S)=\frac{114036}{34}-\frac{1224}{2}+\frac{17^2-1}{12}=3354-612+24=2766.$$
Следовательно,
$$U(1)=\frac{59\cdot 58}{2}+59\cdot 64+2766=1711+3776+2766=8253,$$
что совпадает с малой проверкой, используемой реализациями.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала вычисляются степени \(17^p\), \(19^p\) и \(23^p\), затем наименьший генератор выбирается в качестве модуля, после чего на графе вычетов из шага 3 запускается алгоритм Дейкстры.
Полученная таблица расстояний и есть множество Апери. Затем реализация накапливает два моментных суммирования \(W_1=\sum w_r\) и \(W_2=\sum w_r^2\), постоянно работая по модулю \(10^9+7\).
В формулах для \(g(S)\), \(\sigma(S)\) и \(U(p)\) присутствует деление на \(2\), \(12\) и \(a\). Поскольку модуль прост и взаимно прост с этими числами, деление выполняется через модульные обратные элементы.
Та же схема сначала воспроизводит контрольные значения \(U(1)=8253\) и \(U(2)=60258000\), а затем вычисляет целевой случай \(p=6\).
Граф вычетов содержит \(a=17^p\) вершин и ровно две исходящие дуги из каждой вершины. При использовании бинарной кучи алгоритм Дейкстры работает за \(O(a\log a)\) по времени и требует \(O(a)\) памяти. Финальный проход для вычисления \(W_1\) и \(W_2\) линейный, поэтому общий асимптотический порядок не меняется.
لتكن \(a=17^p\) و\(b=19^p\) و\(c=23^p\). المطلوب هو حساب مجموع جميع الأعداد الصحيحة الموجبة التي لا يمكن كتابتها على الصورة
$$n=ax+by+cz,\qquad x,y,z\in \mathbb{Z}_{>0}$$
في الحالة المستهدفة \(p=6\)، مع أخذ الناتج النهائي بترديد \(10^9+7\). وبما أن \(a\) و\(b\) و\(c\) أولية فيما بينها زوجيًا، فإن مجموعة الأعداد غير القابلة للوصول منتهية، ولذلك تتحول المسألة إلى حساب فجوات شبه زمرة عددية.
الفكرة الأساسية هي تحويل شرط كون المعاملات موجبة تمامًا إلى مسألة فجوات في شبه زمرة عددية عادية، ثم استرجاع عدد هذه الفجوات ومجموعها من مجموعة أبيري بالنسبة إلى أصغر مولد.
نعرّف شبه الزمرة العددية
$$S=\langle a,b,c\rangle=\{ia+jb+kc:i,j,k\in \mathbb{Z}_{\ge 0}\}.$$
ونضع أيضًا
$$s=a+b+c.$$
إذا كان \(x,y,z\ge 1\)، فإن
$$ax+by+cz=s+\bigl(a(x-1)+b(y-1)+c(z-1)\bigr).$$
إذًا يكون العدد الموجب \(n\) قابلًا للتمثيل بمعاملات موجبة كلها إذا وفقط إذا كان
$$n-s\in S.$$
وعليه فإن الأعداد الموجبة غير القابلة للوصول تتكوّن من جزأين:
$$1,2,\dots,s-1,$$
وجميع الأعداد من الشكل
$$s+g,$$
حيث إن \(g\) فجوة في \(S\)، أي \(g\notin S\).
إذا رمزنا بعدد الفجوات بـ \(g(S)\)، وبرمز \(\sigma(S)\) إلى مجموعها، فإن الكمية المطلوبة هي
$$U(p)=\frac{s(s-1)}{2}+s\,g(S)+\sigma(S).$$
بما أن \(a=17^p\) هو أصغر المولدات، فإن العمل modulo \(a\) يعطي أصغر فضاء حالات ممكن. ولكل باقٍ \(r\in\{0,1,\dots,a-1\}\) نعرّف
$$w_r=\min\{m\in S:m\equiv r\pmod a\}.$$
والمجموعة \(\{w_0,\dots,w_{a-1}\}\) هي مجموعة أبيري الخاصة بـ \(S\) بالنسبة إلى \(a\). وبعد معرفة \(w_r\)، تكون كل الأعداد غير السالبة القابلة للوصول في فئة الباقي \(r\) هي
$$w_r,\ w_r+a,\ w_r+2a,\dots,$$
أما الأعداد الأصغر من ذلك في الفئة نفسها فهي فجوات.
نبني رسمًا موجهًا على فئات البواقي modulo \(a\). ومن كل باقٍ \(u\) نضيف ضلعين:
$$u\to u+b\pmod a,\qquad u\to u+c\pmod a.$$
وزنا هذين الضلعين هما \(b\) و\(c\) على الترتيب.
كل مسار من \(0\) إلى الباقي \(r\) يمثّل عددًا من الصورة \(jb+kc\) له هذا الباقي، وطول المسار يساوي هذا العدد نفسه. لذلك فإن أقصر مسار إلى \(r\) يعطي أصغر عنصر في شبه الزمرة يقع في فئة الباقي تلك.
ولا حاجة إلى ضلع إضافي لعملية \(+a\)، لأن إضافة \(a\) لا تغيّر الباقي وإنما تزيد القيمة فقط، وبالتالي لا تساعد أبدًا في إيجاد الممثل الأصغر. ومن ثم فإن خوارزمية ديكسترا تعطي مباشرة القيم \(w_r\).
نكتب كل عنصر من عناصر مجموعة أبيري على الصورة
$$w_r=r+a q_r,\qquad q_r\in \mathbb{Z}_{\ge 0}.$$
وعندئذ تكون فجوات فئة الباقي \(r\) هي
$$r,\ r+a,\ r+2a,\dots,r+(q_r-1)a,$$
أي إن هذه الفئة تساهم بعدد \(q_r\) من الفجوات. وبجمع ذلك على جميع البواقي نحصل على
$$g(S)=\sum_{r=0}^{a-1} q_r=\frac{1}{a}\sum_{r=0}^{a-1} w_r-\frac{a-1}{2}.$$
وإذا عرّفنا
$$W_1=\sum_{r=0}^{a-1} w_r,$$
فإن
$$g(S)=\frac{W_1}{a}-\frac{a-1}{2}.$$
فجوات فئة باقٍ واحدة تشكل متتالية حسابية، ولذلك يكون مجموعها
$$q_r r+\frac{a q_r(q_r-1)}{2}.$$
وبالتعويض عن \(q_r=(w_r-r)/a\) ثم التبسيط نحصل على هوية أبيري القياسية
$$\sigma(S)=\frac{1}{2a}\sum_{r=0}^{a-1} w_r^2-\frac12\sum_{r=0}^{a-1} w_r+\frac{a^2-1}{12}.$$
ومع التعريف
$$W_2=\sum_{r=0}^{a-1} w_r^2,$$
تصبح الصيغة
$$\sigma(S)=\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}.$$
بدمج الإزاحة في الخطوة الأولى مع هويتي أبيري السابقتين نحصل على
$$\boxed{U(p)=\frac{s(s-1)}{2}+s\left(\frac{W_1}{a}-\frac{a-1}{2}\right)+\left(\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}\right).}$$
وهذه هي بالضبط الكمية التي تحسبها التطبيقات modulo \(10^9+7\).
عندما \(p=1\)، يكون \(a=17\) و\(b=19\) و\(c=23\) و\(s=59\). مجموعة أبيري الكاملة modulo \(17\) هي
$$\left(w_0,\dots,w_{16}\right)=\left(0,69,19,88,38,107,23,92,42,111,61,130,46,115,65,134,84\right).$$
ومن ثم
$$W_1=1224,\qquad W_2=114036.$$
عدد فجوات \(S\) يساوي
$$g(S)=\frac{1224}{17}-\frac{16}{2}=72-8=64,$$
ومجموع هذه الفجوات هو
$$\sigma(S)=\frac{114036}{34}-\frac{1224}{2}+\frac{17^2-1}{12}=3354-612+24=2766.$$
وعليه
$$U(1)=\frac{59\cdot 58}{2}+59\cdot 64+2766=1711+3776+2766=8253,$$
وهو نفس مقدار التحقق الصغير الذي تستخدمه التطبيقات.
تتبع تطبيقات C++ وPython وJava الخطوات نفسها. فهي تحسب أولًا القيم \(17^p\) و\(19^p\) و\(23^p\)، ثم تختار أصغر مولد بوصفه المقياس الذي نأخذ عليه البواقي، وبعد ذلك تشغّل خوارزمية ديكسترا على الرسم الموصوف في الخطوة 3.
جدول المسافات الناتج هو نفسه مجموعة أبيري. ثم تجمع الشيفرة مجموعي العزوم \(W_1=\sum w_r\) و\(W_2=\sum w_r^2\)، مع إبقاء جميع العمليات تحت modulo \(10^9+7\).
وبما أن صيغ \(g(S)\) و\(\sigma(S)\) و\(U(p)\) تتضمن قسمة على \(2\) و\(12\) و\(a\)، فإن التنفيذ يستخدم المعكوسات الضربية modular inverses لأن المودولو عدد أولي وغير قابل للقسمة على هذه القيم.
والمنهج نفسه يعيد أولًا القيمتين التحققيتين \(U(1)=8253\) و\(U(2)=60258000\)، ثم ينتقل إلى الحالة المستهدفة \(p=6\).
يحتوي رسم البواقي على \(a=17^p\) رأسًا، ولكل رأس ضلعان خارجيان فقط. مع استخدام كومة ثنائية، تعمل خوارزمية ديكسترا بزمن \(O(a\log a)\) وذاكرة \(O(a)\). أما المرور اللاحق لحساب \(W_1\) و\(W_2\) فهو خطي، لذلك لا يغيّر التعقيد الكلي.