For each integer \(n\), let \(S_n\) be the regular \(n\)-gon with the fixed orientation from the problem. The task is to count the sides of the Minkowski sum
$$S_{1864}+S_{1865}+\cdots+S_{1909}.$$
The implementations show that this is not really a coordinate-geometry problem. To determine how many sides the final polygon has, we only need to know which outer-normal directions occur on the boundary. Once those directions are classified correctly, the rest is a number-theoretic counting argument.
The key idea is to translate the geometry of Minkowski sums into a union of direction classes, and then count those classes by Euler's totient function.
For a convex set \(P\), its support function is \(h_P(u)=\max_{x\in P} u\cdot x\). Minkowski addition satisfies
$$h_{A+B}(u)=h_A(u)+h_B(u).$$
When the direction \(u\) rotates around the circle, the boundary of a convex polygon changes edge whenever one of its supporting directions changes. Therefore the edge normals of a Minkowski sum are exactly the distinct edge normals contributed by the summands. If several summands have the same normal direction, they only lengthen the corresponding edge of the sum; they do not create extra sides.
So if \(D(P)\) denotes the set of outer-normal directions of a polygon \(P\), then
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{n=1864}^{1909} D(S_n),$$
and the number of sides is simply the size of that union.
With the orientation used in the problem, the outer normals of \(S_n\) occur at the equally spaced angles
$$D(S_n)=\left\{\frac{2\pi k}{n}: 0\le k \lt n\right\},$$
with angles understood modulo \(2\pi\). Now reduce the fraction \(k/n\) to lowest terms, say
$$\frac{k}{n}=\frac{a}{d},\qquad \gcd(a,d)=1.$$
The integer \(d\) is the exact denominator of that direction, and it is always a divisor of \(n\). For every divisor \(d\mid n\), define the primitive direction class
$$\Theta_d=\left\{\frac{2\pi a}{d}: 0\le a \lt d,\ \gcd(a,d)=1\right\}.$$
Its size is \(|\Theta_d|=\varphi(d)\). Distinct values of \(d\) give disjoint classes because a rational angle has a unique reduced denominator. Therefore the directions of one regular \(n\)-gon split as
$$D(S_n)=\bigcup_{d\mid n}\Theta_d,$$
and counting those directions gives the familiar identity
$$n=\sum_{d\mid n}\varphi(d).$$
Geometrically, this says that \(S_n\) contains every primitive direction whose denominator divides \(n\).
Now collect every denominator that appears for at least one polygon in the interval:
$$U=\left\{d\ge 1:\exists n\in[1864,1909],\ d\mid n\right\}.$$
Because the Minkowski sum just unions the direction sets, we get
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{d\in U}\Theta_d.$$
The classes \(\Theta_d\) are disjoint, so the final side count is
$$\boxed{N=\sum_{d\in U}\varphi(d)}$$
This formula is exactly what the C++, Python, and Java implementations evaluate: mark every divisor that occurs somewhere between 1864 and 1909, then add the totient of each marked divisor once.
This small case is useful because it mirrors the checkpoint used in the implementations. The triangle contributes the denominator classes \(1\) and \(3\), while the square contributes \(1\), \(2\), and \(4\). Hence
$$U=\{1,2,3,4\}.$$
The resulting polygon has
$$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)=1+1+2+2=6$$
sides. The denominator \(1\) is shared by both summands, but it is counted only once because repeated directions do not create new edges in the Minkowski sum.
The C++, Python, and Java implementations follow the formula above directly. They never build explicit polygon coordinates, never add vectors on the boundary, and never run a geometric hull algorithm.
First, the implementation computes \(\varphi(d)\) for every \(1\le d\le 1909\) with a standard sieve. It starts from \(\varphi(d)=d\) and, for each prime \(p\), applies the update
$$\varphi(k)\leftarrow \varphi(k)-\frac{\varphi(k)}{p}$$
to every multiple \(k\) of \(p\). After this pass, the totient table is ready for the final sum.
Next, the code scans every \(n\) from 1864 through 1909. For each \(n\), it tries every divisor candidate \(d\) with \(d^2\le n\). Whenever \(d\mid n\), it marks both \(d\) and \(n/d\). After all values of \(n\) have been processed, a denominator is marked exactly when it divides at least one integer in the interval.
This is the computational version of building the set \(U\).
Finally, the implementation loops over all denominators \(d\le 1909\) and adds \(\varphi(d)\) whenever \(d\) was marked. Because each denominator class is added only once, the program matches the geometric rule that coincident directions merge into a single side of the final polygon.
Let \(M=1909\). The totient sieve runs in \(O(M\log\log M)\) time. The divisor-marking phase checks all integers \(d\) up to \(\sqrt n\) for each \(n\in[1864,1909]\), so its cost is
$$O\!\left(\sum_{n=1864}^{1909}\sqrt n\right),$$
or, in the usual worst-case form, \(O((N_2-N_1+1)\sqrt{N_2})\).
The final summation over marked denominators is \(O(M)\), and the memory usage is \(O(M)\) for the totient table and the boolean marker array. Since the interval is short and \(M\) is small, this direct divisor scan is already more than sufficient.
Für jedes ganze \(n\) sei \(S_n\) das reguläre \(n\)-Eck in der durch die Aufgabe festgelegten Orientierung. Gesucht ist die Seitenzahl der Minkowski-Summe
$$S_{1864}+S_{1865}+\cdots+S_{1909}.$$
Die Implementierungen zeigen, dass dies kein Koordinatenproblem im eigentlichen Sinn ist. Für die Anzahl der Seiten des Endpolygons ist nur relevant, welche Richtungen äußerer Normalen auf dem Rand auftreten. Sobald man diese Richtungen richtig klassifiziert, bleibt nur noch ein zahlentheoretisches Zählproblem übrig.
Die zentrale Idee besteht darin, die Geometrie der Minkowski-Summe in eine Vereinigung von Richtungsklassen zu übersetzen und diese Klassen dann mit der eulerschen Phi-Funktion zu zählen.
Für eine konvexe Menge \(P\) ist ihre Stützfunktion \(h_P(u)=\max_{x\in P} u\cdot x\). Für Minkowski-Summen gilt
$$h_{A+B}(u)=h_A(u)+h_B(u).$$
Wenn die Richtung \(u\) einmal um den Kreis läuft, ändert sich der Rand eines konvexen Polygons genau dann zu einer neuen Seite, wenn sich eine tragende Richtung ändert. Daher sind die Kanten-Normalen einer Minkowski-Summe genau die verschiedenen Kanten-Normalen, die von mindestens einem Summanden kommen. Haben mehrere Summanden dieselbe Normalenrichtung, wird die entsprechende Kante nur länger; es entsteht keine zusätzliche Seite.
Bezeichnet also \(D(P)\) die Menge der äußeren Normalenrichtungen eines Polygons \(P\), dann gilt
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{n=1864}^{1909} D(S_n),$$
und die gesuchte Seitenzahl ist einfach die Größe dieser Vereinigung.
In der in der Aufgabe verwendeten Orientierung liegen die äußeren Normalen von \(S_n\) bei den gleichmäßig verteilten Winkeln
$$D(S_n)=\left\{\frac{2\pi k}{n}: 0\le k \lt n\right\},$$
wobei die Winkel modulo \(2\pi\) zu verstehen sind. Reduziert man \(k/n\) vollständig, also
$$\frac{k}{n}=\frac{a}{d},\qquad \gcd(a,d)=1,$$
dann ist \(d\) der exakte Nenner dieser Richtung, und \(d\) teilt stets \(n\). Für jeden Teiler \(d\mid n\) definieren wir die primitive Richtungsklasse
$$\Theta_d=\left\{\frac{2\pi a}{d}: 0\le a \lt d,\ \gcd(a,d)=1\right\}.$$
Ihre Mächtigkeit ist \(|\Theta_d|=\varphi(d)\). Verschiedene Werte von \(d\) liefern disjunkte Klassen, weil ein rationaler Winkel genau einen vollständig gekürzten Nenner besitzt. Daher zerfällt die Richtungsmenge eines regulären \(n\)-Ecks in
$$D(S_n)=\bigcup_{d\mid n}\Theta_d,$$
und das Zählen dieser Richtungen ergibt die bekannte Identität
$$n=\sum_{d\mid n}\varphi(d).$$
Geometrisch bedeutet das: \(S_n\) enthält jede primitive Richtung, deren Nenner ein Teiler von \(n\) ist.
Nun sammeln wir alle Nenner, die bei mindestens einem Polygon des Intervalls vorkommen:
$$U=\left\{d\ge 1:\exists n\in[1864,1909],\ d\mid n\right\}.$$
Da die Minkowski-Summe nur die Richtungsmenge vereinigt, folgt
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{d\in U}\Theta_d.$$
Die Klassen \(\Theta_d\) sind disjunkt, also ist die endgültige Seitenzahl
$$\boxed{N=\sum_{d\in U}\varphi(d)}$$
Genau diese Formel werten die C++-, Python- und Java-Implementierungen aus: Alle im Intervall auftretenden Teiler werden markiert, und die Totienten dieser markierten Teiler werden genau einmal aufsummiert.
Dieser kleine Fall ist nützlich, weil er dasselbe Prinzip wie die Prüfbeispiele in den Implementierungen zeigt. Das Dreieck liefert die Nennerklassen \(1\) und \(3\), das Quadrat die Klassen \(1\), \(2\) und \(4\). Damit ist
$$U=\{1,2,3,4\}.$$
Das resultierende Polygon besitzt also
$$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)=1+1+2+2=6$$
Seiten. Der Nenner \(1\) kommt in beiden Summanden vor, wird aber nur einmal gezählt, weil zusammenfallende Richtungen in der Minkowski-Summe keine neue Seite erzeugen.
Die C++-, Python- und Java-Implementierungen folgen der obigen Formel direkt. Sie konstruieren keine expliziten Polygonkoordinaten, addieren keine Randvektoren und berechnen keine geometrische Hülle.
Zuerst berechnet die Implementierung \(\varphi(d)\) für alle \(1\le d\le 1909\) mit einem Standardsieb. Man startet mit \(\varphi(d)=d\) und führt für jede Primzahl \(p\) auf jedem Vielfachen \(k\) das Update
$$\varphi(k)\leftarrow \varphi(k)-\frac{\varphi(k)}{p}$$
aus. Danach steht die komplette Totiententabelle für die Endsumme bereit.
Anschließend durchläuft der Code alle \(n\) von 1864 bis 1909. Für jedes \(n\) werden alle Teilerkandidaten \(d\) mit \(d^2\le n\) geprüft. Falls \(d\mid n\) gilt, werden sowohl \(d\) als auch \(n/d\) markiert. Nach diesem Durchlauf ist genau dann ein Nenner markiert, wenn er mindestens eine Zahl aus dem Intervall teilt.
Das ist die algorithmische Realisierung der Menge \(U\).
Zum Schluss läuft die Implementierung über alle Nenner \(d\le 1909\) und addiert \(\varphi(d)\), sobald \(d\) markiert wurde. Da jede Nennerklasse nur einmal eingeht, entspricht das Programm exakt der geometrischen Regel, dass identische Richtungen zu einer einzigen Seite zusammenfallen.
Sei \(M=1909\). Das Totientensieb benötigt \(O(M\log\log M)\) Zeit. In der Phase zum Markieren der Teiler werden für jedes \(n\in[1864,1909]\) alle Zahlen bis \(\sqrt n\) getestet; das kostet insgesamt
$$O\!\left(\sum_{n=1864}^{1909}\sqrt n\right),$$
oder in der üblichen Worst-Case-Form \(O((N_2-N_1+1)\sqrt{N_2})\).
Die abschließende Summe über die markierten Nenner ist \(O(M)\), und der Speicherverbrauch ist \(O(M)\) für die Totiententabelle sowie das Markierungsarray. Weil das Intervall kurz und \(M\) klein ist, ist dieser direkte Teilerscan bereits völlig ausreichend.
Her \(n\) tam sayısı için \(S_n\), soruda verilen yönelime sahip düzenli \(n\)-gendir. İstenen şey, şu Minkowski toplamının kaç kenarlı olduğunu bulmaktır:
$$S_{1864}+S_{1865}+\cdots+S_{1909}.$$
Uygulamalar gösteriyor ki bu aslında bir koordinat geometrisi problemi değildir. Son çokgenin kenar sayısını belirleyen şey, sınır üzerinde hangi dış normal yönlerinin ortaya çıktığıdır. Bu yönleri doğru şekilde sınıflandırınca geriye yalnızca sayılar teorisi tabanlı bir sayım kalır.
Ana fikir, Minkowski toplamının geometrisini yön sınıflarının birleşimine çevirmek ve bu sınıfları Euler phi fonksiyonuyla saymaktır.
Konveks bir \(P\) kümesi için destek fonksiyonu \(h_P(u)=\max_{x\in P} u\cdot x\) olarak tanımlanır. Minkowski toplamı için
$$h_{A+B}(u)=h_A(u)+h_B(u)$$
eşitliği geçerlidir. \(u\) yönü çember etrafında dönerken, bir konveks çokgenin sınırında yeni bir kenara geçiş tam olarak destekleyici yön değiştiğinde olur. Bu yüzden Minkowski toplamındaki kenar normal yönleri, summandlarda bulunan farklı kenar normal yönlerinin birleşimidir. Birden fazla summand aynı yönü taşıyorsa, bu sadece ilgili kenarın uzunluğunu değiştirir; yeni bir kenar oluşturmaz.
Dolayısıyla bir çokgenin dış normal yön kümesini \(D(P)\) ile gösterirsek
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{n=1864}^{1909} D(S_n)$$
olur ve aranan kenar sayısı bu birleşimin eleman sayısıdır.
Sorudaki yönelimle birlikte \(S_n\)'in dış normal yönleri eşit aralıklı şu açılarda bulunur:
$$D(S_n)=\left\{\frac{2\pi k}{n}: 0\le k \lt n\right\},$$
burada açılar \(2\pi\) modunda düşünülür. Şimdi \(k/n\) kesrini sadeleştirip
$$\frac{k}{n}=\frac{a}{d},\qquad \gcd(a,d)=1$$
yazalım. Bu durumda \(d\), o yönün tam paydasıdır ve her zaman \(n\)'in bir bölenidir. Her \(d\mid n\) için ilkel yön sınıfını
$$\Theta_d=\left\{\frac{2\pi a}{d}: 0\le a \lt d,\ \gcd(a,d)=1\right\}$$
olarak tanımlayalım. Bu kümenin büyüklüğü \(|\Theta_d|=\varphi(d)\) olur. Farklı \(d\) değerleri ayrık sınıflar verir; çünkü rasyonel bir açının sadeleştirilmiş paydası tektir. Böylece tek bir düzenli \(n\)-genin yönleri
$$D(S_n)=\bigcup_{d\mid n}\Theta_d$$
şeklinde ayrışır ve bu yönlerin sayısı
$$n=\sum_{d\mid n}\varphi(d)$$
özdeşliğini verir. Geometrik anlamı şudur: \(S_n\), paydası \(n\)'i bölen her ilkel yönü içerir.
Şimdi aralıkta en az bir kez görünen bütün paydaları toplayalım:
$$U=\left\{d\ge 1:\exists n\in[1864,1909],\ d\mid n\right\}.$$
Minkowski toplamı yalnızca yön kümelerini birleştirdiği için
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{d\in U}\Theta_d$$
elde edilir. \(\Theta_d\) sınıfları ayrık olduğundan son kenar sayısı
$$\boxed{N=\sum_{d\in U}\varphi(d)}$$
C++, Python ve Java uygulamalarının hesapladığı şey tam olarak budur: 1864 ile 1909 arasında en az bir sayıyı bölen tüm paydaları işaretlemek ve işaretlenen her payda için \(\varphi(d)\) değerini bir kez toplamak.
Bu küçük örnek, uygulamalardaki kontrol durumuyla aynı mantığı gösterir. Üçgen \(1\) ve \(3\) payda sınıflarını, kare ise \(1\), \(2\) ve \(4\) sınıflarını getirir. O halde
$$U=\{1,2,3,4\}.$$
Sonuç çokgeninin kenar sayısı
$$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)=1+1+2+2=6$$
olur. \(1\) paydası iki çokgende de vardır ama yalnızca bir kez sayılır; çünkü çakışan yönler Minkowski toplamında ekstra kenar üretmez.
C++, Python ve Java uygulamaları yukarıdaki formülü doğrudan uygular. Açık çokgen koordinatları oluşturulmaz, sınır vektörleri toplanmaz ve geometrik bir kabuk algoritması çalıştırılmaz.
İlk adımda uygulama \(1\le d\le 1909\) için tüm \(\varphi(d)\) değerlerini standart bir elek ile üretir. Başlangıçta \(\varphi(d)=d\) alınır; sonra her asal \(p\) için bütün \(p\) katlarında
$$\varphi(k)\leftarrow \varphi(k)-\frac{\varphi(k)}{p}$$
güncellemesi yapılır. Böylece son toplama için gerekli tüm phi tablosu hazır olur.
Daha sonra kod 1864'ten 1909'a kadar bütün \(n\) değerlerini tarar. Her \(n\) için \(d^2\le n\) koşulunu sağlayan tüm bölen adayları denenir. Eğer \(d\mid n\) ise hem \(d\) hem de \(n/d\) işaretlenir. Tüm aralık bittikten sonra bir payda tam ve yalnızca aralıkta en az bir sayıyı böldüğünde işaretli olur.
Bu adım, \(U\) kümesinin hesaplamalı karşılığıdır.
Son aşamada uygulama \(d\le 1909\) olan bütün paydaları dolaşır ve işaretli olan her \(d\) için \(\varphi(d)\) ekler. Her payda sınıfı yalnızca bir kez eklendiği için program, aynı yönlerin tek bir kenarda birleşmesi kuralını bire bir yansıtır.
\(M=1909\) olsun. Totient eleği \(O(M\log\log M)\) zamanda çalışır. Bölen işaretleme aşamasında her \(n\in[1864,1909]\) için \(\sqrt n\)'ye kadar deneme yapılır; toplam maliyet
$$O\!\left(\sum_{n=1864}^{1909}\sqrt n\right)$$
olur. Bunu standart üst sınır biçiminde \(O((N_2-N_1+1)\sqrt{N_2})\) diye de yazabiliriz.
İşaretlenen paydalar üzerinden yapılan son toplama \(O(M)\), bellek kullanımı ise phi tablosu ile işaret dizisi için \(O(M)\)'dir. Aralık kısa ve \(M\) küçük olduğu için bu doğrudan bölen taraması fazlasıyla yeterlidir.
Para cada entero \(n\), sea \(S_n\) el polígono regular de \(n\) lados con la orientación fijada por el enunciado. Hay que contar cuántos lados tiene la suma de Minkowski
$$S_{1864}+S_{1865}+\cdots+S_{1909}.$$
Las implementaciones dejan claro que no hace falta trabajar con coordenadas concretas. Para conocer el número de lados del polígono final solo importa qué direcciones de normales exteriores aparecen en la frontera. Una vez clasificadas esas direcciones, el problema se convierte en una cuenta aritmética.
La idea central es traducir la geometría de la suma de Minkowski a una unión de clases de direcciones y contar esas clases mediante la función totiente de Euler.
Para un conjunto convexo \(P\), su función soporte es \(h_P(u)=\max_{x\in P} u\cdot x\). La suma de Minkowski satisface
$$h_{A+B}(u)=h_A(u)+h_B(u).$$
Cuando la dirección \(u\) gira alrededor del círculo, la frontera de un polígono convexo cambia de lado exactamente cuando cambia una dirección de soporte. Por eso, las normales de los lados de una suma de Minkowski son precisamente las distintas normales que ya aparecen en alguno de los sumandos. Si varios sumandos comparten la misma dirección, solo alargan ese lado del resultado; no crean lados adicionales.
Si \(D(P)\) representa el conjunto de direcciones de normales exteriores de un polígono \(P\), entonces
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{n=1864}^{1909} D(S_n),$$
y el número de lados buscado es simplemente el tamaño de esa unión.
Con la orientación usada en el problema, las normales exteriores de \(S_n\) aparecen en los ángulos igualmente espaciados
$$D(S_n)=\left\{\frac{2\pi k}{n}: 0\le k \lt n\right\},$$
entendidos módulo \(2\pi\). Ahora reducimos la fracción \(k/n\) a términos mínimos:
$$\frac{k}{n}=\frac{a}{d},\qquad \gcd(a,d)=1.$$
El entero \(d\) es el denominador exacto de esa dirección y siempre divide a \(n\). Para cada divisor \(d\mid n\), definimos la clase primitiva
$$\Theta_d=\left\{\frac{2\pi a}{d}: 0\le a \lt d,\ \gcd(a,d)=1\right\}.$$
Su tamaño es \(|\Theta_d|=\varphi(d)\). Distintos valores de \(d\) producen clases disjuntas, porque un ángulo racional tiene un único denominador reducido. Así, las direcciones de un polígono regular de \(n\) lados se descomponen como
$$D(S_n)=\bigcup_{d\mid n}\Theta_d,$$
y al contarlas reaparece la identidad clásica
$$n=\sum_{d\mid n}\varphi(d).$$
La interpretación geométrica es que \(S_n\) contiene todas las direcciones primitivas cuyo denominador divide a \(n\).
Ahora reunimos todos los denominadores que aparecen al menos una vez en el intervalo:
$$U=\left\{d\ge 1:\exists n\in[1864,1909],\ d\mid n\right\}.$$
Como la suma de Minkowski solo une conjuntos de direcciones, obtenemos
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{d\in U}\Theta_d.$$
Las clases \(\Theta_d\) son disjuntas, por lo que el número final de lados es
$$\boxed{N=\sum_{d\in U}\varphi(d)}$$
Eso es exactamente lo que calculan las implementaciones en C++, Python y Java: marcar todos los divisores que aparecen en algún \(n\) entre 1864 y 1909 y sumar una sola vez el totiente de cada divisor marcado.
Este caso pequeño reproduce la misma lógica que usan las comprobaciones básicas. El triángulo aporta las clases de denominador \(1\) y \(3\), mientras que el cuadrado aporta \(1\), \(2\) y \(4\). Entonces
$$U=\{1,2,3,4\}.$$
El polígono resultante tiene
$$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)=1+1+2+2=6$$
lados. El denominador \(1\) aparece en ambos sumandos, pero se cuenta una sola vez porque las direcciones coincidentes no generan lados nuevos en la suma de Minkowski.
Las implementaciones en C++, Python y Java siguen la fórmula anterior de manera directa. No construyen coordenadas explícitas de los polígonos, no suman vectores del contorno y no ejecutan un algoritmo geométrico de envolvente.
Primero, la implementación calcula \(\varphi(d)\) para todo \(1\le d\le 1909\) mediante una criba estándar. Se parte de \(\varphi(d)=d\) y, para cada primo \(p\), se aplica a cada múltiplo \(k\) la actualización
$$\varphi(k)\leftarrow \varphi(k)-\frac{\varphi(k)}{p}.$$
Al terminar esta fase, la tabla de totientes ya está lista para la suma final.
Después, el código recorre todos los valores \(n\) desde 1864 hasta 1909. Para cada \(n\), prueba todos los candidatos \(d\) con \(d^2\le n\). Si \(d\mid n\), marca tanto \(d\) como \(n/d\). Tras procesar todo el intervalo, un denominador queda marcado si y solo si divide al menos a un entero del intervalo.
Esa es la realización computacional del conjunto \(U\).
Por último, la implementación recorre todos los denominadores \(d\le 1909\) y suma \(\varphi(d)\) cuando \(d\) está marcado. Como cada clase se incorpora una sola vez, el programa reproduce exactamente la regla geométrica de que varias apariciones de la misma dirección se fusionan en un único lado del polígono suma.
Sea \(M=1909\). La criba de totientes cuesta \(O(M\log\log M)\). La fase de marcado de divisores prueba todos los valores hasta \(\sqrt n\) para cada \(n\in[1864,1909]\), así que su coste total es
$$O\!\left(\sum_{n=1864}^{1909}\sqrt n\right),$$
o, en la forma habitual de peor caso, \(O((N_2-N_1+1)\sqrt{N_2})\).
La suma final sobre los denominadores marcados es \(O(M)\), y la memoria empleada es \(O(M)\) para la tabla de totientes y el arreglo de marcas. Como el intervalo es corto y \(M\) es pequeño, este barrido directo de divisores es más que suficiente.
对每个整数 \(n\)，记 \(S_n\) 为题目所采用固定朝向下的正 \(n\) 边形。要求计算下面这个 Minkowski 和最终有多少条边：
$$S_{1864}+S_{1865}+\cdots+S_{1909}.$$
实现代码说明，这个题目真正关键的并不是顶点坐标，也不是把多边形边界逐段相加。决定答案的只有一件事：最终边界上会出现哪些外法向方向。一旦把这些方向按“约分后的分母”分类，整个问题就变成了一个纯粹的数论计数问题。
核心思路是把 Minkowski 和的几何结构转写成若干方向类的并集，再用欧拉函数统计这些方向类的总数。
对任意凸集 \(P\)，其支撑函数定义为 \(h_P(u)=\max_{x\in P} u\cdot x\)。Minkowski 加法满足
$$h_{A+B}(u)=h_A(u)+h_B(u).$$
当方向 \(u\) 沿着单位圆转动时，凸多边形边界在哪些位置切换到下一条边，正是由支撑方向何时发生变化决定的。因此，和多边形的边法向方向，恰好就是所有加数中出现过的法向方向的并集。如果几个加数拥有同一个法向方向，那么它们只会把对应边拉长，而不会凭空制造新的边。
记 \(D(P)\) 为多边形 \(P\) 的外法向方向集合，则有
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{n=1864}^{1909} D(S_n),$$
所以题目要求的边数，就是这个并集的大小。
在题目固定的朝向下，\(S_n\) 的外法向方向恰好落在等间距的角度
$$D(S_n)=\left\{\frac{2\pi k}{n}: 0\le k \lt n\right\},$$
其中角度按 \(2\pi\) 同余理解。现在把分数 \(k/n\) 约到最简，写成
$$\frac{k}{n}=\frac{a}{d},\qquad \gcd(a,d)=1.$$
这个 \(d\) 就是该方向的“精确分母”，而且它一定是 \(n\) 的一个因子。对每个满足 \(d\mid n\) 的 \(d\)，定义原始方向类
$$\Theta_d=\left\{\frac{2\pi a}{d}: 0\le a \lt d,\ \gcd(a,d)=1\right\}.$$
这个集合的大小是 \(|\Theta_d|=\varphi(d)\)。不同的 \(d\) 会得到互不重叠的方向类，因为一个有理角度的最简分母是唯一的。所以单个正 \(n\) 边形的方向集合可以拆成
$$D(S_n)=\bigcup_{d\mid n}\Theta_d,$$
从而立刻得到熟悉的恒等式
$$n=\sum_{d\mid n}\varphi(d).$$
在这里，这个恒等式有非常直接的几何意义：只要某个原始方向的分母整除 \(n\)，它就一定会出现在 \(S_n\) 的边法向集合中。
接下来，把区间里至少出现过一次的所有分母集中起来：
$$U=\left\{d\ge 1:\exists n\in[1864,1909],\ d\mid n\right\}.$$
由于 Minkowski 和只会把方向集合做并集，我们得到
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{d\in U}\Theta_d.$$
而 \(\Theta_d\) 彼此不相交，所以最终边数就是
$$\boxed{N=\sum_{d\in U}\varphi(d)}$$
这正是三份实现代码所做的事：先找出 1864 到 1909 之间所有整数的全部因子，保留那些真正出现过的分母，然后把这些分母对应的欧拉函数值各加一次。
这个小例子正好对应实现里使用的基础校验。正三角形提供分母类 \(1\) 和 \(3\)，正方形提供分母类 \(1\)、\(2\)、\(4\)。因此
$$U=\{1,2,3,4\}.$$
最终多边形的边数为
$$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)=1+1+2+2=6.$$
这里分母 \(1\) 同时来自两个加数，但只能计数一次，因为相同方向在 Minkowski 和中会合并成同一条边，而不是变成两条边。
C++、Python 和 Java 实现都直接按照上面的公式来做。它们不显式构造多边形坐标，不在几何意义上逐边相加，也不调用凸包之类的算法。
第一步是用标准筛法求出所有 \(1\le d\le 1909\) 的 \(\varphi(d)\)。初始时令 \(\varphi(d)=d\)，然后对每个素数 \(p\)，在其所有倍数 \(k\) 上执行更新
$$\varphi(k)\leftarrow \varphi(k)-\frac{\varphi(k)}{p}.$$
完成后，就得到了后续累加需要的完整欧拉函数表。
第二步遍历区间内每个 \(n\)。对固定的 \(n\)，代码检查所有满足 \(d^2\le n\) 的候选因子 \(d\)。一旦发现 \(d\mid n\)，就同时标记 \(d\) 和配对因子 \(n/d\)。整个区间扫描结束后，一个分母被标记，当且仅当它至少整除过区间内某个整数。
这一步就是在程序里构造集合 \(U\)。
最后，程序遍历全部 \(d\le 1909\) 的分母；如果该分母被标记，就把 \(\varphi(d)\) 加入答案。因为每个分母类只会被加入一次，所以实现精确对应了前面的几何结论：相同方向只保留一条边。
设 \(M=1909\)。欧拉函数筛法的时间复杂度是 \(O(M\log\log M)\)。标记因子的阶段中，对每个 \(n\in[1864,1909]\) 都会检查到 \(\sqrt n\) 为止，因此这部分总开销为
$$O\!\left(\sum_{n=1864}^{1909}\sqrt n\right),$$
也可以写成更常见的上界 \(O((N_2-N_1+1)\sqrt{N_2})\)。
最后一轮对已标记分母求和是 \(O(M)\)，额外空间也是 \(O(M)\)，分别用于存储欧拉函数表和标记数组。由于区间很短，而且 \(M\) 本身不大，这种直接枚举因子的实现已经足够高效。
Для каждого целого \(n\) обозначим через \(S_n\) правильный \(n\)-угольник в той ориентации, которая задана в условии. Требуется найти число сторон суммы Минковского
$$S_{1864}+S_{1865}+\cdots+S_{1909}.$$
Код показывает, что это не задача про явные координаты вершин. Чтобы узнать число сторон итогового многоугольника, нужно понять только одно: какие направления внешних нормалей вообще появляются на границе. После этого геометрия сводится к чистому арифметическому подсчету.
Главная идея состоит в том, чтобы заменить геометрию суммы Минковского объединением классов направлений, а затем посчитать эти классы с помощью функции Эйлера \(\varphi\).
Для выпуклого множества \(P\) его опорная функция равна \(h_P(u)=\max_{x\in P} u\cdot x\). Для суммы Минковского верно
$$h_{A+B}(u)=h_A(u)+h_B(u).$$
Когда направление \(u\) обходит окружность, переход от одной стороны выпуклого многоугольника к другой происходит именно там, где меняется опорное направление. Поэтому направления нормалей у суммы Минковского совпадают с объединением всех различных направлений нормалей, которые уже есть у слагаемых. Если несколько слагаемых имеют одну и ту же нормаль, это лишь удлиняет соответствующую сторону; новых сторон не возникает.
Если \(D(P)\) обозначает множество направлений внешних нормалей многоугольника \(P\), то
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{n=1864}^{1909} D(S_n),$$
и искомое число сторон равно мощности этого объединения.
При ориентации из условия внешние нормали \(S_n\) расположены на равномерно распределенных углах
$$D(S_n)=\left\{\frac{2\pi k}{n}: 0\le k \lt n\right\},$$
где углы понимаются по модулю \(2\pi\). Приведем дробь \(k/n\) к несократимому виду:
$$\frac{k}{n}=\frac{a}{d},\qquad \gcd(a,d)=1.$$
Число \(d\) и есть точный знаменатель данного направления, причем \(d\) всегда делит \(n\). Для каждого делителя \(d\mid n\) введем примитивный класс направлений
$$\Theta_d=\left\{\frac{2\pi a}{d}: 0\le a \lt d,\ \gcd(a,d)=1\right\}.$$
Его размер равен \(|\Theta_d|=\varphi(d)\). Разные значения \(d\) дают непересекающиеся классы, потому что у рационального угла единственный сокращенный знаменатель. Следовательно, направления одного правильного \(n\)-угольника раскладываются как
$$D(S_n)=\bigcup_{d\mid n}\Theta_d,$$
и их подсчет немедленно дает хорошо известное тождество
$$n=\sum_{d\mid n}\varphi(d).$$
В геометрическом смысле это означает: \(S_n\) содержит все примитивные направления, чей знаменатель делит \(n\).
Теперь соберем все знаменатели, которые встречаются хотя бы у одного многоугольника из интервала:
$$U=\left\{d\ge 1:\exists n\in[1864,1909],\ d\mid n\right\}.$$
Поскольку сумма Минковского просто объединяет множества направлений, имеем
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{d\in U}\Theta_d.$$
Классы \(\Theta_d\) не пересекаются, поэтому окончательная формула такова:
$$\boxed{N=\sum_{d\in U}\varphi(d)}$$
Именно это и вычисляют реализации на C++, Python и Java: отмечают все делители, встречающиеся хотя бы один раз между 1864 и 1909, а затем по одному разу добавляют тотенты всех отмеченных делителей.
Этот маленький пример полезен тем, что повторяет ту же логику, что и простые проверочные случаи. Треугольник дает классы знаменателей \(1\) и \(3\), квадрат дает \(1\), \(2\) и \(4\). Значит,
$$U=\{1,2,3,4\}.$$
Итоговый многоугольник имеет
$$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)=1+1+2+2=6$$
сторон. Знаменатель \(1\) присутствует у обоих слагаемых, но считается только один раз, потому что совпадающие направления сливаются в одну сторону суммы Минковского.
Реализации на C++, Python и Java напрямую следуют формуле выше. Они не строят явные координаты многоугольников, не складывают граничные векторы и не запускают отдельный геометрический алгоритм оболочки.
Сначала программа вычисляет \(\varphi(d)\) для всех \(1\le d\le 1909\) стандартным решетом. Инициализация берется как \(\varphi(d)=d\), а затем для каждого простого \(p\) на каждом кратном \(k\) выполняется обновление
$$\varphi(k)\leftarrow \varphi(k)-\frac{\varphi(k)}{p}.$$
После этого таблица значений функции Эйлера полностью готова.
Далее код перебирает все \(n\) от 1864 до 1909. Для каждого \(n\) проверяются все кандидаты \(d\), удовлетворяющие \(d^2\le n\). Если выполнено \(d\mid n\), то помечаются и \(d\), и сопряженный делитель \(n/d\). После обработки всего интервала знаменатель помечен тогда и только тогда, когда он делит хотя бы одно число из этого интервала.
Это и есть алгоритмическое построение множества \(U\).
На последнем шаге программа проходит по всем \(d\le 1909\) и прибавляет \(\varphi(d)\), если знаменатель \(d\) был помечен. Поскольку каждый класс знаменателя учитывается только один раз, реализация в точности воспроизводит геометрическое правило: одинаковые направления дают одну сторону, а не несколько.
Пусть \(M=1909\). Решето для функции Эйлера работает за \(O(M\log\log M)\). Этап пометки делителей проверяет все числа до \(\sqrt n\) для каждого \(n\in[1864,1909]\), поэтому его суммарная стоимость равна
$$O\!\left(\sum_{n=1864}^{1909}\sqrt n\right),$$
или, в стандартной форме верхней оценки, \(O((N_2-N_1+1)\sqrt{N_2})\).
Финальное суммирование по помеченным знаменателям занимает \(O(M)\), а память равна \(O(M)\) для таблицы тотентов и массива пометок. Поскольку сам интервал короткий, а \(M\) невелико, прямой перебор делителей здесь полностью достаточен.
لكل عدد صحيح \(n\)، نرمز بـ \(S_n\) إلى المضلع المنتظم ذي \(n\) أضلاع وفق التوجيه المثبّت في نص المسألة. المطلوب هو حساب عدد أضلاع مجموع Minkowski التالي:
$$S_{1864}+S_{1865}+\cdots+S_{1909}.$$
توضح الحلول البرمجية أن المسألة ليست مسألة إحداثيات صريحة. عدد أضلاع المضلع النهائي يتحدد فقط من خلال اتجاهات العموديات الخارجية التي تظهر على الحد. وما إن نرتب هذه الاتجاهات بحسب المقام بعد الاختزال، حتى يتحول السؤال كله إلى عملية عدٍّ عددية.
الفكرة الأساسية هي تحويل هندسة مجموع Minkowski إلى اتحاد لفئات من الاتجاهات، ثم عدّ تلك الفئات بواسطة دالة أويلر \(\varphi\).
لأي مجموعة محدبة \(P\)، تُعرَّف دالة الدعم بـ \(h_P(u)=\max_{x\in P} u\cdot x\). ويحقق مجموع Minkowski العلاقة
$$h_{A+B}(u)=h_A(u)+h_B(u).$$
عندما يدور الاتجاه \(u\) حول الدائرة، فإن انتقال حد المضلع المحدب من ضلع إلى الضلع التالي يحدث بالضبط عند تبدل اتجاهات الدعم. لذلك فإن اتجاهات عموديات الأضلاع في المجموع هي اتحاد الاتجاهات المختلفة الموجودة أصلًا في المضلعين أو المضلعات المكوِّنة. وإذا اشتركت عدة حدود في الاتجاه نفسه، فإن هذا يطيل الضلع الموافق في الناتج ولا يخلق ضلعًا جديدًا.
إذا رمزنا إلى مجموعة اتجاهات العموديات الخارجية للمضلع \(P\) بالرمز \(D(P)\)، فلدينا
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{n=1864}^{1909} D(S_n),$$
ومن ثم فإن عدد الأضلاع المطلوب يساوي حجم هذا الاتحاد.
مع التوجيه المعتمد في المسألة، تقع اتجاهات العموديات الخارجية لـ \(S_n\) عند الزوايا المتساوية التباعد
$$D(S_n)=\left\{\frac{2\pi k}{n}: 0\le k \lt n\right\},$$
مع فهم الزوايا بترديد \(2\pi\). الآن نختزل الكسر \(k/n\) إلى أبسط صورة:
$$\frac{k}{n}=\frac{a}{d},\qquad \gcd(a,d)=1.$$
حينئذ يكون \(d\) هو المقام الدقيق لهذا الاتجاه، وهو دائمًا قاسم للعدد \(n\). ولكل قاسم \(d\mid n\) نعرّف فئة الاتجاهات الأولية
$$\Theta_d=\left\{\frac{2\pi a}{d}: 0\le a \lt d,\ \gcd(a,d)=1\right\}.$$
عدد عناصر هذه الفئة هو \(|\Theta_d|=\varphi(d)\). والقيم المختلفة لـ \(d\) تعطي فئات متباينة، لأن كل زاوية نسبية لها مقام مختزل وحيد. لذا فإن مجموعة الاتجاهات في مضلع منتظم واحد تتحلل إلى
$$D(S_n)=\bigcup_{d\mid n}\Theta_d,$$
ومن عدّ هذه الاتجاهات نحصل على الهوية المعروفة
$$n=\sum_{d\mid n}\varphi(d).$$
والمعنى الهندسي لذلك أن \(S_n\) يحتوي كل اتجاه أولي مقامه يقسم \(n\).
نجمع الآن كل المقامات التي تظهر مرة واحدة على الأقل داخل المجال:
$$U=\left\{d\ge 1:\exists n\in[1864,1909],\ d\mid n\right\}.$$
وبما أن مجموع Minkowski لا يفعل هنا إلا توحيد مجموعات الاتجاهات، فإننا نحصل على
$$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{d\in U}\Theta_d.$$
ولأن الفئات \(\Theta_d\) متباينة، فإن عدد الأضلاع النهائي هو
$$\boxed{N=\sum_{d\in U}\varphi(d)}$$
وهذا بالضبط ما تحسبه تطبيقات C++ وPython وJava: تُعلَّم جميع القواسم التي تظهر لأي عدد بين 1864 و1909، ثم تُجمع قيمة \(\varphi(d)\) لكل مقام معلَّم مرة واحدة فقط.
هذا المثال الصغير مفيد لأنه يطابق الفكرة نفسها المستعملة في اختبارات التحقق البسيطة. المثلث يضيف فئتي المقام \(1\) و\(3\)، والمربع يضيف \(1\) و\(2\) و\(4\). إذن
$$U=\{1,2,3,4\}.$$
وبالتالي يكون عدد أضلاع المضلع الناتج
$$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)=1+1+2+2=6.$$
المقام \(1\) يظهر في كلا الحدّين، لكنه يُحسب مرة واحدة فقط، لأن الاتجاهات المتطابقة تندمج في ضلع واحد داخل مجموع Minkowski.
تتبع تطبيقات C++ وPython وJava الصيغة السابقة مباشرة. فهي لا تبني إحداثيات المضلعات صراحة، ولا تجمع متجهات الحدود، ولا تشغّل خوارزمية هندسية لبناء غلاف.
تبدأ الشيفرة بحساب \(\varphi(d)\) لكل \(1\le d\le 1909\) باستعمال غربال قياسي. نبدأ من \(\varphi(d)=d\)، ثم لكل عدد أولي \(p\) نطبّق على كل مضاعف \(k\) التحديث
$$\varphi(k)\leftarrow \varphi(k)-\frac{\varphi(k)}{p}.$$
بعد هذه الخطوة تصبح قيم دالة أويلر جاهزة للاستعمال في الجمع النهائي.
بعد ذلك تمر الشيفرة على كل \(n\) من 1864 إلى 1909. ولكل \(n\) تُفحَص جميع قيم \(d\) التي تحقق \(d^2\le n\). فإذا كان \(d\mid n\)، تُعلَّم كل من \(d\) و\(n/d\). وبعد إنهاء المجال كله يكون المقام معلَّمًا إذا وفقط إذا كان يقسم عددًا واحدًا على الأقل من أعداد المجال.
هذه هي الصياغة الحاسوبية لبناء المجموعة \(U\).
في النهاية تمر الشيفرة على جميع المقامات \(d\le 1909\)، وتضيف \(\varphi(d)\) كلما كان \(d\) معلَّمًا. وبما أن كل فئة مقام تُضاف مرة واحدة فقط، فإن التنفيذ يطابق تمامًا القاعدة الهندسية القائلة إن الاتجاهات المتكررة لا تزيد عدد الأضلاع.
لنكتب \(M=1909\). يعمل غربال دالة أويلر في زمن \(O(M\log\log M)\). أما مرحلة تعليم القواسم فتفحص جميع الأعداد حتى \(\sqrt n\) لكل \(n\in[1864,1909]\)، لذا يكون مجموع زمنها
$$O\!\left(\sum_{n=1864}^{1909}\sqrt n\right),$$
ويمكن كتابة ذلك أيضًا على الصورة المعتادة \(O((N_2-N_1+1)\sqrt{N_2})\).
أما المرور الأخير لجمع القيم المعلَّمة فتكلفته \(O(M)\)، واستهلاك الذاكرة هو \(O(M)\) لتخزين جدول \(\varphi\) ومصفوفة التعليم. وبما أن المجال قصير و\(M\) صغير، فإن هذا الفحص المباشر للقواسم كافٍ تمامًا.