The geometric statement can be converted into an arithmetic counting problem. For a fixed bound pair \((A,B)\), every admissible tangent configuration is encoded by a positive integer \(n \le A\), a positive integer \(b \le B\), and a factor pair of the square \(b^2\). The direct formulation is still too slow, but it exposes enough structure to turn the geometry into a divisor sum.
The official task requires two such counts, for \((10^8,10^9)\) and \((10^9,10^8)\), and adds them together. The whole challenge is therefore to derive a fast closed form for a single subproblem \(F(A,B)\).
The direct counting model shows that \(F(A,B)\) can be written in terms of positive integers satisfying
$$1 \le n \le A,\qquad 1 \le b \le B,\qquad cd=b^2,$$
together with the two arithmetic constraints
$$b \mid n(c+d),\qquad \frac{n(c+d)}{b}\equiv d-c \pmod 2.$$
Whenever these conditions hold, there are two symmetric sign choices, so each admissible arithmetic encoding contributes exactly \(2\) geometric configurations. This is the only part where the geometry still appears; from here onward the problem is pure number theory.
Let \(\lambda=\gcd(c,d)\). Then \(c=\lambda c_0\), \(d=\lambda d_0\), and \(\gcd(c_0,d_0)=1\). Since \(cd=b^2\), we obtain
$$c_0d_0=\left(\frac{b}{\lambda}\right)^2.$$
A product of two coprime positive integers can be a square only if each factor is already a square. Hence there exist coprime integers \(p,q \ge 1\) such that
$$c=\lambda p^2,\qquad d=\lambda q^2,\qquad \gcd(p,q)=1,$$
and therefore
$$b=\lambda pq.$$
This is the key normalization step: the square condition is no longer hidden inside divisors of \(b^2\); it is explicit in the parameters \((\lambda,p,q)\).
Substituting the decomposition above into the divisibility condition gives
$$\lambda pq \mid n\lambda(p^2+q^2),$$
so equivalently
$$pq \mid n(p^2+q^2).$$
Now \(\gcd(p,q)=1\), and no prime dividing \(pq\) can divide \(p^2+q^2\). Therefore
$$\gcd(pq,p^2+q^2)=1,$$
which forces
$$pq \mid n.$$
Write
$$m=pq,\qquad n=mt.$$
Then \(t\) can range through
$$1 \le t \le \left\lfloor\frac{A}{m}\right\rfloor,$$
while the scale factor \(\lambda\) is constrained only by \(b=\lambda m \le B\), hence
$$1 \le \lambda \le \left\lfloor\frac{B}{m}\right\rfloor.$$
Fix \(m\). We must count ordered coprime pairs \((p,q)\) such that \(pq=m\). If
$$m=\prod_{i=1}^{r}\ell_i^{e_i},$$
then coprimality means each whole prime power \(\ell_i^{e_i}\) must go entirely to \(p\) or entirely to \(q\). Every distinct prime gives exactly two choices, so the number of ordered pairs is
$$2^r=2^{\omega(m)},$$
where \(\omega(m)\) is the number of distinct prime divisors of \(m\). This explains the multiplicative weight used in the implementation.
After substitution, the parity condition becomes
$$\frac{n(c+d)}{b}=t(p^2+q^2),\qquad d-c=\lambda(q^2-p^2).$$
We need these two quantities to have the same parity. Since
$$p^2+q^2\equiv q^2-p^2 \pmod 2,$$
the condition is equivalent to
$$ (t-\lambda)(p^2+q^2)\equiv 0 \pmod 2.$$
If \(m\) is odd, then both \(p\) and \(q\) are odd, so \(p^2+q^2\) is even. The parity restriction disappears completely. For each of the \(2^{\omega(m)}\) coprime factorizations, every pair \((t,\lambda)\) is valid, and the two sign choices contribute
$$2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor.$$
If \(m\) is even, exactly one of \(p,q\) is even, so \(p^2+q^2\) is odd. Now we must have \(t\equiv\lambda\pmod 2\). Let
$$t_{\max}=\left\lfloor\frac{A}{m}\right\rfloor,\qquad \lambda_{\max}=\left\lfloor\frac{B}{m}\right\rfloor.$$
The number of pairs \((t,\lambda)\) with equal parity is
$$\left\lceil\frac{t_{\max}}{2}\right\rceil\left\lceil\frac{\lambda_{\max}}{2}\right\rceil+\left\lfloor\frac{t_{\max}}{2}\right\rfloor\left\lfloor\frac{\lambda_{\max}}{2}\right\rfloor =\frac{t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2)}{2}.$$
After multiplying by the two sign choices, the even case contributes
$$t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2).$$
Define the parity-dependent unit contribution by
$$U_m(A,B)= \begin{cases} 2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor, & m\ \mathrm{odd},\\[6pt] \left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor+ \left(\left\lfloor\frac{A}{m}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{B}{m}\right\rfloor\bmod 2\right), & m\ \mathrm{even}. \end{cases}$$
Then the whole subproblem is
$$\boxed{F(A,B)=\sum_{m=1}^{\min(A,B)}2^{\omega(m)}\,U_m(A,B).}$$
The required total is
$$F(10^8,10^9)+F(10^9,10^8).$$
The summand is symmetric in \(A\) and \(B\), so the two terms are equal, but writing the result as a sum of two evaluations mirrors the original statement and the implementations.
Only \(m=1\) and \(m=2\) can contribute.
For \(m=1\), we have \(\omega(1)=0\), so the weight is \(1\). Since \(1\) is odd,
$$U_1(2,10)=2\cdot 2\cdot 10=40.$$
For \(m=2\), we have \(\omega(2)=1\), so the weight is \(2\). Since \(2\) is even,
$$U_2(2,10)=\left\lfloor\frac{2}{2}\right\rfloor\left\lfloor\frac{10}{2}\right\rfloor+ \left(\left\lfloor\frac{2}{2}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{10}{2}\right\rfloor\bmod 2\right) =1\cdot 5+1\cdot 1=6.$$
Therefore
$$F(2,10)=1\cdot 40+2\cdot 6=52,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations first precompute \(\omega(m)\) for every \(m\) up to the largest required limit by a sieve: each prime visits all of its multiples once, so every integer accumulates its number of distinct prime divisors. Then the implementation evaluates the summation above term by term, using only floor divisions, parity checks, a bit shift for \(2^{\omega(m)}\), and integer accumulation.
The same scalar routine is applied to the two official bound pairs. Because each \(m\)-term is independent, the outer sum is naturally parallelizable; the C++ and Java implementations exploit that independence, while the Python implementation keeps the same mathematics in a straightforward single-threaded loop.
Let \(L=\max(\min(10^8,10^9),\min(10^9,10^8))=10^8\). Building the distinct-prime-factor table costs \(O(L\log\log L)\) time and \(O(L)\) memory. The final summation is \(O(L)\) time because every \(m\) contributes a constant-time term. Thus the overall method runs in \(O(L\log\log L)\) time and uses \(O(L)\) space.
Die geometrische Aufgabenstellung lässt sich in ein arithmetisches Zählproblem umformen. Für ein festes Parameterpaar \((A,B)\) wird jede zulässige Tangentenkonfiguration durch eine positive ganze Zahl \(n \le A\), eine positive ganze Zahl \(b \le B\) und ein Teilerpaar des Quadrats \(b^2\) beschrieben. Die direkte Form ist noch zu langsam, aber sie legt bereits die Struktur frei, aus der die schnelle Summenformel entsteht.
Gesucht ist die Summe der beiden Teilwerte zu \((10^8,10^9)\) und \((10^9,10^8)\). Daher genügt es, eine effiziente geschlossene Darstellung für ein einzelnes Teilproblem \(F(A,B)\) herzuleiten.
Das direkte Modell zeigt, dass \(F(A,B)\) über positive ganze Zahlen mit
$$1 \le n \le A,\qquad 1 \le b \le B,\qquad cd=b^2$$
gezählt werden kann, wobei zusätzlich gelten muss:
$$b \mid n(c+d),\qquad \frac{n(c+d)}{b}\equiv d-c \pmod 2.$$
Wenn diese Bedingungen erfüllt sind, gibt es zwei symmetrische Vorzeichenwahlen. Jede zulässige arithmetische Kodierung liefert also genau \(2\) geometrische Konfigurationen.
Setze \(\lambda=\gcd(c,d)\). Dann gilt \(c=\lambda c_0\), \(d=\lambda d_0\) und \(\gcd(c_0,d_0)=1\). Aus \(cd=b^2\) folgt
$$c_0d_0=\left(\frac{b}{\lambda}\right)^2.$$
Ein Produkt zweier teilerfremder positiver Zahlen kann nur dann ein Quadrat sein, wenn beide Faktoren selbst Quadrate sind. Also existieren teilerfremde \(p,q \ge 1\) mit
$$c=\lambda p^2,\qquad d=\lambda q^2,\qquad \gcd(p,q)=1,$$
und damit
$$b=\lambda pq.$$
Damit ist die Quadratbedingung vollständig normalisiert: Statt mit beliebigen Teilern von \(b^2\) zu arbeiten, zählen wir direkt nach \((\lambda,p,q)\).
Einsetzen in \(b \mid n(c+d)\) ergibt
$$\lambda pq \mid n\lambda(p^2+q^2),$$
also
$$pq \mid n(p^2+q^2).$$
Wegen \(\gcd(p,q)=1\) kann kein Primteiler von \(pq\) den Ausdruck \(p^2+q^2\) teilen. Daher gilt
$$\gcd(pq,p^2+q^2)=1,$$
und folglich zwingend
$$pq \mid n.$$
Schreibe
$$m=pq,\qquad n=mt.$$
Dann läuft \(t\) durch
$$1 \le t \le \left\lfloor\frac{A}{m}\right\rfloor,$$
während der Skalierungsfaktor \(\lambda\) nur durch \(b=\lambda m \le B\) beschränkt ist:
$$1 \le \lambda \le \left\lfloor\frac{B}{m}\right\rfloor.$$
Für festes \(m\) müssen wir die geordneten teilerfremden Paare \((p,q)\) mit \(pq=m\) zählen. Ist
$$m=\prod_{i=1}^{r}\ell_i^{e_i},$$
dann erzwingt die Teilerfremdheit, dass jede vollständige Primzahlpotenz \(\ell_i^{e_i}\) entweder ganz in \(p\) oder ganz in \(q\) liegt. Jede verschiedene Primzahl liefert also genau zwei Möglichkeiten. Somit ist die Anzahl der geordneten Paare
$$2^r=2^{\omega(m)},$$
wobei \(\omega(m)\) die Anzahl der verschiedenen Primteiler von \(m\) bezeichnet.
Die Paritätsbedingung wird nach dem Einsetzen zu
$$\frac{n(c+d)}{b}=t(p^2+q^2),\qquad d-c=\lambda(q^2-p^2).$$
Beide Größen müssen dieselbe Parität haben. Da
$$p^2+q^2\equiv q^2-p^2 \pmod 2,$$
ist das äquivalent zu
$$ (t-\lambda)(p^2+q^2)\equiv 0 \pmod 2.$$
Ist \(m\) ungerade, dann sind \(p\) und \(q\) beide ungerade, also ist \(p^2+q^2\) gerade. Die Paritätsbedingung ist automatisch erfüllt. Für jede der \(2^{\omega(m)}\) Faktorisierungen ist jedes Paar \((t,\lambda)\) zulässig, und die zwei Vorzeichen liefern
$$2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor.$$
Ist \(m\) gerade, dann ist genau einer von \(p,q\) gerade und \(p^2+q^2\) damit ungerade. Dann muss \(t\equiv\lambda\pmod 2\) gelten. Mit
$$t_{\max}=\left\lfloor\frac{A}{m}\right\rfloor,\qquad \lambda_{\max}=\left\lfloor\frac{B}{m}\right\rfloor$$
ist die Zahl gleichparitärer Paare
$$\left\lceil\frac{t_{\max}}{2}\right\rceil\left\lceil\frac{\lambda_{\max}}{2}\right\rceil+\left\lfloor\frac{t_{\max}}{2}\right\rfloor\left\lfloor\frac{\lambda_{\max}}{2}\right\rfloor =\frac{t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2)}{2}.$$
Mit den zwei Vorzeichen ergibt der gerade Fall daher
$$t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2).$$
Definiere den paritätsabhängigen Einheitsbeitrag als
$$U_m(A,B)= \begin{cases} 2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor, & m\ \mathrm{odd},\\[6pt] \left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor+ \left(\left\lfloor\frac{A}{m}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{B}{m}\right\rfloor\bmod 2\right), & m\ \mathrm{even}. \end{cases}$$
Dann lautet das gesamte Teilproblem
$$\boxed{F(A,B)=\sum_{m=1}^{\min(A,B)}2^{\omega(m)}\,U_m(A,B).}$$
Gesucht ist also
$$F(10^8,10^9)+F(10^9,10^8).$$
Der Summand ist symmetrisch in \(A\) und \(B\), daher sind beide Terme gleich; die zweifache Auswertung bleibt jedoch in derselben Form wie Aufgabenstellung und Implementierung.
Nur \(m=1\) und \(m=2\) können beitragen.
Für \(m=1\) ist \(\omega(1)=0\), also das Gewicht \(1\). Weil \(1\) ungerade ist, gilt
$$U_1(2,10)=2\cdot 2\cdot 10=40.$$
Für \(m=2\) ist \(\omega(2)=1\), also das Gewicht \(2\). Da \(2\) gerade ist, folgt
$$U_2(2,10)=\left\lfloor\frac{2}{2}\right\rfloor\left\lfloor\frac{10}{2}\right\rfloor+ \left(\left\lfloor\frac{2}{2}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{10}{2}\right\rfloor\bmod 2\right) =1\cdot 5+1\cdot 1=6.$$
Somit
$$F(2,10)=1\cdot 40+2\cdot 6=52,$$
genau der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen berechnen zunächst \(\omega(m)\) für alle benötigten \(m\) per Sieb: Jede Primzahl erhöht den Zähler aller ihrer Vielfachen genau einmal, sodass jede Zahl ihre Anzahl verschiedener Primteiler erhält. Danach wird die Summenformel direkt ausgewertet: zwei Ganzzahldivisionen, ein Paritätstest, das Gewicht \(2^{\omega(m)}\) und eine Addition pro \(m\).
Dieselbe skalare Zählfunktion wird auf beide offiziellen Parameterpaare angewandt. Da jeder Summand unabhängig ist, lässt sich die äußere Summe problemlos parallelisieren; C++ und Java nutzen das, während Python dieselbe Mathematik in einer einfachen sequentiellen Schleife umsetzt.
Sei \(L=\max(\min(10^8,10^9),\min(10^9,10^8))=10^8\). Das Sieb für die Anzahl verschiedener Primteiler benötigt \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Die anschließende Summation ist \(O(L)\), weil jeder Wert von \(m\) nur einen konstant teuren Beitrag liefert. Insgesamt ergibt das \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher.
Geometrik ifade, bütünüyle aritmetik bir sayma problemine dönüştürülebilir. Sabit bir \((A,B)\) çifti için her geçerli teğet konfigürasyonu, \(n \le A\) olan pozitif bir tam sayı, \(b \le B\) olan başka bir pozitif tam sayı ve \(b^2\)'nin bir çarpan çifti ile kodlanır. Doğrudan formül hâlâ yavaştır; fakat hızlı toplam formülünü doğuran yapı tam da burada görünür hâle gelir.
Resmî görev, \((10^8,10^9)\) ve \((10^9,10^8)\) için elde edilen iki sayının toplamını ister. Bu yüzden asıl iş, tek bir alt problem \(F(A,B)\) için hızlı bir kapalı form türetmektir.
Doğrudan sayım modeli, \(F(A,B)\)'nin şu koşulları sağlayan pozitif tam sayılar üzerinden yazılabildiğini gösterir:
$$1 \le n \le A,\qquad 1 \le b \le B,\qquad cd=b^2,$$
ve ayrıca
$$b \mid n(c+d),\qquad \frac{n(c+d)}{b}\equiv d-c \pmod 2.$$
Bu şartlar sağlandığında iki simetrik işaret seçimi vardır. Dolayısıyla her geçerli aritmetik kodlama tam olarak \(2\) geometrik konfigürasyon üretir.
\(\lambda=\gcd(c,d)\) olsun. O zaman \(c=\lambda c_0\), \(d=\lambda d_0\) ve \(\gcd(c_0,d_0)=1\) olur. \(cd=b^2\) eşitliğinden
$$c_0d_0=\left(\frac{b}{\lambda}\right)^2$$
elde edilir. Aralarında asal iki pozitif tamsayının çarpımı ancak her biri ayrı ayrı kare ise kare olabilir. Bu nedenle aralarında asal \(p,q \ge 1\) için
$$c=\lambda p^2,\qquad d=\lambda q^2,\qquad \gcd(p,q)=1,$$
ve dolayısıyla
$$b=\lambda pq$$
yazabiliriz. Böylece kare olma koşulu açık bir parametrizasyona dönüşür.
Yukarıdaki ayrışımı \(b \mid n(c+d)\) içine koyarsak
$$\lambda pq \mid n\lambda(p^2+q^2),$$
yani
$$pq \mid n(p^2+q^2)$$
elde ederiz. \(\gcd(p,q)=1\) olduğundan, \(pq\)'nun hiçbir asal böleni \(p^2+q^2\)'yi bölemez. Demek ki
$$\gcd(pq,p^2+q^2)=1,$$
ve zorunlu olarak
$$pq \mid n.$$
Şimdi
$$m=pq,\qquad n=mt$$
yazalım. Böylece
$$1 \le t \le \left\lfloor\frac{A}{m}\right\rfloor,$$
ve \(b=\lambda m \le B\) olduğundan
$$1 \le \lambda \le \left\lfloor\frac{B}{m}\right\rfloor$$
olur.
Sabit \(m\) için, \(pq=m\) ve \(\gcd(p,q)=1\) koşulunu sağlayan sıralı çiftleri saymamız gerekir. Eğer
$$m=\prod_{i=1}^{r}\ell_i^{e_i}$$
ise, aralarında asallık her asal kuvvetin \(\ell_i^{e_i}\) ya tamamen \(p\)'ye ya da tamamen \(q\)'ya gitmesini zorlar. Her farklı asal için tam iki seçim vardır. Dolayısıyla sıralı çift sayısı
$$2^r=2^{\omega(m)}$$
olur; burada \(\omega(m)\), \(m\)'nin farklı asal bölen sayısıdır.
Yerine koyduktan sonra parite koşulu
$$\frac{n(c+d)}{b}=t(p^2+q^2),\qquad d-c=\lambda(q^2-p^2)$$
şekline gelir. Bu iki büyüklüğün aynı paritede olması gerekir. Çünkü
$$p^2+q^2\equiv q^2-p^2 \pmod 2,$$
koşul şu eşdeğer biçime dönüşür:
$$ (t-\lambda)(p^2+q^2)\equiv 0 \pmod 2.$$
Eğer \(m\) tek ise, \(p\) ve \(q\) de tektir; bu yüzden \(p^2+q^2\) çifttir. Parite kısıtı otomatik olarak sağlanır. Her \((t,\lambda)\) çifti geçerlidir ve iki işaret seçimi ile katkı
$$2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor$$
olur.
Eğer \(m\) çift ise, \(p\) ve \(q\)'dan yalnızca biri çifttir; dolayısıyla \(p^2+q^2\) tektir. Bu durumda \(t\equiv\lambda\pmod 2\) gerekir. Şimdi
$$t_{\max}=\left\lfloor\frac{A}{m}\right\rfloor,\qquad \lambda_{\max}=\left\lfloor\frac{B}{m}\right\rfloor$$
olsun. Aynı pariteye sahip çiftlerin sayısı
$$\left\lceil\frac{t_{\max}}{2}\right\rceil\left\lceil\frac{\lambda_{\max}}{2}\right\rceil+\left\lfloor\frac{t_{\max}}{2}\right\rfloor\left\lfloor\frac{\lambda_{\max}}{2}\right\rfloor =\frac{t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2)}{2}$$
olur. İki işaret seçimi ile çift durumundaki toplam katkı
$$t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2)$$
şeklindedir.
Pariteye bağlı birim katkıyı şöyle tanımlayalım:
$$U_m(A,B)= \begin{cases} 2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor, & m\ \mathrm{odd},\\[6pt] \left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor+ \left(\left\lfloor\frac{A}{m}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{B}{m}\right\rfloor\bmod 2\right), & m\ \mathrm{even}. \end{cases}$$
Böylece tek alt problem
$$\boxed{F(A,B)=\sum_{m=1}^{\min(A,B)}2^{\omega(m)}\,U_m(A,B).}$$
aranan toplam ise
$$F(10^8,10^9)+F(10^9,10^8)$$
olur. Toplamdaki terim \(A\) ve \(B\) açısından simetriktir; yani iki terim eşittir. Yine de iki ayrı değerlendirme biçimi, özgün problemin yapısını daha doğrudan yansıtır.
Katkı verebilecek tek değerler \(m=1\) ve \(m=2\)'dir.
\(m=1\) için \(\omega(1)=0\), yani ağırlık \(1\)'dir. \(1\) tek olduğundan
$$U_1(2,10)=2\cdot 2\cdot 10=40.$$
\(m=2\) için \(\omega(2)=1\), yani ağırlık \(2\)'dir. \(2\) çift olduğu için
$$U_2(2,10)=\left\lfloor\frac{2}{2}\right\rfloor\left\lfloor\frac{10}{2}\right\rfloor+ \left(\left\lfloor\frac{2}{2}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{10}{2}\right\rfloor\bmod 2\right) =1\cdot 5+1\cdot 1=6.$$
Dolayısıyla
$$F(2,10)=1\cdot 40+2\cdot 6=52,$$
ve bu değer uygulamanın kontrol noktasıyla tam olarak aynıdır.
C++, Python ve Java uygulamaları önce gereken en büyük sınıra kadar \(\omega(m)\) dizisini elekle oluşturur: her asal, kendi katlarının sayacını bir kez artırır ve böylece her tamsayı farklı asal bölen sayısını alır. Ardından yukarıdaki toplam doğrudan hesaplanır; her \(m\) için iki taban bölmesi, bir parite testi, \(2^{\omega(m)}\) ağırlığı ve bir toplama işlemi yeterlidir.
Aynı skaler sayma yordamı iki resmî parametre çifti için uygulanır. Her \(m\)-terimi diğerlerinden bağımsız olduğundan dış toplam kolayca paralelleştirilebilir; C++ ve Java bunu kullanır, Python ise aynı matematiği daha sade tek iş parçacıklı bir döngüde yürütür.
\(L=\max(\min(10^8,10^9),\min(10^9,10^8))=10^8\) olsun. Farklı asal bölen sayısını üreten elek \(O(L\log\log L)\) zaman ve \(O(L)\) bellek ister. Son toplam ise \(O(L)\) zamandır; çünkü her \(m\) için sabit maliyetli tek bir terim vardır. Toplam karmaşıklık \(O(L\log\log L)\) zaman ve \(O(L)\) bellektir.
La parte geométrica puede transformarse en un problema puramente aritmético. Para un par fijo \((A,B)\), cada configuración tangente válida queda codificada por un entero positivo \(n \le A\), otro entero positivo \(b \le B\) y un par de factores del cuadrado \(b^2\). La formulación directa sigue siendo demasiado lenta, pero ya revela la estructura que permite obtener una suma cerrada.
La tarea final pide sumar los dos conteos correspondientes a \((10^8,10^9)\) y \((10^9,10^8)\). Por eso basta con derivar una fórmula rápida para un solo subproblema \(F(A,B)\).
El modelo directo muestra que \(F(A,B)\) se puede contar mediante enteros positivos que satisfacen
$$1 \le n \le A,\qquad 1 \le b \le B,\qquad cd=b^2,$$
junto con las dos restricciones
$$b \mid n(c+d),\qquad \frac{n(c+d)}{b}\equiv d-c \pmod 2.$$
Siempre que estas condiciones se cumplen, existen dos elecciones simétricas de signo. Así, cada codificación aritmética admisible aporta exactamente \(2\) configuraciones geométricas.
Sea \(\lambda=\gcd(c,d)\). Entonces \(c=\lambda c_0\), \(d=\lambda d_0\) y \(\gcd(c_0,d_0)=1\). Como \(cd=b^2\), se obtiene
$$c_0d_0=\left(\frac{b}{\lambda}\right)^2.$$
El producto de dos enteros positivos coprimos solo puede ser un cuadrado si cada factor ya es un cuadrado. Por lo tanto existen \(p,q \ge 1\) coprimos tales que
$$c=\lambda p^2,\qquad d=\lambda q^2,\qquad \gcd(p,q)=1,$$
y en consecuencia
$$b=\lambda pq.$$
Este es el paso de normalización fundamental: la condición cuadrática deja de estar escondida entre divisores arbitrarios y pasa a ser explícita.
Al sustituir en \(b \mid n(c+d)\) obtenemos
$$\lambda pq \mid n\lambda(p^2+q^2),$$
es decir,
$$pq \mid n(p^2+q^2).$$
Como \(\gcd(p,q)=1\), ningún primo que divide a \(pq\) puede dividir \(p^2+q^2\). Por ello
$$\gcd(pq,p^2+q^2)=1,$$
y la condición obliga a
$$pq \mid n.$$
Escribimos
$$m=pq,\qquad n=mt.$$
Entonces \(t\) puede variar en
$$1 \le t \le \left\lfloor\frac{A}{m}\right\rfloor,$$
mientras que el factor de escala \(\lambda\) solo está limitado por \(b=\lambda m \le B\), o sea
$$1 \le \lambda \le \left\lfloor\frac{B}{m}\right\rfloor.$$
Fijado \(m\), debemos contar los pares ordenados coprimos \((p,q)\) con \(pq=m\). Si
$$m=\prod_{i=1}^{r}\ell_i^{e_i},$$
la coprimalidad obliga a que cada potencia prima completa \(\ell_i^{e_i}\) vaya entera a \(p\) o entera a \(q\). Cada primo distinto aporta exactamente dos opciones. Por tanto el número de pares ordenados es
$$2^r=2^{\omega(m)},$$
donde \(\omega(m)\) denota el número de divisores primos distintos de \(m\).
Tras sustituir, la condición de paridad toma la forma
$$\frac{n(c+d)}{b}=t(p^2+q^2),\qquad d-c=\lambda(q^2-p^2).$$
Estas dos cantidades deben tener la misma paridad. Como
$$p^2+q^2\equiv q^2-p^2 \pmod 2,$$
la condición equivale a
$$ (t-\lambda)(p^2+q^2)\equiv 0 \pmod 2.$$
Si \(m\) es impar, entonces \(p\) y \(q\) son ambos impares, de modo que \(p^2+q^2\) es par. La restricción de paridad desaparece. Para cada una de las \(2^{\omega(m)}\) factorizaciones coprimas, todo par \((t,\lambda)\) es válido, y las dos elecciones de signo aportan
$$2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor.$$
Si \(m\) es par, exactamente uno de \(p,q\) es par, por lo que \(p^2+q^2\) es impar. Ahora se requiere \(t\equiv\lambda\pmod 2\). Definimos
$$t_{\max}=\left\lfloor\frac{A}{m}\right\rfloor,\qquad \lambda_{\max}=\left\lfloor\frac{B}{m}\right\rfloor.$$
El número de pares \((t,\lambda)\) con la misma paridad es
$$\left\lceil\frac{t_{\max}}{2}\right\rceil\left\lceil\frac{\lambda_{\max}}{2}\right\rceil+\left\lfloor\frac{t_{\max}}{2}\right\rfloor\left\lfloor\frac{\lambda_{\max}}{2}\right\rfloor =\frac{t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2)}{2}.$$
Multiplicando por las dos elecciones de signo, la contribución del caso par es
$$t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2).$$
Definimos la contribución unitaria dependiente de la paridad como
$$U_m(A,B)= \begin{cases} 2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor, & m\ \mathrm{odd},\\[6pt] \left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor+ \left(\left\lfloor\frac{A}{m}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{B}{m}\right\rfloor\bmod 2\right), & m\ \mathrm{even}. \end{cases}$$
Entonces el subproblema completo es
$$\boxed{F(A,B)=\sum_{m=1}^{\min(A,B)}2^{\omega(m)}\,U_m(A,B).}$$
El total pedido es
$$F(10^8,10^9)+F(10^9,10^8).$$
El sumando es simétrico en \(A\) y \(B\), así que ambos términos son iguales, aunque mantener la suma de dos evaluaciones reproduce fielmente la formulación original.
Solo pueden contribuir \(m=1\) y \(m=2\).
Para \(m=1\), \(\omega(1)=0\), por lo tanto el peso es \(1\). Como \(1\) es impar,
$$U_1(2,10)=2\cdot 2\cdot 10=40.$$
Para \(m=2\), \(\omega(2)=1\), por lo tanto el peso es \(2\). Como \(2\) es par,
$$U_2(2,10)=\left\lfloor\frac{2}{2}\right\rfloor\left\lfloor\frac{10}{2}\right\rfloor+ \left(\left\lfloor\frac{2}{2}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{10}{2}\right\rfloor\bmod 2\right) =1\cdot 5+1\cdot 1=6.$$
Por consiguiente
$$F(2,10)=1\cdot 40+2\cdot 6=52,$$
que coincide con el punto de control usado por la implementación.
Las implementaciones en C++, Python y Java primero precalculan \(\omega(m)\) hasta el mayor límite necesario mediante una criba: cada primo recorre sus múltiplos exactamente una vez y cada entero acumula así su número de factores primos distintos. Después se evalúa la suma anterior término por término usando solo divisiones enteras, pruebas de paridad, el peso \(2^{\omega(m)}\) y una acumulación entera.
La misma rutina escalar se aplica a los dos pares oficiales de cotas. Como cada término asociado a \(m\) es independiente de los demás, la suma exterior se paraleliza de manera natural; las versiones en C++ y Java aprovechan esa independencia, mientras que la versión en Python mantiene la misma fórmula en un bucle secuencial simple.
Sea \(L=\max(\min(10^8,10^9),\min(10^9,10^8))=10^8\). Construir la tabla de factores primos distintos cuesta \(O(L\log\log L)\) tiempo y \(O(L)\) memoria. La suma final cuesta \(O(L)\) tiempo porque cada \(m\) aporta un término de costo constante. En consecuencia, el método completo usa \(O(L\log\log L)\) tiempo y \(O(L)\) espacio.
这道几何题最终可以化成纯整数计数。对固定参数对 \((A,B)\)，每个合法的切线构型都可以用一个正整数 \(n \le A\)、一个正整数 \(b \le B\) 以及平方数 \(b^2\) 的一组因子来表示。直接枚举仍然太慢，但它已经暴露出可以被数论化简的核心结构。
题目最终要求把 \((10^8,10^9)\) 与 \((10^9,10^8)\) 这两个子问题的结果相加。因此，关键就在于为单个子问题 \(F(A,B)\) 推出一个足够快的闭式求和公式。
直接计数模型表明，\(F(A,B)\) 可以写成满足下列条件的正整数计数：
$$1 \le n \le A,\qquad 1 \le b \le B,\qquad cd=b^2,$$
并且还要满足
$$b \mid n(c+d),\qquad \frac{n(c+d)}{b}\equiv d-c \pmod 2.$$
一旦这些条件成立，就有两个对称的符号选择，所以每一个合法的算术编码都会对应恰好 \(2\) 个几何构型。到这一步为止还看得到几何背景，但从这里开始问题已经完全变成整数论。
令 \(\lambda=\gcd(c,d)\)。于是 \(c=\lambda c_0\)、\(d=\lambda d_0\)，并且 \(\gcd(c_0,d_0)=1\)。由 \(cd=b^2\) 可得
$$c_0d_0=\left(\frac{b}{\lambda}\right)^2.$$
两个互素正整数的乘积若是平方数，则它们各自都必须是平方数。因此存在互素整数 \(p,q \ge 1\)，使得
$$c=\lambda p^2,\qquad d=\lambda q^2,\qquad \gcd(p,q)=1,$$
从而
$$b=\lambda pq.$$
这是整个推导中最关键的规范化步骤，因为原来隐藏在 \(b^2\) 因子对中的平方结构，现在被显式写成了 \((\lambda,p,q)\) 的形式。
把上面的分解代入 \(b \mid n(c+d)\)，得到
$$\lambda pq \mid n\lambda(p^2+q^2),$$
即
$$pq \mid n(p^2+q^2).$$
由于 \(\gcd(p,q)=1\)，任何整除 \(pq\) 的质数都不可能整除 \(p^2+q^2\)。因此
$$\gcd(pq,p^2+q^2)=1,$$
于是必然有
$$pq \mid n.$$
写成
$$m=pq,\qquad n=mt.$$
那么 \(t\) 的范围就是
$$1 \le t \le \left\lfloor\frac{A}{m}\right\rfloor,$$
而缩放因子 \(\lambda\) 只受 \(b=\lambda m \le B\) 的限制，因此
$$1 \le \lambda \le \left\lfloor\frac{B}{m}\right\rfloor.$$
固定 \(m\) 以后，我们需要统计满足 \(pq=m\) 且 \(\gcd(p,q)=1\) 的有序对 \((p,q)\)。如果
$$m=\prod_{i=1}^{r}\ell_i^{e_i},$$
那么互素性要求每个完整的质数幂 \(\ell_i^{e_i}\) 要么全部放入 \(p\)，要么全部放入 \(q\)。每个不同质数都只有两种选择，因此有序对总数为
$$2^r=2^{\omega(m)},$$
其中 \(\omega(m)\) 表示 \(m\) 的不同质因子个数。这正是程序中出现的乘法权重。
代换之后，奇偶条件变成
$$\frac{n(c+d)}{b}=t(p^2+q^2),\qquad d-c=\lambda(q^2-p^2).$$
这两个量必须同奇同偶。因为
$$p^2+q^2\equiv q^2-p^2 \pmod 2,$$
所以条件等价于
$$ (t-\lambda)(p^2+q^2)\equiv 0 \pmod 2.$$
如果 \(m\) 是奇数，那么 \(p\) 和 \(q\) 都是奇数，所以 \(p^2+q^2\) 是偶数，奇偶限制自动满足。对于每一种互素分解，任意 \((t,\lambda)\) 都可行，再乘上两个符号选择，贡献为
$$2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor.$$
如果 \(m\) 是偶数，那么 \(p,q\) 中恰有一个是偶数，所以 \(p^2+q^2\) 是奇数。这时必须满足 \(t\equiv\lambda\pmod 2\)。设
$$t_{\max}=\left\lfloor\frac{A}{m}\right\rfloor,\qquad \lambda_{\max}=\left\lfloor\frac{B}{m}\right\rfloor.$$
同奇偶的 \((t,\lambda)\) 对数为
$$\left\lceil\frac{t_{\max}}{2}\right\rceil\left\lceil\frac{\lambda_{\max}}{2}\right\rceil+\left\lfloor\frac{t_{\max}}{2}\right\rfloor\left\lfloor\frac{\lambda_{\max}}{2}\right\rfloor =\frac{t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2)}{2}.$$
再乘以两个符号选择，偶数情形的总贡献就是
$$t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2).$$
定义与奇偶性有关的单位贡献
$$U_m(A,B)= \begin{cases} 2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor, & m\ \mathrm{odd},\\[6pt] \left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor+ \left(\left\lfloor\frac{A}{m}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{B}{m}\right\rfloor\bmod 2\right), & m\ \mathrm{even}. \end{cases}$$
于是单个子问题可以写成
$$\boxed{F(A,B)=\sum_{m=1}^{\min(A,B)}2^{\omega(m)}\,U_m(A,B).}$$
题目所需总值为
$$F(10^8,10^9)+F(10^9,10^8).$$
由于求和项对 \(A\) 与 \(B\) 是对称的，这两个值实际上相等；但保留两次求值的形式，更贴近原题与实现方式。
只有 \(m=1\) 与 \(m=2\) 会产生贡献。
当 \(m=1\) 时，\(\omega(1)=0\)，所以权重是 \(1\)。因为 \(1\) 是奇数，
$$U_1(2,10)=2\cdot 2\cdot 10=40.$$
当 \(m=2\) 时，\(\omega(2)=1\)，所以权重是 \(2\)。因为 \(2\) 是偶数，
$$U_2(2,10)=\left\lfloor\frac{2}{2}\right\rfloor\left\lfloor\frac{10}{2}\right\rfloor+ \left(\left\lfloor\frac{2}{2}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{10}{2}\right\rfloor\bmod 2\right) =1\cdot 5+1\cdot 1=6.$$
因此
$$F(2,10)=1\cdot 40+2\cdot 6=52,$$
与实现中的检查值完全一致。
C++、Python 和 Java 实现都会先用筛法预处理所有需要的 \(\omega(m)\)：每个质数访问自己的所有倍数一次，因此每个整数都能累积出不同质因子的个数。随后实现按 \(m=1,2,\dots,\min(A,B)\) 逐项计算公式，只需要整除、奇偶判断、\(2^{\omega(m)}\) 的权重以及整数累加。
同一个标量计数过程会应用到两个官方参数对上。因为不同的 \(m\) 项互不依赖，所以外层求和天然可以并行；C++ 与 Java 版本利用了这一点，而 Python 版本则用更直接的单线程循环保留相同数学结构。
设 \(L=\max(\min(10^8,10^9),\min(10^9,10^8))=10^8\)。构造不同质因子个数表的筛法时间复杂度为 \(O(L\log\log L)\)，空间复杂度为 \(O(L)\)。最终求和是 \(O(L)\) 时间，因为每个 \(m\) 只对应常数成本的一项。因此总复杂度为 \(O(L\log\log L)\) 时间和 \(O(L)\) 空间。
Геометрическую постановку можно полностью перевести в арифметическую задачу подсчета. Для фиксированной пары параметров \((A,B)\) каждая допустимая конфигурация касания кодируется положительным числом \(n \le A\), положительным числом \(b \le B\) и парой делителей квадрата \(b^2\). Прямой перебор остается слишком медленным, но именно он показывает структуру, из которой выводится быстрая формула.
В задаче требуется сложить два значения, соответствующие \((10^8,10^9)\) и \((10^9,10^8)\). Поэтому достаточно вывести эффективную формулу для одного подзадачного количества \(F(A,B)\).
Прямая модель подсчета показывает, что \(F(A,B)\) выражается через положительные целые числа, удовлетворяющие
$$1 \le n \le A,\qquad 1 \le b \le B,\qquad cd=b^2,$$
а также двум дополнительным условиям
$$b \mid n(c+d),\qquad \frac{n(c+d)}{b}\equiv d-c \pmod 2.$$
Когда эти условия выполнены, существуют два симметричных выбора знака. Значит, каждая допустимая арифметическая кодировка дает ровно \(2\) геометрические конфигурации.
Положим \(\lambda=\gcd(c,d)\). Тогда \(c=\lambda c_0\), \(d=\lambda d_0\), причем \(\gcd(c_0,d_0)=1\). Из равенства \(cd=b^2\) следует
$$c_0d_0=\left(\frac{b}{\lambda}\right)^2.$$
Произведение двух взаимно простых положительных чисел может быть квадратом только тогда, когда каждое из них само является квадратом. Поэтому существуют взаимно простые \(p,q \ge 1\) такие, что
$$c=\lambda p^2,\qquad d=\lambda q^2,\qquad \gcd(p,q)=1,$$
и, следовательно,
$$b=\lambda pq.$$
После этого шага квадратная структура уже явно вынесена в параметры \((\lambda,p,q)\).
Подставляя разложение в условие \(b \mid n(c+d)\), получаем
$$\lambda pq \mid n\lambda(p^2+q^2),$$
то есть
$$pq \mid n(p^2+q^2).$$
Так как \(\gcd(p,q)=1\), ни один простой делитель числа \(pq\) не делит \(p^2+q^2\). Поэтому
$$\gcd(pq,p^2+q^2)=1,$$
и остается только
$$pq \mid n.$$
Обозначим
$$m=pq,\qquad n=mt.$$
Тогда
$$1 \le t \le \left\lfloor\frac{A}{m}\right\rfloor,$$
а масштабный множитель \(\lambda\) ограничен лишь условием \(b=\lambda m \le B\), то есть
$$1 \le \lambda \le \left\lfloor\frac{B}{m}\right\rfloor.$$
При фиксированном \(m\) нужно посчитать упорядоченные взаимно простые пары \((p,q)\) с \(pq=m\). Если
$$m=\prod_{i=1}^{r}\ell_i^{e_i},$$
то взаимная простота заставляет каждую полную степень простого \(\ell_i^{e_i}\) целиком отправиться либо в \(p\), либо в \(q\). Для каждого различного простого есть ровно два выбора. Значит, число упорядоченных пар равно
$$2^r=2^{\omega(m)},$$
где \(\omega(m)\) обозначает число различных простых делителей \(m\).
После подстановки условие на четность принимает вид
$$\frac{n(c+d)}{b}=t(p^2+q^2),\qquad d-c=\lambda(q^2-p^2).$$
Эти две величины должны иметь одинаковую четность. Поскольку
$$p^2+q^2\equiv q^2-p^2 \pmod 2,$$
условие эквивалентно
$$ (t-\lambda)(p^2+q^2)\equiv 0 \pmod 2.$$
Если \(m\) нечетно, то \(p\) и \(q\) оба нечетны, а значит \(p^2+q^2\) четно. Ограничение по четности исчезает. Для каждой из \(2^{\omega(m)}\) взаимно простых факторизаций допустима любая пара \((t,\lambda)\), а два выбора знака дают вклад
$$2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor.$$
Если \(m\) четно, то ровно одно из чисел \(p,q\) четно, поэтому \(p^2+q^2\) нечетно. Тогда требуется \(t\equiv\lambda\pmod 2\). Обозначим
$$t_{\max}=\left\lfloor\frac{A}{m}\right\rfloor,\qquad \lambda_{\max}=\left\lfloor\frac{B}{m}\right\rfloor.$$
Число пар \((t,\lambda)\) одинаковой четности равно
$$\left\lceil\frac{t_{\max}}{2}\right\rceil\left\lceil\frac{\lambda_{\max}}{2}\right\rceil+\left\lfloor\frac{t_{\max}}{2}\right\rfloor\left\lfloor\frac{\lambda_{\max}}{2}\right\rfloor =\frac{t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2)}{2}.$$
После умножения на два выбора знака вклад четного случая становится равным
$$t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2).$$
Введем зависящий от четности единичный вклад
$$U_m(A,B)= \begin{cases} 2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor, & m\ \mathrm{odd},\\[6pt] \left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor+ \left(\left\lfloor\frac{A}{m}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{B}{m}\right\rfloor\bmod 2\right), & m\ \mathrm{even}. \end{cases}$$
Тогда весь подзадачный подсчет равен
$$\boxed{F(A,B)=\sum_{m=1}^{\min(A,B)}2^{\omega(m)}\,U_m(A,B).}$$
Требуемый итог:
$$F(10^8,10^9)+F(10^9,10^8).$$
Слагаемое симметрично по \(A\) и \(B\), поэтому оба значения равны, но запись в виде суммы двух вычислений сохраняет форму исходной задачи.
Вклад могут дать только \(m=1\) и \(m=2\).
Для \(m=1\) имеем \(\omega(1)=0\), значит вес равен \(1\). Поскольку \(1\) нечетно,
$$U_1(2,10)=2\cdot 2\cdot 10=40.$$
Для \(m=2\) имеем \(\omega(2)=1\), значит вес равен \(2\). Поскольку \(2\) четно,
$$U_2(2,10)=\left\lfloor\frac{2}{2}\right\rfloor\left\lfloor\frac{10}{2}\right\rfloor+ \left(\left\lfloor\frac{2}{2}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{10}{2}\right\rfloor\bmod 2\right) =1\cdot 5+1\cdot 1=6.$$
Следовательно,
$$F(2,10)=1\cdot 40+2\cdot 6=52,$$
что совпадает с контрольным значением реализации.
Реализации на C++, Python и Java сначала вычисляют \(\omega(m)\) для всех нужных \(m\) с помощью решета: каждый простой увеличивает счетчик всех своих кратных ровно один раз, поэтому каждое число получает число различных простых делителей. Затем формула выше суммируется напрямую: для каждого \(m\) нужны только целочисленные деления, проверка четности, вес \(2^{\omega(m)}\) и добавление к сумме.
Одна и та же скалярная процедура применяется к двум официальным парам параметров. Поскольку вклад каждого \(m\) не зависит от остальных, внешняя сумма естественно распараллеливается; версии на C++ и Java используют эту независимость, а версия на Python сохраняет ту же математику в простом последовательном цикле.
Пусть \(L=\max(\min(10^8,10^9),\min(10^9,10^8))=10^8\). Построение таблицы числа различных простых делителей требует \(O(L\log\log L)\) времени и \(O(L)\) памяти. Финальная сумма требует \(O(L)\) времени, потому что каждый \(m\) дает вклад постоянной стоимости. Итого общий алгоритм работает за \(O(L\log\log L)\) времени и использует \(O(L)\) памяти.
يمكن تحويل الصياغة الهندسية للمسألة إلى مسألة عدٍّ حسابية خالصة. فلكل زوج ثابت من الحدود \((A,B)\)، يمكن تمثيل كل وضعية تماس صالحة بعدد صحيح موجب \(n \le A\)، وعدد صحيح موجب \(b \le B\)، وزوج عوامل للمربع \(b^2\). الصيغة المباشرة ما تزال بطيئة، لكنها تكشف البنية التي تسمح باشتقاق مجموع مغلق سريع.
المطلوب النهائي هو جمع قيمتين متناظرتين تخصان \((10^8,10^9)\) و\((10^9,10^8)\). لذلك يكفي أن نشتق صيغة فعالة للمسألة الفرعية الواحدة \(F(A,B)\).
يبين نموذج العد المباشر أن \(F(A,B)\) يمكن التعبير عنه من خلال أعداد صحيحة موجبة تحقق
$$1 \le n \le A,\qquad 1 \le b \le B,\qquad cd=b^2,$$
مع الشرطين الإضافيين
$$b \mid n(c+d),\qquad \frac{n(c+d)}{b}\equiv d-c \pmod 2.$$
ومتى تحقق هذان الشرطان، توجد إشارتان متناظرتان ممكنتان، ولذلك فإن كل ترميز حسابي صالح يعطي بالضبط \(2\) من الوضعيات الهندسية.
لنضع \(\lambda=\gcd(c,d)\). عندئذٍ \(c=\lambda c_0\) و\(d=\lambda d_0\) و\(\gcd(c_0,d_0)=1\). ومن المعادلة \(cd=b^2\) نحصل على
$$c_0d_0=\left(\frac{b}{\lambda}\right)^2.$$
إذا كان حاصل ضرب عددين صحيحين موجبين ومتباينين أوليًا مربعًا كاملًا، فلا بد أن يكون كل منهما مربعًا كاملًا أيضًا. إذن توجد أعداد \(p,q \ge 1\) متباينة أوليًا بحيث
$$c=\lambda p^2,\qquad d=\lambda q^2,\qquad \gcd(p,q)=1,$$
ومن ثم
$$b=\lambda pq.$$
وهذه هي خطوة التطبيع الأساسية، لأن شرط المربع يصبح ظاهرًا وصريحًا في المعاملات \((\lambda,p,q)\).
بالتعويض في الشرط \(b \mid n(c+d)\) نحصل على
$$\lambda pq \mid n\lambda(p^2+q^2),$$
أي
$$pq \mid n(p^2+q^2).$$
وبما أن \(\gcd(p,q)=1\)، فلا يمكن لأي عدد أولي يقسم \(pq\) أن يقسم \(p^2+q^2\). لذلك
$$\gcd(pq,p^2+q^2)=1,$$
ومن ثم يلزم أن
$$pq \mid n.$$
لنكتب
$$m=pq,\qquad n=mt.$$
وعندئذٍ يكون مدى \(t\) هو
$$1 \le t \le \left\lfloor\frac{A}{m}\right\rfloor,$$
بينما يكون عامل القياس \(\lambda\) محكومًا فقط بالعلاقة \(b=\lambda m \le B\)، أي
$$1 \le \lambda \le \left\lfloor\frac{B}{m}\right\rfloor.$$
عند تثبيت \(m\)، يجب أن نعد الأزواج المرتبة والمتباينة أوليًا \((p,q)\) التي تحقق \(pq=m\). إذا كان
$$m=\prod_{i=1}^{r}\ell_i^{e_i},$$
فإن شرط التباين الأولي يفرض أن تذهب كل قوة أولية كاملة \(\ell_i^{e_i}\) إما كلها إلى \(p\) أو كلها إلى \(q\). كل عدد أولي مميز يعطي اختيارين بالضبط. ولذلك يكون عدد الأزواج المرتبة
$$2^r=2^{\omega(m)},$$
حيث ترمز \(\omega(m)\) إلى عدد العوامل الأولية المميزة للعدد \(m\).
بعد التعويض يصبح شرط الزوجية
$$\frac{n(c+d)}{b}=t(p^2+q^2),\qquad d-c=\lambda(q^2-p^2).$$
ويجب أن يكون لهذين المقدارين نفس الزوجية. وبما أن
$$p^2+q^2\equiv q^2-p^2 \pmod 2,$$
فإن الشرط يكافئ
$$ (t-\lambda)(p^2+q^2)\equiv 0 \pmod 2.$$
إذا كان \(m\) فرديًا، فكل من \(p\) و\(q\) فردي، وبالتالي يكون \(p^2+q^2\) زوجيًا. عندئذٍ يختفي قيد الزوجية بالكامل، وتكون كل الأزواج \((t,\lambda)\) صالحة، ومع الإشارتين نحصل على مساهمة قدرها
$$2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor.$$
أما إذا كان \(m\) زوجيًا، فبالضبط واحد من \(p,q\) زوجي، ومن ثم يكون \(p^2+q^2\) فرديًا. في هذه الحالة يجب أن يتحقق \(t\equiv\lambda\pmod 2\). نضع
$$t_{\max}=\left\lfloor\frac{A}{m}\right\rfloor,\qquad \lambda_{\max}=\left\lfloor\frac{B}{m}\right\rfloor.$$
عدد الأزواج \((t,\lambda)\) ذات الزوجية نفسها هو
$$\left\lceil\frac{t_{\max}}{2}\right\rceil\left\lceil\frac{\lambda_{\max}}{2}\right\rceil+\left\lfloor\frac{t_{\max}}{2}\right\rfloor\left\lfloor\frac{\lambda_{\max}}{2}\right\rfloor =\frac{t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2)}{2}.$$
وبعد ضربه في خياري الإشارة، تصبح مساهمة الحالة الزوجية
$$t_{\max}\lambda_{\max}+(t_{\max}\bmod 2)(\lambda_{\max}\bmod 2).$$
لنعرّف المساهمة الوحدوية التابعة للزوجية كما يلي:
$$U_m(A,B)= \begin{cases} 2\left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor, & m\ \mathrm{odd},\\[6pt] \left\lfloor\frac{A}{m}\right\rfloor\left\lfloor\frac{B}{m}\right\rfloor+ \left(\left\lfloor\frac{A}{m}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{B}{m}\right\rfloor\bmod 2\right), & m\ \mathrm{even}. \end{cases}$$
وعندئذٍ تصبح المسألة الفرعية بأكملها
$$\boxed{F(A,B)=\sum_{m=1}^{\min(A,B)}2^{\omega(m)}\,U_m(A,B).}$$
أما المجموع المطلوب فهو
$$F(10^8,10^9)+F(10^9,10^8).$$
الحد داخل المجموع متناظر في \(A\) و\(B\)، ولذلك فالقيمتان متساويتان، لكن إبقاء الجواب على صورة مجموع تقييمين يتوافق مع نص المسألة وطريقة التنفيذ.
لا يمكن أن يساهم إلا \(m=1\) و\(m=2\).
عندما \(m=1\)، يكون \(\omega(1)=0\)، وبالتالي الوزن يساوي \(1\). وبما أن \(1\) فردي، فإن
$$U_1(2,10)=2\cdot 2\cdot 10=40.$$
وعندما \(m=2\)، يكون \(\omega(2)=1\)، وبالتالي الوزن يساوي \(2\). ولأن \(2\) زوجي، نحصل على
$$U_2(2,10)=\left\lfloor\frac{2}{2}\right\rfloor\left\lfloor\frac{10}{2}\right\rfloor+ \left(\left\lfloor\frac{2}{2}\right\rfloor\bmod 2\right)\left(\left\lfloor\frac{10}{2}\right\rfloor\bmod 2\right) =1\cdot 5+1\cdot 1=6.$$
إذن
$$F(2,10)=1\cdot 40+2\cdot 6=52,$$
وهو تمامًا مقدار التحقق الذي تستخدمه التطبيقات.
تبدأ تطبيقات C++ وPython وJava بحساب \(\omega(m)\) لكل \(m\) حتى أكبر حد مطلوب باستعمال غربال: كل عدد أولي يزور جميع مضاعفاته مرة واحدة، وبذلك يجمع كل عدد عدد عوامله الأولية المميزة. بعد ذلك تطبق الصيغة السابقة مباشرة حدًا حدًا؛ فلكل \(m\) لا نحتاج إلا إلى قسمة صحيحة، وفحص زوجية، والوزن \(2^{\omega(m)}\)، ثم إضافة إلى المجموع.
ويُستخدم الروتين العددي نفسه مع زوجي الحدود الرسميين. وبما أن مساهمة كل \(m\) مستقلة عن البقية، فإن المجموع الخارجي قابل للتوازي طبيعيًا؛ تستفيد نسختا C++ وJava من ذلك، بينما تحتفظ نسخة Python بالرياضيات نفسها داخل حلقة تسلسلية أبسط.
لنضع \(L=\max(\min(10^8,10^9),\min(10^9,10^8))=10^8\). بناء جدول عدد العوامل الأولية المميزة يحتاج إلى زمن \(O(L\log\log L)\) وذاكرة \(O(L)\). أما المجموع النهائي فيحتاج إلى \(O(L)\) زمنًا لأن كل قيمة \(m\) تعطي حدًا واحدًا ثابت الكلفة. لذلك فالتعقيد الكلي هو \(O(L\log\log L)\) زمنًا و\(O(L)\) مساحة.