For every pair \(1\le i\le m\), \(1\le j\le n\), the picture contains the segment from the lower point \((i,1)\) to the upper point \((j,2)\). A triangle is formed by three of these segments when the three pairwise intersections are real and not all the same point. Intersections at shared endpoints count, and intersections created inside other segments count as well.
The target is \(T(1234\cdot 10^8,2345\cdot 10^8)\) modulo \(10^9+7\). The given checks are \(T(2,3)=8\), \(T(3,5)=146\), and \(T(12,23)=756716\). A geometric drawing is far too large, so the implementation counts triples of segments algebraically.
Represent the segment from \((i,1)\) to \((j,2)\) by the grid point \((i,j)\) in an \(m\times n\) rectangle. Two distinct segments \((i_1,j_1)\) and \((i_2,j_2)\) intersect exactly when
$$i_1=i_2,\qquad\text{or}\qquad j_1=j_2,\qquad\text{or}\qquad (i_1-i_2)(j_1-j_2)\lt 0.$$
The first two cases are shared lower or upper endpoints. The third case says that the two endpoints appear in opposite order on the two horizontal lines, so the segments cross in the interior.
We first count triples of segments for which every pair intersects. Some of these will later be removed because all three meet at one point. The count splits cleanly by how many lower endpoints and upper endpoints are used.
If the triple uses three different lower endpoints and three different upper endpoints, then after the lower endpoints are ordered increasingly, the upper endpoints must be ordered decreasingly. Thus there is one valid matching for every choice of three lower and three upper endpoints:
$$\binom m3\binom n3.$$
If it uses three lower endpoints but only two upper endpoints, choose the three lower endpoints and an ordered pair of distinct upper endpoints; the singleton upper endpoint must be attached to the extreme lower endpoint on the side that makes it cross the other two. This gives \(\binom m3 n(n-1)\). By symmetry, the case of two lower endpoints and three upper endpoints contributes \(m(m-1)\binom n3\).
Finally, in a \(2\times 2\) rectangle of endpoints, exactly two of the four three-corner choices are pairwise intersecting. Therefore the \(2\)-by-\(2\) case contributes
$$2\binom m2\binom n2={m(m-1)n(n-1)\over 2}.$$
So the pairwise-intersecting candidate count is
$$P(m,n)=\binom m3\binom n3+\binom m3 n(n-1)+m(m-1)\binom n3+{m(m-1)n(n-1)\over 2}.$$
A candidate triple fails to be a triangle precisely when the three segment-lines are concurrent. In the dual grid this is the same as the three points \((i,j)\) being collinear on a line of negative slope.
Take the two extreme dual points of such a collinear triple. Let their horizontal separation be \(A\) and their vertical separation be \(B\), with both positive. There are \((m-A)(n-B)\) ways to place those two extremes in the rectangle. The number of possible middle lattice points on the open segment between them is
$$\gcd(A,B)-1.$$
Hence the number of concurrent triples is
$$C(m,n)=\sum_{A=1}^{m-1}\sum_{B=1}^{n-1}(\gcd(A,B)-1)(m-A)(n-B).$$
The double sum above is still too large. Use the classical identity
$$\gcd(A,B)=\sum_{d\mid\gcd(A,B)}\varphi(d),$$
so that
$$\gcd(A,B)-1=\sum_{\substack{d\mid A,\ d\mid B\\d\ge 2}}\varphi(d).$$
Switching the order of summation gives
$$C(m,n)=\sum_{d=2}^{\min(m,n)-1}\varphi(d) \left(\sum_{r=1}^{\lfloor(m-1)/d\rfloor}(m-dr)\right) \left(\sum_{s=1}^{\lfloor(n-1)/d\rfloor}(n-ds)\right).$$
Define
$$Q_m(d)=\left\lfloor {m-1\over d}\right\rfloor,\qquad A_m(d)=mQ_m(d)-d{Q_m(d)(Q_m(d)+1)\over 2}.$$
Then \(C(m,n)=\sum_d \varphi(d)A_m(d)A_n(d)\).
The values \(Q_m(d)\) and \(Q_n(d)\) are constant on long intervals of \(d\). On such an interval, \(A_m(d)A_n(d)\) is a quadratic polynomial in \(d\), so only three prefix sums are required:
$$\Phi_k(x)=\sum_{d\le x}d^k\varphi(d),\qquad k=0,1,2.$$
The code builds these sums up to \(5\cdot 10^6\) by a linear sieve and evaluates larger arguments with the divisor-summatory recurrence
$$\Phi_k(n)=\sum_{r=1}^{n}r^{k+1} -\sum_{\ell=2}^{n}\left(\sum_{d=\ell}^{h}d^k\right)\Phi_k\!\left(\left\lfloor {n\over \ell}\right\rfloor\right),$$
where \(h=\left\lfloor n/\left\lfloor n/\ell\right\rfloor\right\rfloor\). Grouping equal quotients makes this recurrence fast enough for the huge target.
The answer is
$$\boxed{T(m,n)=P(m,n)-C(m,n)\pmod {10^9+7}}.$$
For \(m=2,n=3\), the concurrent sum is zero and \(P(2,3)=8\), so \(T(2,3)=8\). For \(m=3,n=5\), \(P(3,5)=150\). The only nonzero concurrent block is \(d=2\), which contributes \(4\), giving \(150-4=146\). The larger checkpoint \(T(12,23)=756716\) is also asserted in the implementation.
The C++ program first initializes modular arithmetic helpers, binomial forms, and power-sum formulas up to degree three. pairwise_triangle_candidates evaluates \(P(m,n)\) directly.
TotientSummatory builds \(\varphi(d)\), \(\Phi_0\), \(\Phi_1\), and \(\Phi_2\) up to the sieve limit, then memoizes the recursive prefix calls for larger \(n\). concurrent_triples walks over quotient blocks of \(d\), expands \(A_m(d)A_n(d)\), and subtracts the required totient-weighted sum. The small brute-force checker enumerates all segment triples for \(1\le m,n\le 5\), then verifies the three official checkpoints.
The fixed sieve costs \(O(L)\) time and memory for \(L=5\cdot 10^6\). The main summation uses quotient blocks, so the number of outer iterations is \(O(\sqrt{\min(m,n)})\), with memoized summatory-totient queries. The memory use is dominated by the three prefix arrays and the totient table.
A direct enumeration of all triples of the \(mn\) segments would be impossible. The formula replaces that \(O((mn)^3)\) geometry with arithmetic over divisors and floor-division blocks.
Für jedes Paar \(1\le i\le m\), \(1\le j\le n\) wird die Strecke von \((i,1)\) nach \((j,2)\) gezeichnet. Drei Strecken bilden genau dann ein Dreieck, wenn ihre drei paarweisen Schnittpunkte existieren und nicht alle derselbe Punkt sind. Gemeinsame Endpunkte zählen ebenso wie innere Schnittpunkte.
Gesucht ist \(T(1234\cdot 10^8,2345\cdot 10^8)\) modulo \(10^9+7\). Die Kontrollwerte sind \(T(2,3)=8\), \(T(3,5)=146\) und \(T(12,23)=756716\). Die Lösung zeichnet die Anordnung nicht, sondern zählt die Streckentripel rein arithmetisch.
Die Strecke von \((i,1)\) nach \((j,2)\) wird als Gitterpunkt \((i,j)\) betrachtet. Zwei Strecken \((i_1,j_1)\) und \((i_2,j_2)\) schneiden sich genau dann, wenn
$$i_1=i_2,\qquad\text{oder}\qquad j_1=j_2,\qquad\text{oder}\qquad (i_1-i_2)(j_1-j_2)\lt 0.$$
Die ersten beiden Fälle sind gemeinsame Endpunkte. Im dritten Fall erscheinen die Endpunkte auf den beiden waagerechten Geraden in umgekehrter Reihenfolge, also kreuzen sich die Strecken im Inneren.
Zunächst zählen wir alle Tripel, in denen jedes Paar von Strecken einen Schnittpunkt hat. Verwendet ein Tripel drei untere und drei obere Endpunkte, gibt es nach Sortierung der unteren Endpunkte genau eine zulässige umgekehrte Zuordnung der oberen Endpunkte. Das liefert \(\binom m3\binom n3\).
Bei drei unteren, aber nur zwei oberen Endpunkten wählt man die drei unteren Punkte und ein geordnetes Paar verschiedener oberer Punkte. Die einzelne obere Wahl muss mit einem extremen unteren Punkt verbunden werden; das ergibt \(\binom m3 n(n-1)\). Symmetrisch erhält man \(m(m-1)\binom n3\).
Für zwei untere und zwei obere Endpunkte gibt es in jedem \(2\times 2\)-Rechteck genau zwei gültige Drei-Ecken-Auswahlen. Daher ist der Beitrag
$$2\binom m2\binom n2={m(m-1)n(n-1)\over 2}.$$
Damit ist
$$P(m,n)=\binom m3\binom n3+\binom m3 n(n-1)+m(m-1)\binom n3+{m(m-1)n(n-1)\over 2}.$$
Ein solches Kandidatentripel ist kein Dreieck, wenn alle drei Strecken durch denselben Punkt laufen. In der dualen Darstellung bedeutet das: Die drei Punkte \((i,j)\) liegen auf einer Geraden mit negativer Steigung.
Seien \(A\) und \(B\) die horizontalen und vertikalen Abstände der beiden extremen dualen Punkte. Diese Extreme können auf \((m-A)(n-B)\) Arten platziert werden. Die Anzahl der möglichen mittleren Gitterpunkte zwischen ihnen ist
$$\gcd(A,B)-1.$$
Also
$$C(m,n)=\sum_{A=1}^{m-1}\sum_{B=1}^{n-1}(\gcd(A,B)-1)(m-A)(n-B).$$
Mit
$$\gcd(A,B)=\sum_{d\mid\gcd(A,B)}\varphi(d)$$
folgt
$$C(m,n)=\sum_{d=2}^{\min(m,n)-1}\varphi(d) \left(\sum_{r=1}^{\lfloor(m-1)/d\rfloor}(m-dr)\right) \left(\sum_{s=1}^{\lfloor(n-1)/d\rfloor}(n-ds)\right).$$
Setze \(Q_m(d)=\lfloor(m-1)/d\rfloor\) und
$$A_m(d)=mQ_m(d)-d{Q_m(d)(Q_m(d)+1)\over 2}.$$
Dann ist \(C(m,n)=\sum_d\varphi(d)A_m(d)A_n(d)\).
Auf Intervallen mit konstanten Quotienten \(Q_m(d)\) und \(Q_n(d)\) ist \(A_m(d)A_n(d)\) ein quadratisches Polynom in \(d\). Deshalb reichen die Präfixsummen
$$\Phi_k(x)=\sum_{d\le x}d^k\varphi(d),\qquad k=0,1,2.$$
Der Code erzeugt sie bis \(5\cdot 10^6\) per linearem Sieb. Größere Werte berechnet er mit einer memoisierten Summationsrekursion, in der gleiche Werte von \(\lfloor n/d\rfloor\) zusammengefasst werden.
Die gesuchte Zahl ist
$$\boxed{T(m,n)=P(m,n)-C(m,n)\pmod {10^9+7}}.$$
Für \(m=3,n=5\) erhält man \(P=150\). Der Korrekturterm aus gleichzeitigen Schnitten ist \(4\), also \(T(3,5)=146\). Die Implementierung prüft zusätzlich alle kleinen Fälle bis \(5\times 5\) durch Brute Force.
pairwise_triangle_candidates wertet \(P(m,n)\) direkt aus. TotientSummatory speichert \(\Phi_0,\Phi_1,\Phi_2\) und beantwortet große Präfixanfragen rekursiv. concurrent_triples läuft über die Quotientenblöcke, bildet die drei nötigen Totientsummen und zieht den Korrekturterm ab.
Das Sieb benötigt \(O(L)\) Zeit und Speicher für \(L=5\cdot 10^6\). Danach verarbeitet die Hauptsumme nur \(O(\sqrt{\min(m,n)})\) Quotientenblöcke. Eine direkte Betrachtung aller \((mn)^3\) Streckentripel wäre völlig ausgeschlossen.
Her \(1\le i\le m\) ve \(1\le j\le n\) çifti için \((i,1)\) alt noktasından \((j,2)\) üst noktasına bir doğru parçası çiziliyor. Üç doğru parçası, ikili kesişim noktaları varsa ve bu üç kesişim noktası tek bir noktaya çökmediyse bir üçgen oluşturur. Ortak uç noktalar da, içerideki kesişimler de sayılır.
Hedef değer \(T(1234\cdot 10^8,2345\cdot 10^8)\)'in \(10^9+7\)'ye göre kalanıdır. Verilen kontroller \(T(2,3)=8\), \(T(3,5)=146\) ve \(T(12,23)=756716\). Bu büyüklükte bir resmi çizmek yerine çözüm, doğru parçalarını temsil eden tamsayı çiftleri üzerinde sayım yapar.
\((i,1)\) ile \((j,2)\) arasındaki segmenti \(m\times n\) ızgarasındaki \((i,j)\) noktasıyla temsil edelim. İki segment \((i_1,j_1)\) ve \((i_2,j_2)\) şu üç durumdan birinde kesişir:
$$i_1=i_2,\qquad\text{veya}\qquad j_1=j_2,\qquad\text{veya}\qquad (i_1-i_2)(j_1-j_2)\lt 0.$$
İlk iki koşul ortak alt ya da üst uç noktadır. Son koşul ise alt sıradaki düzen ile üst sıradaki düzenin ters olduğunu, dolayısıyla iki segmentin içeride kesiştiğini söyler.
Önce her iki segmenti kesişen tüm üçlüleri sayalım. Üç farklı alt ve üç farklı üst uç noktası varsa, alt uçlar artan sıraya konduğunda üst uçlar azalan sırada eşlenmelidir. Bu yüzden katkı
$$\binom m3\binom n3$$
olur. Üç alt, iki üst uç noktası durumunda üç alt nokta ve sıralı iki farklı üst nokta seçilir; tek kalan üst nokta, diğer iki segmenti kesecek uçtaki alt noktaya bağlanır. Bu katkı \(\binom m3 n(n-1)\)'dir. Simetriyle iki alt, üç üst durumu \(m(m-1)\binom n3\) verir.
İki alt ve iki üst uç noktasının oluşturduğu her küçük dikdörtgende dört üç-köşe seçiminin tam ikisi geçerlidir. Bu katkı
$$2\binom m2\binom n2={m(m-1)n(n-1)\over 2}.$$
Dolayısıyla aday sayısı
$$P(m,n)=\binom m3\binom n3+\binom m3 n(n-1)+m(m-1)\binom n3+{m(m-1)n(n-1)\over 2}.$$
Her aday gerçek bir üçgen değildir. Üç segmentin tamamı aynı noktadan geçiyorsa üç ayrı köşe oluşmaz. Dual ızgarada bu durum, üç \((i,j)\) noktasının negatif eğimli tek bir doğru üzerinde bulunmasına denktir.
Böyle bir doğrusal üçlüde iki uç dual noktanın yatay farkı \(A\), düşey farkı \(B\) olsun. Uçları yerleştirme sayısı \((m-A)(n-B)\)'dir. Bu iki uç arasında açık segment üzerindeki tamsayı orta nokta sayısı
$$\gcd(A,B)-1$$
olduğundan eşzamanlı kesişen üçlü sayısı
$$C(m,n)=\sum_{A=1}^{m-1}\sum_{B=1}^{n-1}(\gcd(A,B)-1)(m-A)(n-B).$$
Temel kimlik
$$\gcd(A,B)=\sum_{d\mid\gcd(A,B)}\varphi(d)$$
olduğu için \(\gcd(A,B)-1\), \(A\) ve \(B\)'yi ortak bölen \(d\ge 2\) değerlerinin \(\varphi(d)\) toplamıdır. Toplam sırası değiştirilince
$$C(m,n)=\sum_{d=2}^{\min(m,n)-1}\varphi(d) \left(\sum_{r=1}^{\lfloor(m-1)/d\rfloor}(m-dr)\right) \left(\sum_{s=1}^{\lfloor(n-1)/d\rfloor}(n-ds)\right)$$
elde edilir. Burada
$$A_m(d)=mQ_m(d)-d{Q_m(d)(Q_m(d)+1)\over 2},\qquad Q_m(d)=\left\lfloor {m-1\over d}\right\rfloor.$$
\(Q_m(d)\) ve \(Q_n(d)\) uzun aralıklarda sabit kalır. Bu aralıklarda \(A_m(d)A_n(d)\) yalnızca \(d\)'ye göre ikinci dereceden bir polinomdur. Bu yüzden kod sadece
$$\Phi_k(x)=\sum_{d\le x}d^k\varphi(d),\qquad k=0,1,2$$
önek toplamlarına ihtiyaç duyar. Bunlar \(5\cdot 10^6\)'ya kadar lineer sieve ile hazırlanır; daha büyük argümanlarda \(\lfloor n/d\rfloor\) değerleri bloklanarak memoize edilmiş summatory totient özyinelemesi kullanılır.
Nihai formül
$$\boxed{T(m,n)=P(m,n)-C(m,n)\pmod {10^9+7}}.$$
\(m=2,n=3\) için eşzamanlı kesişim yoktur ve sonuç \(8\)'dir. \(m=3,n=5\) için aday sayısı \(150\), çıkarılması gereken eşzamanlı üçlü sayısı \(4\), dolayısıyla sonuç \(146\)'dır. Kod ayrıca \(1\le m,n\le 5\) aralığını brute force ile ve \(T(12,23)=756716\) değerini doğrudan doğrular.
pairwise_triangle_candidates fonksiyonu \(P(m,n)\)'yi kapalı formdan hesaplar. TotientSummatory sınıfı \(\varphi\), \(\Phi_0\), \(\Phi_1\), \(\Phi_2\) tablolarını kurar ve büyük önek sorgularını memoization ile çözer. concurrent_triples sabit bölüm aralıklarını dolaşır, her blokta gerekli üç totient toplamını alır ve \(C(m,n)\)'yi modüler aritmetikle toplar.
Sieve maliyeti \(L=5\cdot 10^6\) için \(O(L)\) zaman ve bellektir. Ana döngü bölüm blokları sayesinde \(O(\sqrt{\min(m,n)})\) mertebesinde blok gezer. Tüm segment üçlülerini denemek \(O((mn)^3)\) olacağından bu aritmetik dönüşüm problemin esas kilididir.
Para cada \(1\le i\le m\) y \(1\le j\le n\) se dibuja el segmento que une \((i,1)\) con \((j,2)\). Tres segmentos cuentan como triángulo si sus intersecciones por pares existen y no se reducen todas a un único punto. También cuentan las intersecciones en extremos compartidos y las intersecciones interiores.
La instancia final pide \(T(1234\cdot 10^8,2345\cdot 10^8)\) módulo \(10^9+7\). Los valores de control son \(T(2,3)=8\), \(T(3,5)=146\) y \(T(12,23)=756716\). La solución evita construir la figura y cuenta triples de segmentos mediante una transformación aritmética.
Codificamos el segmento \((i,1)\)-\((j,2)\) como el punto \((i,j)\). Dos segmentos \((i_1,j_1)\) y \((i_2,j_2)\) se cortan si
$$i_1=i_2,\qquad\text{o}\qquad j_1=j_2,\qquad\text{o}\qquad (i_1-i_2)(j_1-j_2)\lt 0.$$
Las dos primeras alternativas son extremos compartidos; la tercera expresa que el orden de los extremos se invierte entre la línea inferior y la superior.
Primero contamos todos los triples donde cada par de segmentos se intersecta. Con tres extremos inferiores y tres superiores distintos hay una única correspondencia válida, la inversa, por cada elección: \(\binom m3\binom n3\).
Con tres extremos inferiores y dos superiores, la elección ordenada de los dos superiores determina qué extremo inferior debe quedar solo, lo que da \(\binom m3 n(n-1)\). El caso simétrico aporta \(m(m-1)\binom n3\). Con dos inferiores y dos superiores hay dos triples válidos por rectángulo, es decir
$$2\binom m2\binom n2={m(m-1)n(n-1)\over 2}.$$
Por tanto
$$P(m,n)=\binom m3\binom n3+\binom m3 n(n-1)+m(m-1)\binom n3+{m(m-1)n(n-1)\over 2}.$$
Un candidato no es un triángulo si los tres segmentos pasan por el mismo punto. En la red dual esto equivale a que los tres puntos \((i,j)\) sean colineales con pendiente negativa.
Si los dos puntos extremos de ese triple tienen separación horizontal \(A\) y vertical \(B\), se pueden colocar de \((m-A)(n-B)\) maneras. Entre ellos hay exactamente
$$\gcd(A,B)-1$$
puntos reticulares interiores posibles. Así,
$$C(m,n)=\sum_{A=1}^{m-1}\sum_{B=1}^{n-1}(\gcd(A,B)-1)(m-A)(n-B).$$
Usamos
$$\gcd(A,B)=\sum_{d\mid\gcd(A,B)}\varphi(d).$$
Al cambiar el orden de suma queda
$$C(m,n)=\sum_{d=2}^{\min(m,n)-1}\varphi(d) \left(\sum_{r=1}^{\lfloor(m-1)/d\rfloor}(m-dr)\right) \left(\sum_{s=1}^{\lfloor(n-1)/d\rfloor}(n-ds)\right).$$
Con \(Q_m(d)=\lfloor(m-1)/d\rfloor\), el primer paréntesis es \(mQ_m(d)-dQ_m(d)(Q_m(d)+1)/2\).
Como los cocientes \(Q_m(d)\) y \(Q_n(d)\) son constantes en intervalos largos, cada bloque sólo requiere
$$\Phi_k(x)=\sum_{d\le x}d^k\varphi(d),\qquad k=0,1,2.$$
El programa calcula estas sumas hasta \(5\cdot 10^6\) con una criba lineal y usa una recurrencia memoizada para los valores mayores. La expansión cuadrática de \(A_m(d)A_n(d)\) permite combinar cada bloque con \(\Phi_0,\Phi_1,\Phi_2\).
Finalmente
$$\boxed{T(m,n)=P(m,n)-C(m,n)\pmod {10^9+7}}.$$
En el ejemplo \(m=3,n=5\), \(P=150\) y los triples concurrentes suman \(4\), por lo que \(T=146\). El código confirma además todos los casos pequeños hasta \(5\times 5\) con una enumeración directa.
Las tres versiones implementan las mismas piezas: fórmulas combinatorias para \(P\), una clase de sumas totientes para \(\Phi_k\), un recorrido por bloques de división entera y verificaciones pequeñas por fuerza bruta. Todo se evalúa módulo \(10^9+7\), evitando enteros gigantes en los productos principales.
La criba tiene coste \(O(L)\) para \(L=5\cdot 10^6\). La suma principal usa \(O(\sqrt{\min(m,n)})\) bloques de cocientes, con consultas memoizadas a las sumas totientes. Enumerar triples directamente costaría \(O((mn)^3)\), totalmente inviable.
对每个 \(1\le i\le m\) 和 \(1\le j\le n\)，图中画出从 \((i,1)\) 到 \((j,2)\) 的线段。三条线段在两两相交且三个交点不是同一个点时形成一个三角形；共享端点和内部交点都要计入。
目标是求 \(T(1234\cdot 10^8,2345\cdot 10^8)\) 模 \(10^9+7\)。已知检验值为 \(T(2,3)=8\)、\(T(3,5)=146\)、\(T(12,23)=756716\)。直接处理 \(mn\) 条线段的所有三元组不可行，因此程序使用数论计数。
把线段 \((i,1)\)-\((j,2)\) 表示为网格点 \((i,j)\)。两条线段 \((i_1,j_1)\)、\((i_2,j_2)\) 相交当且仅当
$$i_1=i_2,\qquad\text{或}\qquad j_1=j_2,\qquad\text{或}\qquad (i_1-i_2)(j_1-j_2)\lt 0.$$
前两种是共享下端点或上端点；后一种说明上下两行中的端点顺序相反，所以线段在内部交叉。
若使用三个不同的下端点和三个不同的上端点，则上端点必须按反序匹配，因此贡献为 \(\binom m3\binom n3\)。若使用三个下端点但只有两个上端点，则贡献为 \(\binom m3 n(n-1)\)；对称情况贡献为 \(m(m-1)\binom n3\)。
若只使用两个下端点和两个上端点，每个 \(2\times 2\) 小矩形中恰有两个三角候选，所以贡献是
$$2\binom m2\binom n2={m(m-1)n(n-1)\over 2}.$$
候选总数为
$$P(m,n)=\binom m3\binom n3+\binom m3 n(n-1)+m(m-1)\binom n3+{m(m-1)n(n-1)\over 2}.$$
如果三条线段全都经过同一个点，就不会形成真正的三角形。在对偶网格中，这等价于三个点 \((i,j)\) 位于同一条负斜率直线上。
设这三个点中两个极端点的水平距离为 \(A\)，垂直距离为 \(B\)。极端点有 \((m-A)(n-B)\) 种放置方式，而它们之间的内部格点数为
$$\gcd(A,B)-1.$$
因此共点三元组数为
$$C(m,n)=\sum_{A=1}^{m-1}\sum_{B=1}^{n-1}(\gcd(A,B)-1)(m-A)(n-B).$$
利用恒等式
$$\gcd(A,B)=\sum_{d\mid\gcd(A,B)}\varphi(d),$$
交换求和顺序后得到
$$C(m,n)=\sum_{d=2}^{\min(m,n)-1}\varphi(d) \left(\sum_{r=1}^{\lfloor(m-1)/d\rfloor}(m-dr)\right) \left(\sum_{s=1}^{\lfloor(n-1)/d\rfloor}(n-ds)\right).$$
令 \(Q_m(d)=\lfloor(m-1)/d\rfloor\)，则第一个括号为 \(mQ_m(d)-dQ_m(d)(Q_m(d)+1)/2\)。
\(Q_m(d)\)、\(Q_n(d)\) 在很长的 \(d\) 区间上保持不变，所以每个区间只需要三个前缀和：
$$\Phi_k(x)=\sum_{d\le x}d^k\varphi(d),\qquad k=0,1,2.$$
程序先用线性筛预处理到 \(5\cdot 10^6\)，再用记忆化递归处理更大的参数，并把相同的 \(\lfloor n/d\rfloor\) 商合并成块。
答案为
$$\boxed{T(m,n)=P(m,n)-C(m,n)\pmod {10^9+7}}.$$
例如 \(m=3,n=5\) 时，候选数 \(P=150\)，共点三元组数为 \(4\)，所以 \(T=146\)。程序还用暴力枚举验证 \(1\le m,n\le 5\) 的所有小情况。
代码先计算候选公式 \(P\)，再通过 TotientSummatory 获得 \(\Phi_0,\Phi_1,\Phi_2\)。主循环按整除商分块，把每块中的二次多项式与这三个前缀和组合，得到需要扣除的 \(C\)。
筛法部分为 \(O(L)\) 时间和空间，其中 \(L=5\cdot 10^6\)。主求和只需 \(O(\sqrt{\min(m,n)})\) 个商分块。相比直接枚举所有线段三元组的 \(O((mn)^3)\)，这是数量级上的根本压缩。
Для каждой пары \(1\le i\le m\), \(1\le j\le n\) проводится отрезок от \((i,1)\) до \((j,2)\). Три отрезка образуют треугольник, если все три попарные точки пересечения существуют и не совпадают в одной точке. Пересечения в общих концах и внутренние пересечения учитываются одинаково.
Нужно найти \(T(1234\cdot 10^8,2345\cdot 10^8)\) по модулю \(10^9+7\). Проверочные значения: \(T(2,3)=8\), \(T(3,5)=146\), \(T(12,23)=756716\). Решение считает тройки алгебраически, не строя огромную конфигурацию прямых.
Отрезок \((i,1)\)-\((j,2)\) кодируется точкой \((i,j)\). Два отрезка \((i_1,j_1)\) и \((i_2,j_2)\) пересекаются тогда и только тогда, когда
$$i_1=i_2,\qquad\text{или}\qquad j_1=j_2,\qquad\text{или}\qquad (i_1-i_2)(j_1-j_2)\lt 0.$$
Это покрывает общие нижние концы, общие верхние концы и внутреннее пересечение при обратном порядке концов.
Если используются три разных нижних и три разных верхних конца, то после сортировки нижних концов верхние должны идти в обратном порядке. Это даёт \(\binom m3\binom n3\). Случай трёх нижних и двух верхних концов даёт \(\binom m3 n(n-1)\), а симметричный случай даёт \(m(m-1)\binom n3\).
При двух нижних и двух верхних концах каждый \(2\times 2\) прямоугольник даёт ровно два допустимых выбора из трёх углов:
$$2\binom m2\binom n2={m(m-1)n(n-1)\over 2}.$$
Итак,
$$P(m,n)=\binom m3\binom n3+\binom m3 n(n-1)+m(m-1)\binom n3+{m(m-1)n(n-1)\over 2}.$$
Кандидат не является треугольником, если все три отрезка проходят через одну точку. В двойственной решётке это означает, что три точки \((i,j)\) лежат на одной прямой отрицательного наклона.
Пусть расстояния между крайними двойственными точками равны \(A\) по горизонтали и \(B\) по вертикали. Крайние точки можно разместить \((m-A)(n-B)\) способами, а число внутренних решёточных точек между ними равно
$$\gcd(A,B)-1.$$
Поэтому
$$C(m,n)=\sum_{A=1}^{m-1}\sum_{B=1}^{n-1}(\gcd(A,B)-1)(m-A)(n-B).$$
Так как
$$\gcd(A,B)=\sum_{d\mid\gcd(A,B)}\varphi(d),$$
после перестановки сумм получаем
$$C(m,n)=\sum_{d=2}^{\min(m,n)-1}\varphi(d) \left(\sum_{r=1}^{\lfloor(m-1)/d\rfloor}(m-dr)\right) \left(\sum_{s=1}^{\lfloor(n-1)/d\rfloor}(n-ds)\right).$$
Если \(Q_m(d)=\lfloor(m-1)/d\rfloor\), то первый множитель равен \(mQ_m(d)-dQ_m(d)(Q_m(d)+1)/2\).
На интервалах, где \(Q_m(d)\) и \(Q_n(d)\) постоянны, выражение является квадратным многочленом по \(d\). Нужны только суммы
$$\Phi_k(x)=\sum_{d\le x}d^k\varphi(d),\qquad k=0,1,2.$$
Программа строит их до \(5\cdot 10^6\) линейным решетом, а для больших \(x\) использует мемоизированную рекурсию по одинаковым значениям \(\lfloor n/d\rfloor\).
Искомое значение равно
$$\boxed{T(m,n)=P(m,n)-C(m,n)\pmod {10^9+7}}.$$
Для \(m=3,n=5\) получаем \(P=150\) и \(C=4\), значит \(T=146\). Малые случаи до \(5\times 5\) проверяются в коде прямым перебором.
pairwise_triangle_candidates считает \(P\) по закрытой формуле. TotientSummatory хранит \(\Phi_0,\Phi_1,\Phi_2\) и отвечает на большие запросы с мемоизацией. concurrent_triples проходит по блокам целочисленного деления и суммирует поправку \(C\) по модулю.
Решето требует \(O(L)\) времени и памяти при \(L=5\cdot 10^6\). Основная сумма имеет порядка \(O(\sqrt{\min(m,n)})\) блоков. Прямой перебор всех троек отрезков имел бы стоимость \(O((mn)^3)\), что невозможно для данной задачи.
لكل \(1\le i\le m\) و \(1\le j\le n\) نرسم القطعة من \((i,1)\) إلى \((j,2)\). ثلاث قطع تكوّن مثلثا عندما توجد تقاطعاتها الثنائية الثلاثة ولا تكون كلها نقطة واحدة. لذلك تدخل التقاطعات عند النهايات المشتركة والتقاطعات الداخلية في العد.
المطلوب هو \(T(1234\cdot 10^8,2345\cdot 10^8)\) بترديد \(10^9+7\). القيم المعطاة للفحص هي \(T(2,3)=8\)، و \(T(3,5)=146\)، و \(T(12,23)=756716\). الحل لا يرسم الشكل، بل يحول العد إلى صيغ عددية على أزواج صحيحة.
نمثل القطعة \((i,1)\)-\((j,2)\) بالنقطة \((i,j)\) في شبكة \(m\times n\). قطعتان \((i_1,j_1)\) و \((i_2,j_2)\) تتقاطعان إذا وفقط إذا
$$i_1=i_2,\qquad\text{or}\qquad j_1=j_2,\qquad\text{or}\qquad (i_1-i_2)(j_1-j_2)\lt 0.$$
الحالتان الأوليان هما نهاية مشتركة في الأسفل أو الأعلى. أما الحالة الثالثة فتعني أن ترتيب النهايات انعكس بين الخطين، ومن ثم يوجد تقاطع داخلي.
نعد أولا كل ثلاثيات القطع التي تتقاطع كل قطعتين منها. إذا استعملت الثلاثية ثلاث نهايات سفلية وثلاث نهايات علوية مختلفة، فالربط الصحيح الوحيد هو الربط العكسي، ومساهمته \(\binom m3\binom n3\).
إذا استعملت ثلاث نهايات سفلية ونهايتين علويتين فقط، نحصل على \(\binom m3 n(n-1)\). وبالتناظر، حالة نهايتين سفليتين وثلاث نهايات علوية تعطي \(m(m-1)\binom n3\). أما حالة \(2\times 2\) فتعطي اختيارين صالحين في كل مستطيل صغير:
$$2\binom m2\binom n2={m(m-1)n(n-1)\over 2}.$$
إذن عدد المرشحات هو
$$P(m,n)=\binom m3\binom n3+\binom m3 n(n-1)+m(m-1)\binom n3+{m(m-1)n(n-1)\over 2}.$$
المرشح لا يكون مثلثا إذا مرت القطع الثلاث كلها بنقطة واحدة. في الشبكة المزدوجة هذا يكافئ أن تكون النقاط الثلاث \((i,j)\) على خط واحد ذي ميل سالب.
ليكن الفرق الأفقي بين النقطتين الطرفيتين \(A\)، والفرق العمودي \(B\). يمكن وضع الطرفين بعدد \((m-A)(n-B)\) من الطرق، وعدد نقاط الشبكة الداخلية بينهما هو
$$\gcd(A,B)-1.$$
لذلك
$$C(m,n)=\sum_{A=1}^{m-1}\sum_{B=1}^{n-1}(\gcd(A,B)-1)(m-A)(n-B).$$
نستخدم الهوية
$$\gcd(A,B)=\sum_{d\mid\gcd(A,B)}\varphi(d).$$
وبتبديل ترتيب الجمع نحصل على
$$C(m,n)=\sum_{d=2}^{\min(m,n)-1}\varphi(d) \left(\sum_{r=1}^{\lfloor(m-1)/d\rfloor}(m-dr)\right) \left(\sum_{s=1}^{\lfloor(n-1)/d\rfloor}(n-ds)\right).$$
إذا عرّفنا \(Q_m(d)=\lfloor(m-1)/d\rfloor\)، فالقوس الأول يساوي \(mQ_m(d)-dQ_m(d)(Q_m(d)+1)/2\).
القيم \(Q_m(d)\) و \(Q_n(d)\) ثابتة على فترات طويلة، لذلك يكفي لكل كتلة استعمال
$$\Phi_k(x)=\sum_{d\le x}d^k\varphi(d),\qquad k=0,1,2.$$
يبني البرنامج هذه المجاميع حتى \(5\cdot 10^6\) بغربال خطي، ثم يستعمل عودية محفوظة للمدخلات الأكبر مع تجميع القيم المتساوية لـ \(\lfloor n/d\rfloor\).
القيمة المطلوبة هي
$$\boxed{T(m,n)=P(m,n)-C(m,n)\pmod {10^9+7}}.$$
في المثال \(m=3,n=5\)، نجد \(P=150\)، وعدد الثلاثيات المتلاقية في نقطة واحدة هو \(4\)، فتكون النتيجة \(146\). كما يتحقق الكود من كل الحالات الصغيرة حتى \(5\times 5\) بالعد المباشر.
الدالة pairwise_triangle_candidates تحسب \(P\) مباشرة. الصنف TotientSummatory يخزن \(\Phi_0,\Phi_1,\Phi_2\) ويجيب عن الاستعلامات الكبيرة بالتخزين المؤقت. ثم تمر concurrent_triples على كتل القسمة الصحيحة وتحسب \(C\) بالترديد.
الغربال يحتاج \(O(L)\) وقتا وذاكرة حيث \(L=5\cdot 10^6\). الجمع الرئيسي يستعمل عددا من الكتل من رتبة \(O(\sqrt{\min(m,n)})\). أما العد المباشر لكل ثلاثيات القطع فيتطلب \(O((mn)^3)\)، ولذلك لا يصلح هنا.