The snowflake construction leads to two integer sequences \(A(n)\) and \(B(n)\). For each \(n\ge 3\) we define
$$G(n)=\gcd(A(n),B(n)),$$
and the goal is to evaluate
$$\sum_{n=3}^{10^7} G(n).$$
The closed forms are easy to write down, but the raw values grow exponentially, so directly building the integers and then taking gcds would be far too expensive. The key is to reduce every gcd to one involving only numbers of size about \(7n\).
The implementation starts from explicit formulas for the two snowflake counts and then transforms the gcd into a much smaller modular problem.
The formulas used by the implementation are
$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1},$$
$$B(n)=\frac{(9n-69)\cdot 4^{n-1}+2(4n+26)\cdot 3^{n-1}}{2}.$$
These are exact integer expressions for the two quantities whose gcd is needed. The problem is not the formulas themselves, but the fact that \(4^{n-1}\) and \(3^{n-1}\) are enormous when \(n\) approaches \(10^7\).
Write
$$U=4^{n-2},\qquad V=3^{n-2}.$$
Then both closed forms simplify cleanly:
$$A(n)=6(2U-V),$$
$$B(n)=6\big((3n-23)U+(2n+13)V\big).$$
If we define
$$S=2U-V,\qquad T=(3n-23)U+(2n+13)V,$$
then
$$G(n)=\gcd(A(n),B(n))=6\gcd(S,T).$$
This already removes one fixed factor from every term in the sum.
The pair \((S,T)\) is a linear transformation of \((U,V)\). Two useful combinations are
$$ (2n+13)S+T=(7n+3)U, $$
$$ 2T-(3n-23)S=(7n+3)V. $$
Therefore any common divisor \(d\) of \(S\) and \(T\) must divide both \((7n+3)U\) and \((7n+3)V\).
But \(U=4^{n-2}\) and \(V=3^{n-2}\) are powers of coprime bases, so
$$\gcd(U,V)=1.$$
Hence every common divisor of \(S\) and \(T\) must divide
$$7n+3.$$
Equivalently, the determinant of the coefficient matrix
$$\begin{pmatrix}2 & -1 \\ 3n-23 & 2n+13\end{pmatrix}$$
is exactly
$$2(2n+13)-(-1)(3n-23)=7n+3,$$
and that determinant controls the gcd.
We now show that no information is lost when replacing \(T\) by \(7n+3\). Suppose \(d\) divides both \(S\) and \(7n+3\). Since \(S=2U-V\), we have
$$V\equiv 2U \pmod d.$$
Substituting this into \(T\) gives
$$T\equiv (3n-23)U+(2n+13)(2U)=(7n+3)U\equiv 0 \pmod d.$$
So every common divisor of \(S\) and \(7n+3\) is also a divisor of \(T\). Combining this with Step 3 yields
$$\gcd(S,T)=\gcd(S,7n+3).$$
Therefore the exact formula becomes
$$\boxed{G(n)=6\gcd\left(7n+3,\ 2\cdot 4^{n-2}-3^{n-2}\right).}$$
Let
$$M=7n+3.$$
The gcd only depends on the second argument modulo \(M\), so we only need the residue
$$R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M,\qquad 0\le R<M.$$
Then
$$G(n)=6\gcd(M,R).$$
This is the crucial speedup: instead of manipulating exponentially large integers, we compute two modular powers and one gcd for each \(n\).
The entire problem is therefore reduced to
$$\sum_{n=3}^{10^7} 6\gcd(M,R),\qquad M=7n+3,\qquad R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M.$$
That expression is exactly what the implementations evaluate.
For \(n=11\), the reduced modulus is
$$M=7\cdot 11+3=80.$$
Now compute the two powers only modulo \(80\):
$$4^9\equiv 64 \pmod{80},\qquad 3^9\equiv 3 \pmod{80}.$$
So
$$R\equiv 2\cdot 64-3=125\equiv 45 \pmod{80}.$$
Hence
$$G(11)=6\gcd(80,45)=6\cdot 5=30.$$
This agrees with the exact values
$$A(11)=3027630,\qquad B(11)=19862070,$$
whose gcd is indeed \(30\).
The C++, Python, and Java implementations all follow the same loop from \(n=3\) to \(10^7\). For each \(n\), they first form the modulus \(7n+3\). They then use binary exponentiation to evaluate \(4^{n-2}\bmod (7n+3)\) and \(3^{n-2}\bmod (7n+3)\) efficiently, combine those residues into the reduced value \(R\), compute \(\gcd(7n+3,R)\), multiply by \(6\), and add the result to the running total.
The C++ implementation adds a practical optimization: it splits the interval into disjoint blocks and lets several threads process different ranges in parallel, then combines the partial sums at the end. The Python and Java implementations keep the same mathematics but use a direct single-loop version of the algorithm.
For one value of \(n\), the dominant work is modular exponentiation with exponent \(n-2\), which costs \(O(\log n)\) time by repeated squaring. Summing over all \(n\le N\) gives total time
$$O\!\left(\sum_{n=3}^{N}\log n\right)=O(N\log N).$$
The memory usage is \(O(1)\) for the serial versions. The threaded C++ version uses \(O(T)\) extra memory for \(T\) partial sums and worker state, which is still constant with respect to \(N\).
Die Schneeflocken-Konstruktion führt auf zwei ganzzahlige Folgen \(A(n)\) und \(B(n)\). Für jedes \(n\ge 3\) wird
$$G(n)=\gcd(A(n),B(n))$$
gebildet, und gesucht ist die Summe
$$\sum_{n=3}^{10^7} G(n).$$
Die geschlossenen Formeln sind zwar einfach, aber ihre Werte wachsen exponentiell. Man darf also die Zahlen nicht direkt ausrechnen und erst danach den ggT bestimmen. Der entscheidende Schritt ist, jedes ggT-Problem auf Zahlen der Größenordnung \(7n\) zu reduzieren.
Die Implementierung startet mit exakten Formeln für die beiden Schneeflocken-Zahlen und formt den ggT dann zu einem viel kleineren modularen Problem um.
Verwendet werden die Formeln
$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1},$$
$$B(n)=\frac{(9n-69)\cdot 4^{n-1}+2(4n+26)\cdot 3^{n-1}}{2}.$$
Das sind exakte ganzzahlige Ausdrücke für die beiden Größen, deren ggT gesucht ist. Das eigentliche Problem ist nicht die Formel selbst, sondern die Größe von \(4^{n-1}\) und \(3^{n-1}\), wenn \(n\) nahe bei \(10^7\) liegt.
Setze
$$U=4^{n-2},\qquad V=3^{n-2}.$$
Dann vereinfachen sich beide Ausdrücke zu
$$A(n)=6(2U-V),$$
$$B(n)=6\big((3n-23)U+(2n+13)V\big).$$
Mit
$$S=2U-V,\qquad T=(3n-23)U+(2n+13)V$$
folgt sofort
$$G(n)=\gcd(A(n),B(n))=6\gcd(S,T).$$
Damit ist ein fester Faktor bereits vollständig abgespalten.
Das Paar \((S,T)\) ist eine lineare Transformation von \((U,V)\). Besonders nützlich sind die Kombinationen
$$ (2n+13)S+T=(7n+3)U, $$
$$ 2T-(3n-23)S=(7n+3)V. $$
Jeder gemeinsame Teiler \(d\) von \(S\) und \(T\) teilt also sowohl \((7n+3)U\) als auch \((7n+3)V\).
Da \(U=4^{n-2}\) und \(V=3^{n-2}\) Potenzen teilerfremder Basen sind, gilt
$$\gcd(U,V)=1.$$
Somit muss jeder gemeinsame Teiler von \(S\) und \(T\) bereits
$$7n+3$$
teilen. Gleichwertig dazu ist die Determinante der Koeffizientenmatrix
$$\begin{pmatrix}2 & -1 \\ 3n-23 & 2n+13\end{pmatrix}$$
nämlich
$$2(2n+13)-(-1)(3n-23)=7n+3,$$
und genau diese Determinante kontrolliert den ggT.
Nun muss man noch zeigen, dass beim Ersetzen von \(T\) durch \(7n+3\) nichts verloren geht. Angenommen, \(d\) teilt sowohl \(S\) als auch \(7n+3\). Aus \(S=2U-V\) folgt dann
$$V\equiv 2U \pmod d.$$
Setzt man dies in \(T\) ein, erhält man
$$T\equiv (3n-23)U+(2n+13)(2U)=(7n+3)U\equiv 0 \pmod d.$$
Also ist jeder gemeinsame Teiler von \(S\) und \(7n+3\) automatisch auch ein Teiler von \(T\). Zusammen mit Schritt 3 folgt
$$\gcd(S,T)=\gcd(S,7n+3).$$
Damit ergibt sich die exakte Formel
$$\boxed{G(n)=6\gcd\left(7n+3,\ 2\cdot 4^{n-2}-3^{n-2}\right).}$$
Sei
$$M=7n+3.$$
Für den ggT braucht man vom zweiten Argument nur den Rest modulo \(M\):
$$R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M,\qquad 0\le R<M.$$
Dann gilt
$$G(n)=6\gcd(M,R).$$
Genau das ist der Geschwindigkeitsgewinn: Für jedes \(n\) genügen zwei modulare Potenzen und ein ggT, statt mit exponentiell großen Ganzzahlen zu arbeiten.
Damit reduziert sich das gesamte Problem auf
$$\sum_{n=3}^{10^7} 6\gcd(M,R),\qquad M=7n+3,\qquad R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M.$$
Genau diesen Ausdruck werten die Implementierungen aus.
Für \(n=11\) ist der reduzierte Modulus
$$M=7\cdot 11+3=80.$$
Nun berechnet man die beiden Potenzen nur modulo \(80\):
$$4^9\equiv 64 \pmod{80},\qquad 3^9\equiv 3 \pmod{80}.$$
Also
$$R\equiv 2\cdot 64-3=125\equiv 45 \pmod{80}.$$
Damit folgt
$$G(11)=6\gcd(80,45)=6\cdot 5=30.$$
Das stimmt mit den exakten Werten
$$A(11)=3027630,\qquad B(11)=19862070$$
überein, deren ggT tatsächlich \(30\) ist.
Die C++-, Python- und Java-Implementierungen laufen alle dieselbe Schleife für \(n=3\) bis \(10^7\). Für jedes \(n\) wird zuerst der Modulus \(7n+3\) gebildet. Danach werden mit binärer Exponentiation die Werte \(4^{n-2}\bmod (7n+3)\) und \(3^{n-2}\bmod (7n+3)\) effizient berechnet, zu dem reduzierten Rest \(R\) kombiniert, der ggT \(\gcd(7n+3,R)\) bestimmt, mit \(6\) multipliziert und zum Gesamtergebnis addiert.
Die C++-Implementierung ergänzt dazu eine praktische Parallelisierung: Das Intervall wird in disjunkte Blöcke zerlegt, mehrere Threads bearbeiten verschiedene Bereiche gleichzeitig, und am Ende werden die Teilsummen zusammengeführt. Die Python- und Java-Implementierungen verwenden dieselbe Mathematik in einer direkten seriellen Schleife.
Für ein einzelnes \(n\) dominiert die modulare Exponentiation mit Exponent \(n-2\). Durch binäres Potenzieren kostet das \(O(\log n)\) Zeit. Summiert über alle \(n\le N\) ergibt sich insgesamt
$$O\!\left(\sum_{n=3}^{N}\log n\right)=O(N\log N).$$
Der Speicherverbrauch beträgt \(O(1)\) für die seriellen Versionen. Die parallele C++-Variante benötigt \(O(T)\) Zusatzspeicher für \(T\) Threads und ihre Teilsummen, also weiterhin konstanten Speicher in Bezug auf \(N\).
Kar tanesi yapısından iki tam sayı dizisi \(A(n)\) ve \(B(n)\) elde edilir. Her \(n\ge 3\) için
$$G(n)=\gcd(A(n),B(n))$$
tanımlanır ve istenen değer
$$\sum_{n=3}^{10^7} G(n)$$
toplamıdır. Kapalı formüller açık olsa da sayılar üstel olarak büyür; dolayısıyla dev tam sayıları üretip sonra EBOB almak verimli değildir. Esas fikir, her EBOB hesabını yaklaşık \(7n\) büyüklüğündeki sayılara indirmektir.
Uygulama önce iki kar tanesi sayımı için açık formülleri kullanır, sonra EBOB ifadesini çok daha küçük bir modüler probleme dönüştürür.
Kullanılan ifadeler şunlardır:
$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1},$$
$$B(n)=\frac{(9n-69)\cdot 4^{n-1}+2(4n+26)\cdot 3^{n-1}}{2}.$$
Bunlar EBOB'u alınacak iki niceliğin tam kapalı formlarıdır. Zorluk formüllerde değil, \(n\) büyüdüğünde \(4^{n-1}\) ve \(3^{n-1}\) değerlerinin astronomik hale gelmesindedir.
Şöyle yazalım:
$$U=4^{n-2},\qquad V=3^{n-2}.$$
O zaman her iki ifade de sadeleşir:
$$A(n)=6(2U-V),$$
$$B(n)=6\big((3n-23)U+(2n+13)V\big).$$
Şimdi
$$S=2U-V,\qquad T=(3n-23)U+(2n+13)V$$
tanımlarını yaparsak
$$G(n)=\gcd(A(n),B(n))=6\gcd(S,T)$$
elde edilir. Böylece her terimdeki sabit ortak çarpan tamamen ayrılmış olur.
\((S,T)\) çifti, \((U,V)\)'nin lineer bir dönüşümüdür. Özellikle şu iki kombinasyon kritik önemdedir:
$$ (2n+13)S+T=(7n+3)U, $$
$$ 2T-(3n-23)S=(7n+3)V. $$
Bu nedenle \(S\) ve \(T\)'nin her ortak böleni \(d\), hem \((7n+3)U\)'yu hem de \((7n+3)V\)'yi böler.
Fakat \(U=4^{n-2}\) ve \(V=3^{n-2}\), aralarında asal tabanların kuvvetleri olduğu için
$$\gcd(U,V)=1.$$
Dolayısıyla \(S\) ile \(T\)'nin her ortak böleni mutlaka
$$7n+3$$
sayısını da bölmelidir. Aynı sonuç, katsayı matrisinin determinantından da görülür:
$$\begin{pmatrix}2 & -1 \\ 3n-23 & 2n+13\end{pmatrix}$$
için determinant
$$2(2n+13)-(-1)(3n-23)=7n+3$$
çıkar ve EBOB'u kontrol eden sayı budur.
Şimdi \(T\) yerine \(7n+3\) yazmanın bilgi kaybettirmediğini gösterelim. Eğer \(d\), hem \(S\)'yi hem de \(7n+3\)'ü bölüyorsa, \(S=2U-V\) olduğundan
$$V\equiv 2U \pmod d$$
elde edilir. Bunu \(T\)'de yerine koyarsak
$$T\equiv (3n-23)U+(2n+13)(2U)=(7n+3)U\equiv 0 \pmod d.$$
Yani \(S\) ile \(7n+3\)'ün her ortak böleni, otomatik olarak \(T\)'yi de böler. Adım 3 ile birleştirince
$$\gcd(S,T)=\gcd(S,7n+3)$$
sonucuna ulaşırız. Böylece tam formül
$$\boxed{G(n)=6\gcd\left(7n+3,\ 2\cdot 4^{n-2}-3^{n-2}\right)}$$
olur.
Şimdi
$$M=7n+3$$
olsun. EBOB için ikinci argümanın yalnızca \(M\)'ye göre kalanı gerekir:
$$R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M,\qquad 0\le R<M.$$
Böylece
$$G(n)=6\gcd(M,R)$$
yazılır. Asıl hız kazancı burada gelir: her \(n\) için üstel büyüklükte sayılar yerine iki modüler üs alma ve bir EBOB hesabı yeterlidir.
Tüm problem şu ifadeye indirgenir:
$$\sum_{n=3}^{10^7} 6\gcd(M,R),\qquad M=7n+3,\qquad R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M.$$
Uygulamalar tam olarak bu toplamı hesaplar.
\(n=11\) için indirgenmiş modül
$$M=7\cdot 11+3=80$$
olur. Güçleri yalnızca modulo \(80\) hesaplamak yeterlidir:
$$4^9\equiv 64 \pmod{80},\qquad 3^9\equiv 3 \pmod{80}.$$
Bu yüzden
$$R\equiv 2\cdot 64-3=125\equiv 45 \pmod{80}.$$
Sonuç olarak
$$G(11)=6\gcd(80,45)=6\cdot 5=30$$
elde edilir. Bu, tam değerler
$$A(11)=3027630,\qquad B(11)=19862070$$
için bulunan EBOB ile aynıdır.
C++, Python ve Java uygulamaları aynı temel döngüyü izler: \(n=3\)'ten \(10^7\)'ye kadar gider, her adımda \(7n+3\) modülünü oluşturur, ikili üs alma yöntemiyle \(4^{n-2}\bmod (7n+3)\) ve \(3^{n-2}\bmod (7n+3)\) değerlerini hesaplar, bunlardan indirgenmiş kalan \(R\)'yi üretir, \(\gcd(7n+3,R)\) alır, sonucu \(6\) ile çarpar ve toplama ekler.
C++ uygulaması buna ek olarak aralığı ayrık bloklara bölüp çok çekirdekli çalıştırır; farklı iş parçacıkları farklı \(n\) aralıklarını toplar, sonra kısmi toplamlar birleştirilir. Python ve Java sürümleri ise aynı matematiği daha doğrudan tek döngü halinde uygular.
Tek bir \(n\) için baskın maliyet, üs \(n-2\) ile yapılan modüler üs almadır. İkili üs alma sayesinde bunun maliyeti \(O(\log n)\) olur. Tüm \(n\le N\) için toplam süre
$$O\!\left(\sum_{n=3}^{N}\log n\right)=O(N\log N)$$
seviyesindedir. Seri sürümlerde bellek \(O(1)\)'dir. Paralel C++ sürümünde \(T\) iş parçacığı için \(O(T)\) ek durum tutulur; bu da \(N\)'e göre sabit kabul edilir.
La construcción de la copa de nieve produce dos sucesiones enteras \(A(n)\) y \(B(n)\). Para cada \(n\ge 3\) se define
$$G(n)=\gcd(A(n),B(n)),$$
y el objetivo es calcular
$$\sum_{n=3}^{10^7} G(n).$$
Las fórmulas cerradas son sencillas, pero los valores crecen de forma exponencial. Por eso no conviene construir los enteros gigantes y después aplicar el mcd. La idea central es transformar cada cálculo de mcd en otro donde solo intervienen números del orden de \(7n\).
La implementación parte de fórmulas explícitas para las dos cantidades geométricas y luego convierte el mcd en un problema modular mucho más pequeño.
Las expresiones utilizadas son
$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1},$$
$$B(n)=\frac{(9n-69)\cdot 4^{n-1}+2(4n+26)\cdot 3^{n-1}}{2}.$$
Estas son fórmulas exactas para las dos cantidades cuyo mcd se necesita. El problema no es la forma cerrada en sí, sino que \(4^{n-1}\) y \(3^{n-1}\) se vuelven inmensos cuando \(n\) se acerca a \(10^7\).
Definimos
$$U=4^{n-2},\qquad V=3^{n-2}.$$
Entonces ambas expresiones se simplifican a
$$A(n)=6(2U-V),$$
$$B(n)=6\big((3n-23)U+(2n+13)V\big).$$
Si escribimos
$$S=2U-V,\qquad T=(3n-23)U+(2n+13)V,$$
obtenemos
$$G(n)=\gcd(A(n),B(n))=6\gcd(S,T).$$
Así se separa de inmediato un factor fijo presente en todos los términos.
El par \((S,T)\) es una transformación lineal de \((U,V)\). Dos combinaciones especialmente útiles son
$$ (2n+13)S+T=(7n+3)U, $$
$$ 2T-(3n-23)S=(7n+3)V. $$
Por lo tanto, cualquier divisor común \(d\) de \(S\) y \(T\) también divide a \((7n+3)U\) y a \((7n+3)V\).
Pero como \(U=4^{n-2}\) y \(V=3^{n-2}\) son potencias de bases coprimas, se cumple
$$\gcd(U,V)=1.$$
En consecuencia, todo divisor común de \(S\) y \(T\) debe dividir ya a
$$7n+3.$$
La misma conclusión se ve en el determinante de la matriz de coeficientes
$$\begin{pmatrix}2 & -1 \\ 3n-23 & 2n+13\end{pmatrix},$$
que vale
$$2(2n+13)-(-1)(3n-23)=7n+3.$$
Ahora hay que probar que sustituir \(T\) por \(7n+3\) no pierde información. Supongamos que \(d\) divide a la vez \(S\) y \(7n+3\). Como \(S=2U-V\), tenemos
$$V\equiv 2U \pmod d.$$
Al sustituir esto en \(T\), resulta
$$T\equiv (3n-23)U+(2n+13)(2U)=(7n+3)U\equiv 0 \pmod d.$$
Por tanto, todo divisor común de \(S\) y \(7n+3\) también divide a \(T\). Junto con el paso anterior se obtiene
$$\gcd(S,T)=\gcd(S,7n+3).$$
La fórmula exacta queda entonces
$$\boxed{G(n)=6\gcd\left(7n+3,\ 2\cdot 4^{n-2}-3^{n-2}\right).}$$
Sea
$$M=7n+3.$$
Para el mcd solo importa el segundo argumento módulo \(M\), así que basta calcular
$$R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M,\qquad 0\le R<M.$$
Entonces
$$G(n)=6\gcd(M,R).$$
Aquí aparece la mejora decisiva: para cada \(n\) solo hacen falta dos potencias modulares y un mcd, sin construir enteros exponencialmente grandes.
Todo el problema se reduce a
$$\sum_{n=3}^{10^7} 6\gcd(M,R),\qquad M=7n+3,\qquad R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M.$$
Esa es exactamente la expresión que evalúan las implementaciones.
Cuando \(n=11\), el módulo reducido es
$$M=7\cdot 11+3=80.$$
Solo necesitamos las potencias módulo \(80\):
$$4^9\equiv 64 \pmod{80},\qquad 3^9\equiv 3 \pmod{80}.$$
Por tanto,
$$R\equiv 2\cdot 64-3=125\equiv 45 \pmod{80}.$$
Luego
$$G(11)=6\gcd(80,45)=6\cdot 5=30.$$
Esto coincide con los valores exactos
$$A(11)=3027630,\qquad B(11)=19862070,$$
cuyo mcd también es \(30\).
Las implementaciones en C++, Python y Java siguen el mismo esquema: recorren \(n\) desde \(3\) hasta \(10^7\), forman el módulo \(7n+3\), calculan mediante exponenciación binaria los residuos \(4^{n-2}\bmod (7n+3)\) y \(3^{n-2}\bmod (7n+3)\), construyen el valor reducido \(R\), obtienen \(\gcd(7n+3,R)\), multiplican por \(6\) y acumulan el resultado.
La versión en C++ añade una optimización práctica: divide el intervalo en bloques disjuntos y los procesa en paralelo con varios hilos, para combinar las sumas parciales al final. Las versiones en Python y Java mantienen exactamente la misma matemática en un bucle directo y secuencial.
Para un valor fijo de \(n\), el coste dominante es la exponenciación modular con exponente \(n-2\), que mediante exponenciación por cuadrados cuesta \(O(\log n)\). Sumando para todos los \(n\le N\), el tiempo total es
$$O\!\left(\sum_{n=3}^{N}\log n\right)=O(N\log N).$$
El uso de memoria es \(O(1)\) en las versiones secuenciales. La versión paralela en C++ utiliza \(O(T)\) memoria adicional para \(T\) hilos y sus sumas parciales, lo que sigue siendo constante respecto de \(N\).
雪花构造会导出两个整数序列 \(A(n)\) 和 \(B(n)\)。对每个 \(n\ge 3\)，定义
$$G(n)=\gcd(A(n),B(n)),$$
题目要求计算
$$\sum_{n=3}^{10^7} G(n).$$
难点不在于写出闭式，而在于这些值增长得极快。若直接生成 \(A(n)\) 和 \(B(n)\) 的完整整数，再对它们求最大公约数，计算量会非常大。真正有效的方法，是把每一次 gcd 计算都压缩成一个只涉及约 \(7n\) 规模整数的问题。
实现所依据的思路是：先从几何构造得到两个精确闭式，再把 \(\gcd(A(n),B(n))\) 转化成一个小模数下的同余问题。
实现采用的公式为
$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1},$$
$$B(n)=\frac{(9n-69)\cdot 4^{n-1}+2(4n+26)\cdot 3^{n-1}}{2}.$$
这两个表达式都是严格的整数公式。问题在于，当 \(n\) 接近 \(10^7\) 时，\(4^{n-1}\) 与 \(3^{n-1}\) 已经大得无法直接操作，所以必须继续化简。
令
$$U=4^{n-2},\qquad V=3^{n-2}.$$
则两式可改写为
$$A(n)=6(2U-V),$$
$$B(n)=6\big((3n-23)U+(2n+13)V\big).$$
进一步记
$$S=2U-V,\qquad T=(3n-23)U+(2n+13)V,$$
于是
$$G(n)=\gcd(A(n),B(n))=6\gcd(S,T).$$
这一步很重要，因为它把所有项中固定存在的因子 \(6\) 直接剥离出来，剩下的问题只需研究 \(\gcd(S,T)\)。
\((S,T)\) 是由 \((U,V)\) 线性变换得到的。下面两个恒等式最关键：
$$ (2n+13)S+T=(7n+3)U, $$
$$ 2T-(3n-23)S=(7n+3)V. $$
因此，若某个整数 \(d\) 同时整除 \(S\) 和 \(T\)，那么它也一定整除 \((7n+3)U\) 与 \((7n+3)V\)。
而 \(U=4^{n-2}\)、\(V=3^{n-2}\) 分别是 \(4\) 和 \(3\) 的幂，所以
$$\gcd(U,V)=1.$$
既然 \(U\) 与 \(V\) 互素，那么 \(d\) 不可能从两边都“吃掉”额外的公共因子，只能真正整除
$$7n+3.$$
同样的结论也可以从系数矩阵
$$\begin{pmatrix}2 & -1 \\ 3n-23 & 2n+13\end{pmatrix}$$
的行列式看出来，因为
$$2(2n+13)-(-1)(3n-23)=7n+3.$$
这说明 \(\gcd(S,T)\) 必然被一个线性大小的整数控制住，而不是被巨大幂次控制。
上一步说明 \(\gcd(S,T)\) 一定整除 \(7n+3\)，但还需要证明反过来也成立到 gcd 层面。设 \(d\) 同时整除 \(S\) 与 \(7n+3\)。由于
$$S=2U-V,$$
可得
$$V\equiv 2U \pmod d.$$
把它代回 \(T\)：
$$T\equiv (3n-23)U+(2n+13)(2U)=(7n+3)U\equiv 0 \pmod d.$$
所以，只要某个数同时整除 \(S\) 和 \(7n+3\)，它也一定整除 \(T\)。结合步骤 3，就得到完全等价的结论
$$\gcd(S,T)=\gcd(S,7n+3).$$
于是问题被精确化简为
$$\boxed{G(n)=6\gcd\left(7n+3,\ 2\cdot 4^{n-2}-3^{n-2}\right).}$$
令
$$M=7n+3.$$
求 gcd 时，第二个参数只需要知道模 \(M\) 的余数，因此只要计算
$$R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M,\qquad 0\le R<M.$$
就足够了。于是
$$G(n)=6\gcd(M,R).$$
这一点直接决定了算法可行：每个 \(n\) 只需要两次模幂计算和一次 gcd，而不需要构造任何真正的超大整数。
整个题目因此化为
$$\sum_{n=3}^{10^7} 6\gcd(M,R),\qquad M=7n+3,\qquad R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M.$$
这正是实现最终逐项累加的表达式。
当 \(n=11\) 时，先得到
$$M=7\cdot 11+3=80.$$
现在只需在模 \(80\) 下求幂：
$$4^9\equiv 64 \pmod{80},\qquad 3^9\equiv 3 \pmod{80}.$$
因此
$$R\equiv 2\cdot 64-3=125\equiv 45 \pmod{80}.$$
从而
$$G(11)=6\gcd(80,45)=6\cdot 5=30.$$
如果回到原始闭式，也会得到
$$A(11)=3027630,\qquad B(11)=19862070,$$
它们的最大公约数同样是 \(30\)。这个例子说明，模运算版本与原始大整数版本完全一致，但计算代价小得多。
C++、Python 和 Java 实现都遵循同一个核心流程。它们从 \(n=3\) 枚举到 \(10^7\)，对每个 \(n\) 先构造模数 \(7n+3\)，再用二进制快速幂计算 \(4^{n-2}\bmod (7n+3)\) 与 \(3^{n-2}\bmod (7n+3)\)，据此形成余数 \(R\)，接着求 \(\gcd(7n+3,R)\)，乘以 \(6\)，最后加入总和。
C++ 版本还做了工程上的并行化处理：把整个区间切成互不重叠的块，由多个线程分别累加，最后再把部分和合并。Python 和 Java 版本则保留相同的数学公式，但使用直接的单循环写法。
对单个 \(n\)，主要代价来自指数为 \(n-2\) 的模幂运算。使用平方递推后，时间复杂度为 \(O(\log n)\)。因此对所有 \(n\le N\) 的总时间为
$$O\!\left(\sum_{n=3}^{N}\log n\right)=O(N\log N).$$
串行版本的额外空间是 \(O(1)\)。并行的 C++ 版本需要为线程和部分和保存 \(O(T)\) 的附加状态，其中 \(T\) 是线程数，因此相对于 \(N\) 仍可视为常数级空间。
Построение снежинки приводит к двум целочисленным последовательностям \(A(n)\) и \(B(n)\). Для каждого \(n\ge 3\) определяется
$$G(n)=\gcd(A(n),B(n)),$$
и требуется вычислить сумму
$$\sum_{n=3}^{10^7} G(n).$$
Закрытые формулы известны, но сами значения растут экспоненциально. Поэтому напрямую строить огромные числа и только потом брать их НОД невыгодно. Нужно свести каждое вычисление к НОД чисел порядка \(7n\).
Реализация начинает с точных формул для двух количеств, возникающих в конструкции, а затем превращает вычисление НОД в существенно более маленькую модульную задачу.
Используются выражения
$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1},$$
$$B(n)=\frac{(9n-69)\cdot 4^{n-1}+2(4n+26)\cdot 3^{n-1}}{2}.$$
Это точные целочисленные формулы для двух величин, чей НОД нам нужен. Трудность состоит не в самих формулах, а в том, что степени \(4^{n-1}\) и \(3^{n-1}\) становятся колоссальными, когда \(n\) близко к \(10^7\).
Положим
$$U=4^{n-2},\qquad V=3^{n-2}.$$
Тогда формулы переписываются так:
$$A(n)=6(2U-V),$$
$$B(n)=6\big((3n-23)U+(2n+13)V\big).$$
Если обозначить
$$S=2U-V,\qquad T=(3n-23)U+(2n+13)V,$$
то получаем
$$G(n)=\gcd(A(n),B(n))=6\gcd(S,T).$$
Так фиксированный множитель \(6\) сразу выносится наружу, и дальше нужно анализировать только \(\gcd(S,T)\).
Пара \((S,T)\) является линейным преобразованием пары \((U,V)\). Особенно полезны равенства
$$ (2n+13)S+T=(7n+3)U, $$
$$ 2T-(3n-23)S=(7n+3)V. $$
Следовательно, любой общий делитель \(d\) чисел \(S\) и \(T\) обязан делить и \((7n+3)U\), и \((7n+3)V\).
Но \(U=4^{n-2}\) и \(V=3^{n-2}\) являются степенями взаимно простых оснований, поэтому
$$\gcd(U,V)=1.$$
Значит, общий делитель \(S\) и \(T\) обязательно делит уже
$$7n+3.$$
То же самое видно из детерминанта матрицы коэффициентов
$$\begin{pmatrix}2 & -1 \\ 3n-23 & 2n+13\end{pmatrix},$$
поскольку
$$2(2n+13)-(-1)(3n-23)=7n+3.$$
Теперь нужно доказать, что замена \(T\) на \(7n+3\) не теряет информации. Пусть \(d\) делит и \(S\), и \(7n+3\). Из равенства
$$S=2U-V$$
следует
$$V\equiv 2U \pmod d.$$
Подставляя это в \(T\), получаем
$$T\equiv (3n-23)U+(2n+13)(2U)=(7n+3)U\equiv 0 \pmod d.$$
Значит, каждый общий делитель \(S\) и \(7n+3\) автоматически делит и \(T\). В сочетании с предыдущим шагом это дает
$$\gcd(S,T)=\gcd(S,7n+3).$$
Тем самым получаем точную формулу
$$\boxed{G(n)=6\gcd\left(7n+3,\ 2\cdot 4^{n-2}-3^{n-2}\right).}$$
Обозначим
$$M=7n+3.$$
Для НОД нужен только остаток второго аргумента по модулю \(M\), то есть достаточно вычислить
$$R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M,\qquad 0\le R<M.$$
Тогда
$$G(n)=6\gcd(M,R).$$
Именно здесь появляется основное ускорение: вместо гигантских целых чисел для каждого \(n\) нужны только две модульные степени и один НОД.
Вся задача сводится к выражению
$$\sum_{n=3}^{10^7} 6\gcd(M,R),\qquad M=7n+3,\qquad R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M.$$
Именно эту сумму вычисляют реализации.
При \(n=11\) получаем
$$M=7\cdot 11+3=80.$$
Теперь степени нужны только по модулю \(80\):
$$4^9\equiv 64 \pmod{80},\qquad 3^9\equiv 3 \pmod{80}.$$
Следовательно,
$$R\equiv 2\cdot 64-3=125\equiv 45 \pmod{80}.$$
Отсюда
$$G(11)=6\gcd(80,45)=6\cdot 5=30.$$
Это полностью совпадает с точными значениями
$$A(11)=3027630,\qquad B(11)=19862070,$$
НОД которых тоже равен \(30\).
Реализации на C++, Python и Java следуют одному и тому же алгоритму. Они перебирают \(n\) от \(3\) до \(10^7\), для каждого значения строят модуль \(7n+3\), с помощью бинарного возведения в степень вычисляют \(4^{n-2}\bmod (7n+3)\) и \(3^{n-2}\bmod (7n+3)\), составляют остаток \(R\), находят \(\gcd(7n+3,R)\), умножают результат на \(6\) и прибавляют к сумме.
Версия на C++ дополнительно распараллеливает вычисления: весь диапазон разбивается на непересекающиеся блоки, разные потоки считают частичные суммы, а затем эти суммы складываются. Реализации на Python и Java используют ту же математику в прямом последовательном цикле.
Для одного фиксированного \(n\) основная стоимость определяется модульным возведением в степень с показателем \(n-2\). Благодаря бинарному методу это занимает \(O(\log n)\) времени. Поэтому суммарная сложность по всем \(n\le N\) равна
$$O\!\left(\sum_{n=3}^{N}\log n\right)=O(N\log N).$$
Память у последовательных версий равна \(O(1)\). Параллельная версия на C++ использует \(O(T)\) дополнительной памяти для \(T\) потоков и их частичных сумм, что по-прежнему является константой относительно \(N\).
يؤدي بناء رقاقات الثلج إلى متتاليتين صحيحتي القيم \(A(n)\) و\(B(n)\). ولكل \(n\ge 3\) نعرّف
$$G(n)=\gcd(A(n),B(n)),$$
والمطلوب هو حساب
$$\sum_{n=3}^{10^7} G(n).$$
الصيغ المغلقة نفسها ليست المشكلة، بل إن قيمها تنمو نموًا أسيًا. لذلك لا يمكن الاعتماد على بناء الأعداد الضخمة كاملة ثم أخذ القاسم المشترك الأكبر. الفكرة الأساسية هي اختزال كل حساب إلى أعداد حجمها يقارب \(7n\) فقط.
تنطلق الشيفرة من صيغ صريحة للكميتين الناتجتين عن البناء الهندسي، ثم تحوّل مسألة \(\gcd(A(n),B(n))\) إلى مسألة توافقات أصغر بكثير.
الصيغ المستخدمة هي
$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1},$$
$$B(n)=\frac{(9n-69)\cdot 4^{n-1}+2(4n+26)\cdot 3^{n-1}}{2}.$$
هاتان الصيغتان تعطيان قيمتين صحيحتين تمامًا. لكن عند اقتراب \(n\) من \(10^7\)، تصبح القوى \(4^{n-1}\) و\(3^{n-1}\) هائلة جدًا، ولذلك لا بد من اختزال إضافي قبل أي حساب عملي.
لنضع
$$U=4^{n-2},\qquad V=3^{n-2}.$$
حينها تصبح الصيغتان
$$A(n)=6(2U-V),$$
$$B(n)=6\big((3n-23)U+(2n+13)V\big).$$
وباستخدام
$$S=2U-V,\qquad T=(3n-23)U+(2n+13)V,$$
نحصل على
$$G(n)=\gcd(A(n),B(n))=6\gcd(S,T).$$
وهكذا يُفصل العامل الثابت \(6\) من البداية، ويبقى التركيز على \(\gcd(S,T)\).
الزوج \((S,T)\) هو تحويل خطي للزوج \((U,V)\). والهوّيتان الأساسيتان هنا هما
$$ (2n+13)S+T=(7n+3)U, $$
$$ 2T-(3n-23)S=(7n+3)V. $$
إذن أي عدد \(d\) يقسم كلًا من \(S\) و\(T\) لا بد أن يقسم أيضًا \((7n+3)U\) و\((7n+3)V\).
لكن \(U=4^{n-2}\) و\(V=3^{n-2}\) قوتان لأساسين متباينين، ولذلك
$$\gcd(U,V)=1.$$
ومن ثم لا بد أن يقسم أي قاسم مشترك لـ \(S\) و\(T\) العدد
$$7n+3.$$
وتظهر الفكرة نفسها من محدد مصفوفة المعاملات
$$\begin{pmatrix}2 & -1 \\ 3n-23 & 2n+13\end{pmatrix}$$
لأن
$$2(2n+13)-(-1)(3n-23)=7n+3.$$
الآن نثبت أن استبدال \(T\) بالعدد \(7n+3\) لا يفقد أي معلومة. إذا كان \(d\) يقسم كلًا من \(S\) و\(7n+3\)، فبما أن
$$S=2U-V,$$
فإننا نحصل على
$$V\equiv 2U \pmod d.$$
وبالتعويض في \(T\) ينتج
$$T\equiv (3n-23)U+(2n+13)(2U)=(7n+3)U\equiv 0 \pmod d.$$
إذن كل قاسم مشترك لـ \(S\) و\(7n+3\) هو أيضًا قاسم لـ \(T\). ومع نتيجة الخطوة السابقة نحصل على
$$\gcd(S,T)=\gcd(S,7n+3).$$
ومن ثم تصبح الصيغة الدقيقة
$$\boxed{G(n)=6\gcd\left(7n+3,\ 2\cdot 4^{n-2}-3^{n-2}\right).}$$
لنرمز إلى
$$M=7n+3.$$
في حساب القاسم المشترك الأكبر يكفي معرفة باقي الحد الثاني modulo \(M\)، أي يكفي حساب
$$R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M,\qquad 0\le R<M.$$
وعندئذٍ
$$G(n)=6\gcd(M,R).$$
وهنا يظهر التسريع الحقيقي: لكل \(n\) نحتاج فقط إلى حساب قوتين معياريتين وقاسم مشترك أكبر واحد، من دون بناء الأعداد الأسية الضخمة نفسها.
بذلك تختزل المسألة كلها إلى
$$\sum_{n=3}^{10^7} 6\gcd(M,R),\qquad M=7n+3,\qquad R\equiv 2\cdot 4^{n-2}-3^{n-2}\pmod M.$$
وهذا هو التعبير الذي تنفذه التطبيقات مباشرة.
عندما \(n=11\) يكون
$$M=7\cdot 11+3=80.$$
ثم نحسب القوتين modulo \(80\) فقط:
$$4^9\equiv 64 \pmod{80},\qquad 3^9\equiv 3 \pmod{80}.$$
إذن
$$R\equiv 2\cdot 64-3=125\equiv 45 \pmod{80}.$$
ومن ثم
$$G(11)=6\gcd(80,45)=6\cdot 5=30.$$
وهذا يطابق القيمتين الدقيقتين
$$A(11)=3027630,\qquad B(11)=19862070,$$
إذ إن القاسم المشترك الأكبر لهما يساوي فعلًا \(30\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها. فهي تمر على جميع قيم \(n\) من \(3\) حتى \(10^7\)، وتكوّن لكل قيمة العدد \(7n+3\)، ثم تستخدم الرفع الثنائي السريع لحساب \(4^{n-2}\bmod (7n+3)\) و\(3^{n-2}\bmod (7n+3)\)، وبعد ذلك تكوّن الباقي \(R\)، وتحسب \(\gcd(7n+3,R)\)، وتضرب الناتج في \(6\)، ثم تضيفه إلى المجموع الكلي.
تضيف نسخة C++ تحسينًا عمليًا مهمًا، إذ تقسّم المجال إلى كتل مستقلة وتعالجها خيوط متعددة بالتوازي، ثم تجمع المجاميع الجزئية في النهاية. أما نسختا Python وJava فتطبقان الرياضيات نفسها في حلقة تسلسلية مباشرة.
بالنسبة إلى قيمة واحدة من \(n\)، فإن الكلفة المسيطرة هي حساب القوى المعيارية ذات الأس \(n-2\). وباستخدام الرفع بالتربيع تكون الكلفة \(O(\log n)\). لذلك فإن الزمن الكلي لجميع القيم حتى \(N\) يساوي
$$O\!\left(\sum_{n=3}^{N}\log n\right)=O(N\log N).$$
استهلاك الذاكرة هو \(O(1)\) في النسخ التسلسلية. أما نسخة C++ المتوازية فتستخدم \(O(T)\) من الذاكرة الإضافية لحفظ حالة \(T\) خيطًا والمجاميع الجزئية، وهو ما يظل ثابتًا بالنسبة إلى \(N\).