In a hexagonal orchard of order \(n\), every tree lies in one of six congruent triangular sectors around the center. A tree is hidden if another tree lies on the same ray from the center and is closer to the origin. The solution does not compare every pair of trees. Instead it turns visibility into a coprimality condition and then reduces the whole problem to evaluating the summatory Euler totient function.
Because the orchard has sixfold rotational symmetry, it is enough to count hidden trees in one \(60^\circ\) sector and multiply by 6 at the end. In one sector, row \(r\) contains exactly \(r\) trees for \(r=1,2,\dots,n\). Therefore the total number of trees in one sector is the triangular number
$$T(n)=\sum_{r=1}^{n} r=\frac{n(n+1)}{2}.$$
The center itself is only the observation point, so it is not included in this count.
Index the trees on row \(r\) by positions \(x=1,2,\dots,r\). In the lattice underlying one hexagonal sector, the tree \((x,r)\) lies on the same ray as \((x/d,r/d)\) whenever \(d\) divides both \(x\) and \(r\). Hence
$$\text{tree }(x,r)\text{ is visible from the center} \iff \gcd(x,r)=1.$$
If \(\gcd(x,r)=d>1\), then \((x/d,r/d)\) is a nearer tree on the same line of sight, so \((x,r)\) is hidden. If \(\gcd(x,r)=1\), there is no intermediate orchard point on that ray. The number of visible trees on row \(r\) is therefore
$$\varphi(r)=\#\{1\le x\le r:\gcd(x,r)=1\},$$
which is Euler's totient function. The number of hidden trees on row \(r\) is then
$$r-\varphi(r).$$
Summing over all rows of one sector gives
$$H_{\mathrm{sector}}(n)=\sum_{r=1}^{n}\bigl(r-\varphi(r)\bigr)=\frac{n(n+1)}{2}-\sum_{r=1}^{n}\varphi(r).$$
Introduce the summatory totient function
$$\Phi(n)=\sum_{k=1}^{n}\varphi(k).$$
Then the hidden-tree count for the entire orchard is
$$\boxed{H(n)=6\,H_{\mathrm{sector}}(n)=6\left(\frac{n(n+1)}{2}-\Phi(n)\right).}$$
This closed form is exactly what the C++, Python, and Java programs evaluate.
The code does not build all totients up to \(n\) with a full sieve. Instead it uses the classical divisor identity
$$\sum_{d\mid m}\varphi(d)=m.$$
Summing this identity for \(m=1,2,\dots,n\) yields
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d\mid m}\varphi(d)=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Since \(\sum_{m=1}^{n} m=\frac{n(n+1)}{2}\), we obtain
$$\frac{n(n+1)}{2}=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Now rewrite the right-hand side by expanding each floor term as a count of prefixes:
$$\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{k=1}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Separating the \(k=1\) term gives the recurrence used in all three implementations:
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
The recurrence still appears to contain \(n-1\) terms, but many consecutive indices produce the same quotient
\(q=\left\lfloor n/k\right\rfloor\). If a block starts at left, its last index is
$$\text{right}=\left\lfloor\frac{n}{q}\right\rfloor.$$
So the entire block
$$k=\text{left},\text{left}+1,\dots,\text{right}$$
contributes
$$(\text{right}-\text{left}+1)\,\Phi(q).$$
This is exactly why the code keeps left, computes quotient = n / left, derives
right = n / quotient, subtracts one whole block, and then jumps directly to right + 1.
Memoization stores previously computed values of \(\Phi\), so each distinct recursive argument is evaluated only
once.
For the first five rows we have
$$\varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4,$$
so
$$\Phi(5)=1+1+2+2+4=10.$$
Also
$$T(5)=\frac{5\cdot 6}{2}=15,$$
hence
$$H_{\mathrm{sector}}(5)=15-10=5,\qquad H(5)=6\cdot 5=30.$$
This matches the checkpoint in the C++ file. The same source also checks \(H(10)=138\) and \(H(1000)=1177848\), plus a brute-force cross-check at order 200.
All three solution files implement the same formula. They initialize a memo table with \(\Phi(0)=0\) and \(\Phi(1)=1\), compute the summatory totient recursively, evaluate the triangular number \(\frac{n(n+1)}{2}\), subtract the visible count in one sector, and multiply the result by 6.
The C++ version encapsulates the recursion in a TotientSummatory class backed by
std::unordered_map and uses unsigned __int128 for intermediate arithmetic safety. The
Python version uses a nested function with a dictionary, and the Java version uses a static
HashMap<Long, Long>. The mathematical logic is identical in all three languages.
A naive method would examine every tree in every row and test visibility with repeated \(\gcd\) calls, which is quadratic in the orchard order. The implemented method avoids that completely. For a fixed argument \(m\), the floor-division grouping visits only the distinct quotients \(\left\lfloor m/k\right\rfloor\), and there are \(O(\sqrt{m})\) of them. If \(S\) is the set of distinct arguments reached by memoized recursion, then the total running time is
$$O\left(\sum_{m\in S}\sqrt{m}\right),$$
with memory usage \(O(|S|)\) for the memo table. In practice this is dramatically smaller than computing and storing every totient value up to \(10^8\).
In einem hexagonalen Obstgarten der Ordnung \(n\) liegt jeder Baum in einem von sechs kongruenten dreieckigen Sektoren um das Zentrum. Ein Baum ist verdeckt, wenn auf demselben Strahl vom Mittelpunkt ein anderer Baum näher am Ursprung liegt. Die Lösung vergleicht nicht alle Baumpaare direkt, sondern übersetzt Sichtbarkeit in eine Teilerfremdheitsbedingung und reduziert die Aufgabe anschließend auf die Summenfunktion der eulerschen Phi-Funktion.
Wegen der sechsfachen Rotationssymmetrie genügt es, die verdeckten Bäume in einem \(60^\circ\)-Sektor zu zählen und das Ergebnis am Ende mit 6 zu multiplizieren. In einem Sektor enthält Zeile \(r\) genau \(r\) Bäume für \(r=1,2,\dots,n\). Damit ist die Gesamtzahl der Bäume in einem Sektor die Dreieckszahl
$$T(n)=\sum_{r=1}^{n} r=\frac{n(n+1)}{2}.$$
Das Zentrum selbst wird nicht mitgezählt; es ist nur der Beobachtungspunkt.
Nummeriere die Bäume in Zeile \(r\) mit Positionen \(x=1,2,\dots,r\). Im schiefen Gitter eines hexagonalen Sektors liegt der Baum \((x,r)\) genau dann auf demselben Strahl wie \((x/d,r/d)\), wenn \(d\) sowohl \(x\) als auch \(r\) teilt. Daher gilt
$$\text{der Baum }(x,r)\text{ ist vom Zentrum sichtbar} \iff \gcd(x,r)=1.$$
Ist \(\gcd(x,r)=d>1\), dann liegt \((x/d,r/d)\) näher am Zentrum und blockiert die Sicht. Ist \(\gcd(x,r)=1\), gibt es keinen Zwischenpunkt auf diesem Strahl. Die Zahl der sichtbaren Bäume in Zeile \(r\) ist also
$$\varphi(r)=\#\{1\le x\le r:\gcd(x,r)=1\},$$
also die eulersche Phi-Funktion. Die Zahl der verdeckten Bäume in dieser Zeile ist damit
$$r-\varphi(r).$$
Für einen Sektor erhält man
$$H_{\mathrm{sector}}(n)=\sum_{r=1}^{n}\bigl(r-\varphi(r)\bigr)=\frac{n(n+1)}{2}-\sum_{r=1}^{n}\varphi(r).$$
Definiere nun die Summenfunktion
$$\Phi(n)=\sum_{k=1}^{n}\varphi(k).$$
Dann gilt für den gesamten Obstgarten
$$\boxed{H(n)=6\,H_{\mathrm{sector}}(n)=6\left(\frac{n(n+1)}{2}-\Phi(n)\right).}$$
Genau diese Formel werten die C++-, Python- und Java-Programme aus.
Der Code berechnet nicht alle Totienten bis \(n\) mit einem vollständigen Sieb. Stattdessen verwendet er die klassische Teileridentität
$$\sum_{d\mid m}\varphi(d)=m.$$
Summiert man diese Gleichung für \(m=1,2,\dots,n\), so folgt
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d\mid m}\varphi(d)=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Mit \(\sum_{m=1}^{n}m=\frac{n(n+1)}{2}\) ergibt sich
$$\frac{n(n+1)}{2}=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Nun schreibt man die rechte Seite als Summe über Präfixsummen um:
$$\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{k=1}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Trennt man den Term \(k=1\) ab, erhält man die im Code verwendete Rekursion:
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Die Rekursion scheint noch immer \(n-1\) Summanden zu besitzen, aber viele aufeinanderfolgende Indizes erzeugen
denselben Quotienten \(q=\left\lfloor n/k\right\rfloor\). Beginnt ein solcher Block bei left, dann
endet er bei
$$\text{right}=\left\lfloor\frac{n}{q}\right\rfloor.$$
Der gesamte Block
$$k=\text{left},\text{left}+1,\dots,\text{right}$$
liefert also den Beitrag
$$(\text{right}-\text{left}+1)\,\Phi(q).$$
Genau deshalb hält der Code einen linken Rand fest, berechnet quotient = n / left, bestimmt daraus
right = n / quotient, subtrahiert den kompletten Block und springt dann direkt zu
right + 1. Durch Memoisierung wird jeder unterschiedliche Rekursionswert nur einmal berechnet.
Für die ersten fünf Zeilen gilt
$$\varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4,$$
also
$$\Phi(5)=1+1+2+2+4=10.$$
Außerdem ist
$$T(5)=\frac{5\cdot 6}{2}=15,$$
und damit
$$H_{\mathrm{sector}}(5)=15-10=5,\qquad H(5)=6\cdot 5=30.$$
Das stimmt mit dem Prüfwert in der C++-Datei überein. Dieselbe Quelle testet außerdem \(H(10)=138\) und \(H(1000)=1177848\) sowie einen Brute-Force-Abgleich bei Ordnung 200.
Alle drei Lösungsdateien setzen dieselbe Formel um. Sie initialisieren eine Memo-Tabelle mit \(\Phi(0)=0\) und \(\Phi(1)=1\), berechnen die summierte Phi-Funktion rekursiv, bilden die Dreieckszahl \(\frac{n(n+1)}{2}\), ziehen die sichtbaren Punkte in einem Sektor ab und multiplizieren das Resultat mit 6.
Die C++-Version kapselt die Rekursion in einer TotientSummatory-Klasse mit
std::unordered_map und verwendet unsigned __int128 für sichere Zwischenwerte. Die
Python-Version nutzt eine geschachtelte Funktion mit Dictionary, die Java-Version eine statische
HashMap<Long, Long>. Die zugrunde liegende Mathematik ist in allen drei Sprachen identisch.
Ein naiver Ansatz würde jeden Baum in jeder Zeile betrachten und Sichtbarkeit mit vielen \(\gcd\)-Aufrufen prüfen; das ist quadratisch in der Gartenordnung. Die implementierte Methode vermeidet das vollständig. Für ein festes Argument \(m\) besucht die Blockzerlegung nur die verschiedenen Quotienten \(\left\lfloor m/k\right\rfloor\), und davon gibt es \(O(\sqrt{m})\). Ist \(S\) die Menge der durch Memoisierung erreichten Argumente, dann beträgt die Gesamtlaufzeit
$$O\left(\sum_{m\in S}\sqrt{m}\right),$$
und der Speicherverbrauch ist \(O(|S|)\) für die Memo-Tabelle. In der Praxis ist das erheblich kleiner als ein vollständiges Totient-Sieb bis \(10^8\).
Merkezi çevreleyen altı eş üçgensel bölgeden oluşan bir altıgen bahçede, bazı ağaçlar aynı doğrultuda daha yakın bir ağaç tarafından gizlenir. Buradaki amaç, düzenin derecesi \(n\) iken gizli kalan ağaçların sayısını bulmaktır. Çözüm tüm ağaç çiftlerini tek tek karşılaştırmaz; görünürlüğü aralarında asallık koşuluna çevirir ve problemi Euler phi fonksiyonunun kümülatif toplamına indirger.
Şekil altı kat dönel simetriye sahip olduğu için önce yalnızca bir \(60^\circ\) sektör sayılır, sonra sonuç 6 ile çarpılır. Tek bir sektörde \(r=1,2,\dots,n\) için \(r\). satırda tam olarak \(r\) ağaç vardır. Böylece bir sektördeki toplam ağaç sayısı üçgensel sayı olur:
$$T(n)=\sum_{r=1}^{n} r=\frac{n(n+1)}{2}.$$
Merkez bu toplamın içinde yer almaz; yalnızca bakış noktasıdır.
\(r\). satırdaki ağaçları \(x=1,2,\dots,r\) diye numaralandıralım. Altıgensel sektörün altında yatan eğik örgüde \((x,r)\) noktası, \(d\) hem \(x\)'i hem \(r\)'yi bölüyorsa \((x/d,r/d)\) ile aynı ışın üzerinde bulunur. Bu yüzden
$$\text{\((x,r)\) ağacı merkezden görünür} \iff \gcd(x,r)=1.$$
Eğer \(\gcd(x,r)=d>1\) ise \((x/d,r/d)\) aynı görüş doğrusu üzerinde daha yakın bir ağaçtır ve \((x,r)\) gizlidir. Eğer \(\gcd(x,r)=1\) ise arada başka bahçe noktası yoktur. Dolayısıyla \(r\). satırdaki görünür ağaç sayısı
$$\varphi(r)=\#\{1\le x\le r:\gcd(x,r)=1\}$$
olur. Bu da Euler phi fonksiyonudur. O halde o satırdaki gizli ağaç sayısı
$$r-\varphi(r).$$
Tek sektördeki gizli ağaç sayısı
$$H_{\mathrm{sector}}(n)=\sum_{r=1}^{n}\bigl(r-\varphi(r)\bigr)=\frac{n(n+1)}{2}-\sum_{r=1}^{n}\varphi(r).$$
Şimdi kümülatif phi toplamını
$$\Phi(n)=\sum_{k=1}^{n}\varphi(k)$$
diye tanımlarsak tüm bahçe için
$$\boxed{H(n)=6\,H_{\mathrm{sector}}(n)=6\left(\frac{n(n+1)}{2}-\Phi(n)\right).}$$
C++, Python ve Java dosyalarının doğrudan hesapladığı ifade tam olarak budur.
Kod, \(1\)'den \(n\)'ye kadar tüm phi değerlerini doğrusal bir elekle üretmez. Bunun yerine şu klasik özdeşliği kullanır:
$$\sum_{d\mid m}\varphi(d)=m.$$
Bu özdeşliği \(m=1,2,\dots,n\) için toplarsak
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d\mid m}\varphi(d)=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor$$
elde edilir. Sol taraf üçgensel toplam olduğundan
$$\frac{n(n+1)}{2}=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Sağ tarafı önek toplamları cinsinden yeniden yazarsak
$$\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{k=1}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$$
olur. \(k=1\) terimini ayırınca uygulamadaki özyineleme çıkar:
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Bu toplam ilk bakışta hâlâ uzun görünür, fakat birçok ardışık \(k\) aynı
\(q=\left\lfloor n/k\right\rfloor\) bölümünü üretir. Bir blok left konumunda başlıyorsa son indeksi
$$\text{right}=\left\lfloor\frac{n}{q}\right\rfloor$$
olur. Böylece
$$k=\text{left},\text{left}+1,\dots,\text{right}$$
bloğunun katkısı tek seferde
$$(\text{right}-\text{left}+1)\,\Phi(q)$$
şeklinde çıkarılır. Çözümlerde görülen left, quotient ve right değişkenleri
tam olarak bu bloklamayı uygular. Daha önce bulunan \(\Phi\) değerleri saklandığı için her farklı argüman yalnızca
bir kez hesaplanır.
İlk beş satır için
$$\varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4,$$
dolayısıyla
$$\Phi(5)=1+1+2+2+4=10.$$
Ayrıca
$$T(5)=\frac{5\cdot 6}{2}=15,$$
olduğu için
$$H_{\mathrm{sector}}(5)=15-10=5,\qquad H(5)=6\cdot 5=30.$$
Bu değer C++ kaynağındaki kontrol noktasıyla aynıdır. Aynı dosya ayrıca \(H(10)=138\), \(H(1000)=1177848\) ve mertebe 200 için kaba kuvvet doğrulaması yapar.
Üç çözüm dosyasının yapısı aynıdır. Önce \(\Phi(0)=0\) ve \(\Phi(1)=1\) başlangıç değerleriyle bir bellek tablosu kurulur. Ardından kümülatif phi fonksiyonu özyineli biçimde hesaplanır, üçgensel sayı \(\frac{n(n+1)}{2}\) bulunur, tek sektördeki görünür ağaç sayısı çıkarılır ve sonuç 6 ile çarpılır.
C++ sürümü bunu TotientSummatory sınıfı ve std::unordered_map ile uygular; ara
çarpımlarda güvenlik için unsigned __int128 kullanır. Python sürümü bir iç fonksiyon ve sözlük,
Java sürümü ise statik bir HashMap<Long, Long> kullanır. Matematiksel yöntem üçünde de aynıdır.
Naif yaklaşım, her satırdaki her ağacı inceleyip görünürlüğü tekrar tekrar \(\gcd\) ile test ederdi; bu da bahçe derecesine göre karesel büyür. Gerçek çözüm bunu tamamen atlar. Sabit bir \(m\) için bölme bloklaması yalnızca farklı \(\left\lfloor m/k\right\rfloor\) değerlerini ziyaret eder; bunların sayısı \(O(\sqrt{m})\)'dir. Memoization ile ulaşılan argüman kümesine \(S\) dersek toplam süre
$$O\left(\sum_{m\in S}\sqrt{m}\right)$$
olur. Bellek kullanımı memo tablosu için \(O(|S|)\)'dir. Pratikte bu yaklaşım \(10^8\)'e kadar tüm phi değerlerini saklamaktan çok daha verimlidir.
En un huerto hexagonal de orden \(n\), cada árbol pertenece a uno de seis sectores triangulares congruentes alrededor del centro. Un árbol está oculto si otro árbol se encuentra sobre el mismo rayo desde el centro y está más cerca del origen. La solución no compara todos los pares de árboles. En su lugar, transforma la visibilidad en una condición de coprimalidad y reduce el conteo a la suma acumulada de la función phi de Euler.
Por la simetría rotacional de orden 6, basta contar los árboles ocultos en un sector de \(60^\circ\) y multiplicar por 6 al final. En un sector, la fila \(r\) contiene exactamente \(r\) árboles para \(r=1,2,\dots,n\). Por tanto, el número total de árboles en un sector es el número triangular
$$T(n)=\sum_{r=1}^{n} r=\frac{n(n+1)}{2}.$$
El centro no se incluye en esta cantidad; solo es el punto de observación.
Numeremos los árboles de la fila \(r\) por posiciones \(x=1,2,\dots,r\). En la red oblicua que modela un sector hexagonal, el árbol \((x,r)\) está sobre el mismo rayo que \((x/d,r/d)\) cuando \(d\) divide a la vez a \(x\) y a \(r\). Por eso
$$\text{el árbol }(x,r)\text{ es visible desde el centro} \iff \gcd(x,r)=1.$$
Si \(\gcd(x,r)=d>1\), entonces \((x/d,r/d)\) es un árbol más cercano sobre la misma línea de visión y \((x,r)\) queda oculto. Si \(\gcd(x,r)=1\), no existe ningún punto intermedio. El número de árboles visibles en la fila \(r\) es entonces
$$\varphi(r)=\#\{1\le x\le r:\gcd(x,r)=1\},$$
es decir, la función phi de Euler. Por consiguiente, los árboles ocultos en esa fila son
$$r-\varphi(r).$$
En un solo sector obtenemos
$$H_{\mathrm{sector}}(n)=\sum_{r=1}^{n}\bigl(r-\varphi(r)\bigr)=\frac{n(n+1)}{2}-\sum_{r=1}^{n}\varphi(r).$$
Definimos ahora la función phi acumulada
$$\Phi(n)=\sum_{k=1}^{n}\varphi(k).$$
Entonces el número de árboles ocultos en todo el huerto es
$$\boxed{H(n)=6\,H_{\mathrm{sector}}(n)=6\left(\frac{n(n+1)}{2}-\Phi(n)\right).}$$
Esta es exactamente la fórmula que calculan los programas en C++, Python y Java.
El código no construye todos los valores de \(\varphi\) hasta \(n\) con un cribado completo. En cambio usa la identidad clásica
$$\sum_{d\mid m}\varphi(d)=m.$$
Al sumar esa identidad para \(m=1,2,\dots,n\), se obtiene
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d\mid m}\varphi(d)=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Como \(\sum_{m=1}^{n}m=\frac{n(n+1)}{2}\), queda
$$\frac{n(n+1)}{2}=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Ahora reescribimos el lado derecho en términos de sumas prefijo:
$$\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{k=1}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Separando el término \(k=1\), aparece la recurrencia usada por las tres implementaciones:
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Aunque la suma parece larga, muchos valores consecutivos de \(k\) producen el mismo cociente
\(q=\left\lfloor n/k\right\rfloor\). Si un bloque empieza en left, su último índice es
$$\text{right}=\left\lfloor\frac{n}{q}\right\rfloor.$$
Por tanto, el bloque completo
$$k=\text{left},\text{left}+1,\dots,\text{right}$$
aporta
$$(\text{right}-\text{left}+1)\,\Phi(q).$$
Eso explica exactamente el bucle de las soluciones: fijan left, calculan
quotient = n / left, obtienen right = n / quotient, restan un bloque entero y saltan a
right + 1. La memoización evita recalcular valores ya conocidos de \(\Phi\).
Para las cinco primeras filas,
$$\varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4,$$
de modo que
$$\Phi(5)=1+1+2+2+4=10.$$
Además,
$$T(5)=\frac{5\cdot 6}{2}=15,$$
y por ello
$$H_{\mathrm{sector}}(5)=15-10=5,\qquad H(5)=6\cdot 5=30.$$
Este valor coincide con el punto de control del archivo C++. La misma fuente verifica también \(H(10)=138\), \(H(1000)=1177848\) y un contraste por fuerza bruta en orden 200.
Los tres archivos de solución siguen la misma estructura. Inicializan una tabla de memoria con \(\Phi(0)=0\) y \(\Phi(1)=1\), calculan recursivamente la suma acumulada de totientes, forman el número triangular \(\frac{n(n+1)}{2}\), restan los puntos visibles de un sector y multiplican por 6.
La versión en C++ encapsula la recurrencia en una clase TotientSummatory apoyada en
std::unordered_map y usa unsigned __int128 para evitar problemas en valores intermedios.
La versión en Python usa una función interna con diccionario, y la versión en Java una
HashMap<Long, Long> estática. La lógica matemática es la misma en los tres lenguajes.
Un método ingenuo revisaría cada árbol de cada fila y comprobaría visibilidad con llamadas repetidas a \(\gcd\), lo cual es cuadrático en el orden del huerto. El método implementado lo evita por completo. Para un argumento fijo \(m\), la descomposición por divisiones enteras visita solo los distintos cocientes \(\left\lfloor m/k\right\rfloor\), y su cantidad es \(O(\sqrt{m})\). Si \(S\) es el conjunto de argumentos distintos alcanzados por la recursión memorizada, el tiempo total es
$$O\left(\sum_{m\in S}\sqrt{m}\right),$$
mientras que la memoria es \(O(|S|)\) para la tabla de memoización. En la práctica esto es muchísimo menor que calcular y almacenar todos los totientes hasta \(10^8\).
在阶数为 \(n\) 的六边形果园中，所有树点可以按对称性分成六个全等的三角扇区。若某棵树与中心共线， 并且在同一条射线上有另一棵更靠近中心的树，那么这棵树就是被遮挡的。程序并不枚举所有树对，而是先把 可见性转化为互素条件，再把总计数化成欧拉函数前缀和的问题。
由于图形具有 6 重旋转对称，只需求出一个 \(60^\circ\) 扇区中的遮挡树数，最后再乘以 6。单个扇区中， 第 \(r\) 行恰好有 \(r\) 棵树，其中 \(r=1,2,\dots,n\)。因此一个扇区的树总数是三角数
$$T(n)=\sum_{r=1}^{n} r=\frac{n(n+1)}{2}.$$
中心点只是观察位置，不计入树的数量。
把第 \(r\) 行上的树编号为 \(x=1,2,\dots,r\)。在六边形扇区对应的斜格点模型中，只要 \(d\) 同时整除 \(x\) 与 \(r\)，点 \((x,r)\) 就与 \((x/d,r/d)\) 位于同一条从中心发出的射线上。因此
$$\text{树 }(x,r)\text{ 从中心可见} \iff \gcd(x,r)=1.$$
若 \(\gcd(x,r)=d>1\)，那么 \((x/d,r/d)\) 就是同一直线方向上更近的树，\((x,r)\) 会被挡住。若 \(\gcd(x,r)=1\)，则中间不存在其他格点树。于是第 \(r\) 行可见树数正好是
$$\varphi(r)=\#\{1\le x\le r:\gcd(x,r)=1\},$$
也就是欧拉函数。该行被遮挡的树数因此为
$$r-\varphi(r).$$
单个扇区中的遮挡树总数为
$$H_{\mathrm{sector}}(n)=\sum_{r=1}^{n}\bigl(r-\varphi(r)\bigr)=\frac{n(n+1)}{2}-\sum_{r=1}^{n}\varphi(r).$$
定义欧拉函数前缀和
$$\Phi(n)=\sum_{k=1}^{n}\varphi(k).$$
则整个果园的答案满足
$$\boxed{H(n)=6\,H_{\mathrm{sector}}(n)=6\left(\frac{n(n+1)}{2}-\Phi(n)\right).}$$
这正是 C++、Python 与 Java 解法共同实现的公式。
代码并没有对 \(1\) 到 \(n\) 的所有 \(\varphi\) 做完整筛法，而是使用经典恒等式
$$\sum_{d\mid m}\varphi(d)=m.$$
把它对 \(m=1,2,\dots,n\) 求和，可得
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d\mid m}\varphi(d)=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
左边就是三角和，因此
$$\frac{n(n+1)}{2}=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
再把右侧改写成前缀和形式：
$$\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{k=1}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
把 \(k=1\) 这一项单独移到左边，就得到三份代码都在使用的递推关系：
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
虽然递推式表面上仍有很多项，但大量连续的 \(k\) 会产生相同的商
\(q=\left\lfloor n/k\right\rfloor\)。如果某个块从 left 开始，那么它的末尾位置就是
$$\text{right}=\left\lfloor\frac{n}{q}\right\rfloor.$$
于是整段
$$k=\text{left},\text{left}+1,\dots,\text{right}$$
可以一次性贡献
$$(\text{right}-\text{left}+1)\,\Phi(q).$$
这正对应解法中的做法：维护 left，计算 quotient = n / left，
再令 right = n / quotient，一次减去整个块，然后直接跳到 right + 1。
由于带有记忆化，每个不同的 \(\Phi\) 参数只会真正计算一次。
前五行的欧拉函数值为
$$\varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4,$$
因此
$$\Phi(5)=1+1+2+2+4=10.$$
同时
$$T(5)=\frac{5\cdot 6}{2}=15,$$
于是
$$H_{\mathrm{sector}}(5)=15-10=5,\qquad H(5)=6\cdot 5=30.$$
这与 C++ 源文件中的检查值一致。该文件还验证了 \(H(10)=138\)、\(H(1000)=1177848\)，并在 阶数 200 时进行了暴力交叉验证。
三个解法文件的结构完全一致。它们先建立 \(\Phi(0)=0\)、\(\Phi(1)=1\) 的记忆表，然后递归计算前缀和 \(\Phi(n)\)，再求三角数 \(\frac{n(n+1)}{2}\)，减去一个扇区中的可见树数，最后乘以 6。
C++ 版本把递推封装在 TotientSummatory 类里，底层使用
std::unordered_map，并用 unsigned __int128 保护中间运算。Python 版本使用
带字典的内部函数，Java 版本使用静态 HashMap<Long, Long>。三种语言的数学逻辑完全相同。
朴素做法需要检查每一行中的每一棵树，并频繁调用 \(\gcd\) 判断是否可见，时间复杂度近似二次。实际实现 完全避免了这一点。对固定参数 \(m\)，整除分块只会访问不同的 \(\left\lfloor m/k\right\rfloor\) 值， 其数量是 \(O(\sqrt{m})\)。若 \(S\) 表示记忆化递归最终访问到的所有不同参数集合，则总时间可写成
$$O\left(\sum_{m\in S}\sqrt{m}\right),$$
而内存复杂度为保存记忆表所需的 \(O(|S|)\)。在实际规模下，这比保存到 \(10^8\) 的全部欧拉函数值节省得多。
В шестиугольном саду порядка \(n\) все деревья разбиваются на шесть одинаковых треугольных секторов вокруг центра. Дерево считается скрытым, если на том же луче из центра уже стоит другое дерево, расположенное ближе к началу координат. Решение не перебирает все пары деревьев. Вместо этого оно переводит видимость в условие взаимной простоты и сводит задачу к вычислению сумматорной функции Эйлера.
Из-за шестикратной вращательной симметрии достаточно посчитать скрытые деревья в одном секторе \(60^\circ\), а затем умножить результат на 6. В одном секторе строка \(r\) содержит ровно \(r\) деревьев для \(r=1,2,\dots,n\). Поэтому общее число деревьев в секторе равно треугольному числу
$$T(n)=\sum_{r=1}^{n} r=\frac{n(n+1)}{2}.$$
Центральная точка не входит в этот подсчет; это только точка наблюдения.
Пронумеруем деревья в строке \(r\) позициями \(x=1,2,\dots,r\). В косой решетке, соответствующей одному сектору, точка \((x,r)\) лежит на том же луче, что и \((x/d,r/d)\), если число \(d\) делит и \(x\), и \(r\). Поэтому
$$\text{дерево }(x,r)\text{ видно из центра} \iff \gcd(x,r)=1.$$
Если \(\gcd(x,r)=d>1\), то \((x/d,r/d)\) находится ближе на той же линии обзора, и дерево \((x,r)\) скрыто. Если \(\gcd(x,r)=1\), промежуточной точки на этом луче нет. Следовательно, число видимых деревьев в строке \(r\) равно
$$\varphi(r)=\#\{1\le x\le r:\gcd(x,r)=1\},$$
то есть функции Эйлера. Тогда число скрытых деревьев в этой строке равно
$$r-\varphi(r).$$
Для одного сектора получаем
$$H_{\mathrm{sector}}(n)=\sum_{r=1}^{n}\bigl(r-\varphi(r)\bigr)=\frac{n(n+1)}{2}-\sum_{r=1}^{n}\varphi(r).$$
Введем сумматорную функцию
$$\Phi(n)=\sum_{k=1}^{n}\varphi(k).$$
Тогда для всего сада имеем
$$\boxed{H(n)=6\,H_{\mathrm{sector}}(n)=6\left(\frac{n(n+1)}{2}-\Phi(n)\right).}$$
Именно эту формулу вычисляют программы на C++, Python и Java.
Код не строит все значения \(\varphi\) до \(n\) полным решетом. Вместо этого используется классическое тождество
$$\sum_{d\mid m}\varphi(d)=m.$$
Просуммируем его по всем \(m=1,2,\dots,n\):
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d\mid m}\varphi(d)=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Поскольку \(\sum_{m=1}^{n}m=\frac{n(n+1)}{2}\), получаем
$$\frac{n(n+1)}{2}=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
Теперь перепишем правую часть через префиксные суммы:
$$\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{k=1}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Выделяя слагаемое \(k=1\), получаем рекурсию, совпадающую с реализацией:
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Хотя сумма кажется длинной, многие подряд идущие значения \(k\) дают один и тот же частный
\(q=\left\lfloor n/k\right\rfloor\). Если блок начинается в left, его последний индекс равен
$$\text{right}=\left\lfloor\frac{n}{q}\right\rfloor.$$
Значит, весь блок
$$k=\text{left},\text{left}+1,\dots,\text{right}$$
вносит вклад
$$(\text{right}-\text{left}+1)\,\Phi(q).$$
Именно поэтому код хранит левую границу, вычисляет quotient = n / left, затем
right = n / quotient, вычитает весь блок сразу и переходит к right + 1. Мемоизация
гарантирует, что каждое различное значение аргумента \(\Phi\) вычисляется только один раз.
Для первых пяти строк имеем
$$\varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4,$$
следовательно,
$$\Phi(5)=1+1+2+2+4=10.$$
Кроме того,
$$T(5)=\frac{5\cdot 6}{2}=15,$$
и потому
$$H_{\mathrm{sector}}(5)=15-10=5,\qquad H(5)=6\cdot 5=30.$$
Это совпадает с контрольным значением в файле C++. Там же проверяются \(H(10)=138\), \(H(1000)=1177848\) и полный перебор для порядка 200.
Все три файла решения устроены одинаково. Сначала инициализируется таблица памяти значениями \(\Phi(0)=0\) и \(\Phi(1)=1\), затем рекурсивно вычисляется сумматорная функция Эйлера, строится треугольное число \(\frac{n(n+1)}{2}\), из него вычитается число видимых точек в одном секторе, после чего результат умножается на 6.
Версия на C++ оформляет рекурсию в классе TotientSummatory на базе
std::unordered_map и использует unsigned __int128 для промежуточных вычислений. В
Python используется вложенная функция со словарем, а в Java статическая
HashMap<Long, Long>. Математическая идея во всех случаях одинаковая.
Наивный способ проверял бы каждое дерево в каждой строке и многократно вызывал бы \(\gcd\), что дает квадратичную зависимость от порядка сада. Реализованный алгоритм этого полностью избегает. Для фиксированного аргумента \(m\) разбиение по целочисленному делению посещает только различные значения \(\left\lfloor m/k\right\rfloor\), а их число равно \(O(\sqrt{m})\). Если \(S\) обозначает множество различных аргументов, реально достигнутых мемоизированной рекурсией, то суммарное время равно
$$O\left(\sum_{m\in S}\sqrt{m}\right),$$
а память составляет \(O(|S|)\) для хранения таблицы. На практике это несравнимо меньше, чем вычислять и хранить все значения функции Эйлера до \(10^8\).
في بستان سداسي من الرتبة \(n\)، يمكن تقسيم جميع الأشجار إلى ستة قطاعات مثلثية متطابقة حول المركز. تكون الشجرة محجوبة إذا وُجدت شجرة أخرى على الشعاع نفسه الخارج من المركز وكانت أقرب إلى الأصل. الحل لا يقارن كل زوج من الأشجار، بل يحول شرط الرؤية إلى شرط يتعلق بالتباين الأولي، ثم يختزل العد كله إلى حساب المجموع التراكمي لدالة أويلر.
بسبب التناظر الدوراني من الدرجة 6 يكفي أن نعد الأشجار المحجوبة في قطاع واحد زاويته \(60^\circ\)، ثم نضرب النتيجة في 6. في هذا القطاع يحتوي الصف \(r\) على \(r\) أشجار تمامًا عندما \(r=1,2,\dots,n\). لذلك يكون عدد الأشجار في قطاع واحد هو العدد المثلثي
$$T(n)=\sum_{r=1}^{n} r=\frac{n(n+1)}{2}.$$
النقطة المركزية ليست ضمن هذا العد، فهي مجرد موضع الرصد.
لنرقم أشجار الصف \(r\) بالمواقع \(x=1,2,\dots,r\). في الشبكة المائلة التي تمثل قطاعًا سداسيًا، تكون النقطة \((x,r)\) على الشعاع نفسه الذي تمر به \((x/d,r/d)\) متى كان \(d\) يقسم كلًا من \(x\) و\(r\). لذلك تكون الشجرة \((x,r)\) مرئية من المركز إذا وفقط إذا كان
$$\gcd(x,r)=1.$$
إذا كان \(\gcd(x,r)=d>1\)، فإن \((x/d,r/d)\) تمثل شجرة أقرب على خط النظر نفسه، وبالتالي تكون \((x,r)\) محجوبة. وإذا كان \(\gcd(x,r)=1\)، فلا توجد نقطة وسيطة على ذلك الشعاع. ومن ثم فإن عدد الأشجار المرئية في الصف \(r\) هو
$$\varphi(r)=\#\{1\le x\le r:\gcd(x,r)=1\},$$
أي دالة أويلر. وعدد الأشجار المحجوبة في الصف نفسه يساوي
$$r-\varphi(r).$$
إذن عدد الأشجار المحجوبة في قطاع واحد هو
$$H_{\mathrm{sector}}(n)=\sum_{r=1}^{n}\bigl(r-\varphi(r)\bigr)=\frac{n(n+1)}{2}-\sum_{r=1}^{n}\varphi(r).$$
ونعرف الآن المجموع التراكمي لدالة أويلر على الصورة
$$\Phi(n)=\sum_{k=1}^{n}\varphi(k).$$
وعندئذ يصبح عدد الأشجار المحجوبة في البستان كله
$$\boxed{H(n)=6\,H_{\mathrm{sector}}(n)=6\left(\frac{n(n+1)}{2}-\Phi(n)\right).}$$
وهذه هي الصيغة نفسها التي تحسبها ملفات C++ وPython وJava.
الكود لا يبني كل قيم \(\varphi\) حتى \(n\) باستخدام غربال كامل، بل يعتمد على الهوية الكلاسيكية
$$\sum_{d\mid m}\varphi(d)=m.$$
وبجمع هذه الهوية من \(m=1\) إلى \(n\) نحصل على
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d\mid m}\varphi(d)=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
وبما أن \(\sum_{m=1}^{n}m=\frac{n(n+1)}{2}\)، فإن
$$\frac{n(n+1)}{2}=\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor.$$
ثم نعيد كتابة الطرف الأيمن بدلالة المجاميع الأولية:
$$\sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor=\sum_{k=1}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
وبفصل الحد الموافق لـ \(k=1\) تظهر العلاقة العودية المستخدمة في اللغات الثلاث:
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}\Phi\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
قد يبدو أن العلاقة السابقة تحتوي عددًا كبيرًا من الحدود، لكن قيمًا متتالية كثيرة من \(k\) تعطي خارج القسمة
نفسه \(q=\left\lfloor n/k\right\rfloor\). إذا بدأ مقطع عند left فإن آخر فهرس فيه يساوي
$$\text{right}=\left\lfloor\frac{n}{q}\right\rfloor.$$
وعليه فإن المقطع الكامل
$$k=\text{left},\text{left}+1,\dots,\text{right}$$
يسهم بمقدار
$$(\text{right}-\text{left}+1)\,\Phi(q).$$
وهذا يفسر مباشرة ما يفعله الكود: يثبت left، ثم يحسب quotient = n / left، وبعد ذلك
يستنتج right = n / quotient، ويطرح كتلة كاملة دفعة واحدة، ثم يقفز إلى right + 1.
وباستخدام الحفظ في الذاكرة لا يُحسب كل وسيط مختلف لـ \(\Phi\) إلا مرة واحدة.
في الصفوف الخمسة الأولى نجد
$$\varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4,$$
ومن ثم
$$\Phi(5)=1+1+2+2+4=10.$$
وكذلك
$$T(5)=\frac{5\cdot 6}{2}=15,$$
وبالتالي
$$H_{\mathrm{sector}}(5)=15-10=5,\qquad H(5)=6\cdot 5=30.$$
وهذا يطابق نقطة الفحص الموجودة في ملف C++. كما أن المصدر نفسه يتحقق أيضًا من \(H(10)=138\) و\(H(1000)=1177848\)، ويجري مقارنة بالقوة الغاشمة عندما تكون الرتبة 200.
الملفات الثلاثة تستخدم البنية نفسها. فهي تبدأ بجدول حفظ يحوي \(\Phi(0)=0\) و\(\Phi(1)=1\)، ثم تحسب \(\Phi(n)\) عوديًا، وبعد ذلك تكوّن العدد المثلثي \(\frac{n(n+1)}{2}\)، وتطرح عدد النقاط المرئية في قطاع واحد، ثم تضرب الناتج في 6.
نسخة C++ تضع العلاقة العودية داخل الصنف TotientSummatory المعتمد على
std::unordered_map، وتستخدم unsigned __int128 لحماية الحسابات الوسيطة. نسخة Python
تستخدم دالة داخلية مع قاموس، أما نسخة Java فتستخدم HashMap<Long, Long> ساكنة. المنطق
الرياضي واحد في جميع اللغات.
الطريقة الساذجة كانت ستفحص كل شجرة في كل صف وتستدعي \(\gcd\) مرارًا، وهذا يعني تعقيدًا تربيعيًا في رتبة البستان. أما الطريقة المنفذة فتتجنب ذلك بالكامل. بالنسبة إلى وسيط ثابت \(m\)، فإن تجميع القسمة الصحيحة يزور فقط القيم المختلفة لـ \(\left\lfloor m/k\right\rfloor\)، وعددها \(O(\sqrt{m})\). وإذا رمزنا بـ \(S\) إلى مجموعة الوسائط المختلفة التي تصل إليها العودية مع الحفظ، فإن زمن التنفيذ الكلي هو
$$O\left(\sum_{m\in S}\sqrt{m}\right),$$
بينما يكون استهلاك الذاكرة \(O(|S|)\) لجدول الحفظ. عمليًا هذا أصغر بكثير من حساب جميع قيم دالة أويلر حتى \(10^8\) وتخزينها.