Let
$$P=\{5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149\}$$
be the primes below \(150\) with \(p\equiv1\pmod4\). For every non-empty squarefree product of distinct primes from \(P\), the problem considers all representations
$$n=a^2+b^2$$
and asks us to add the smaller component from each representation. The final numeric answer is omitted here; the goal is to explain why the code can enumerate all valid representations without overcounting.
The whole solution is built on the arithmetic of Gaussian integers \(\mathbb Z[i]\), where the norm
$$N(x+iy)=x^2+y^2$$
is multiplicative.
By Fermat's two-square theorem, every prime \(p\equiv1\pmod4\) has a representation
$$p=u_p^2+v_p^2.$$
Equivalently, in \(\mathbb Z[i]\) it factors as
$$p=(u_p+iv_p)(u_p-iv_p)=z_p\overline{z_p}.$$
The code stores one canonical factor \(z_p\) for each prime. Its helper build_representations()
searches odd \(u\) and even \(v\), which is enough for these primes. For example,
$$5=1^2+2^2,\qquad 13=3^2+2^2,\qquad 17=1^2+4^2.$$
So the stored Gaussian representatives are \(z_5=1+2i\), \(z_{13}=3+2i\), \(z_{17}=1+4i\).
If \(z=a+bi\) and \(w=c+di\), then
$$zw=(ac-bd)+i(ad+bc),$$
and therefore
$$N(zw)=N(z)N(w).$$
Written out in ordinary integers, this is the classical identity
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac-bd)^2+(ad+bc)^2.$$
If we conjugate one factor we get the second standard form
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac+bd)^2+(ad-bc)^2.$$
This is exactly why multiplying Gaussian factors generates every representation of a product as a sum of two squares.
Take a non-empty subset \(S\subseteq P\), and define
$$n=\prod_{p\in S} p.$$
Since every such prime splits as \(p=z_p\overline{z_p}\), a factorization of \(n\) in \(\mathbb Z[i]\) is obtained by choosing exactly one factor from each pair:
$$Z=\prod_{p\in S}\eta_p,\qquad \eta_p\in\{z_p,\overline{z_p}\}.$$
Then \(N(Z)=n\). If \(Z=x+iy\), we immediately get
$$n=x^2+y^2.$$
Conversely, for a squarefree product of such primes, every representation arises from such a choice, up to the usual symmetries \((x,y)\mapsto(\pm x,\pm y)\) and swapping the two coordinates.
Suppose we have already fixed some current Gaussian product \(Z\). For the next prime \(p\), there are only three meaningful options:
1. skip \(p\), meaning \(p\) is not in the subset;
2. multiply by \(z_p\);
3. multiply by \(\overline{z_p}\).
That is why the recursion is ternary:
$$\text{dfs}(idx,Z)=\text{dfs}(idx+1,Z)+\text{dfs}(idx+1,Zz_p)+\text{dfs}(idx+1,Z\overline{z_p}).$$
At a leaf, the code has built one complete representation \(Z=x+iy\), so it contributes
$$\min(|x|,|y|).$$
A naive DFS starting from \(1\) and allowing every selected prime to choose either \(z_p\) or \(\overline{z_p}\) would double-count every non-empty subset. The reason is global conjugation:
$$Z=\prod_{p\in S}\eta_p \qquad \Longrightarrow \qquad \overline{Z}=\prod_{p\in S}\overline{\eta_p}.$$
But \(Z=x+iy\) and \(\overline{Z}=x-iy\) represent the same unordered pair \((|x|,|y|)\), hence the same contribution \(\min(|x|,|y|)\).
The implementation removes that symmetry by choosing the first included prime \(p_k\) in the outer loop and forcing its factor to be \(z_{p_k}\), not \(\overline{z_{p_k}}\). Only primes with larger index branch between \(z_p\) and \(\overline{z_p}\). So each non-empty subset is enumerated exactly once up to global conjugation.
Use \(z_5=1+2i\) and \(z_{13}=3+2i\). The two conjugate choices for the second prime produce the two relevant representations:
$$\left(1+2i\right)\left(3+2i\right)=-1+8i \quad\Longrightarrow\quad 65=1^2+8^2,$$
$$\left(1+2i\right)\left(3-2i\right)=7+4i \quad\Longrightarrow\quad 65=7^2+4^2.$$
Therefore the total contribution of \(65\) is
$$\min(1,8)+\min(7,4)=1+4=5.$$
This also gives a clean checkpoint for the first two primes only:
$$5\mapsto1,\qquad 13\mapsto2,\qquad 65\mapsto5,\qquad \text{total}=8.$$
The same code, restricted to the first three primes \(\{5,13,17\}\), gives \(80\), and restricted to the first four gives \(906\).
Representation table. build_representations() scans odd \(i\) and even \(j\), and when
\(i^2+j^2<150\) it stores the Gaussian integer \(i+ji\). For the 16 target primes, this yields exactly one canonical
representation per prime.
Recursive enumeration. dfs(idx, value) processes the remaining primes in increasing
order. The three recursive calls correspond to skip, multiply by \(z_p\), and multiply by \(\overline{z_p}\).
Leaf contribution. When all primes have been processed, the current Gaussian product
value = x + iy encodes one valid representation of one squarefree product. The code returns
min(abs(x), abs(y)).
Canonical start. solve() loops over the position of the first chosen prime and starts
the DFS with reps[p]. This is the exact mechanism that removes the global conjugation duplicate.
If \(k=16\) is the number of eligible primes, the direct search has size
$$\sum_{m=0}^{k-1}3^m=\frac{3^k-1}{2}=O(3^k).$$
That sounds large in theory, but here \(k\) is tiny and each state only performs a small Gaussian-integer multiplication on 64-bit integers. The recursion depth is \(O(k)\), so memory usage is \(O(k)\).
Sei
$$P=\{5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149\}$$
die Menge aller Primzahlen unter \(150\) mit \(p\equiv1\pmod4\). Für jedes nichtleere quadratfreie Produkt verschiedener Primzahlen aus \(P\) betrachtet das Problem alle Darstellungen
$$n=a^2+b^2$$
und addiert aus jeder Darstellung die kleinere Komponente. Der numerische Endwert ist hier nicht das Ziel; wichtig ist zu verstehen, warum der Code alle Darstellungen vollständig und ohne Doppelzählung erzeugt.
Die gesamte Lösung arbeitet in den gaußschen Zahlen \(\mathbb Z[i]\). Dort ist die Norm
$$N(x+iy)=x^2+y^2$$
multiplikativ.
Nach dem Zwei-Quadrate-Satz von Fermat besitzt jede Primzahl \(p\equiv1\pmod4\) eine Darstellung
$$p=u_p^2+v_p^2.$$
In \(\mathbb Z[i]\) bedeutet das die Faktorisierung
$$p=(u_p+iv_p)(u_p-iv_p)=z_p\overline{z_p}.$$
Der Code speichert für jede Primzahl genau einen kanonischen Faktor \(z_p\). In
build_representations() werden ungerade \(u\) und gerade \(v\) durchsucht; das reicht für diese
Primzahlen. Beispiele:
$$5=1^2+2^2,\qquad 13=3^2+2^2,\qquad 17=1^2+4^2.$$
Daraus folgen \(z_5=1+2i\), \(z_{13}=3+2i\), \(z_{17}=1+4i\).
Für \(z=a+bi\) und \(w=c+di\) gilt
$$zw=(ac-bd)+i(ad+bc),$$
also
$$N(zw)=N(z)N(w).$$
Als Identität über gewöhnlichen ganzen Zahlen ergibt das
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac-bd)^2+(ad+bc)^2.$$
Konjugiert man einen Faktor, erhält man die zweite Standardform
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac+bd)^2+(ad-bc)^2.$$
Genau diese Identität benutzt die DFS implizit bei jeder Multiplikation in \(\mathbb Z[i]\).
Sei \(S\subseteq P\) nichtleer und
$$n=\prod_{p\in S} p.$$
Da jedes solche \(p\) als \(p=z_p\overline{z_p}\) zerfällt, erhält man eine Faktorisierung von \(n\), indem man aus jedem Paar genau einen Faktor wählt:
$$Z=\prod_{p\in S}\eta_p,\qquad \eta_p\in\{z_p,\overline{z_p}\}.$$
Dann ist \(N(Z)=n\). Schreibt man \(Z=x+iy\), folgt sofort
$$n=x^2+y^2.$$
Umgekehrt stammt bei einem quadratfreien Produkt jede Darstellung aus genau solchen Wahlen, bis auf die üblichen Symmetrien von Vorzeichen und Vertauschung der Koordinaten.
Ist ein aktuelles Produkt \(Z\) bereits festgelegt, gibt es für die nächste Primzahl \(p\) genau drei sinnvolle Möglichkeiten:
1. \(p\) wird nicht verwendet;
2. \(Z\) wird mit \(z_p\) multipliziert;
3. \(Z\) wird mit \(\overline{z_p}\) multipliziert.
Daher hat die Rekursion die Form
$$\text{dfs}(idx,Z)=\text{dfs}(idx+1,Z)+\text{dfs}(idx+1,Zz_p)+\text{dfs}(idx+1,Z\overline{z_p}).$$
Am Blatt steht \(Z=x+iy\) für eine vollständige Darstellung, und der Beitrag ist
$$\min(|x|,|y|).$$
Eine naive DFS ab \(1\), bei der jede gewählte Primzahl zwischen \(z_p\) und \(\overline{z_p}\) wählen darf, würde jedes nichtleere Teilmengenprodukt doppelt zählen. Grund ist die globale Konjugation:
$$Z=\prod_{p\in S}\eta_p \qquad \Longrightarrow \qquad \overline{Z}=\prod_{p\in S}\overline{\eta_p}.$$
Aber \(Z=x+iy\) und \(\overline{Z}=x-iy\) beschreiben dieselbe ungeordnete Darstellung und liefern denselben Wert \(\min(|x|,|y|)\).
Der Code beseitigt diese Symmetrie, indem die erste enthaltene Primzahl \(p_k\) in der äußeren Schleife gewählt und ihr Faktor fest auf \(z_{p_k}\) gesetzt wird. Erst alle späteren Primzahlen verzweigen zwischen \(z_p\) und \(\overline{z_p}\). So bleibt aus jedem global konjugierten Paar genau ein Vertreter übrig.
Mit \(z_5=1+2i\) und \(z_{13}=3+2i\) entstehen aus den beiden Konjugationsmöglichkeiten für die zweite Primzahl die beiden relevanten Darstellungen:
$$\left(1+2i\right)\left(3+2i\right)=-1+8i \quad\Longrightarrow\quad 65=1^2+8^2,$$
$$\left(1+2i\right)\left(3-2i\right)=7+4i \quad\Longrightarrow\quad 65=7^2+4^2.$$
Der Gesamtbeitrag von \(65\) ist also
$$\min(1,8)+\min(7,4)=1+4=5.$$
Damit erhält man sofort einen Kontrollpunkt für die ersten zwei Primzahlen:
$$5\mapsto1,\qquad 13\mapsto2,\qquad 65\mapsto5,\qquad \text{Summe}=8.$$
Beschränkt man den Code auf \(\{5,13,17\}\), erhält man \(80\); für die ersten vier Primzahlen erhält man \(906\).
Repräsentationstabelle. build_representations() durchsucht ungerade \(i\) und gerade
\(j\) und speichert bei \(i^2+j^2<150\) den gaußschen Wert \(i+ji\). Für die 16 Zielprimzahlen entsteht so genau
eine kanonische Darstellung.
Rekursive Enumeration. dfs(idx, value) verarbeitet die restlichen Primzahlen in
steigender Reihenfolge. Die drei rekursiven Aufrufe entsprechen: auslassen, mit \(z_p\) multiplizieren, mit
\(\overline{z_p}\) multiplizieren.
Blattbeitrag. Wenn alle Primzahlen verarbeitet sind, kodiert value = x + iy eine
gültige Darstellung eines quadratfreien Produkts. Zurückgegeben wird min(abs(x), abs(y)).
Kanonischer Start. solve() iteriert über die erste gewählte Primzahl und startet die DFS
mit reps[p]. Genau dadurch verschwindet die globale Konjugations-Doppelzählung.
Mit \(k=16\) zulässigen Primzahlen hat die direkte Suche die Größe
$$\sum_{m=0}^{k-1}3^m=\frac{3^k-1}{2}=O(3^k).$$
Das klingt theoretisch groß, ist hier aber praktikabel, weil \(k\) klein ist und jeder Zustand nur eine kleine gaußsche Ganzzahlmultiplikation auf 64-Bit-Werten ausführt. Die Rekursionstiefe ist \(O(k)\), also ist auch der Speicherbedarf \(O(k)\).
$$P=\{5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149\}$$
kümesi, \(150\)'den küçük ve \(p\equiv1\pmod4\) koşulunu sağlayan tüm asalları içerir. Problem, bu kümeden seçilen farklı asalların her boş olmayan karesiz çarpımı için
$$n=a^2+b^2$$
temsillerini inceler ve her temsilde küçük bileşeni toplar. Burada amaç nihai sayıyı vermek değil, kodun neden tüm geçerli temsilleri eksiksiz ve tekrar saymadan üretebildiğini açıklamaktır.
Tüm çözüm Gauss tamsayıları \(\mathbb Z[i]\) üzerinde kuruludur. Burada norm
$$N(x+iy)=x^2+y^2$$
çarpımsaldır.
Fermat'ın iki kare teoremine göre \(p\equiv1\pmod4\) olan her asal için
$$p=u_p^2+v_p^2$$
yazabiliriz. Bu, \(\mathbb Z[i]\) içinde
$$p=(u_p+iv_p)(u_p-iv_p)=z_p\overline{z_p}$$
çarpanlaşması demektir. Kod her asal için tek bir kanonik \(z_p\) saklar.
build_representations() fonksiyonu tek \(u\) ve çift \(v\) arayarak bunu bulur. Örneğin
$$5=1^2+2^2,\qquad 13=3^2+2^2,\qquad 17=1^2+4^2.$$
Dolayısıyla depolanan Gauss çarpanları \(z_5=1+2i\), \(z_{13}=3+2i\), \(z_{17}=1+4i\) olur.
\(z=a+bi\) ve \(w=c+di\) ise
$$zw=(ac-bd)+i(ad+bc),$$
dolayısıyla
$$N(zw)=N(z)N(w).$$
Bunu sıradan tamsayı diliyle açarsak klasik özdeşliği elde ederiz:
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac-bd)^2+(ad+bc)^2.$$
Bir çarpanı eşlenik alırsak ikinci standart biçim gelir:
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac+bd)^2+(ad-bc)^2.$$
DFS'nin her adımında yaptığı şey tam olarak bu iki kare toplamı bileşimini \(\mathbb Z[i]\) içinde uygulamaktır.
Boş olmayan bir \(S\subseteq P\) altkümesi alalım ve
$$n=\prod_{p\in S} p$$
olsun. Her böyle asal \(p=z_p\overline{z_p}\) biçiminde ayrıldığı için, \(n\)'in \(\mathbb Z[i]\) içindeki bir çarpanlaşması her çiftten tam bir çarpan seçilerek yazılır:
$$Z=\prod_{p\in S}\eta_p,\qquad \eta_p\in\{z_p,\overline{z_p}\}.$$
O zaman \(N(Z)=n\) olur. Eğer \(Z=x+iy\) ise hemen
$$n=x^2+y^2$$
elde edilir. Ters yönde de, böyle bir squarefree çarpımın her iki-kare temsili işaret ve yer değiştirme simetrileri dışında tam olarak bu seçimlerden birine karşılık gelir.
O anki Gauss çarpımı \(Z\) sabitken, sıradaki asal \(p\) için yalnızca üç anlamlı seçenek vardır:
1. \(p\)'yi hiç kullanmamak;
2. \(z_p\) ile çarpmak;
3. \(\overline{z_p}\) ile çarpmak.
Bu yüzden özyineleme tam olarak
$$\text{dfs}(idx,Z)=\text{dfs}(idx+1,Z)+\text{dfs}(idx+1,Zz_p)+\text{dfs}(idx+1,Z\overline{z_p})$$
biçimindedir. Yaprakta oluşan \(Z=x+iy\) bir tam temsildir ve katkı
$$\min(|x|,|y|)$$
olarak eklenir.
Eğer DFS'yi \(1\)'den başlatıp her seçilen asal için hem \(z_p\) hem \(\overline{z_p}\) seçimine izin verseydik, her boş olmayan altküme iki kez sayılırdı. Sebep global eşleniktir:
$$Z=\prod_{p\in S}\eta_p \qquad \Longrightarrow \qquad \overline{Z}=\prod_{p\in S}\overline{\eta_p}.$$
Fakat \(Z=x+iy\) ile \(\overline{Z}=x-iy\) aynı sırasız \((|x|,|y|)\) çiftini verir; yani aynı \(\min(|x|,|y|)\) katkısını üretir.
Kod bu simetriyi şu şekilde kırar: dış döngü ilk dahil edilen asalı \(p_k\) seçer ve başlangıcı zorunlu olarak \(z_{p_k}\) yapar; \(\overline{z_{p_k}}\) seçeneği yoktur. Sadece daha büyük indisli asallar \(z_p\) ile \(\overline{z_p}\) arasında dallanır. Böylece her global eşlenik çiftinden yalnızca bir temsilci kalır.
\(z_5=1+2i\) ve \(z_{13}=3+2i\) alalım. İkinci asal için iki eşlenik seçimi iki ilgili temsili üretir:
$$\left(1+2i\right)\left(3+2i\right)=-1+8i \quad\Longrightarrow\quad 65=1^2+8^2,$$
$$\left(1+2i\right)\left(3-2i\right)=7+4i \quad\Longrightarrow\quad 65=7^2+4^2.$$
Dolayısıyla \(65\)'in toplam katkısı
$$\min(1,8)+\min(7,4)=1+4=5$$
olur. Buradan ilk iki asal için temiz bir kontrol noktası da çıkar:
$$5\mapsto1,\qquad 13\mapsto2,\qquad 65\mapsto5,\qquad \text{toplam}=8.$$
Kod yalnızca ilk üç asala \(\{5,13,17\}\) kısıtlanırsa \(80\), ilk dört asala kısıtlanırsa \(906\) üretir.
Temsil tablosu. build_representations() tek \(i\) ve çift \(j\) değerlerini tarar;
\(i^2+j^2<150\) olduğunda \(i+ji\) Gauss tamsayısını saklar. Hedefteki 16 asal için bu, asal başına tam bir
kanonik temsil verir.
Özyinelemeli tarama. dfs(idx, value) kalan asalları artan sırayla işler. Üç çağrı sırasıyla
atla, \(z_p\) ile çarp, \(\overline{z_p}\) ile çarp anlamına gelir.
Yaprak katkısı. Tüm asallar işlendiğinde value = x + iy, karesiz bir çarpımın geçerli
bir temsilini kodlar. Fonksiyon min(abs(x), abs(y)) döndürür.
Kanonik başlangıç. solve() ilk seçilen asalın konumunu dolaşır ve DFS'yi
reps[p] ile başlatır. Global eşlenik tekrarını kaldıran mekanizma tam olarak budur.
\(k=16\) uygun asal için doğrudan aramanın büyüklüğü
$$\sum_{m=0}^{k-1}3^m=\frac{3^k-1}{2}=O(3^k)$$
olur. Bu ifade teoride büyük görünse de burada \(k\) küçüktür ve her durumda yalnızca 64 bit tamsayılar üzerinde küçük bir Gauss çarpımı yapılır. Özyineleme derinliği \(O(k)\), bellek kullanımı da \(O(k)\)'dir.
Sea
$$P=\{5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149\}$$
el conjunto de los primos menores que \(150\) con \(p\equiv1\pmod4\). Para cada producto cuadrado libre y no vacío de primos distintos de \(P\), el problema considera todas las representaciones
$$n=a^2+b^2$$
y suma la componente menor de cada una. Aquí no nos interesa mostrar el valor final, sino explicar por qué el código enumera todas las representaciones válidas sin duplicarlas.
La solución entera vive en los enteros gaussianos \(\mathbb Z[i]\), donde la norma
$$N(x+iy)=x^2+y^2$$
es multiplicativa.
Por el teorema de Fermat sobre suma de dos cuadrados, todo primo \(p\equiv1\pmod4\) admite una descomposición
$$p=u_p^2+v_p^2.$$
En \(\mathbb Z[i]\) esto equivale a
$$p=(u_p+iv_p)(u_p-iv_p)=z_p\overline{z_p}.$$
El código guarda un único factor canónico \(z_p\) para cada primo. La rutina
build_representations() busca \(u\) impar y \(v\) par. Ejemplos:
$$5=1^2+2^2,\qquad 13=3^2+2^2,\qquad 17=1^2+4^2.$$
Así, \(z_5=1+2i\), \(z_{13}=3+2i\) y \(z_{17}=1+4i\).
Si \(z=a+bi\) y \(w=c+di\), entonces
$$zw=(ac-bd)+i(ad+bc),$$
y por tanto
$$N(zw)=N(z)N(w).$$
Escrito con enteros ordinarios, esto da
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac-bd)^2+(ad+bc)^2.$$
Si conjugamos uno de los factores aparece la segunda forma clásica:
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac+bd)^2+(ad-bc)^2.$$
Ese es exactamente el mecanismo algebraico que usa la DFS para combinar representaciones.
Sea \(S\subseteq P\) no vacío y
$$n=\prod_{p\in S} p.$$
Como cada primo se descompone como \(p=z_p\overline{z_p}\), una factorización de \(n\) en \(\mathbb Z[i]\) se obtiene escogiendo exactamente un factor de cada pareja:
$$Z=\prod_{p\in S}\eta_p,\qquad \eta_p\in\{z_p,\overline{z_p}\}.$$
Entonces \(N(Z)=n\). Si \(Z=x+iy\), obtenemos
$$n=x^2+y^2.$$
Recíprocamente, para un producto cuadrado libre de estos primos, toda representación aparece de esta forma, salvo las simetrías triviales de signos y del intercambio de coordenadas.
Fijado un producto gaussiano actual \(Z\), para el siguiente primo \(p\) solo hay tres posibilidades útiles:
1. omitir \(p\);
2. multiplicar por \(z_p\);
3. multiplicar por \(\overline{z_p}\).
Por eso la recurrencia es
$$\text{dfs}(idx,Z)=\text{dfs}(idx+1,Z)+\text{dfs}(idx+1,Zz_p)+\text{dfs}(idx+1,Z\overline{z_p}).$$
En una hoja, \(Z=x+iy\) ya codifica una representación completa y la contribución es
$$\min(|x|,|y|).$$
Si empezáramos la DFS desde \(1\) permitiendo para cada primo escogido tanto \(z_p\) como \(\overline{z_p}\), cada subconjunto no vacío se contaría dos veces. La razón es la conjugación global:
$$Z=\prod_{p\in S}\eta_p \qquad \Longrightarrow \qquad \overline{Z}=\prod_{p\in S}\overline{\eta_p}.$$
Pero \(Z=x+iy\) y \(\overline{Z}=x-iy\) representan el mismo par no ordenado \((|x|,|y|)\), y por tanto la misma contribución \(\min(|x|,|y|)\).
La implementación rompe esa simetría eligiendo en el bucle exterior el primer primo incluido \(p_k\) y obligando a tomar \(z_{p_k}\), no su conjugado. Solo los primos posteriores ramifican entre \(z_p\) y \(\overline{z_p}\). Así, cada pareja global de conjugados queda representada una sola vez.
Tomemos \(z_5=1+2i\) y \(z_{13}=3+2i\). Las dos elecciones conjugadas para el segundo primo producen:
$$\left(1+2i\right)\left(3+2i\right)=-1+8i \quad\Longrightarrow\quad 65=1^2+8^2,$$
$$\left(1+2i\right)\left(3-2i\right)=7+4i \quad\Longrightarrow\quad 65=7^2+4^2.$$
Por tanto, la contribución total de \(65\) es
$$\min(1,8)+\min(7,4)=1+4=5.$$
Esto da un buen punto de control para los dos primeros primos:
$$5\mapsto1,\qquad 13\mapsto2,\qquad 65\mapsto5,\qquad \text{total}=8.$$
Si se restringe el código a \(\{5,13,17\}\), el total es \(80\); con los cuatro primeros primos, el total es \(906\).
Tabla de representaciones. build_representations() recorre \(i\) impar y \(j\) par; si
\(i^2+j^2<150\), guarda el entero gaussiano \(i+ji\). Para los 16 primos objetivo eso produce exactamente una
representación canónica por primo.
Enumeración recursiva. dfs(idx, value) procesa los primos restantes en orden creciente.
Sus tres llamadas recursivas significan omitir, multiplicar por \(z_p\) o multiplicar por \(\overline{z_p}\).
Contribución en la hoja. Cuando ya se procesaron todos los primos, value = x + iy
codifica una representación válida y la función devuelve min(abs(x), abs(y)).
Inicio canónico. solve() itera sobre la posición del primer primo elegido y arranca la
DFS con reps[p]. Ese es exactamente el truco que elimina el duplicado por conjugación global.
Si \(k=16\) es el número de primos válidos, el tamaño de la búsqueda directa es
$$\sum_{m=0}^{k-1}3^m=\frac{3^k-1}{2}=O(3^k).$$
En teoría parece grande, pero aquí \(k\) es muy pequeño y cada estado solo hace una multiplicación gaussiana sencilla sobre enteros de 64 bits. La profundidad recursiva es \(O(k)\), y la memoria también es \(O(k)\).
设
$$P=\{5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149\}$$
为所有小于 \(150\) 且满足 \(p\equiv1\pmod4\) 的素数。对任意由这些素数中若干个不同元素组成的非空平方自由乘积， 题目考察它的所有表示
$$n=a^2+b^2$$
并把每个表示中的较小分量加起来。这里不强调最终数值，而是解释代码为什么能完整枚举所有表示且不重复计数。
整个解法建立在高斯整数 \(\mathbb Z[i]\) 上，其中范数
$$N(x+iy)=x^2+y^2$$
具有乘法性。
根据费马两平方和定理，任何满足 \(p\equiv1\pmod4\) 的素数都可写成
$$p=u_p^2+v_p^2.$$
在 \(\mathbb Z[i]\) 中，这等价于
$$p=(u_p+iv_p)(u_p-iv_p)=z_p\overline{z_p}.$$
代码为每个素数保存一个规范的 \(z_p\)。build_representations() 通过枚举奇数 \(u\) 和偶数
\(v\) 来找到它。比如
$$5=1^2+2^2,\qquad 13=3^2+2^2,\qquad 17=1^2+4^2.$$
因此有 \(z_5=1+2i\)、\(z_{13}=3+2i\)、\(z_{17}=1+4i\)。
若 \(z=a+bi\)、\(w=c+di\)，则
$$zw=(ac-bd)+i(ad+bc),$$
因此
$$N(zw)=N(z)N(w).$$
把它写回普通整数，就得到经典恒等式
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac-bd)^2+(ad+bc)^2.$$
如果把一个因子换成共轭，还会得到第二种标准形式
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac+bd)^2+(ad-bc)^2.$$
DFS 每次做的事情，本质上就是在 \(\mathbb Z[i]\) 里反复应用这条合成规律。
取任意非空子集 \(S\subseteq P\)，定义
$$n=\prod_{p\in S} p.$$
因为每个这样的素数都分解为 \(p=z_p\overline{z_p}\)，所以 \(n\) 在 \(\mathbb Z[i]\) 中的一个因式分解可写成
$$Z=\prod_{p\in S}\eta_p,\qquad \eta_p\in\{z_p,\overline{z_p}\}.$$
于是 \(N(Z)=n\)。若 \(Z=x+iy\)，就得到
$$n=x^2+y^2.$$
反过来，对这种平方自由乘积而言，除去符号和交换坐标的平凡对称性后，每个表示都来自上述某种共轭选择。
当前高斯乘积为 \(Z\) 时，对于下一个素数 \(p\)，只有三种有意义的操作：
1. 跳过 \(p\)；
2. 乘上 \(z_p\)；
3. 乘上 \(\overline{z_p}\)。
所以递推正是
$$\text{dfs}(idx,Z)=\text{dfs}(idx+1,Z)+\text{dfs}(idx+1,Zz_p)+\text{dfs}(idx+1,Z\overline{z_p}).$$
到叶子时，\(Z=x+iy\) 已经对应一个完整表示，贡献就是
$$\min(|x|,|y|).$$
如果从 \(1\) 开始做 DFS，并允许每个被选中的素数自由选择 \(z_p\) 或 \(\overline{z_p}\)，那么每个非空子集都会被计算两次。 原因是整体共轭：
$$Z=\prod_{p\in S}\eta_p \qquad \Longrightarrow \qquad \overline{Z}=\prod_{p\in S}\overline{\eta_p}.$$
但 \(Z=x+iy\) 与 \(\overline{Z}=x-iy\) 给出的是同一个无序对 \((|x|,|y|)\)，因此贡献完全相同。
实现方式是：外层循环先选定第一个被包含的素数 \(p_k\)，并强制使用 \(z_{p_k}\) 而不是其共轭；只有更靠后的素数才在 \(z_p\) 与 \(\overline{z_p}\) 之间分支。这样就恰好去掉了整体共轭造成的重复。
取 \(z_5=1+2i\)、\(z_{13}=3+2i\)。第二个素数的两种共轭选择产生两种相关表示：
$$\left(1+2i\right)\left(3+2i\right)=-1+8i \quad\Longrightarrow\quad 65=1^2+8^2,$$
$$\left(1+2i\right)\left(3-2i\right)=7+4i \quad\Longrightarrow\quad 65=7^2+4^2.$$
因此 \(65\) 的总贡献为
$$\min(1,8)+\min(7,4)=1+4=5.$$
这还给出一个清晰的检查点：
$$5\mapsto1,\qquad 13\mapsto2,\qquad 65\mapsto5,\qquad \text{总计}=8.$$
如果只保留前三个素数 \(\{5,13,17\}\)，代码输出 \(80\)；保留前四个素数时输出 \(906\)。
表示表。 build_representations() 枚举奇数 \(i\) 与偶数 \(j\)，当
\(i^2+j^2<150\) 时保存高斯整数 \(i+ji\)。对目标中的 16 个素数，这恰好得到每个素数一个规范表示。
递归枚举。 dfs(idx, value) 按升序处理剩余素数。三次递归调用分别对应跳过、
乘 \(z_p\)、乘 \(\overline{z_p}\)。
叶子贡献。 所有素数处理完后，value = x + iy 就编码了一个有效表示，函数返回
min(abs(x), abs(y))。
规范起点。 solve() 枚举“第一个被选中的素数”的位置，并以
reps[p] 作为 DFS 起点。这正是去掉整体共轭重复的关键。
设可用素数个数为 \(k=16\)，则直接搜索规模为
$$\sum_{m=0}^{k-1}3^m=\frac{3^k-1}{2}=O(3^k).$$
理论上这是指数级，但在本题中 \(k\) 很小，而且每个状态只做一次很轻量的 64 位高斯整数乘法。递归深度为 \(O(k)\)，内存使用也是 \(O(k)\)。
Пусть
$$P=\{5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149\}$$
это все простые числа меньше \(150\), удовлетворяющие \(p\equiv1\pmod4\). Для каждого непустого squarefree-произведения различных простых из \(P\) задача рассматривает все представления
$$n=a^2+b^2$$
и суммирует меньшую компоненту в каждом представлении. Здесь важен не сам итоговый ответ, а объяснение того, почему код перечисляет все представления полно и без двойного счёта.
Всё решение работает в кольце гауссовых целых \(\mathbb Z[i]\), где норма
$$N(x+iy)=x^2+y^2$$
мультипликативна.
По теореме Ферма о сумме двух квадратов каждый простой \(p\equiv1\pmod4\) имеет вид
$$p=u_p^2+v_p^2.$$
В \(\mathbb Z[i]\) это означает факторизацию
$$p=(u_p+iv_p)(u_p-iv_p)=z_p\overline{z_p}.$$
Код сохраняет по одному каноническому фактору \(z_p\) для каждого простого. Функция
build_representations() перебирает нечётные \(u\) и чётные \(v\), чего здесь достаточно. Например,
$$5=1^2+2^2,\qquad 13=3^2+2^2,\qquad 17=1^2+4^2.$$
Отсюда \(z_5=1+2i\), \(z_{13}=3+2i\), \(z_{17}=1+4i\).
Если \(z=a+bi\) и \(w=c+di\), то
$$zw=(ac-bd)+i(ad+bc),$$
следовательно,
$$N(zw)=N(z)N(w).$$
В обычных целых это даёт тождество
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac-bd)^2+(ad+bc)^2.$$
Если заменить один множитель на сопряжённый, получается вторая стандартная форма:
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac+bd)^2+(ad-bc)^2.$$
Именно так DFS комбинирует представления при каждом умножении.
Возьмём непустое \(S\subseteq P\) и положим
$$n=\prod_{p\in S} p.$$
Поскольку каждый такой простой раскладывается как \(p=z_p\overline{z_p}\), факторизация \(n\) в \(\mathbb Z[i]\) получается выбором ровно одного множителя из каждой пары:
$$Z=\prod_{p\in S}\eta_p,\qquad \eta_p\in\{z_p,\overline{z_p}\}.$$
Тогда \(N(Z)=n\). Если \(Z=x+iy\), то сразу получаем
$$n=x^2+y^2.$$
И наоборот, для такого squarefree-произведения любое представление возникает из некоторого такого выбора, с точностью до обычных симметрий знаков и перестановки координат.
Если текущий гауссов множитель уже равен \(Z\), то для следующего простого \(p\) есть только три содержательных варианта:
1. пропустить \(p\);
2. умножить на \(z_p\);
3. умножить на \(\overline{z_p}\).
Поэтому рекурсия имеет вид
$$\text{dfs}(idx,Z)=\text{dfs}(idx+1,Z)+\text{dfs}(idx+1,Zz_p)+\text{dfs}(idx+1,Z\overline{z_p}).$$
В листе \(Z=x+iy\) уже кодирует одно полное представление, и вклад равен
$$\min(|x|,|y|).$$
Если бы мы запускали DFS из \(1\) и для каждого выбранного простого разрешали как \(z_p\), так и \(\overline{z_p}\), то каждое непустое подмножество считалось бы дважды. Причина в глобальном сопряжении:
$$Z=\prod_{p\in S}\eta_p \qquad \Longrightarrow \qquad \overline{Z}=\prod_{p\in S}\overline{\eta_p}.$$
Но \(Z=x+iy\) и \(\overline{Z}=x-iy\) задают ту же неупорядоченную пару \((|x|,|y|)\), а значит, тот же вклад \(\min(|x|,|y|)\).
Код снимает эту симметрию так: внешний цикл выбирает первый включённый простой \(p_k\) и принудительно берёт фактор \(z_{p_k}\), а не его сопряжение. Только простые с большим индексом ветвятся между \(z_p\) и \(\overline{z_p}\). Поэтому из каждой глобально сопряжённой пары остаётся ровно один представитель.
Возьмём \(z_5=1+2i\) и \(z_{13}=3+2i\). Два выбора для второго простого дают два нужных представления:
$$\left(1+2i\right)\left(3+2i\right)=-1+8i \quad\Longrightarrow\quad 65=1^2+8^2,$$
$$\left(1+2i\right)\left(3-2i\right)=7+4i \quad\Longrightarrow\quad 65=7^2+4^2.$$
Значит, полный вклад числа \(65\) равен
$$\min(1,8)+\min(7,4)=1+4=5.$$
Отсюда получается удобная контрольная точка для первых двух простых:
$$5\mapsto1,\qquad 13\mapsto2,\qquad 65\mapsto5,\qquad \text{итого}=8.$$
Если ограничить код множеством \(\{5,13,17\}\), получится \(80\); для первых четырёх простых получится \(906\).
Таблица представлений. build_representations() перебирает нечётные \(i\) и чётные
\(j\); если \(i^2+j^2<150\), сохраняется гауссово число \(i+ji\). Для нужных 16 простых это даёт ровно одно
каноническое представление на простой.
Рекурсивный перебор. dfs(idx, value) обрабатывает оставшиеся простые по возрастанию.
Три рекурсивных вызова означают пропуск, умножение на \(z_p\) и умножение на \(\overline{z_p}\).
Вклад листа. Когда все простые рассмотрены, value = x + iy кодирует допустимое
представление squarefree-произведения, и функция возвращает min(abs(x), abs(y)).
Канонический старт. solve() перебирает позицию первого выбранного простого и запускает
DFS с reps[p]. Именно это убирает дубликат, возникающий из глобального сопряжения.
Если число подходящих простых равно \(k=16\), то размер прямого перебора равен
$$\sum_{m=0}^{k-1}3^m=\frac{3^k-1}{2}=O(3^k).$$
Теоретически это экспонента, но в данной задаче \(k\) мало, а в каждом состоянии выполняется только одно небольшое умножение гауссовых целых на 64-битных числах. Глубина рекурсии равна \(O(k)\), память тоже \(O(k)\).
لتكن
$$P=\{5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149\}$$
مجموعة جميع الأوليات الأصغر من \(150\) والتي تحقق \(p\equiv1\pmod4\). لكل حاصل ضرب squarefree غير فارغ من أوليات مختلفة من \(P\)، تدرس المسألة جميع التمثيلات
$$n=a^2+b^2$$
ثم تجمع المركبة الأصغر في كل تمثيل. المهم هنا ليس عرض الناتج النهائي، بل شرح سبب قدرة الشيفرة على تعداد جميع التمثيلات الصحيحة من دون تكرار.
الحل كله يعمل داخل الأعداد الغاوسية \(\mathbb Z[i]\)، حيث تكون القيمة المعيارية
$$N(x+iy)=x^2+y^2$$
ضربية.
وفق مبرهنة فيرما لمجموع مربعين، كل أولي يحقق \(p\equiv1\pmod4\) يمكن كتابته على الصورة
$$p=u_p^2+v_p^2.$$
وفي \(\mathbb Z[i]\) يعادل ذلك التحليل
$$p=(u_p+iv_p)(u_p-iv_p)=z_p\overline{z_p}.$$
تخزن الشيفرة عاملاً قانونياً واحداً \(z_p\) لكل أولي. والدالة build_representations() تبحث في \(u\)
الفردية و\(v\) الزوجية. مثلاً:
$$5=1^2+2^2,\qquad 13=3^2+2^2,\qquad 17=1^2+4^2.$$
إذن العوامل المخزنة هي \(z_5=1+2i\)، و\(z_{13}=3+2i\)، و\(z_{17}=1+4i\).
إذا كان \(z=a+bi\) و\(w=c+di\)، فإن
$$zw=(ac-bd)+i(ad+bc),$$
ومن ثم
$$N(zw)=N(z)N(w).$$
وبصياغة صحيحة عادية نحصل على الهوية الكلاسيكية
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac-bd)^2+(ad+bc)^2.$$
وإذا أخذنا مرافق أحد العاملين نحصل على الصورة القياسية الثانية:
$$\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac+bd)^2+(ad-bc)^2.$$
وهذا هو بالضبط الأساس الجبري الذي تستعمله DFS عند تركيب التمثيلات.
خذ مجموعة غير فارغة \(S\subseteq P\) وعرّف
$$n=\prod_{p\in S} p.$$
بما أن كل أولي من هذا النوع يتحلل كـ \(p=z_p\overline{z_p}\)، فإن تحليلاً لـ \(n\) داخل \(\mathbb Z[i]\) يُبنى باختيار عامل واحد من كل زوج:
$$Z=\prod_{p\in S}\eta_p,\qquad \eta_p\in\{z_p,\overline{z_p}\}.$$
وعندها \(N(Z)=n\). فإذا كان \(Z=x+iy\)، نحصل فوراً على
$$n=x^2+y^2.$$
وبالعكس، لأي حاصل ضرب squarefree من هذه الأوليات، فإن كل تمثيل ينشأ من مثل هذا الاختيار، مع إهمال تناظرات الإشارات وتبديل الإحداثيين.
إذا كان حاصل الضرب الغاوسي الحالي هو \(Z\)، فبالنسبة إلى الأولي التالي \(p\) لا توجد إلا ثلاث إمكانات ذات معنى:
1. تجاهل \(p\)؛
2. الضرب في \(z_p\)؛
3. الضرب في \(\overline{z_p}\).
ولهذا تكون العودية
$$\text{dfs}(idx,Z)=\text{dfs}(idx+1,Z)+\text{dfs}(idx+1,Zz_p)+\text{dfs}(idx+1,Z\overline{z_p}).$$
وفي الورقة النهائية يكون \(Z=x+iy\) قد مثّل تمثيلاً كاملاً، فتكون المساهمة
$$\min(|x|,|y|).$$
لو بدأنا DFS من \(1\) وسمحنا لكل أولي مختار بأن يأخذ \(z_p\) أو \(\overline{z_p}\)، لتم عدّ كل مجموعة غير فارغة مرتين. السبب هو المرافق العام:
$$Z=\prod_{p\in S}\eta_p \qquad \Longrightarrow \qquad \overline{Z}=\prod_{p\in S}\overline{\eta_p}.$$
لكن \(Z=x+iy\) و\(\overline{Z}=x-iy\) يعطيان نفس الزوج غير المرتب \((|x|,|y|)\)، وبالتالي نفس القيمة \(\min(|x|,|y|)\).
تزيل الشيفرة هذا التماثل بأن تختار في الحلقة الخارجية أول أولي مدرج \(p_k\) وتفرض العامل \(z_{p_k}\) فقط، لا مرافقه. أما الأوليات اللاحقة وحدها فهي التي تتفرع بين \(z_p\) و\(\overline{z_p}\). وبهذا يبقى ممثل واحد فقط من كل زوج مترافق كلياً.
لنأخذ \(z_5=1+2i\) و\(z_{13}=3+2i\). الاختياران الممكنان للمرافق في الأولي الثاني يعطيان التمثيلين التاليين:
$$\left(1+2i\right)\left(3+2i\right)=-1+8i \quad\Longrightarrow\quad 65=1^2+8^2,$$
$$\left(1+2i\right)\left(3-2i\right)=7+4i \quad\Longrightarrow\quad 65=7^2+4^2.$$
إذن المساهمة الكلية للعدد \(65\) هي
$$\min(1,8)+\min(7,4)=1+4=5.$$
ومن هنا نحصل على نقطة تحقق نظيفة لأول أوليين:
$$5\mapsto1,\qquad 13\mapsto2,\qquad 65\mapsto5,\qquad \text{المجموع}=8.$$
وإذا قُصرت الشيفرة على \(\{5,13,17\}\) فالناتج \(80\)، وإذا قُصرت على أول أربعة أوليات فالناتج \(906\).
جدول التمثيلات. تقوم build_representations() بمسح \(i\) الفردية و\(j\) الزوجية؛ وإذا
كان \(i^2+j^2<150\) فإنها تخزن العدد الغاوسي \(i+ji\). بالنسبة إلى الأوليات الستة عشر المستهدفة يعطي هذا تمثيلاً
قانونياً واحداً لكل أولي.
التعداد التكراري. تقوم dfs(idx, value) بمعالجة الأوليات المتبقية بترتيب تصاعدي.
الاستدعاءات الثلاثة تعني: تجاهل، أو اضرب في \(z_p\)، أو اضرب في \(\overline{z_p}\).
مساهمة الورقة. بعد معالجة جميع الأوليات يصبح value = x + iy ممثلاً صالحاً، وتعيد
الدالة min(abs(x), abs(y)).
البداية القانونية. تقوم solve() بالمرور على موضع أول أولي مختار وتبدأ DFS من
reps[p]. وهذا هو تماماً ما يزيل التكرار الناتج عن المرافق العام.
إذا كان عدد الأوليات المناسبة \(k=16\)، فإن حجم البحث المباشر هو
$$\sum_{m=0}^{k-1}3^m=\frac{3^k-1}{2}=O(3^k).$$
قد يبدو ذلك أسياً نظرياً، لكنه عملي هنا لأن \(k\) صغير جداً، وكل حالة تنفذ فقط ضرباً غاوسياً صغيراً على أعداد 64-بت. عمق الاستدعاء \(O(k)\)، واستهلاك الذاكرة كذلك \(O(k)\).