Let
$$\mathcal{L}_n=\left\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}: \max(|x|,|y|)\le n\right\}.$$
A polar polygon is obtained by choosing lattice points from \(\mathcal{L}_n\), taking at most one vertex on each directed ray from the origin, and reading the chosen vertices in increasing polar angle. The geometric condition used by the implementations is that the origin must lie in the convex hull of the chosen vertices. Equivalently, the chosen directions must not all lie inside one closed half-plane through the origin.
The task is to compute the number \(P(n)\) of such polygons modulo
$$M=10^9+7.$$
The implementations also contain the checkpoints
$$P(1)=131,\qquad P(2)=1648531,\qquad P(3)\equiv 461288482 \pmod{M},\qquad P(343)\equiv 937293740 \pmod{M}.$$
The key simplification is to forget the exact coordinates first and classify vertices by direction. Every directed primitive ray carries a certain number of lattice points, and only that number matters for counting.
Every nonzero lattice point can be written uniquely as
$$t(a,b),\qquad t\ge 1,\qquad \gcd(a,b)=1,$$
where \((a,b)\) gives a primitive direction. Define the level of that direction by
$$k=\max(|a|,|b|).$$
The points on this directed ray that still lie in \(\mathcal{L}_n\) are exactly
$$t(a,b)\qquad\text{for}\qquad 1\le t\le \left\lfloor\frac{n}{k}\right\rfloor.$$
So the ray contributes
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor$$
available lattice points. A valid polygon can use at most one vertex on a fixed directed ray, because two points on the same ray are collinear with the origin and the nearer one cannot be an extreme vertex. Therefore one directed ray contributes exactly
$$1+w(k)$$
choices: choose nothing, or choose one of its \(w(k)\) lattice points.
Fix \(k\ge 1\). Primitive directions of level \(k\) are precisely the visible lattice points on the boundary of the square \(\max(|x|,|y|)=k\).
In one octant there are \(\varphi(k)\) such directions, so symmetry gives
$$8\varphi(k)$$
directed primitive rays on that shell, or
$$4\varphi(k)$$
opposite-direction pairs. Every pair on level \(k\) has the same weight \(w(k)=\lfloor n/k\rfloor\).
The weight depends only on the quotient \(\left\lfloor n/k\right\rfloor\), not on the direction itself. If that quotient is constant and equal to \(u\) for all \(k\) in an interval \([a,b]\), then the number of opposite pairs with weight \(u\) is
$$c(u)=4\sum_{k=a}^{b}\varphi(k).$$
Introduce the summatory totient function
$$\Phi(x)=\sum_{m\le x}\varphi(m).$$
Then every quotient block contributes
$$c(u)=4\bigl(\Phi(b)-\Phi(a-1)\bigr).$$
This is the reason the problem collapses to only \(O(\sqrt n)\) distinct blocks: the values of \(\left\lfloor n/k\right\rfloor\) repeat on long intervals.
Let the opposite pairs have weights \(w_1,\dots,w_m\). For one pair there are four types of choices:
For one pair the four possibilities are: choose nothing, choose one point on the first ray, choose one point on the opposite ray, or choose one point on each ray.
Hence one pair contributes
$$1+w_i+w_i+w_i^2=(1+w_i)^2.$$
If we define
$$H=\prod_{i=1}^{m}(1+w_i),$$
then the total weighted count of all ray selections is
$$T=H^2.$$
After quotient blocking, the same product becomes
$$H=\prod_{u}(u+1)^{c(u)}.$$
A selection fails precisely when all chosen directions lie in some closed semicircle. Count such bad selections by choosing their first selected boundary direction.
Fix one directed boundary ray with weight \(w_i\). We must choose a point on that boundary ray, giving \(w_i\) possibilities. Every other opposite pair contributes exactly one direction inside the following open semicircle, so it contributes a factor \(1+w_j\). The opposite boundary ray itself may be used or skipped, contributing another factor \(1+w_i\). Therefore the count anchored at this directed boundary is
$$w_i\prod_{j=1}^{m}(1+w_j)=w_iH.$$
Summing over both orientations of every opposite pair yields
$$2H\sum_{i=1}^{m}w_i.$$
However, the subset consisting of one point on both rays of the same opposite pair is counted twice, once from each boundary orientation. The total correction for these double counts is
$$\sum_{i=1}^{m} w_i^2.$$
Adding the empty selection gives
$$B=1+2HA_1-A_2,$$
where
$$A_1=\sum_{i=1}^{m} w_i,\qquad A_2=\sum_{i=1}^{m} w_i^2.$$
Therefore
$$P(n)=T-B=H^2-1-2HA_1+A_2.$$
Because all pairs in one block have the same weight \(u\), the two moments become
$$A_1=\sum_{u} c(u)\,u,\qquad A_2=\sum_{u} c(u)\,u^2.$$
Substituting into the previous formula gives the exact expression used by the implementations:
$$\boxed{P(n)\equiv \left(\prod_{u}(u+1)^{c(u)}\right)^2-1-2\left(\prod_{u}(u+1)^{c(u)}\right)\left(\sum_{u} c(u)\,u\right)+\sum_{u} c(u)\,u^2 \pmod{M}.}$$
For \(n=2\) there are only two shell levels:
$$\left\lfloor\frac{2}{1}\right\rfloor=2,\qquad \left\lfloor\frac{2}{2}\right\rfloor=1.$$
The level \(k=1\) shell contributes
$$4\varphi(1)=4$$
opposite pairs of weight \(2\), and the level \(k=2\) shell contributes
$$4\varphi(2)=4$$
opposite pairs of weight \(1\). Hence
$$H=(1+2)^4(1+1)^4=3^4\cdot 2^4=1296,$$
$$A_1=4\cdot 2+4\cdot 1=12,\qquad A_2=4\cdot 2^2+4\cdot 1^2=20.$$
So
$$P(2)=1296^2-1-2\cdot1296\cdot12+20=1648531,$$
which matches the checkpoint.
The C++, Python, and Java implementations all follow the same mathematical pipeline. First they choose a threshold near \(n^{2/3}\), compute \(\varphi(1),\dots,\varphi(B)\) with a sieve, and store the prefix values of \(\Phi(x)\) for every \(x\le B\).
For larger arguments they use memoized divide-block recursion based on the identity
$$\sum_{d=1}^{x}\varphi(d)\left\lfloor\frac{x}{d}\right\rfloor=\frac{x(x+1)}{2},$$
which leads to
$$\Phi(x)=\frac{x(x+1)}{2}-\sum_{i=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{i}\right\rfloor\right),$$
with equal quotient values grouped into one interval. That provides fast access to \(\Phi(x)\) on the boundaries of every quotient block.
Next the implementations enumerate the blocks on which \(\lfloor n/k\rfloor\) is constant, compute the multiplicity \(c(u)\) from two summatory-totient queries, and update the product \(H\) together with the first and second moments \(A_1\) and \(A_2\). The multiplicities are kept exactly for modular exponentiation, while the additive moments are accumulated modulo \(M\).
The C++ and Java implementations optionally split the quotient blocks into chunks, compute partial products and partial moments independently, and merge them at the end. The Python implementation performs the same reduction in one serial pass.
Let \(B\) denote the sieve cutoff, chosen on the order of \(n^{2/3}\). Building the totient table and the small prefix values costs \(O(B)\) time and \(O(B)\) memory. The memoized summatory-totient stage uses divisor-block grouping, so only the distinct quotient values need to be explored; this is the standard \(O(n^{2/3})\)-type approach for one top-level query. The final quotient-block traversal contributes only \(O(\sqrt n)\) additional arithmetic. In practice the totient stage dominates, and parallel block folding improves wall-clock time in the threaded implementations without changing the asymptotic bound.
Sei
$$\mathcal{L}_n=\left\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}: \max(|x|,|y|)\le n\right\}.$$
Ein Polarpolygon entsteht, indem man Gitterpunkte aus \(\mathcal{L}_n\) auswählt, auf jedem gerichteten Strahl vom Ursprung höchstens einen Eckpunkt zulässt und die gewählten Punkte nach wachsendem Polarwinkel anordnet. Die von den Implementierungen benutzte geometrische Bedingung lautet: Der Ursprung muss in der konvexen Hülle der gewählten Punkte liegen. Äquivalent dazu dürfen die gewählten Richtungen nicht vollständig in einer abgeschlossenen Halbebene durch den Ursprung liegen.
Gesucht ist also die Anzahl \(P(n)\) solcher Polygone modulo
$$M=10^9+7.$$
Als Kontrollwerte werden verwendet
$$P(1)=131,\qquad P(2)=1648531,\qquad P(3)\equiv 461288482 \pmod{M},\qquad P(343)\equiv 937293740 \pmod{M}.$$
Die entscheidende Vereinfachung besteht darin, zuerst die exakten Koordinaten zu vergessen und stattdessen nach Richtungen zu klassifizieren. Jeder primitive gerichtete Strahl trägt eine gewisse Anzahl von Gitterpunkten, und genau diese Anzahl steuert die Zählung.
Jeder von null verschiedene Gitterpunkt besitzt eine eindeutige Darstellung
$$t(a,b),\qquad t\ge 1,\qquad \gcd(a,b)=1,$$
wobei \((a,b)\) eine primitive Richtung beschreibt. Das zugehörige Niveau sei
$$k=\max(|a|,|b|).$$
Auf diesem gerichteten Strahl liegen genau die Punkte aus \(\mathcal{L}_n\), für die
$$1\le t\le \left\lfloor\frac{n}{k}\right\rfloor$$
gilt. Somit trägt der Strahl
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor$$
verfügbare Gitterpunkte. Ein gültiges Polygon kann auf einem festen gerichteten Strahl höchstens einen Eckpunkt benutzen, denn zwei Punkte auf demselben Strahl sind mit dem Ursprung kollinear und der nähere Punkt kann kein Extrempunkt sein. Daher liefert ein gerichteter Strahl genau
$$1+w(k)$$
Möglichkeiten: nichts wählen oder einen der \(w(k)\) Punkte wählen.
Fixiere \(k\ge 1\). Primitive Richtungen des Niveaus \(k\) sind genau die sichtbaren Gitterpunkte auf dem Rand des Quadrats \(\max(|x|,|y|)=k\).
In einem Oktanten gibt es \(\varphi(k)\) solche Richtungen, also insgesamt
$$8\varphi(k)$$
gerichtete primitive Strahlen auf dieser Schale beziehungsweise
$$4\varphi(k)$$
Paare entgegengesetzter Richtungen. Jedes dieser Paare besitzt das gleiche Gewicht \(w(k)=\lfloor n/k\rfloor\).
Das Gewicht hängt nur vom Quotienten \(\lfloor n/k\rfloor\) ab, nicht von der Richtung selbst. Ist dieser Quotient für alle \(k\) in einem Intervall \([a,b]\) konstant und gleich \(u\), dann ist die Anzahl der entgegengesetzten Paare mit Gewicht \(u\)
$$c(u)=4\sum_{k=a}^{b}\varphi(k).$$
Mit der summatorischen Phi-Funktion
$$\Phi(x)=\sum_{m\le x}\varphi(m)$$
wird daraus
$$c(u)=4\bigl(\Phi(b)-\Phi(a-1)\bigr).$$
Genau deshalb schrumpft das Problem auf nur \(O(\sqrt n)\) verschiedene Blöcke: Die Werte von \(\lfloor n/k\rfloor\) wiederholen sich auf langen Intervallen.
Seien \(w_1,\dots,w_m\) die Gewichte der Paare entgegengesetzter Richtungen. Für ein einzelnes Paar gibt es vier Typen von Entscheidungen:
Für ein einzelnes Paar gibt es vier Möglichkeiten: nichts wählen, einen Punkt auf dem ersten Strahl wählen, einen Punkt auf dem Gegenstrahl wählen oder auf beiden Strahlen je einen Punkt wählen.
Daher trägt ein Paar den Faktor
$$1+w_i+w_i+w_i^2=(1+w_i)^2.$$
Definiert man
$$H=\prod_{i=1}^{m}(1+w_i),$$
dann ist die gesamte gewichtete Zahl aller Strahl-Auswahlen
$$T=H^2.$$
Nach Quotientenblöcken geschrieben ergibt sich
$$H=\prod_{u}(u+1)^{c(u)}.$$
Eine Auswahl ist genau dann ungültig, wenn alle gewählten Richtungen in einem abgeschlossenen Halbkreis liegen. Solche schlechten Auswahlen zählen wir über ihre erste gewählte Randrichtung.
Fixiere einen gerichteten Randstrahl mit Gewicht \(w_i\). Auf diesem Randstrahl muss ein Punkt gewählt werden, also gibt es \(w_i\) Möglichkeiten. Jedes andere Paar liefert genau eine Richtung im folgenden offenen Halbkreis und damit den Faktor \(1+w_j\). Der entgegengesetzte Randstrahl selbst darf zusätzlich benutzt oder ausgelassen werden und liefert daher einen weiteren Faktor \(1+w_i\). Insgesamt erhält man für diesen verankerten Rand
$$w_i\prod_{j=1}^{m}(1+w_j)=w_iH.$$
Summiert über beide Orientierungen jedes entgegengesetzten Paares ergibt das
$$2H\sum_{i=1}^{m}w_i.$$
Dabei wird jedoch die Auswahl, die genau aus einem Punkt auf beiden Strahlen desselben Paares besteht, doppelt gezählt, nämlich einmal von jeder Randorientierung aus. Die nötige Korrektur ist also
$$\sum_{i=1}^{m} w_i^2.$$
Zusammen mit der leeren Auswahl folgt
$$B=1+2HA_1-A_2,$$
wobei
$$A_1=\sum_{i=1}^{m} w_i,\qquad A_2=\sum_{i=1}^{m} w_i^2.$$
Damit gilt
$$P(n)=T-B=H^2-1-2HA_1+A_2.$$
Da alle Paare innerhalb eines Blocks dasselbe Gewicht \(u\) besitzen, werden die beiden Momente zu
$$A_1=\sum_{u} c(u)\,u,\qquad A_2=\sum_{u} c(u)\,u^2.$$
Einsetzen liefert genau die Formel, die in den Implementierungen verwendet wird:
$$\boxed{P(n)\equiv \left(\prod_{u}(u+1)^{c(u)}\right)^2-1-2\left(\prod_{u}(u+1)^{c(u)}\right)\left(\sum_{u} c(u)\,u\right)+\sum_{u} c(u)\,u^2 \pmod{M}.}$$
Für \(n=2\) gibt es nur zwei Schalen:
$$\left\lfloor\frac{2}{1}\right\rfloor=2,\qquad \left\lfloor\frac{2}{2}\right\rfloor=1.$$
Die Schale \(k=1\) liefert
$$4\varphi(1)=4$$
Paare entgegengesetzter Richtungen mit Gewicht \(2\), und die Schale \(k=2\) liefert
$$4\varphi(2)=4$$
Paare mit Gewicht \(1\). Also
$$H=(1+2)^4(1+1)^4=3^4\cdot 2^4=1296,$$
$$A_1=4\cdot 2+4\cdot 1=12,\qquad A_2=4\cdot 2^2+4\cdot 1^2=20.$$
Daraus folgt
$$P(2)=1296^2-1-2\cdot1296\cdot12+20=1648531,$$
genau der Kontrollwert.
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Pipeline. Zuerst wird eine Schranke in der Größenordnung \(n^{2/3}\) gewählt, dann werden \(\varphi(1),\dots,\varphi(B)\) per Sieb berechnet und die Präfixwerte von \(\Phi(x)\) für alle \(x\le B\) gespeichert.
Für größere Argumente wird eine memoisiert berechnete Divisionsblock-Rekursion auf Basis der Identität
$$\sum_{d=1}^{x}\varphi(d)\left\lfloor\frac{x}{d}\right\rfloor=\frac{x(x+1)}{2}$$
verwendet. Daraus folgt
$$\Phi(x)=\frac{x(x+1)}{2}-\sum_{i=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{i}\right\rfloor\right),$$
wobei gleiche Quotientenwerte intervallweise zusammengefasst werden. So kann \(\Phi(x)\) schnell an den Rändern der Quotientenblöcke abgefragt werden.
Anschließend werden alle Blöcke mit konstantem \(\lfloor n/k\rfloor\) durchlaufen, aus zwei Summenwerten von \(\Phi\) die Vielfachheit \(c(u)\) bestimmt und daraus das Produkt \(H\) sowie die beiden Momente \(A_1\) und \(A_2\) aktualisiert. Die Blockvielfachheiten werden für die modulare Potenzierung exakt gehalten, die additiven Momente aber direkt modulo \(M\) aufsummiert.
Die C++- und Java-Implementierungen können die Quotientenblöcke in unabhängige Teilstücke zerlegen, partielle Produkte und Momente parallel berechnen und am Ende zusammenführen. Die Python-Implementierung führt dieselbe Reduktion seriell aus.
Sei \(B\) die Siebgrenze, also von Größenordnung \(n^{2/3}\). Das Erzeugen der Totient-Tabelle und der kleinen Präfixwerte kostet \(O(B)\) Zeit und \(O(B)\) Speicher. Die memoisiert berechnete summatorische Phi-Funktion nutzt Divisionsblöcke, sodass nur die verschiedenen Quotientenwerte betrachtet werden müssen; das ist der klassische \(O(n^{2/3})\)-artige Ansatz für eine einzelne Top-Level-Abfrage. Die abschließende Traversierung der Quotientenblöcke benötigt nur noch \(O(\sqrt n)\) zusätzliche Arithmetik. Praktisch dominiert daher die Totient-Stufe, und die Parallelisierung verkürzt nur die Laufzeit der Blockfaltung, nicht aber die asymptotische Schranke.
Şunu tanımlayalım:
$$\mathcal{L}_n=\left\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}: \max(|x|,|y|)\le n\right\}.$$
Bir polar çokgen, \(\mathcal{L}_n\) içinden kafes noktaları seçilip, orijinden çıkan her yönlü ışın üzerinde en fazla bir köşe bırakılarak ve seçilen noktalar artan kutupsal açıya göre sıralanarak elde edilir. Uygulamaların kullandığı geometrik koşul şudur: Orijin seçilen köşelerin dışbükey zarfının içinde kalmalıdır. Bunun eşdeğeri, seçilen yönlerin orijinden geçen tek bir kapalı yarı düzlem içine sığmamasıdır.
Dolayısıyla amaç, bu tür çokgenlerin sayısı olan \(P(n)\) değerini
$$M=10^9+7$$
modunda hesaplamaktır.
Uygulamalardaki kontrol değerleri şunlardır:
$$P(1)=131,\qquad P(2)=1648531,\qquad P(3)\equiv 461288482 \pmod{M},\qquad P(343)\equiv 937293740 \pmod{M}.$$
Temel fikir, önce kesin koordinatları unutup noktaları yalnızca yönlerine göre sınıflandırmaktır. Her ilkel yönlü ışın belirli sayıda kafes noktası taşır ve sayımı belirleyen tek şey de bu sayıdır.
Sıfırdan farklı her kafes noktası tekil olarak
$$t(a,b),\qquad t\ge 1,\qquad \gcd(a,b)=1$$
şeklinde yazılır; burada \((a,b)\) ilkel bir yön verir. Bu yönün seviyesi
$$k=\max(|a|,|b|)$$
olsun. Bu yönlü ışın üzerinde \(\mathcal{L}_n\) içinde kalan noktalar tam olarak
$$1\le t\le \left\lfloor\frac{n}{k}\right\rfloor$$
koşulunu sağlayanlardır. O halde ışının taşıdığı kullanılabilir nokta sayısı
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor$$
olur. Geçerli bir çokgen, sabit bir yönlü ışın üzerinde en fazla bir köşe kullanabilir; çünkü aynı ışın üzerindeki iki nokta orijinle doğrusal olur ve içte kalan nokta uç köşe olamaz. Bu yüzden bir yönlü ışın tam olarak
$$1+w(k)$$
seçenek verir: hiç nokta seçmemek ya da mevcut \(w(k)\) noktadan birini seçmek.
\(k\ge 1\) sabit olsun. Seviyesi \(k\) olan ilkel yönler, \(\max(|x|,|y|)=k\) karesinin sınırındaki görünür kafes noktalarıdır.
Bir oktantta \(\varphi(k)\) tane böyle yön vardır; simetriyle toplam
$$8\varphi(k)$$
yönlü ilkel ışın, yani
$$4\varphi(k)$$
zıt yön çifti elde edilir. Bu kabuktaki her çiftin ağırlığı aynıdır:
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor.$$
Ağırlık yalnızca \(\lfloor n/k\rfloor\) bölümüne bağlıdır; yönün kendisine bağlı değildir. Bu bölüm \([a,b]\) aralığındaki tüm \(k\) değerleri için sabit ve \(u\) olsun. O zaman ağırlığı \(u\) olan zıt yön çiftlerinin sayısı
$$c(u)=4\sum_{k=a}^{b}\varphi(k)$$
olur. Burada toplam totient fonksiyonunu
$$\Phi(x)=\sum_{m\le x}\varphi(m)$$
olarak tanımlarsak
$$c(u)=4\bigl(\Phi(b)-\Phi(a-1)\bigr)$$
elde edilir. Böylece problem yalnızca \(O(\sqrt n)\) kadar farklı bloğa iner; çünkü \(\lfloor n/k\rfloor\) uzun aralıklarda tekrar eder.
Zıt yön çiftlerinin ağırlıkları \(w_1,\dots,w_m\) olsun. Tek bir çift için dört tür seçim vardır:
Tek bir çift için dört olasılık vardır: hiç seçim yapmamak, birinci ışından bir nokta seçmek, karşı ışından bir nokta seçmek ya da iki ışından da birer nokta seçmek.
Dolayısıyla bir çiftin katkısı
$$1+w_i+w_i+w_i^2=(1+w_i)^2$$
olur. Eğer
$$H=\prod_{i=1}^{m}(1+w_i)$$
tanımlanırsa, tüm ışın seçimlerinin ağırlıklı toplamı
$$T=H^2$$
olur. Bölüm blokları cinsinden aynı çarpım
$$H=\prod_{u}(u+1)^{c(u)}$$
şeklinde yazılır.
Bir seçim tam olarak, bütün seçilen yönler bir kapalı yarım çember içinde kaldığında başarısız olur. Bu kötü seçimleri, ilk seçilmiş sınır yönüne göre sayarız.
Ağırlığı \(w_i\) olan bir yönlü sınır ışınını sabitleyelim. Bu ışın üzerinde mutlaka bir nokta seçilmelidir; bunun için \(w_i\) seçenek vardır. Diğer her zıt yön çifti, izleyen açık yarım çember içinde tam bir ışın verdiği için \((1+w_j)\) katsayısı getirir. Karşı sınır ışını seçilebilir ya da boş bırakılabilir; onun katkısı da \((1+w_i)\) olur. Böylece bu sınır yönüne ankrajlanan sayı
$$w_i\prod_{j=1}^{m}(1+w_j)=w_iH$$
olur. Bunu her zıt çiftin iki yönü üzerinde toplarsak
$$2H\sum_{i=1}^{m}w_i$$
elde ederiz. Ancak aynı zıt çiftin iki ışınından da birer nokta seçilen altküme iki kez sayılmış olur; biri ilk sınır, diğeri ikinci sınır olarak görünür. Bu çift sayımı düzeltmek için
$$\sum_{i=1}^{m} w_i^2$$
çıkarılır. Boş seçimi de ekleyince
$$B=1+2HA_1-A_2,$$
burada
$$A_1=\sum_{i=1}^{m} w_i,\qquad A_2=\sum_{i=1}^{m} w_i^2.$$
Sonuç olarak
$$P(n)=T-B=H^2-1-2HA_1+A_2$$
olur.
Aynı bloktaki tüm çiftlerin ağırlığı \(u\) olduğundan, iki moment
$$A_1=\sum_{u} c(u)\,u,\qquad A_2=\sum_{u} c(u)\,u^2$$
şeklini alır. Böylece uygulamalarda kullanılan tam ifade
$$\boxed{P(n)\equiv \left(\prod_{u}(u+1)^{c(u)}\right)^2-1-2\left(\prod_{u}(u+1)^{c(u)}\right)\left(\sum_{u} c(u)\,u\right)+\sum_{u} c(u)\,u^2 \pmod{M}.}$$
\(n=2\) için yalnızca iki kabuk seviyesi vardır:
$$\left\lfloor\frac{2}{1}\right\rfloor=2,\qquad \left\lfloor\frac{2}{2}\right\rfloor=1.$$
\(k=1\) kabuğu
$$4\varphi(1)=4$$
adet ağırlığı \(2\) olan zıt yön çifti, \(k=2\) kabuğu ise
$$4\varphi(2)=4$$
adet ağırlığı \(1\) olan zıt yön çifti verir. O halde
$$H=(1+2)^4(1+1)^4=3^4\cdot 2^4=1296,$$
$$A_1=4\cdot 2+4\cdot 1=12,\qquad A_2=4\cdot 2^2+4\cdot 1^2=20.$$
Buradan
$$P(2)=1296^2-1-2\cdot1296\cdot12+20=1648531$$
çıkar ve bu kontrol değeriyle tam uyumludur.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Önce \(n^{2/3}\) mertebesinde bir eşik seçilir, sonra \(\varphi(1),\dots,\varphi(B)\) bir elek ile hesaplanır ve \(x\le B\) için \(\Phi(x)\) ön-ek değerleri saklanır.
Daha büyük argümanlar için
$$\sum_{d=1}^{x}\varphi(d)\left\lfloor\frac{x}{d}\right\rfloor=\frac{x(x+1)}{2}$$
özdeşliğine dayanan, belleklemeli ve bölme-bloklu bir özyineleme kullanılır. Buradan
$$\Phi(x)=\frac{x(x+1)}{2}-\sum_{i=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{i}\right\rfloor\right)$$
elde edilir; eşit bölüm değerleri tek bir aralık halinde gruplanır. Bu sayede blok sınırlarında \(\Phi(x)\) hızlı sorgulanır.
Ardından \(\lfloor n/k\rfloor\) sabit kalan bloklar dolaşılır, iki toplam-totient sorgusundan \(c(u)\) bulunur ve bunlarla \(H\), \(A_1\) ve \(A_2\) güncellenir. Üstel ifadelerde blok çoklukları tam olarak korunur; doğrusal ve ikinci dereceden momentler ise doğrudan \(M\) modunda toplanır.
C++ ve Java sürümleri blokları bağımsız parçalara bölüp kısmi çarpım ve toplamları paralel hesaplayabilir. Python sürümü aynı indirgemeyi tek geçişte seri olarak yapar.
\(B\) elek eşiği olsun ve büyüklüğü \(n^{2/3}\) mertebesinde seçilsin. Totient tablosunu ve küçük ön-ekleri kurmak \(O(B)\) zaman ve \(O(B)\) bellek ister. Belleklemeli toplam-totient aşaması, tamsayı bölme bloklarını kullandığı için yalnızca farklı bölüm değerlerini ziyaret eder; bu da tek bir ana sorgu için standart \(O(n^{2/3})\)-tipi yaklaşımdır. Son blok taraması yalnızca \(O(\sqrt n)\) ek aritmetik getirir. Pratikte baskın maliyet toplam-totient aşamasıdır; çok iş parçacıklı sürümlerde paralel katlama duvar saati süresini düşürür ama asimptotik sınırı değiştirmez.
Definimos
$$\mathcal{L}_n=\left\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}: \max(|x|,|y|)\le n\right\}.$$
Un polígono polar se obtiene eligiendo puntos de la red dentro de \(\mathcal{L}_n\), permitiendo como mucho un vértice en cada semirrecta dirigida que sale del origen, y ordenando los vértices elegidos por ángulo polar creciente. La condición geométrica usada por las implementaciones es que el origen debe pertenecer a la envolvente convexa de los vértices elegidos. De manera equivalente, las direcciones elegidas no pueden quedar contenidas por completo en un único semiplano cerrado que pase por el origen.
La tarea consiste en calcular el número \(P(n)\) de tales polígonos módulo
$$M=10^9+7.$$
Los valores de comprobación incluidos en las implementaciones son
$$P(1)=131,\qquad P(2)=1648531,\qquad P(3)\equiv 461288482 \pmod{M},\qquad P(343)\equiv 937293740 \pmod{M}.$$
La simplificación principal consiste en olvidar primero las coordenadas exactas y clasificar únicamente por dirección. Cada semirrecta primitiva dirigida lleva un cierto número de puntos de la red, y solo ese número interviene en el conteo.
Cada punto no nulo de la red se escribe de forma única como
$$t(a,b),\qquad t\ge 1,\qquad \gcd(a,b)=1,$$
donde \((a,b)\) describe una dirección primitiva. Definimos su nivel como
$$k=\max(|a|,|b|).$$
Los puntos de esa semirrecta dirigida que permanecen dentro de \(\mathcal{L}_n\) son exactamente aquellos con
$$1\le t\le \left\lfloor\frac{n}{k}\right\rfloor.$$
Por tanto, la semirrecta aporta
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor$$
puntos disponibles. Un polígono válido puede usar como máximo un vértice en una semirrecta dirigida fija, porque dos puntos sobre la misma semirrecta son colineales con el origen y el más cercano no puede ser un vértice extremo. Así, una semirrecta dirigida aporta exactamente
$$1+w(k)$$
opciones: no elegir nada o elegir uno de sus \(w(k)\) puntos.
Fijemos \(k\ge 1\). Las direcciones primitivas de nivel \(k\) son precisamente los puntos visibles de la red sobre la frontera del cuadrado \(\max(|x|,|y|)=k\).
En un octante hay \(\varphi(k)\) direcciones de este tipo, de modo que por simetría aparecen
$$8\varphi(k)$$
semirrectas primitivas dirigidas en total, o lo que es lo mismo,
$$4\varphi(k)$$
pares de direcciones opuestas. Todos los pares de la capa \(k\) tienen el mismo peso \(w(k)=\lfloor n/k\rfloor\).
El peso depende solo del cociente \(\lfloor n/k\rfloor\), no de la dirección concreta. Si ese cociente es constante e igual a \(u\) para todos los \(k\) de un intervalo \([a,b]\), entonces el número de pares opuestos con peso \(u\) es
$$c(u)=4\sum_{k=a}^{b}\varphi(k).$$
Introducimos la función sumatoria del totiente
$$\Phi(x)=\sum_{m\le x}\varphi(m).$$
Con ella, cada bloque de cociente aporta
$$c(u)=4\bigl(\Phi(b)-\Phi(a-1)\bigr).$$
Ese es el motivo por el que el problema se reduce a solo \(O(\sqrt n)\) bloques distintos: los valores de \(\lfloor n/k\rfloor\) se repiten en intervalos largos.
Sean \(w_1,\dots,w_m\) los pesos de los pares de direcciones opuestas. Para un solo par existen cuatro tipos de elección:
Para un solo par hay cuatro posibilidades: no elegir nada, elegir un punto en el primer rayo, elegir un punto en el rayo opuesto o elegir un punto en cada rayo.
Por lo tanto, la contribución de un par es
$$1+w_i+w_i+w_i^2=(1+w_i)^2.$$
Si definimos
$$H=\prod_{i=1}^{m}(1+w_i),$$
entonces el conteo ponderado total de todas las selecciones de rayos es
$$T=H^2.$$
En términos de bloques de cociente, el mismo producto se escribe como
$$H=\prod_{u}(u+1)^{c(u)}.$$
Una selección falla exactamente cuando todas las direcciones elegidas quedan dentro de un semicírculo cerrado. Para contarlas, fijamos la primera dirección de frontera seleccionada.
Tomemos un rayo de frontera dirigido con peso \(w_i\). Hay que escoger un punto sobre él, así que aporta \(w_i\) posibilidades. Cada uno de los demás pares aporta exactamente una dirección dentro del semicírculo abierto que sigue a esa frontera y, por tanto, contribuye con un factor \(1+w_j\). El rayo opuesto de frontera puede elegirse o no elegirse, lo cual aporta otro factor \(1+w_i\). Por consiguiente, el conteo anclado en esa frontera dirigida es
$$w_i\prod_{j=1}^{m}(1+w_j)=w_iH.$$
Al sumar sobre las dos orientaciones de cada par opuesto obtenemos
$$2H\sum_{i=1}^{m}w_i.$$
Sin embargo, el subconjunto formado por un punto en ambos rayos del mismo par opuesto queda contado dos veces, una desde cada orientación de frontera. La corrección total de esa doble cuenta es
$$\sum_{i=1}^{m} w_i^2.$$
Incluyendo el subconjunto vacío se llega a
$$B=1+2HA_1-A_2,$$
donde
$$A_1=\sum_{i=1}^{m} w_i,\qquad A_2=\sum_{i=1}^{m} w_i^2.$$
Así pues,
$$P(n)=T-B=H^2-1-2HA_1+A_2.$$
Como todos los pares de un mismo bloque tienen peso \(u\), los dos momentos se convierten en
$$A_1=\sum_{u} c(u)\,u,\qquad A_2=\sum_{u} c(u)\,u^2.$$
Al sustituir se obtiene exactamente la expresión usada por las implementaciones:
$$\boxed{P(n)\equiv \left(\prod_{u}(u+1)^{c(u)}\right)^2-1-2\left(\prod_{u}(u+1)^{c(u)}\right)\left(\sum_{u} c(u)\,u\right)+\sum_{u} c(u)\,u^2 \pmod{M}.}$$
Para \(n=2\) solo aparecen dos niveles de capa:
$$\left\lfloor\frac{2}{1}\right\rfloor=2,\qquad \left\lfloor\frac{2}{2}\right\rfloor=1.$$
La capa \(k=1\) aporta
$$4\varphi(1)=4$$
pares opuestos de peso \(2\), mientras que la capa \(k=2\) aporta
$$4\varphi(2)=4$$
pares opuestos de peso \(1\). Entonces
$$H=(1+2)^4(1+1)^4=3^4\cdot 2^4=1296,$$
$$A_1=4\cdot 2+4\cdot 1=12,\qquad A_2=4\cdot 2^2+4\cdot 1^2=20.$$
Por lo tanto,
$$P(2)=1296^2-1-2\cdot1296\cdot12+20=1648531,$$
en acuerdo exacto con el valor de comprobación.
Las implementaciones en C++, Python y Java siguen la misma tubería matemática. Primero eligen un umbral del orden de \(n^{2/3}\), calculan \(\varphi(1),\dots,\varphi(B)\) con una criba y guardan los prefijos de \(\Phi(x)\) para todo \(x\le B\).
Para valores mayores usan una recursión memoizada por bloques de división basada en la identidad
$$\sum_{d=1}^{x}\varphi(d)\left\lfloor\frac{x}{d}\right\rfloor=\frac{x(x+1)}{2},$$
que conduce a
$$\Phi(x)=\frac{x(x+1)}{2}-\sum_{i=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{i}\right\rfloor\right),$$
agrupando en un mismo intervalo los índices con igual cociente. Así se obtienen rápidamente los valores de \(\Phi(x)\) en los extremos de todos los bloques.
Después se enumeran los bloques donde \(\lfloor n/k\rfloor\) es constante, se calcula la multiplicidad \(c(u)\) con dos consultas a la sumatoria del totiente y se actualizan el producto \(H\) y los momentos \(A_1\) y \(A_2\). Las multiplicidades se conservan exactamente para la exponenciación modular, mientras que los momentos aditivos se reducen módulo \(M\).
Las versiones de C++ y Java pueden repartir los bloques entre varios trabajadores y combinar al final productos y sumas parciales. La versión de Python realiza la misma reducción de manera secuencial.
Sea \(B\) el corte de la criba, elegido del orden de \(n^{2/3}\). Construir la tabla de totientes y los prefijos pequeños cuesta \(O(B)\) tiempo y \(O(B)\) memoria. La etapa memoizada de la sumatoria del totiente usa bloques de división entera, de modo que solo explora los valores distintos del cociente; esa es la estrategia estándar de tipo \(O(n^{2/3})\) para una consulta principal. El recorrido final de bloques añade solo \(O(\sqrt n)\) operaciones aritméticas. En la práctica domina la fase de totientes, y el paralelismo en C++ y Java mejora el tiempo de pared sin cambiar el orden asintótico.
定义
$$\mathcal{L}_n=\left\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}: \max(|x|,|y|)\le n\right\}.$$
所谓极角多边形，可以理解为从 \(\mathcal{L}_n\) 中挑选一些格点，并要求从原点出发的每一条有向射线上至多选取一个顶点，然后把这些顶点按极角从小到大连接起来。实现采用的几何判据是：原点必须落在所选顶点的凸包内。等价地说，所有被选中的方向不能全部落在某一个经过原点的闭半平面里。
因此问题就是计算这类多边形的个数 \(P(n)\)，结果按
$$M=10^9+7$$
取模。
实现中还写入了若干校验值：
$$P(1)=131,\qquad P(2)=1648531,\qquad P(3)\equiv 461288482 \pmod{M},\qquad P(343)\equiv 937293740 \pmod{M}.$$
关键化简在于先不看具体坐标，而只看方向。每一条原始有向射线上可选的格点个数是有限的，而计数最终只依赖这个个数。
每个非零格点都能唯一写成
$$t(a,b),\qquad t\ge 1,\qquad \gcd(a,b)=1,$$
其中 \((a,b)\) 给出一条原始方向。定义该方向的层级为
$$k=\max(|a|,|b|).$$
这条有向射线上落在 \(\mathcal{L}_n\) 内的点，正好对应于
$$1\le t\le \left\lfloor\frac{n}{k}\right\rfloor.$$
因此，这条射线一共携带
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor$$
个可选格点。一个有效多边形在同一条有向射线上最多只能放一个顶点，因为同射线上的两个点与原点共线，较近的那个不可能成为凸包上的极点。所以，一条有向射线恰好贡献
$$1+w(k)$$
种选择：要么不选，要么从这 \(w(k)\) 个点里选一个。
固定 \(k\ge 1\)。层级为 \(k\) 的原始方向，正是边界 \(\max(|x|,|y|)=k\) 上那些与原点可见的格点方向。
在一个八分区里，这样的方向有 \(\varphi(k)\) 个，所以利用对称性，整条方形边界上一共有
$$8\varphi(k)$$
条有向原始射线，也就是
$$4\varphi(k)$$
对相反方向。该壳层内的每一对相反方向都具有相同权重
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor.$$
权重只依赖于商 \(\lfloor n/k\rfloor\)，与具体方向无关。若对区间 \([a,b]\) 内的所有 \(k\)，这个商都等于同一个值 \(u\)，那么权重为 \(u\) 的相反方向对数量就是
$$c(u)=4\sum_{k=a}^{b}\varphi(k).$$
记 totient 的前缀和为
$$\Phi(x)=\sum_{m\le x}\varphi(m).$$
于是分块贡献可以写成
$$c(u)=4\bigl(\Phi(b)-\Phi(a-1)\bigr).$$
这一步说明了为什么问题只剩下 \(O(\sqrt n)\) 个不同块：\(\lfloor n/k\rfloor\) 的值会在较长区间上重复出现。
设全部相反方向对的权重为 \(w_1,\dots,w_m\)。对第 \(i\) 对来说，一共有四种情形：
对一对相反方向来说，一共有四种情况：都不选，只选第一条射线上的一点，只选相反射线上的一点，或者两条射线各选一点。
因此这一对的总贡献是
$$1+w_i+w_i+w_i^2=(1+w_i)^2.$$
定义
$$H=\prod_{i=1}^{m}(1+w_i),$$
那么全部选择的加权总数就是
$$T=H^2.$$
按整除分块改写后，有
$$H=\prod_{u}(u+1)^{c(u)}.$$
一个选择失败，当且仅当所有被选方向都落在某个闭半圆内。对这类坏选择，可以按“第一个被选中的边界方向”来计数。
固定一条边界有向射线，其权重为 \(w_i\)。这条边界上必须选一个点，因此有 \(w_i\) 种办法。对于其余每一对相反方向，在这条边界之后的开半圆里恰好只有一个方向可用，所以它们各自贡献因子 \(1+w_j\)。与之相对的另一条边界射线可以选也可以不选，因此再贡献一个 \(1+w_i\)。于是，以这条有向边界为锚点的计数为
$$w_i\prod_{j=1}^{m}(1+w_j)=w_iH.$$
对每一对相反方向的两个朝向都求和，得到
$$2H\sum_{i=1}^{m}w_i.$$
不过，如果只在同一对相反射线上各选一个点，这个集合会被两次统计，因为它既可以从一个边界方向出发计数，也可以从另一个边界方向出发计数。需要减去的重复量正是
$$\sum_{i=1}^{m} w_i^2.$$
再把空集算进去，就得到
$$B=1+2HA_1-A_2,$$
其中
$$A_1=\sum_{i=1}^{m} w_i,\qquad A_2=\sum_{i=1}^{m} w_i^2.$$
所以最终有
$$P(n)=T-B=H^2-1-2HA_1+A_2.$$
因为同一块中的所有相反方向对都拥有相同权重 \(u\)，所以上面的两个矩可以写成
$$A_1=\sum_{u} c(u)\,u,\qquad A_2=\sum_{u} c(u)\,u^2.$$
代回去以后，就得到实现真正计算的闭式：
$$\boxed{P(n)\equiv \left(\prod_{u}(u+1)^{c(u)}\right)^2-1-2\left(\prod_{u}(u+1)^{c(u)}\right)\left(\sum_{u} c(u)\,u\right)+\sum_{u} c(u)\,u^2 \pmod{M}.}$$
当 \(n=2\) 时，只有两层：
$$\left\lfloor\frac{2}{1}\right\rfloor=2,\qquad \left\lfloor\frac{2}{2}\right\rfloor=1.$$
层 \(k=1\) 提供
$$4\varphi(1)=4$$
对权重为 \(2\) 的相反方向；层 \(k=2\) 提供
$$4\varphi(2)=4$$
对权重为 \(1\) 的相反方向。于是
$$H=(1+2)^4(1+1)^4=3^4\cdot 2^4=1296,$$
$$A_1=4\cdot 2+4\cdot 1=12,\qquad A_2=4\cdot 2^2+4\cdot 1^2=20.$$
因此
$$P(2)=1296^2-1-2\cdot1296\cdot12+20=1648531,$$
与校验值完全一致。
C++、Python 和 Java 实现遵循同一条数学流程。首先选取一个大约为 \(n^{2/3}\) 的阈值，用筛法求出 \(\varphi(1),\dots,\varphi(B)\)，并保存所有 \(x\le B\) 的 \(\Phi(x)\) 前缀值。
对更大的参数，程序使用基于下列恒等式的记忆化整除分块递推：
$$\sum_{d=1}^{x}\varphi(d)\left\lfloor\frac{x}{d}\right\rfloor=\frac{x(x+1)}{2}.$$
由此推出
$$\Phi(x)=\frac{x(x+1)}{2}-\sum_{i=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{i}\right\rfloor\right),$$
再把相同商值的项合并成一个区间。这样就能快速得到每个整除分块边界上的 \(\Phi(x)\)。
接着，程序枚举所有 \(\lfloor n/k\rfloor\) 保持常数的区间，用两次前缀 totient 查询得到块重数 \(c(u)\)，再更新乘积 \(H\) 以及两个矩 \(A_1,A_2\)。块重数在模幂时按精确值使用，而两个加法型矩则直接按 \(M\) 取模累加。
C++ 和 Java 版本还能把这些分块拆给多个工作线程，分别算出局部乘积与局部矩后再合并。Python 版本执行的是同样的归约，只是串行完成。
记筛法阈值为 \(B\)，其规模约为 \(n^{2/3}\)。建立 totient 表和小范围前缀和需要 \(O(B)\) 时间与 \(O(B)\) 空间。记忆化的 totient 前缀求值使用整除分块，因此只访问不同的商值；在标准分析下，这对应于单次主查询的 \(O(n^{2/3})\) 级别方法。最后的分块遍历只增加 \(O(\sqrt n)\) 的算术量。实际运行中主导成本仍是 totient 阶段，而并行化只改善多线程版本的实际耗时，不改变渐近复杂度。
Обозначим
$$\mathcal{L}_n=\left\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}: \max(|x|,|y|)\le n\right\}.$$
Полярный многоугольник получается так: выбираются точки решетки из \(\mathcal{L}_n\), на каждом направленном луче из начала координат допускается не более одной вершины, а затем выбранные точки упорядочиваются по возрастанию полярного угла. Геометрический критерий, который используют реализации, таков: начало координат должно лежать внутри выпуклой оболочки выбранных вершин. Эквивалентно, все выбранные направления не могут целиком помещаться в одну замкнутую полуплоскость, проходящую через начало координат.
Нужно вычислить число таких многоугольников \(P(n)\) по модулю
$$M=10^9+7.$$
В реализациях также зашиты контрольные значения
$$P(1)=131,\qquad P(2)=1648531,\qquad P(3)\equiv 461288482 \pmod{M},\qquad P(343)\equiv 937293740 \pmod{M}.$$
Главное упрощение состоит в том, чтобы сначала забыть о точных координатах и классифицировать вершины только по направлениям. Каждый примитивный направленный луч несет некоторое число решетчатых точек, и именно это число определяет подсчет.
Любая ненулевая точка решетки единственным образом записывается в виде
$$t(a,b),\qquad t\ge 1,\qquad \gcd(a,b)=1,$$
где \((a,b)\) задает примитивное направление. Пусть уровень этого направления равен
$$k=\max(|a|,|b|).$$
Точки на данном направленном луче, остающиеся внутри \(\mathcal{L}_n\), соответствуют точно тем \(t\), для которых
$$1\le t\le \left\lfloor\frac{n}{k}\right\rfloor.$$
Значит, луч содержит
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor$$
доступных точек. Корректный многоугольник может использовать не более одной вершины на фиксированном направленном луче, потому что две точки на одном луче коллинеарны с началом координат, а более близкая из них не может быть крайней вершиной. Следовательно, один направленный луч дает ровно
$$1+w(k)$$
вариантов: ничего не выбрать либо выбрать одну из \(w(k)\) точек.
Зафиксируем \(k\ge 1\). Примитивные направления уровня \(k\) - это в точности видимые точки решетки на границе квадрата \(\max(|x|,|y|)=k\).
В одном октанте таких направлений \(\varphi(k)\), поэтому по симметрии всего имеется
$$8\varphi(k)$$
направленных примитивных лучей, то есть
$$4\varphi(k)$$
пар противоположных направлений. Все пары на уровне \(k\) имеют один и тот же вес \(w(k)=\lfloor n/k\rfloor\).
Вес зависит только от частного \(\lfloor n/k\rfloor\), а не от конкретного направления. Если это частное постоянно и равно \(u\) для всех \(k\) из интервала \([a,b]\), то число противоположных пар веса \(u\) равно
$$c(u)=4\sum_{k=a}^{b}\varphi(k).$$
Введем сумматор функции Эйлера
$$\Phi(x)=\sum_{m\le x}\varphi(m).$$
Тогда вклад блока записывается так:
$$c(u)=4\bigl(\Phi(b)-\Phi(a-1)\bigr).$$
Именно поэтому задача сжимается до \(O(\sqrt n)\) различных блоков: значения \(\lfloor n/k\rfloor\) повторяются на длинных промежутках.
Пусть веса противоположных пар равны \(w_1,\dots,w_m\). Для одной пары возможны четыре типа выбора:
Для одной пары есть четыре возможности: ничего не выбрать, выбрать одну точку на первом луче, выбрать одну точку на противоположном луче или выбрать по одной точке на обоих лучах.
Поэтому вклад одной пары равен
$$1+w_i+w_i+w_i^2=(1+w_i)^2.$$
Если обозначить
$$H=\prod_{i=1}^{m}(1+w_i),$$
то общее взвешенное число всех выборов лучей равно
$$T=H^2.$$
После группировки по блокам частных тот же множитель принимает вид
$$H=\prod_{u}(u+1)^{c(u)}.$$
Выбор плох тогда и только тогда, когда все выбранные направления лежат в некотором замкнутом полуокружности. Посчитаем такие выборы по первой выбранной граничной направляющей.
Зафиксируем один направленный граничный луч веса \(w_i\). На нем обязательно нужно выбрать точку, что дает \(w_i\) вариантов. Каждая из остальных противоположных пар дает ровно одно направление внутри следующей открытой полуокружности, а значит вносит множитель \(1+w_j\). Сам противоположный граничный луч можно выбрать или пропустить, так что он дает еще множитель \(1+w_i\). Следовательно, число выборов, заякоренных в этой граничной направляющей, равно
$$w_i\prod_{j=1}^{m}(1+w_j)=w_iH.$$
Сумма по двум ориентациям каждой противоположной пары дает
$$2H\sum_{i=1}^{m}w_i.$$
Однако подмножество, состоящее из одной точки на каждом луче одной и той же противоположной пары, посчитано дважды: один раз от одной границы и один раз от другой. Полная поправка на двойной счет равна
$$\sum_{i=1}^{m} w_i^2.$$
Добавляя пустой выбор, получаем
$$B=1+2HA_1-A_2,$$
где
$$A_1=\sum_{i=1}^{m} w_i,\qquad A_2=\sum_{i=1}^{m} w_i^2.$$
Отсюда
$$P(n)=T-B=H^2-1-2HA_1+A_2.$$
Поскольку все пары внутри одного блока имеют одинаковый вес \(u\), два момента записываются как
$$A_1=\sum_{u} c(u)\,u,\qquad A_2=\sum_{u} c(u)\,u^2.$$
Подстановка дает точную формулу, реализованную в программах:
$$\boxed{P(n)\equiv \left(\prod_{u}(u+1)^{c(u)}\right)^2-1-2\left(\prod_{u}(u+1)^{c(u)}\right)\left(\sum_{u} c(u)\,u\right)+\sum_{u} c(u)\,u^2 \pmod{M}.}$$
При \(n=2\) существуют только два уровня слоев:
$$\left\lfloor\frac{2}{1}\right\rfloor=2,\qquad \left\lfloor\frac{2}{2}\right\rfloor=1.$$
Слой \(k=1\) дает
$$4\varphi(1)=4$$
противоположных пары веса \(2\), а слой \(k=2\) дает
$$4\varphi(2)=4$$
противоположных пары веса \(1\). Поэтому
$$H=(1+2)^4(1+1)^4=3^4\cdot 2^4=1296,$$
$$A_1=4\cdot 2+4\cdot 1=12,\qquad A_2=4\cdot 2^2+4\cdot 1^2=20.$$
Следовательно,
$$P(2)=1296^2-1-2\cdot1296\cdot12+20=1648531,$$
что совпадает с контрольным значением.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала выбирается порог порядка \(n^{2/3}\), затем с помощью решета вычисляются \(\varphi(1),\dots,\varphi(B)\), а для всех \(x\le B\) сохраняются префиксные значения \(\Phi(x)\).
Для больших аргументов используется мемоизированная рекурсия по блокам целочисленного деления, основанная на тождестве
$$\sum_{d=1}^{x}\varphi(d)\left\lfloor\frac{x}{d}\right\rfloor=\frac{x(x+1)}{2}.$$
Из него выводится
$$\Phi(x)=\frac{x(x+1)}{2}-\sum_{i=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{i}\right\rfloor\right),$$
а одинаковые значения частного объединяются в один интервал. Это позволяет быстро получать \(\Phi(x)\) на границах всех блоков.
Затем перечисляются все интервалы, на которых \(\lfloor n/k\rfloor\) постоянно, по двум запросам к сумматору функции Эйлера вычисляется кратность \(c(u)\), и обновляются произведение \(H\) и моменты \(A_1\) и \(A_2\). Кратности блоков хранятся точно для модульного возведения в степень, а аддитивные моменты сразу суммируются по модулю \(M\).
В версиях на C++ и Java блоки могут делиться между несколькими потоками, после чего частичные произведения и суммы сливаются в финальный ответ. Версия на Python выполняет ту же редукцию последовательно.
Пусть \(B\) - порог решета, выбранный порядка \(n^{2/3}\). Построение таблицы тотиентов и малых префиксов требует \(O(B)\) времени и \(O(B)\) памяти. Мемоизированный сумматор функции Эйлера использует блоки целочисленного деления и потому посещает только различные значения частного; это стандартный метод типа \(O(n^{2/3})\) для одного верхнего запроса. Финальный проход по блокам добавляет лишь \(O(\sqrt n)\) арифметики. На практике доминирует этап вычисления сумматора тотиента, а распараллеливание улучшает лишь реальное время работы, не меняя асимптотики.
لنعرّف المجموعة
$$\mathcal{L}_n=\left\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}: \max(|x|,|y|)\le n\right\}.$$
يتكوّن المضلع القطبي من اختيار نقاط شبكية من \(\mathcal{L}_n\)، مع السماح بحد أقصى رأس واحد على كل شعاع موجّه صادر من الأصل، ثم ترتيب الرؤوس المختارة بحسب الزاوية القطبية تصاعديًا. الشرط الهندسي الذي تعتمد عليه التطبيقات هو أن يقع الأصل داخل الغلاف المحدّب للرؤوس المختارة. وبصورة مكافئة، لا يجوز أن تنحصر جميع الاتجاهات المختارة داخل نصف مستوى مغلق واحد يمر بالأصل.
إذن المطلوب هو حساب عدد هذه المضلعات \(P(n)\) بترديد
$$M=10^9+7.$$
وتستخدم التطبيقات أيضًا قيم تحقق هي
$$P(1)=131,\qquad P(2)=1648531,\qquad P(3)\equiv 461288482 \pmod{M},\qquad P(343)\equiv 937293740 \pmod{M}.$$
الفكرة الحاسمة هي تجاهل الإحداثيات الدقيقة في البداية، والتصنيف بحسب الاتجاه فقط. فكل شعاع بدائي موجّه يحمل عددًا معينًا من النقاط الشبكية، وهذا العدد وحده هو الذي يدخل في العد.
كل نقطة شبكية غير صفرية تكتب بصورة وحيدة على الشكل
$$t(a,b),\qquad t\ge 1,\qquad \gcd(a,b)=1,$$
حيث يحدد الزوج \((a,b)\) اتجاهًا بدائيًا. ولنعرف مستوى هذا الاتجاه بـ
$$k=\max(|a|,|b|).$$
النقاط الواقعة على هذا الشعاع الموجّه والتي تبقى داخل \(\mathcal{L}_n\) هي تمامًا تلك التي تحقق
$$1\le t\le \left\lfloor\frac{n}{k}\right\rfloor.$$
ومن ثم فإن عدد النقاط المتاحة على هذا الشعاع يساوي
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor.$$
ولا يمكن لمضلع صحيح أن يستخدم أكثر من رأس واحد على شعاع موجّه ثابت، لأن نقطتين على الشعاع نفسه تكونان على استقامة واحدة مع الأصل، والنقطة الأقرب لا يمكن أن تكون رأسًا متطرفًا في الغلاف المحدّب. لذلك يساهم كل شعاع موجّه بعدد خيارات يساوي
$$1+w(k)$$
أي إما عدم اختيار شيء، أو اختيار نقطة واحدة من بين \(w(k)\) نقطة.
ثبّت \(k\ge 1\). إن الاتجاهات البدائية ذات المستوى \(k\) هي بالضبط النقاط الشبكية المرئية على حدود المربع \(\max(|x|,|y|)=k\).
في كل ثمن دائرة يوجد \(\varphi(k)\) من هذه الاتجاهات، ولذلك نحصل بالتناظر على
$$8\varphi(k)$$
شعاعًا بدائيًا موجّهًا، أي
$$4\varphi(k)$$
أزواجًا من الاتجاهات المتقابلة. وجميع الأزواج في الغلاف ذي المستوى \(k\) تملك الوزن نفسه
$$w(k)=\left\lfloor\frac{n}{k}\right\rfloor.$$
الوزن يعتمد فقط على خارج القسمة \(\lfloor n/k\rfloor\)، لا على الاتجاه ذاته. فإذا كان هذا الخارج ثابتًا ويساوي \(u\) لكل \(k\) في المجال \([a,b]\)، فإن عدد الأزواج المتقابلة ذات الوزن \(u\) هو
$$c(u)=4\sum_{k=a}^{b}\varphi(k).$$
ولنعرّف دالة المجموع التراكمي للتوتينت بـ
$$\Phi(x)=\sum_{m\le x}\varphi(m).$$
حينئذ يصبح إسهام الكتلة
$$c(u)=4\bigl(\Phi(b)-\Phi(a-1)\bigr).$$
وهذا يفسر لماذا ينهار التعقيد إلى \(O(\sqrt n)\) كتل مختلفة فقط: فقيم \(\lfloor n/k\rfloor\) تتكرر على فترات طويلة.
لتكن أوزان الأزواج المتقابلة هي \(w_1,\dots,w_m\). بالنسبة إلى زوج واحد فقط توجد أربع حالات:
بالنسبة إلى زوج واحد فهناك أربع إمكانات: عدم اختيار شيء، أو اختيار نقطة على الشعاع الأول فقط، أو اختيار نقطة على الشعاع المقابل فقط، أو اختيار نقطة على كل من الشعاعين.
ولذلك يكون إسهام الزوج الواحد
$$1+w_i+w_i+w_i^2=(1+w_i)^2.$$
إذا عرّفنا
$$H=\prod_{i=1}^{m}(1+w_i),$$
فإن العدد الموزون لجميع اختيارات الأشعة يساوي
$$T=H^2.$$
وبصياغة الكتل نحصل على
$$H=\prod_{u}(u+1)^{c(u)}.$$
يكون الاختيار فاسدًا إذا وفقط إذا كانت جميع الاتجاهات المختارة محصورة في نصف دائرة مغلق. ولعدّ هذه الاختيارات نحسبها بحسب أول اتجاه حدّي مختار.
ثبّت شعاعًا حدّيًا موجّهًا وزنه \(w_i\). يجب اختيار نقطة على هذا الشعاع، وهذا يعطي \(w_i\) إمكانات. أما كل زوج متقابل آخر فيعطي اتجاهًا واحدًا فقط داخل نصف الدائرة المفتوح التالي لهذا الحد، ولذلك يساهم بعامل \(1+w_j\). ويمكن اختيار الشعاع الحدّي المقابل أو تركه، فيعطي عاملًا إضافيًا \(1+w_i\). ومن ثم يكون عدد الاختيارات المرتكزة على هذا الحد الموجّه
$$w_i\prod_{j=1}^{m}(1+w_j)=w_iH.$$
وبالجمع على الاتجاهين لكل زوج متقابل نحصل على
$$2H\sum_{i=1}^{m}w_i.$$
لكن المجموعة التي تحتوي على نقطة واحدة على كل من شعاعي الزوج المتقابل نفسه تُعدّ مرتين، مرة من كل حد. لذا يجب طرح مقدار التصحيح
$$\sum_{i=1}^{m} w_i^2.$$
ومع إضافة المجموعة الخالية نحصل على
$$B=1+2HA_1-A_2,$$
حيث
$$A_1=\sum_{i=1}^{m} w_i,\qquad A_2=\sum_{i=1}^{m} w_i^2.$$
إذًا
$$P(n)=T-B=H^2-1-2HA_1+A_2.$$
لأن جميع الأزواج داخل الكتلة الواحدة لها الوزن نفسه \(u\)، فإن العزمين يكتبان على الصورة
$$A_1=\sum_{u} c(u)\,u,\qquad A_2=\sum_{u} c(u)\,u^2.$$
وبالتعويض نحصل على الصيغة المغلقة التي تحسبها التطبيقات مباشرة:
$$\boxed{P(n)\equiv \left(\prod_{u}(u+1)^{c(u)}\right)^2-1-2\left(\prod_{u}(u+1)^{c(u)}\right)\left(\sum_{u} c(u)\,u\right)+\sum_{u} c(u)\,u^2 \pmod{M}.}$$
عند \(n=2\) لا يوجد إلا مستويان من الأغلفة:
$$\left\lfloor\frac{2}{1}\right\rfloor=2,\qquad \left\lfloor\frac{2}{2}\right\rfloor=1.$$
يعطي الغلاف \(k=1\)
$$4\varphi(1)=4$$
أزواجًا متقابلة وزنها \(2\)، ويعطي الغلاف \(k=2\)
$$4\varphi(2)=4$$
أزواجًا متقابلة وزنها \(1\). ومن ثم
$$H=(1+2)^4(1+1)^4=3^4\cdot 2^4=1296,$$
$$A_1=4\cdot 2+4\cdot 1=12,\qquad A_2=4\cdot 2^2+4\cdot 1^2=20.$$
وبالتالي
$$P(2)=1296^2-1-2\cdot1296\cdot12+20=1648531,$$
وهو يطابق قيمة التحقق تمامًا.
تتبع تطبيقات C++ وPython وJava السلسلة الرياضية نفسها. في البداية تختار حدًا من رتبة \(n^{2/3}\)، ثم تحسب \(\varphi(1),\dots,\varphi(B)\) باستعمال غربال، وتخزن القيم السابقة لـ \(\Phi(x)\) لكل \(x\le B\).
أما للقيم الأكبر فتستخدم استدعاءً تكراريًا مع التخزين المؤقت قائمًا على تجميع كتل القسمة الصحيحة، انطلاقًا من الهوية
$$\sum_{d=1}^{x}\varphi(d)\left\lfloor\frac{x}{d}\right\rfloor=\frac{x(x+1)}{2}.$$
ومنها ينتج
$$\Phi(x)=\frac{x(x+1)}{2}-\sum_{i=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{i}\right\rfloor\right),$$
مع دمج الحدود التي تعطي خارج قسمة واحدًا في مجال واحد. وهكذا تُحسب قيم \(\Phi(x)\) بسرعة عند حدود كل كتلة.
بعد ذلك تُعدّد الكتل التي يكون فيها \(\lfloor n/k\rfloor\) ثابتًا، ويُستخرج التعدد \(c(u)\) من استعلامين للمجموع التراكمي للتوتينت، ثم يُحدّث الجداء \(H\) والعزمان \(A_1\) و\(A_2\). وتحفظ تعددات الكتل بدقة كاملة عند الأسس في القوة المعيارية، بينما تُجمع العزوم الإضافية مباشرة بترديد \(M\).
ويمكن في نسختي C++ وJava تقسيم الكتل بين عدة خيوط عمل ثم دمج الجداءات والمجاميع الجزئية في النهاية. أما نسخة Python فتنفذ الاختزال نفسه على نحو تسلسلي.
ليكن \(B\) حد الغربال المختار من رتبة \(n^{2/3}\). بناء جدول التوتينت والقيم السابقة الصغيرة يكلف \(O(B)\) زمنًا و\(O(B)\) ذاكرة. أما مرحلة المجموع التراكمي للتوتينت مع التخزين المؤقت فتستخدم كتل القسمة الصحيحة، ولذلك لا تزور إلا قيم الخارج المختلفة؛ وهذا هو الأسلوب القياسي من النمط \(O(n^{2/3})\) لاستعلام رئيسي واحد. ثم تضيف مرحلة المرور على الكتل \(O(\sqrt n)\) عملية حسابية فقط. عمليًا تظل مرحلة التوتينت هي المسيطرة، بينما يختصر التوازي زمن التنفيذ الفعلي في النسخ متعددة الخيوط من غير أن يغير الرتبة الأسية.