A pair \((a,b)\) with \(1 \le a \lt b \le N\) is called 2-friendly when \(\gcd(a,b)\) is a power of two strictly larger than \(1\). If \(f(N)\) denotes the number of such pairs, the task is to compute
$$f(10^{11}) \pmod{10^9+7}.$$
A direct scan over all pairs would be quadratic in \(N\), so the solution has to reorganize the counting problem around the exact gcd.
We want to count all pairs whose gcd has the form \(2^t\) with \(t \ge 1\). The decisive observation is that once the exact gcd is fixed, what remains is a coprime pair-counting problem.
Suppose \(\gcd(a,b)=2^t\) for some \(t \ge 1\). Then we can write
$$a=2^t x,\qquad b=2^t y,$$
with
$$1 \le x \lt y \le \left\lfloor \frac{N}{2^t} \right\rfloor.$$
Because the gcd was assumed to be exactly \(2^t\), the reduced pair must satisfy
$$\gcd(x,y)=1.$$
Conversely, every coprime pair \((x,y)\) in that range produces exactly one original pair \((2^t x,2^t y)\) whose gcd is exactly \(2^t\). So there is no overcounting between different values of \(t\).
For a fixed upper bound \(m\), define
$$C(m)=\#\{(x,y):1 \le x \lt y \le m,\ \gcd(x,y)=1\}.$$
If we fix the larger coordinate \(y\), then the valid values of \(x\) are precisely the integers \(1 \le x \lt y\) that are coprime to \(y\). Their number is \(\varphi(y)\). Therefore
$$C(m)=\sum_{y=2}^{m}\varphi(y).$$
Now introduce the summatory totient function
$$\Phi(m)=\sum_{k=1}^{m}\varphi(k).$$
Since \(\varphi(1)=1\), we get the compact identity
$$C(m)=\Phi(m)-1.$$
For a fixed \(t\), the admissible pairs with gcd \(2^t\) are counted by
$$C\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)=\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1.$$
Hence
$$f(N)=\sum_{t \ge 1}\left(\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1\right).$$
Only finitely many terms are nonzero, because once \(\left\lfloor N/2^t \right\rfloor \le 1\), there is no room for a pair with \(x \lt y\).
The implementations do not sum \(\varphi(k)\) up to \(n\) from scratch for every query. Instead they use the classical divisor identity
$$\sum_{d \mid m}\varphi(d)=m.$$
Summing this from \(m=1\) to \(m=n\) gives
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d \mid m}\varphi(d).$$
After exchanging the order of summation, this becomes
$$\frac{n(n+1)}{2}=\sum_{q=1}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
Separating the \(q=1\) term yields the recurrence
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
The floor value \(\left\lfloor n/q \right\rfloor\) is constant on intervals, so the sum is grouped by quotient blocks rather than processed one index at a time.
If a block starts at \(l\), let
$$v=\left\lfloor \frac{n}{l} \right\rfloor,\qquad r=\left\lfloor \frac{n}{v} \right\rfloor.$$
Then every \(q\) in the interval \(l \le q \le r\) has the same quotient \(v\), so their total contribution is
$$ (r-l+1)\,\Phi(v). $$
This reduces the amount of work dramatically. Memoization then stores each large \(\Phi(v)\) value after its first computation, which is important because the outer formula asks for \(\Phi\) at the related arguments \(N/2,N/4,N/8,\dots\).
For \(N=10\), the relevant halvings are
$$\left\lfloor \frac{10}{2} \right\rfloor=5,\qquad \left\lfloor \frac{10}{4} \right\rfloor=2,\qquad \left\lfloor \frac{10}{8} \right\rfloor=1.$$
The last term contributes nothing because \(\Phi(1)-1=0\). So
$$f(10)=\left(\Phi(5)-1\right)+\left(\Phi(2)-1\right).$$
Now
$$\Phi(5)=1+1+2+2+4=10,\qquad \Phi(2)=1+1=2,$$
hence
$$f(10)=9+1=10.$$
The ten pairs are
$$(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10),(4,8).$$
The first nine have gcd \(2\), and the last one has gcd \(4\).
The C++, Python, and Java implementations follow the same structure. They first precompute \(\varphi(n)\) up to a fixed cutoff of five million with a linear sieve and store the prefix sums modulo \(10^9+7\). That makes every small \(\Phi(n)\) query an \(O(1)\) table lookup.
For larger \(n\), the implementation evaluates the recurrence
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right)$$
using quotient grouping, so each interval of equal floor value is handled in one step. The result is memoized, which prevents the same large summatory-totient value from being recomputed.
Finally, the main solve loop starts with \(m=\lfloor N/2 \rfloor\), repeatedly halves \(m\), and accumulates \(\Phi(m)-1\) until \(m \lt 2\). Every arithmetic step is reduced modulo \(10^9+7\).
Let \(B=5{,}000{,}000\) be the precomputation cutoff used by the implementations. The linear sieve and prefix table take \(O(B)\) time and \(O(B)\) memory. The outer summation over \(N/2,N/4,N/8,\dots\) has only \(O(\log N)\) terms.
The expensive part is evaluating large \(\Phi(n)\) values, but quotient grouping compresses each summation into blocks of equal floor quotient, and memoization ensures repeated subproblems are solved once. That hybrid strategy is what makes \(N=10^{11}\) practical.
Ein Paar \((a,b)\) mit \(1 \le a \lt b \le N\) heißt 2-friendly, wenn \(\gcd(a,b)\) eine Zweierpotenz größer als \(1\) ist. Gesucht ist also
$$f(10^{11}) \pmod{10^9+7}.$$
Ein direkter Durchlauf über alle Paare wäre quadratisch in \(N\) und damit völlig unpraktikabel. Deshalb ordnet die Lösung die Paare nach ihrem exakten ggT.
Zu zählen sind genau die Paare, deren ggT die Form \(2^t\) mit \(t \ge 1\) hat. Nach dem Herausziehen dieses exakten ggT bleibt ein Problem über teilerfremde Paare übrig.
Angenommen \(\gcd(a,b)=2^t\) mit \(t \ge 1\). Dann schreiben wir
$$a=2^t x,\qquad b=2^t y,$$
wobei
$$1 \le x \lt y \le \left\lfloor \frac{N}{2^t} \right\rfloor.$$
Weil der ggT exakt \(2^t\) sein soll, muss das reduzierte Paar erfüllen
$$\gcd(x,y)=1.$$
Umgekehrt erzeugt jedes teilerfremde Paar \((x,y)\) in diesem Bereich genau ein ursprüngliches Paar \((2^t x,2^t y)\) mit ggT \(2^t\). Dadurch gibt es keine Doppelzählung zwischen verschiedenen \(t\).
Für eine feste obere Grenze \(m\) definieren wir
$$C(m)=\#\{(x,y):1 \le x \lt y \le m,\ \gcd(x,y)=1\}.$$
Fixiert man die größere Zahl \(y\), dann sind die zulässigen Werte von \(x\) genau die Zahlen \(1 \le x \lt y\), die zu \(y\) teilerfremd sind. Davon gibt es \(\varphi(y)\). Also
$$C(m)=\sum_{y=2}^{m}\varphi(y).$$
Mit der summierten Phi-Funktion
$$\Phi(m)=\sum_{k=1}^{m}\varphi(k)$$
folgt wegen \(\varphi(1)=1\)
$$C(m)=\Phi(m)-1.$$
Für ein festes \(t\) ist die Anzahl der Paare mit ggT \(2^t\)
$$C\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)=\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1.$$
Damit erhält man
$$f(N)=\sum_{t \ge 1}\left(\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1\right).$$
Nur endlich viele Summanden sind ungleich null, denn sobald \(\left\lfloor N/2^t \right\rfloor \le 1\) ist, existiert kein Paar mehr mit \(x \lt y\).
Die Implementierungen summieren \(\varphi(k)\) für große \(n\) nicht jedes Mal neu auf, sondern nutzen die klassische Identität
$$\sum_{d \mid m}\varphi(d)=m.$$
Summiert man diese Gleichung für \(m=1,\dots,n\), so ergibt sich
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d \mid m}\varphi(d).$$
Nach Vertauschen der Summationen folgt
$$\frac{n(n+1)}{2}=\sum_{q=1}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
Trennt man den Term \(q=1\) ab, erhält man die Rekursion
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
Der Ausdruck \(\left\lfloor n/q \right\rfloor\) bleibt auf ganzen Intervallen konstant. Genau diese Quotientenblöcke nutzt der Code aus.
Beginnt ein Block bei \(l\), so setzen wir
$$v=\left\lfloor \frac{n}{l} \right\rfloor,\qquad r=\left\lfloor \frac{n}{v} \right\rfloor.$$
Dann gilt für alle \(q\) mit \(l \le q \le r\) derselbe Quotient \(v\), also ist ihr gemeinsamer Beitrag
$$ (r-l+1)\,\Phi(v). $$
Das reduziert die Arbeit erheblich. Zusätzlich speichert Memoisierung jedes große \(\Phi(v)\) nach der ersten Berechnung, was wichtig ist, weil die äußere Formel eng verwandte Argumente \(N/2,N/4,N/8,\dots\) abfragt.
Für \(N=10\) sind die relevanten Halbierungen
$$\left\lfloor \frac{10}{2} \right\rfloor=5,\qquad \left\lfloor \frac{10}{4} \right\rfloor=2,\qquad \left\lfloor \frac{10}{8} \right\rfloor=1.$$
Der letzte Term verschwindet, weil \(\Phi(1)-1=0\). Also
$$f(10)=\left(\Phi(5)-1\right)+\left(\Phi(2)-1\right).$$
Weiter gilt
$$\Phi(5)=1+1+2+2+4=10,\qquad \Phi(2)=1+1=2,$$
somit
$$f(10)=9+1=10.$$
Die zehn Paare sind
$$(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10),(4,8).$$
Die ersten neun haben ggT \(2\), das letzte Paar ggT \(4\).
Die C++-, Python- und Java-Implementierungen benutzen denselben Aufbau. Zuerst werden \(\varphi(n)\) bis zu einer festen Grenze von fünf Millionen mit einem linearen Sieb vorab berechnet, und daraus werden Präfixsummen modulo \(10^9+7\) gebildet. Kleine \(\Phi(n)\)-Abfragen sind dadurch direkte Tabellenzugriffe.
Für größere \(n\) wird die Rekursion
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right)$$
mit Quotientenblöcken ausgewertet, sodass jedes Intervall mit gleichem Ganzzahlquotienten in einem Schritt behandelt wird. Das Ergebnis wird memoisiert, damit derselbe große Wert nicht mehrfach berechnet wird.
Im letzten Schritt startet die Hauptschleife mit \(m=\lfloor N/2 \rfloor\), halbiert \(m\) wiederholt und addiert jedes Mal \(\Phi(m)-1\), bis \(m \lt 2\) gilt. Alle Rechnungen werden modulo \(10^9+7\) geführt.
Sei \(B=5{,}000{,}000\) die in den Implementierungen verwendete Vorberechnungsgrenze. Das lineare Sieb mit Präfixsummen braucht \(O(B)\) Zeit und \(O(B)\) Speicher. Die äußere Summe über \(N/2,N/4,N/8,\dots\) enthält nur \(O(\log N)\) Terme.
Der teure Teil sind die großen \(\Phi(n)\)-Abfragen, aber Quotientenblöcke komprimieren die Summation stark, und Memoisierung verhindert Wiederholungsarbeit. Genau diese Kombination macht \(N=10^{11}\) praktikabel.
\(1 \le a \lt b \le N\) koşulunu sağlayan bir \((a,b)\) çifti için \(\gcd(a,b)\) değeri \(1\)'den büyük bir \(2\) kuvvetiyse bu çift 2-friendly sayılır. Aranan nicelik
$$f(10^{11}) \pmod{10^9+7}$$
değeridir. Tüm çiftleri tek tek taramak \(N\) açısından karesel maliyet doğuracağı için çözüm, sayımı tam olarak gcd üzerinden yeniden kurar.
Saymak istediğimiz çiftlerin gcd değeri mutlaka \(2^t\) biçimindedir ve \(t \ge 1\) olur. Bu nedenle önce bu tam gcd'yi dışarı alıp geride kalan sadeleştirilmiş çifti saymak en doğru yaklaşımdır.
\(\gcd(a,b)=2^t\) olsun. O zaman
$$a=2^t x,\qquad b=2^t y,$$
ve
$$1 \le x \lt y \le \left\lfloor \frac{N}{2^t} \right\rfloor$$
yazabiliriz. Gcd'nin tam olarak \(2^t\) olması demek, sadeleştirilmiş çiftin artık aralarında asal olması demektir:
$$\gcd(x,y)=1.$$
Tersi de doğrudur: Bu aralıkta alınan her aralarında asal \((x,y)\) çifti, \((2^t x,2^t y)\) biçiminde gcd'si tam olarak \(2^t\) olan tek bir özgün çift üretir. Böylece farklı \(t\) değerleri arasında çakışma olmaz.
Sabit bir üst sınır \(m\) için
$$C(m)=\#\{(x,y):1 \le x \lt y \le m,\ \gcd(x,y)=1\}$$
tanımını yapalım. Büyük koordinatı \(y\) sabitlersek, geçerli \(x\) sayısı tam olarak \(\varphi(y)\) olur; çünkü \(1 \le x \lt y\) ve \(\gcd(x,y)=1\) koşulunu sağlayan sayıların sayısı budur. Dolayısıyla
$$C(m)=\sum_{y=2}^{m}\varphi(y).$$
Şimdi toplam \(\varphi\) fonksiyonunu
$$\Phi(m)=\sum_{k=1}^{m}\varphi(k)$$
olarak tanımlarsak ve \(\varphi(1)=1\) olduğunu kullanırsak
$$C(m)=\Phi(m)-1$$
elde edilir.
Sabit bir \(t\) için gcd'si \(2^t\) olan çiftlerin sayısı
$$C\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)=\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1$$
olur. Bu yüzden
$$f(N)=\sum_{t \ge 1}\left(\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1\right).$$
\(\left\lfloor N/2^t \right\rfloor \le 1\) olduğunda artık \(x \lt y\) şartını sağlayan bir çift kalmadığından toplam yalnızca sonlu sayıda terim içerir.
Uygulama her sorguda \(\varphi(1)+\cdots+\varphi(n)\) toplamını yeniden hesaplamaz. Bunun yerine şu klasik özdeşliği kullanır:
$$\sum_{d \mid m}\varphi(d)=m.$$
Bunu \(m=1\)'den \(n\)'ye kadar toplarsak
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d \mid m}\varphi(d)$$
elde edilir. Toplam sırasını değiştirince
$$\frac{n(n+1)}{2}=\sum_{q=1}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right)$$
çıkar. Buradan \(q=1\) terimini ayırınca
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right)$$
bağıntısı bulunur. Bu, büyük \(\Phi(n)\) değerlerini hızlı hesaplamanın temelidir.
Bir blok \(l\) noktasında başlasın. O zaman
$$v=\left\lfloor \frac{n}{l} \right\rfloor,\qquad r=\left\lfloor \frac{n}{v} \right\rfloor$$
alınırsa, \(l \le q \le r\) aralığındaki tüm indeksler için \(\left\lfloor n/q \right\rfloor=v\) olur. Bu bloğun katkısı topluca
$$ (r-l+1)\,\Phi(v) $$
şeklinde yazılır. Böylece her \(q\) tek tek işlenmez. Ayrıca büyük \(\Phi(v)\) değerleri ilk hesaplamadan sonra saklanır; dış toplam \(N/2,N/4,N/8,\dots\) gibi akraba argümanlar kullandığı için bu önbellek çok önemlidir.
\(N=10\) için ilgili yarılmalar
$$\left\lfloor \frac{10}{2} \right\rfloor=5,\qquad \left\lfloor \frac{10}{4} \right\rfloor=2,\qquad \left\lfloor \frac{10}{8} \right\rfloor=1$$
olur. Son terim sıfırdır; çünkü \(\Phi(1)-1=0\). O halde
$$f(10)=\left(\Phi(5)-1\right)+\left(\Phi(2)-1\right).$$
Şimdi
$$\Phi(5)=1+1+2+2+4=10,\qquad \Phi(2)=1+1=2$$
olduğundan
$$f(10)=9+1=10$$
elde edilir. On çift şunlardır:
$$(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10),(4,8).$$
İlk dokuz çiftin gcd'si \(2\), son çiftin gcd'si ise \(4\)'tür.
C++, Python ve Java uygulamaları aynı planı izler. Önce beş milyonluk sabit bir eşiğe kadar lineer elek ile tüm \(\varphi(n)\) değerleri hesaplanır ve bunların önek toplamları \(10^9+7\) modunda tutulur. Böylece küçük \(\Phi(n)\) sorguları doğrudan tablodan gelir.
Daha büyük \(n\) değerleri için
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right)$$
bağıntısı, eşit bölüm bloklarına ayrılarak hesaplanır. Sonuç belleğe alınır; böylece aynı büyük toplam bir daha çözülmez.
En sonda ana döngü \(m=\lfloor N/2 \rfloor\) ile başlar, her adımda \(m\)'yi ikiye böler ve \(\Phi(m)-1\) terimini cevaba ekler. Tüm aritmetik \(10^9+7\) modunda yürütülür.
Uygulamaların kullandığı ön hesap eşiği \(B=5{,}000{,}000\) olsun. Lineer elek ve önek toplam tablosu \(O(B)\) zaman ve \(O(B)\) bellek kullanır. Dış toplam \(N/2,N/4,N/8,\dots\) biçiminde ilerlediği için yalnızca \(O(\log N)\) terim içerir.
Pahalı kısım büyük \(\Phi(n)\) sorgularıdır; ancak bölüm bloklaması toplamı ciddi biçimde sıkıştırır ve önbellekleme aynı alt problemi tekrar çözmeyi engeller. \(N=10^{11}\) için yöntemin uygulanabilir olmasının nedeni budur.
Un par \((a,b)\) con \(1 \le a \lt b \le N\) se llama 2-friendly cuando \(\gcd(a,b)\) es una potencia de \(2\) estrictamente mayor que \(1\). Por tanto, hay que calcular
$$f(10^{11}) \pmod{10^9+7}.$$
Recorrer todos los pares sería un proceso cuadrático en \(N\), así que la solución reorganiza el conteo alrededor del valor exacto del mcd.
Los pares válidos son exactamente aquellos cuyo mcd tiene la forma \(2^t\) con \(t \ge 1\). Una vez fijado ese mcd exacto, el resto del problema se convierte en contar pares coprimos.
Supongamos que \(\gcd(a,b)=2^t\) con \(t \ge 1\). Entonces podemos escribir
$$a=2^t x,\qquad b=2^t y,$$
con
$$1 \le x \lt y \le \left\lfloor \frac{N}{2^t} \right\rfloor.$$
Como el mcd era exactamente \(2^t\), el par reducido debe cumplir
$$\gcd(x,y)=1.$$
La recíproca también vale: cualquier par coprimo \((x,y)\) en ese rango produce un único par original \((2^t x,2^t y)\) cuyo mcd es exactamente \(2^t\). Eso evita la doble cuenta entre distintos valores de \(t\).
Para una cota superior \(m\), definimos
$$C(m)=\#\{(x,y):1 \le x \lt y \le m,\ \gcd(x,y)=1\}.$$
Si fijamos el valor mayor \(y\), los posibles \(x\) son exactamente los enteros \(1 \le x \lt y\) coprimos con \(y\), y su cantidad es \(\varphi(y)\). Por consiguiente
$$C(m)=\sum_{y=2}^{m}\varphi(y).$$
Introduciendo la función totiente acumulada
$$\Phi(m)=\sum_{k=1}^{m}\varphi(k),$$
y usando \(\varphi(1)=1\), obtenemos
$$C(m)=\Phi(m)-1.$$
Para un \(t\) fijo, el número de pares con mcd \(2^t\) es
$$C\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)=\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1.$$
Así, la respuesta total es
$$f(N)=\sum_{t \ge 1}\left(\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1\right).$$
Solo hay un número finito de términos no nulos, porque cuando \(\left\lfloor N/2^t \right\rfloor \le 1\) ya no existe ningún par con \(x \lt y\).
Las implementaciones no vuelven a sumar \(\varphi(1)+\cdots+\varphi(n)\) desde cero en cada consulta. En su lugar usan la identidad clásica
$$\sum_{d \mid m}\varphi(d)=m.$$
Al sumarla para \(m=1,\dots,n\), se llega a
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d \mid m}\varphi(d).$$
Reordenando las sumas se obtiene
$$\frac{n(n+1)}{2}=\sum_{q=1}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
Separando el término \(q=1\), resulta
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
La clave es que \(\left\lfloor n/q \right\rfloor\) permanece constante en intervalos enteros, así que la suma se agrupa por bloques de cociente.
Si un bloque empieza en \(l\), definimos
$$v=\left\lfloor \frac{n}{l} \right\rfloor,\qquad r=\left\lfloor \frac{n}{v} \right\rfloor.$$
Entonces todos los índices \(q\) con \(l \le q \le r\) tienen el mismo cociente \(v\), y su contribución conjunta es
$$ (r-l+1)\,\Phi(v). $$
Eso reduce mucho el trabajo. Además, la memoización guarda cada valor grande de \(\Phi(v)\) tras su primer cálculo, algo especialmente útil porque la fórmula exterior pide \(\Phi\) en argumentos emparentados como \(N/2,N/4,N/8,\dots\).
Para \(N=10\), las divisiones relevantes por potencias de dos son
$$\left\lfloor \frac{10}{2} \right\rfloor=5,\qquad \left\lfloor \frac{10}{4} \right\rfloor=2,\qquad \left\lfloor \frac{10}{8} \right\rfloor=1.$$
El último término no aporta nada porque \(\Phi(1)-1=0\). Luego
$$f(10)=\left(\Phi(5)-1\right)+\left(\Phi(2)-1\right).$$
Como
$$\Phi(5)=1+1+2+2+4=10,\qquad \Phi(2)=1+1=2,$$
tenemos
$$f(10)=9+1=10.$$
Los diez pares son
$$(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10),(4,8).$$
Los nueve primeros tienen mcd \(2\), y el último tiene mcd \(4\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero precalculan \(\varphi(n)\) hasta un corte fijo de cinco millones mediante una criba lineal, y almacenan las sumas prefijas módulo \(10^9+7\). Así, cualquier consulta pequeña de \(\Phi(n)\) se responde en tiempo constante.
Para valores grandes de \(n\), la implementación evalúa
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right)$$
agrupando los intervalos con el mismo cociente entero. El resultado se memoriza para no volver a calcular la misma suma acumulada.
Después, el bucle principal empieza en \(m=\lfloor N/2 \rfloor\), va sustituyendo \(m\) por \(\lfloor m/2 \rfloor\) y añade \(\Phi(m)-1\) en cada paso, siempre trabajando módulo \(10^9+7\).
Sea \(B=5{,}000{,}000\) la cota de precomputación usada por las implementaciones. La criba lineal y la tabla de prefijos cuestan \(O(B)\) tiempo y \(O(B)\) memoria. La suma exterior sobre \(N/2,N/4,N/8,\dots\) contiene solo \(O(\log N)\) términos.
El coste delicado está en las consultas grandes de \(\Phi(n)\), pero la agrupación por cocientes iguales comprime mucho la recurrencia, y la memoización elimina trabajo repetido. Esa combinación es la que hace viable \(N=10^{11}\).
当 \((a,b)\) 满足 \(1 \le a \lt b \le N\) 且 \(\gcd(a,b)\) 是一个严格大于 \(1\) 的 \(2\) 的幂时，这个数对就被称为 2-friendly。题目要求计算
$$f(10^{11}) \pmod{10^9+7}.$$
如果直接枚举所有 \((a,b)\)，时间复杂度会是 \(O(N^2)\)，在这里完全不可行。因此必须把问题改写成更适合数论求和的形式。
所有合法数对的 gcd 都可以写成 \(2^t\) 的形式，其中 \(t \ge 1\)。核心思想是先固定这个“精确的 gcd”，再把问题转化成对互素数对的计数。
若某个合法数对满足 \(\gcd(a,b)=2^t\)，其中 \(t \ge 1\)，则可写成
$$a=2^t x,\qquad b=2^t y,$$
并且有
$$1 \le x \lt y \le \left\lfloor \frac{N}{2^t} \right\rfloor.$$
由于我们要求的是 gcd 恰好等于 \(2^t\)，所以约去这个公因子之后，剩下的 \((x,y)\) 必须互素：
$$\gcd(x,y)=1.$$
反过来，如果 \((x,y)\) 在这个范围内且互素，那么 \((2^t x,2^t y)\) 的 gcd 就恰好是 \(2^t\)。因此不同的 \(t\) 不会重复计数。
对固定上界 \(m\)，定义
$$C(m)=\#\{(x,y):1 \le x \lt y \le m,\ \gcd(x,y)=1\}.$$
如果把较大的那个数 \(y\) 固定住，那么合法的 \(x\) 正好是所有满足 \(1 \le x \lt y\) 且与 \(y\) 互素的整数，其数量就是 \(\varphi(y)\)。于是
$$C(m)=\sum_{y=2}^{m}\varphi(y).$$
再引入欧拉函数的前缀和
$$\Phi(m)=\sum_{k=1}^{m}\varphi(k).$$
由于 \(\varphi(1)=1\)，立刻得到
$$C(m)=\Phi(m)-1.$$
这一步把原问题化成了对若干个 \(\Phi(m)\) 的查询。
当 gcd 固定为 \(2^t\) 时，可行数对个数就是
$$C\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)=\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1.$$
因此总答案满足
$$f(N)=\sum_{t \ge 1}\left(\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1\right).$$
这里只会出现有限项，因为一旦 \(\left\lfloor N/2^t \right\rfloor \le 1\)，就已经不可能再有 \(x \lt y\) 的数对了。
实现中的难点不在外层求和，而在于如何快速求很多个大的 \(\Phi(n)\)。基础恒等式是
$$\sum_{d \mid m}\varphi(d)=m.$$
把它对 \(m=1,2,\dots,n\) 全部求和，得到
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d \mid m}\varphi(d).$$
交换求和顺序后可以整理成
$$\frac{n(n+1)}{2}=\sum_{q=1}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
把 \(q=1\) 那一项移到左边，就得到递推关系
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
这条公式的关键价值在于：右边并不是需要访问所有更小整数，而是只依赖若干个形如 \(\left\lfloor n/q \right\rfloor\) 的商值。
设某个分块从 \(l\) 开始，记
$$v=\left\lfloor \frac{n}{l} \right\rfloor,\qquad r=\left\lfloor \frac{n}{v} \right\rfloor.$$
那么对所有 \(q\) 满足 \(l \le q \le r\)，都有相同的商 \(\left\lfloor n/q \right\rfloor=v\)。这一整段的总贡献可以一次性写成
$$ (r-l+1)\,\Phi(v). $$
因此，原本按 \(q=2,3,\dots,n\) 逐项相加的做法，被压缩成了按“商相同的区间”处理。再加上记忆化，每个大的 \(\Phi(v)\) 只需要真正计算一次。由于外层公式会查询 \(N/2,N/4,N/8,\dots\) 这些彼此高度相关的参数，这种缓存尤其有效。
当 \(N=10\) 时，外层求和只会用到
$$\left\lfloor \frac{10}{2} \right\rfloor=5,\qquad \left\lfloor \frac{10}{4} \right\rfloor=2,\qquad \left\lfloor \frac{10}{8} \right\rfloor=1.$$
最后一个值对应的贡献为零，因为 \(\Phi(1)-1=0\)。因此
$$f(10)=\left(\Phi(5)-1\right)+\left(\Phi(2)-1\right).$$
而
$$\Phi(5)=1+1+2+2+4=10,\qquad \Phi(2)=1+1=2,$$
所以
$$f(10)=9+1=10.$$
对应的十个数对为
$$(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10),(4,8).$$
前九个数对的 gcd 是 \(2\)，最后一个数对的 gcd 是 \(4\)。这个例子很好地展示了“按 gcd 的不同幂次分层计数”的思路。
C++、Python 和 Java 实现采用的是同一套算法框架。首先，它们用线性筛预处理到五百万为止的所有 \(\varphi(n)\)，然后把这些值的前缀和按 \(10^9+7\) 取模存起来。这样，所有较小的 \(\Phi(n)\) 查询都可以直接查表得到。
对于更大的 \(n\)，实现根据
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right)$$
递归求值，并且按相同的整数商分块处理每一段区间。求出的结果会被缓存起来，避免同一个较大的 \(\Phi(n)\) 值在后续查询中被反复计算。
最后，主循环从 \(m=\lfloor N/2 \rfloor\) 开始，每次把 \(m\) 整除 \(2\)，并把 \(\Phi(m)-1\) 累加到答案中，直到 \(m \lt 2\) 为止。整个过程中始终在模 \(10^9+7\) 下运算。
设预处理上界为 \(B=5{,}000{,}000\)。线性筛和前缀和表需要 \(O(B)\) 时间与 \(O(B)\) 空间。外层求和只遍历 \(N/2,N/4,N/8,\dots\)，因此只有 \(O(\log N)\) 项。
真正昂贵的是大规模 \(\Phi(n)\) 的求值，但相同商分块大幅压缩了递推中的求和长度，而记忆化又避免了重复子问题。正因为如此，\(N=10^{11}\) 的目标规模才变得可计算。
Пара \((a,b)\) с условиями \(1 \le a \lt b \le N\) называется 2-friendly, если \(\gcd(a,b)\) является степенью двойки, строго большей \(1\). Нужно вычислить
$$f(10^{11}) \pmod{10^9+7}.$$
Полный перебор всех пар имел бы квадратичную сложность по \(N\), поэтому решение перестраивает задачу через точное значение НОД.
Все допустимые пары имеют НОД вида \(2^t\) при \(t \ge 1\). После фиксации этого точного НОД задача сводится к подсчету взаимно простых пар.
Пусть \(\gcd(a,b)=2^t\), где \(t \ge 1\). Тогда
$$a=2^t x,\qquad b=2^t y,$$
и одновременно
$$1 \le x \lt y \le \left\lfloor \frac{N}{2^t} \right\rfloor.$$
Поскольку НОД должен быть именно \(2^t\), сокращенная пара обязана удовлетворять условию
$$\gcd(x,y)=1.$$
Обратное тоже верно: каждая взаимно простая пара \((x,y)\) в этом диапазоне задает ровно одну исходную пару \((2^t x,2^t y)\) с НОД \(2^t\). Поэтому разные значения \(t\) не пересекаются и не дают двойного счета.
Для верхней границы \(m\) введем
$$C(m)=\#\{(x,y):1 \le x \lt y \le m,\ \gcd(x,y)=1\}.$$
Если зафиксировать большее число \(y\), то допустимые значения \(x\) — это все числа \(1 \le x \lt y\), взаимно простые с \(y\). Их количество равно \(\varphi(y)\). Следовательно,
$$C(m)=\sum_{y=2}^{m}\varphi(y).$$
Обозначив суммарную функцию Эйлера через
$$\Phi(m)=\sum_{k=1}^{m}\varphi(k),$$
и учитывая \(\varphi(1)=1\), получаем компактную формулу
$$C(m)=\Phi(m)-1.$$
Для фиксированного \(t\) число пар с НОД \(2^t\) равно
$$C\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)=\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1.$$
Значит, общий ответ есть
$$f(N)=\sum_{t \ge 1}\left(\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1\right).$$
Ненулевых членов здесь лишь конечное число: как только \(\left\lfloor N/2^t \right\rfloor \le 1\), пар с \(x \lt y\) уже не остается.
В реализации нельзя для каждого запроса заново считать \(\varphi(1)+\cdots+\varphi(n)\). Вместо этого используется стандартная тождественная формула
$$\sum_{d \mid m}\varphi(d)=m.$$
Если просуммировать ее по всем \(m\) от \(1\) до \(n\), выйдет
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d \mid m}\varphi(d).$$
После перестановки сумм это превращается в
$$\frac{n(n+1)}{2}=\sum_{q=1}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
Выделяя член при \(q=1\), получаем рекурсию
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
Ее сила в том, что значения \(\left\lfloor n/q \right\rfloor\) повторяются на больших интервалах, а значит суммирование можно выполнять блоками.
Пусть блок начинается с \(l\). Тогда положим
$$v=\left\lfloor \frac{n}{l} \right\rfloor,\qquad r=\left\lfloor \frac{n}{v} \right\rfloor.$$
Для всех \(q\) из диапазона \(l \le q \le r\) частное \(\left\lfloor n/q \right\rfloor\) одинаково и равно \(v\), поэтому суммарный вклад блока равен
$$ (r-l+1)\,\Phi(v). $$
Это резко уменьшает объем работы. Дальше мемоизация сохраняет каждое большое значение \(\Phi(v)\) после первого вычисления, что особенно полезно, потому что внешняя формула обращается к тесно связанным аргументам \(N/2,N/4,N/8,\dots\).
При \(N=10\) нужны только следующие деления пополам:
$$\left\lfloor \frac{10}{2} \right\rfloor=5,\qquad \left\lfloor \frac{10}{4} \right\rfloor=2,\qquad \left\lfloor \frac{10}{8} \right\rfloor=1.$$
Последний вклад равен нулю, потому что \(\Phi(1)-1=0\). Следовательно,
$$f(10)=\left(\Phi(5)-1\right)+\left(\Phi(2)-1\right).$$
Имеем
$$\Phi(5)=1+1+2+2+4=10,\qquad \Phi(2)=1+1=2,$$
значит
$$f(10)=9+1=10.$$
Соответствующие десять пар:
$$(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10),(4,8).$$
Первые девять имеют НОД \(2\), а последняя пара — НОД \(4\).
Реализации на C++, Python и Java устроены одинаково. Сначала они линейным решетом заранее считают все значения \(\varphi(n)\) до фиксированного порога в пять миллионов, а затем строят по ним префиксные суммы по модулю \(10^9+7\). Поэтому малые запросы к \(\Phi(n)\) обрабатываются простым чтением из таблицы.
Для больших \(n\) используется рекурсия
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right),$$
где суммирование идет не по отдельным индексам, а по блокам одинакового целого частного. Полученные значения кешируются, чтобы не вычислять одну и ту же суммарную функцию повторно.
После этого главный цикл начинает с \(m=\lfloor N/2 \rfloor\), каждый раз делит \(m\) на \(2\) и добавляет к ответу \(\Phi(m)-1\), пока \(m \ge 2\). Все вычисления ведутся по модулю \(10^9+7\).
Пусть \(B=5{,}000{,}000\) — порог предварительного расчета в реализации. Линейное решето и таблица префиксов требуют \(O(B)\) времени и \(O(B)\) памяти. Внешняя сумма по аргументам \(N/2,N/4,N/8,\dots\) содержит только \(O(\log N)\) членов.
Основная трудность связана с большими значениями \(\Phi(n)\), но разбиение на блоки одинакового частного сильно сокращает суммирование, а мемоизация убирает повторную работу. Именно поэтому вычисление для \(N=10^{11}\) оказывается практичным.
يُسمى الزوج \((a,b)\) مع الشرط \(1 \le a \lt b \le N\) زوجًا 2-friendly إذا كانت \(\gcd(a,b)\) قوة للعدد \(2\) وأكبر من \(1\). المطلوب إذن هو حساب
$$f(10^{11}) \pmod{10^9+7}.$$
العدّ المباشر لجميع الأزواج مستحيل عمليًا لأن كلفته تربيعية في \(N\)، لذلك تعيد الفكرة تنظيم المسألة حول القيمة الدقيقة للقاسم المشترك الأكبر.
كل زوج صالح يملك قاسمًا مشتركًا أكبر يكتب على الصورة \(2^t\) حيث \(t \ge 1\). وإذا ثبّتنا هذه القيمة الدقيقة، فإن بقية المسألة تتحول إلى عدّ أزواج أولية نسبيًا.
افترض أن
$$\gcd(a,b)=2^t,\qquad t \ge 1.$$
عندئذ نستطيع أن نكتب
$$a=2^t x,\qquad b=2^t y,$$
بحيث
$$1 \le x \lt y \le \left\lfloor \frac{N}{2^t} \right\rfloor.$$
ولأن المطلوب أن يكون القاسم المشترك الأكبر مساويًا تمامًا لـ \(2^t\)، فإن الزوج المختزل يجب أن يحقق
$$\gcd(x,y)=1.$$
والعكس صحيح أيضًا: كل زوج أولي نسبيًا \((x,y)\) في هذا المدى يولد زوجًا وحيدًا \((2^t x,2^t y)\) قاسمه المشترك الأكبر هو بالضبط \(2^t\). لذلك لا يوجد تداخل أو عدّ مكرر بين القيم المختلفة لـ \(t\).
لحد علوي ثابت \(m\)، نعرّف
$$C(m)=\#\{(x,y):1 \le x \lt y \le m,\ \gcd(x,y)=1\}.$$
إذا ثبتنا القيمة الأكبر \(y\)، فإن القيم الممكنة لـ \(x\) هي بالضبط الأعداد \(1 \le x \lt y\) الأولية نسبيًا مع \(y\)، وعددها \(\varphi(y)\). ومن ثم
$$C(m)=\sum_{y=2}^{m}\varphi(y).$$
وبتعريف الدالة التراكمية
$$\Phi(m)=\sum_{k=1}^{m}\varphi(k),$$
وباستخدام \(\varphi(1)=1\)، نحصل على
$$C(m)=\Phi(m)-1.$$
إذا ثبتنا \(t\)، فإن عدد الأزواج التي يكون قاسمها المشترك الأكبر \(2^t\) هو
$$C\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)=\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1.$$
إذًا يكون الجواب الكلي
$$f(N)=\sum_{t \ge 1}\left(\Phi\left(\left\lfloor \frac{N}{2^t} \right\rfloor\right)-1\right).$$
وهذا المجموع يحوي عددًا منتهيًا فقط من الحدود غير الصفرية، لأن \(\left\lfloor N/2^t \right\rfloor \le 1\) يعني أنه لم يعد هناك مجال لزوج يحقق \(x \lt y\).
التنفيذ لا يعيد حساب \(\varphi(1)+\cdots+\varphi(n)\) من البداية في كل مرة، بل يستعمل الهوية المعروفة
$$\sum_{d \mid m}\varphi(d)=m.$$
وعند جمعها من \(m=1\) حتى \(m=n\) نحصل على
$$\sum_{m=1}^{n} m=\sum_{m=1}^{n}\sum_{d \mid m}\varphi(d).$$
وبتبديل ترتيب الجمع ينتج
$$\frac{n(n+1)}{2}=\sum_{q=1}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
ومن ثم، بعد فصل حد \(q=1\)، نحصل على العلاقة التراجعية
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right).$$
فائدة هذه الصيغة أن القيم \(\left\lfloor n/q \right\rfloor\) تتكرر على فترات كاملة، ولذلك يمكن معالجة المجموع على شكل كتل بدل المرور على كل \(q\) على حدة.
إذا بدأت كتلة عند \(l\)، فنعرّف
$$v=\left\lfloor \frac{n}{l} \right\rfloor,\qquad r=\left\lfloor \frac{n}{v} \right\rfloor.$$
حينها تكون جميع القيم \(q\) ضمن المجال \(l \le q \le r\) ذات خارج قسمة واحد هو \(v\)، وبالتالي يكون إسهام هذه الكتلة بالكامل
$$ (r-l+1)\,\Phi(v). $$
هذا يقلص العمل كثيرًا. ثم إن التخزين المؤقت يحتفظ بكل قيمة كبيرة لـ \(\Phi(v)\) بعد أول حساب لها، وهو أمر مهم لأن المجموع الخارجي يطلب القيم عند الحدود المترابطة \(N/2,N/4,N/8,\dots\).
عندما \(N=10\)، فإن القيم المهمة في المجموع الخارجي هي
$$\left\lfloor \frac{10}{2} \right\rfloor=5,\qquad \left\lfloor \frac{10}{4} \right\rfloor=2,\qquad \left\lfloor \frac{10}{8} \right\rfloor=1.$$
الحد الأخير يساوي صفرًا لأن \(\Phi(1)-1=0\). لذلك
$$f(10)=\left(\Phi(5)-1\right)+\left(\Phi(2)-1\right).$$
وبما أن
$$\Phi(5)=1+1+2+2+4=10,\qquad \Phi(2)=1+1=2,$$
فإن
$$f(10)=9+1=10.$$
والأزواج العشرة هي
$$(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10),(4,8).$$
الأزواج التسعة الأولى قاسمها المشترك الأكبر \(2\)، أما الزوج الأخير فقاسمه المشترك الأكبر \(4\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولًا تُحسب قيم \(\varphi(n)\) حتى حد ثابت مقداره خمسة ملايين باستعمال غربال خطي، ثم تُخزَّن المجاميع التراكمية لهذه القيم بترديد \(10^9+7\). وهكذا تصبح الاستعلامات الصغيرة عن \(\Phi(n)\) مجرد قراءة مباشرة من جدول.
أما عندما يكون \(n\) كبيرًا، فإن التنفيذ يستعمل العلاقة
$$\Phi(n)=\frac{n(n+1)}{2}-\sum_{q=2}^{n}\Phi\left(\left\lfloor \frac{n}{q} \right\rfloor\right)$$
ويحسبها على شكل كتل ذات خارج قسمة متساوٍ، ثم يخزن النتيجة مؤقتًا حتى لا يعاد حساب القيمة نفسها مرة أخرى.
وفي النهاية تبدأ الحلقة الرئيسية من \(m=\lfloor N/2 \rfloor\)، ثم تقسم \(m\) على \(2\) في كل مرة وتضيف \(\Phi(m)-1\) إلى الجواب حتى يصبح \(m \lt 2\). جميع العمليات الحسابية تُجرى بترديد \(10^9+7\).
إذا رمزنا إلى حد ما قبل الحساب المسبق بالرمز \(B=5{,}000{,}000\)، فإن الغربال الخطي وجدول المجاميع التراكمية يحتاجان إلى \(O(B)\) زمنًا و\(O(B)\) ذاكرة. أما المجموع الخارجي على القيم \(N/2,N/4,N/8,\dots\) فلا يحتوي إلا على \(O(\log N)\) حدًا.
الجزء الأثقل هو تقييم \(\Phi(n)\) للقيم الكبيرة، لكن تجميع الحدود بحسب خارج القسمة يضغط المجموع كثيرًا، كما أن التخزين المؤقت يزيل الحسابات المكررة. ولهذا السبب يصبح التعامل مع \(N=10^{11}\) ممكنًا عمليًا.