For an interval \([a,b]\), let \(C(a,b)\) be the number of non-empty subsets of \(\{a,a+1,\dots,b\}\) whose product is a perfect square. The task is to compute
$$C(10^6,1234567)\bmod(10^9+7).$$
Small checkpoints such as \(C(5,10)=3\) and \(C(40,55)=15\) clarify the intended interpretation. The interval is far too large for direct subset enumeration, so the problem must be transformed into linear algebra over \(\mathbb F_2\).
Write the interval elements as \(x_1,\dots,x_n\), where \(n=b-a+1\). The key observation is that a product is a square exactly when every prime exponent in that product is even, and parity is naturally encoded over \(\mathbb F_2\).
If
$$x=\prod_p p^{e_p},$$
then only the residues \(e_p\bmod 2\) matter. Define a binary vector \(v_x\) by
$$v_x(p)=e_p\bmod 2.$$
Equivalently, every integer can be written as \(x=q^2s\) with \(s\) squarefree, and \(v_x\) records exactly the primes dividing \(s\). For example, \(12=2^2\cdot 3\) contributes only the prime \(3\), while \(18=2\cdot 3^2\) contributes only the prime \(2\).
For a subset \(S\subseteq \{a,a+1,\dots,b\}\), the product is
$$\prod_{x\in S}x=\prod_p p^{\sum_{x\in S}e_p(x)}.$$
This product is a perfect square if and only if every exponent sum is even. In vector form, that is exactly
$$\bigoplus_{x\in S} v_x=0.$$
If we introduce coefficients \(\lambda_i\in\{0,1\}\) telling whether \(x_i\) is chosen, the condition becomes
$$\lambda_1v_{x_1}\oplus \lambda_2v_{x_2}\oplus\cdots\oplus \lambda_nv_{x_n}=0.$$
So square subsets are precisely the linear relations among the parity vectors.
Let \(r\) be the rank of the family \(v_{x_1},\dots,v_{x_n}\) over \(\mathbb F_2\). The linear map sending \((\lambda_1,\dots,\lambda_n)\) to the xor-sum above has image dimension \(r\), so its kernel has size
$$2^{n-r}.$$
Every kernel vector corresponds to a subset whose product is a square, and the zero vector corresponds to the empty subset. Therefore
$$C(a,b)=2^{n-r}-1.$$
Once the rank is known, the counting part of the problem is finished.
A dense vector would have one coordinate for every prime up to \(b\), but most integers leave only a small set of primes with odd exponent. That means each row is naturally sparse. Over \(\mathbb F_2\), row addition is xor, which on supports is just symmetric difference: a prime remains present exactly when it appears in one row but not the other.
This lets the implementation work with sorted prime-index lists instead of huge dense bit matrices. Numbers that are already perfect squares produce the zero vector immediately, which is consistent with the fact that such singletons already form valid square subsets.
The six interval elements give the parity supports
$$5\mapsto\{5\},\quad 6\mapsto\{2,3\},\quad 7\mapsto\{7\},\quad 8\mapsto\{2\},\quad 9\mapsto\varnothing,\quad 10\mapsto\{2,5\}.$$
The nonzero rows for \(5,6,7,8\) are independent, while
$$\{2,5\}=\{2\}\oplus\{5\}.$$
Hence the rank is \(r=4\). Since \(n=6\), the nullity is \(6-4=2\), so
$$C(5,10)=2^2-1=3.$$
The three non-empty square subsets are \(\{9\}\), \(\{5,8,10\}\), and \(\{5,8,9,10\}\), which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations first build a smallest-prime-factor table up to the upper end of the interval. This makes repeated factorization fast enough for every number from \(a\) to \(b\).
Each interval element is then factored, and every prime whose exponent is odd is kept in a sparse support list. The list is ordered by prime index, so xor-reduction can be done by merging two ordered supports and removing entries that appear twice.
During Gaussian elimination over \(\mathbb F_2\), the implementation uses the largest remaining prime index as the current pivot. If no basis row owns that pivot yet, the current row becomes a new basis vector and the rank increases. Otherwise the current row is xor-reduced by the stored basis row and the process continues until the row vanishes or claims a new pivot.
After all rows have been processed, the implementation knows \(r\), computes \(n-r\), and returns
$$2^{n-r}-1 \pmod{10^9+7}$$
using fast modular exponentiation.
Let \(B=b\) and \(n=b-a+1\). Building the smallest-prime-factor sieve up to \(B\) costs \(O(B\log\log B)\) time and \(O(B)\) memory. Factoring the \(n\) interval elements through that table is near-linear in practice and has average order \(O(n\log\log B)\).
The elimination phase depends on the total sizes of the sparse supports and on how much cancellation occurs during xor-reduction. In this problem that sparse representation is far smaller than a dense matrix with one column per prime up to \(B\). The overall method is therefore dominated by the sieve plus sparse elimination, while memory remains \(O(B)\) for the sieve together with the stored sparse basis.
Für ein Intervall \([a,b]\) sei \(C(a,b)\) die Anzahl der nichtleeren Teilmengen von \(\{a,a+1,\dots,b\}\), deren Produkt ein perfektes Quadrat ist. Gesucht ist
$$C(10^6,1234567)\bmod(10^9+7).$$
Kleine Kontrollwerte wie \(C(5,10)=3\) und \(C(40,55)=15\) verdeutlichen die Bedeutung der Aufgabe. Das Intervall ist viel zu groß für direkte Teilmengen-Enumeration, daher muss das Problem in lineare Algebra über \(\mathbb F_2\) übersetzt werden.
Bezeichne die Intervallelemente mit \(x_1,\dots,x_n\), wobei \(n=b-a+1\). Die zentrale Beobachtung ist: Ein Produkt ist genau dann ein Quadrat, wenn jeder Primexponent in diesem Produkt gerade ist. Diese Parität lässt sich natürlich über \(\mathbb F_2\) kodieren.
Ist
$$x=\prod_p p^{e_p},$$
dann sind nur die Reste \(e_p\bmod 2\) relevant. Definiere daher einen binären Vektor \(v_x\) durch
$$v_x(p)=e_p\bmod 2.$$
Äquivalent dazu kann man \(x=q^2s\) mit quadratfreiem \(s\) schreiben, und \(v_x\) merkt sich genau die Primzahlen, die \(s\) teilen. Zum Beispiel trägt \(12=2^2\cdot 3\) nur die Primzahl \(3\), während \(18=2\cdot 3^2\) nur die Primzahl \(2\) beiträgt.
Für eine Teilmenge \(S\subseteq \{a,a+1,\dots,b\}\) gilt
$$\prod_{x\in S}x=\prod_p p^{\sum_{x\in S}e_p(x)}.$$
Dieses Produkt ist genau dann ein perfektes Quadrat, wenn jede Exponentensumme gerade ist. In Vektorform ist das äquivalent zu
$$\bigoplus_{x\in S} v_x=0.$$
Führt man Koeffizienten \(\lambda_i\in\{0,1\}\) ein, die angeben, ob \(x_i\) gewählt wird, so wird die Bedingung zu
$$\lambda_1v_{x_1}\oplus \lambda_2v_{x_2}\oplus\cdots\oplus \lambda_nv_{x_n}=0.$$
Quadratische Produkte entsprechen also genau den linearen Relationen zwischen den Paritätsvektoren.
Sei \(r\) der Rang der Familie \(v_{x_1},\dots,v_{x_n}\) über \(\mathbb F_2\). Die lineare Abbildung, die \((\lambda_1,\dots,\lambda_n)\) auf die obige xor-Summe schickt, hat Bilddimension \(r\). Daher besitzt ihr Kern genau
$$2^{n-r}$$
Elemente. Jeder Kernvektor entspricht einer Teilmenge mit Quadratprodukt, und der Nullvektor steht für die leere Teilmenge. Also
$$C(a,b)=2^{n-r}-1.$$
Sobald der Rang bestimmt ist, ist der Zählteil der Aufgabe erledigt.
Ein dichter Vektor hätte eine Koordinate für jede Primzahl bis \(b\), aber die meisten Zahlen hinterlassen nur eine kleine Menge von Primzahlen mit ungeradem Exponenten. Dadurch sind die Zeilen von Natur aus dünn besetzt. Über \(\mathbb F_2\) ist Zeilenaddition xor, und auf Trägermengen ist das nichts anderes als die symmetrische Differenz.
Darum kann die Implementierung mit sortierten Listen von Primzahlindizes arbeiten statt mit riesigen dichten Bitmatrizen. Zahlen, die bereits perfekte Quadrate sind, liefern sofort den Nullvektor, was dazu passt, dass solche Einzelmengen bereits gültige Quadratprodukte bilden.
Die sechs Intervallelemente liefern die Paritätsträger
$$5\mapsto\{5\},\quad 6\mapsto\{2,3\},\quad 7\mapsto\{7\},\quad 8\mapsto\{2\},\quad 9\mapsto\varnothing,\quad 10\mapsto\{2,5\}.$$
Die vier von Null verschiedenen Zeilen für \(5,6,7,8\) sind unabhängig, während
$$\{2,5\}=\{2\}\oplus\{5\}.$$
Somit ist der Rang \(r=4\). Wegen \(n=6\) ist die Nullität \(6-4=2\), also
$$C(5,10)=2^2-1=3.$$
Die drei nichtleeren Quadrat-Teilmengen sind \(\{9\}\), \(\{5,8,10\}\) und \(\{5,8,9,10\}\). Das stimmt mit dem Kontrollwert der Implementierung überein.
Die C++-, Python- und Java-Implementierungen bauen zuerst eine Tabelle der kleinsten Primteiler bis zur oberen Intervallgrenze auf. Dadurch wird die Faktorisierung jedes Wertes von \(a\) bis \(b\) schnell genug.
Jedes Intervallelement wird dann faktorisiert, und jede Primzahl mit ungeradem Exponenten bleibt in einer sparsamen Trägerliste erhalten. Diese Liste ist nach Primzahlindizes sortiert, sodass eine xor-Reduktion als Zusammenführen zweier geordneter Träger mit Wegfall doppelter Einträge durchgeführt werden kann.
Während der Gauß-Elimination über \(\mathbb F_2\) verwendet die Implementierung jeweils den größten noch vorhandenen Primzahlindex als Pivot. Wenn noch keine Basiszeile diesen Pivot besitzt, wird die aktuelle Zeile ein neuer Basisvektor und der Rang steigt um \(1\). Andernfalls wird die aktuelle Zeile per xor mit der gespeicherten Basiszeile reduziert, bis sie verschwindet oder einen neuen Pivot beansprucht.
Nachdem alle Zeilen verarbeitet sind, kennt die Implementierung \(r\), berechnet \(n-r\) und gibt
$$2^{n-r}-1 \pmod{10^9+7}$$
mittels schneller modularer Exponentiation aus.
Seien \(B=b\) und \(n=b-a+1\). Das Sieb der kleinsten Primteiler bis \(B\) benötigt \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Die Faktorisierung der \(n\) Intervallelemente über diese Tabelle ist in der Praxis nahezu linear und hat mittlere Größenordnung \(O(n\log\log B)\).
Die Eliminationsphase hängt von der Gesamtlänge der sparsamen Trägermengen und vom Ausmaß der Kürzungen bei der xor-Reduktion ab. In dieser Aufgabe ist die sparse Darstellung wesentlich kleiner als eine dichte Matrix mit einer Spalte pro Primzahl bis \(B\). Insgesamt wird das Verfahren daher vom Sieb und von der sparsamen Elimination dominiert, während der Speicher bei \(O(B)\) für das Sieb plus der gespeicherten dünn besetzten Basis bleibt.
\([a,b]\) aralığı için \(C(a,b)\), \(\{a,a+1,\dots,b\}\) kümesinin çarpımı tam kare olan boş olmayan alt kümelerinin sayısı olsun. İstenen değer
$$C(10^6,1234567)\bmod(10^9+7).$$
\(C(5,10)=3\) ve \(C(40,55)=15\) gibi küçük kontrol değerleri sorunun nasıl yorumlandığını gösterir. Aralık çok büyük olduğu için alt kümeleri doğrudan denemek imkansızdır; bu yüzden problemi \(\mathbb F_2\) üzerinde lineer cebire dönüştürmek gerekir.
Aralıktaki sayıları \(x_1,\dots,x_n\) diye yazalım; burada \(n=b-a+1\). Ana gözlem şudur: Bir çarpım ancak ve ancak içindeki her asalın üssü çiftse karedir. Üslerin paritesi de doğal olarak \(\mathbb F_2\) üzerinde kodlanır.
Eğer
$$x=\prod_p p^{e_p},$$
ise sadece \(e_p\bmod 2\) kalıntıları önemlidir. Bu nedenle
$$v_x(p)=e_p\bmod 2$$
şeklinde bir ikili vektör tanımlarız. Eşdeğer biçimde her sayı \(x=q^2s\) olarak yazılabilir; burada \(s\) karesizdir ve \(v_x\) tam olarak \(s\)'yi bölen asalları kaydeder. Örneğin \(12=2^2\cdot 3\) yalnızca \(3\) asalını bırakırken, \(18=2\cdot 3^2\) yalnızca \(2\) asalını bırakır.
\(S\subseteq \{a,a+1,\dots,b\}\) için alt küme çarpımı
$$\prod_{x\in S}x=\prod_p p^{\sum_{x\in S}e_p(x)}$$
şeklindedir. Bunun tam kare olması için her üs toplamının çift olması gerekir. Vektör dilinde bu tam olarak
$$\bigoplus_{x\in S} v_x=0$$
demektir. \(x_i\)'nin seçilip seçilmediğini gösteren \(\lambda_i\in\{0,1\}\) katsayılarını yazarsak koşul
$$\lambda_1v_{x_1}\oplus \lambda_2v_{x_2}\oplus\cdots\oplus \lambda_nv_{x_n}=0$$
olur. Yani kare veren alt kümeler, parite vektörleri arasındaki lineer bağıntıların ta kendisidir.
\(v_{x_1},\dots,v_{x_n}\) ailesinin \(\mathbb F_2\) üzerindeki rütbesi \(r\) olsun. \((\lambda_1,\dots,\lambda_n)\) vektörünü yukarıdaki xor-toplamına gönderen lineer dönüşümün görüntü boyutu \(r\) olduğundan çekirdeğinin büyüklüğü
$$2^{n-r}$$
olur. Çekirdekteki her vektör, çarpımı kare olan bir alt kümeye karşılık gelir; sıfır vektör ise boş alt kümedir. Bu yüzden
$$C(a,b)=2^{n-r}-1$$
elde edilir. Rütbe bulununca sayım işi tamamlanmış olur.
Yoğun bir vektörde \(b\)'ye kadar olan her asal için bir koordinat bulunurdu, fakat çoğu sayıda yalnızca az sayıda asal tek üsle kalır. Bu yüzden satırlar doğal olarak seyrektir. \(\mathbb F_2\) üzerinde satır toplama xor olduğundan, taşıyıcı kümelerde bu işlem sadece simetrik farktır.
Böylece uygulama devasa bit matrisleri yerine sıralı asal-indeks listeleriyle çalışabilir. Zaten tam kare olan sayılar doğrudan sıfır vektör üretir; bu da böyle tekli alt kümelerin baştan geçerli çözümler olmasına tam olarak uyar.
Altı sayı için parite taşıyıcıları
$$5\mapsto\{5\},\quad 6\mapsto\{2,3\},\quad 7\mapsto\{7\},\quad 8\mapsto\{2\},\quad 9\mapsto\varnothing,\quad 10\mapsto\{2,5\}$$
şeklindedir. \(5,6,7,8\) için gelen sıfır olmayan dört satır bağımsızdır; ayrıca
$$\{2,5\}=\{2\}\oplus\{5\}$$
olduğu için son satır bunlardan türetilir. Dolayısıyla rütbe \(r=4\) olur. \(n=6\) olduğundan nullity \(6-4=2\)'dir ve
$$C(5,10)=2^2-1=3$$
çıkar. Üç boş olmayan kare alt küme \(\{9\}\), \(\{5,8,10\}\) ve \(\{5,8,9,10\}\) olur; bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları önce aralığın üst sınırına kadar en küçük asal bölen tablosu kurar. Böylece \(a\) ile \(b\) arasındaki her sayının tekrar tekrar çarpanlara ayrılması yeterince hızlı hale gelir.
Daha sonra her sayı ayrıştırılır ve üssü tek olan asallar seyrek bir taşıyıcı listede tutulur. Liste asal indekslerine göre sıralandığı için xor indirgeme, iki sıralı taşıyıcıyı birleştirip iki kez görünenleri silmekten ibarettir.
\(\mathbb F_2\) üzerindeki Gauss eliminasyonunda uygulama, elde kalan en büyük asal indeksini pivot olarak kullanır. Eğer bu pivot için henüz bir baz satırı yoksa mevcut satır yeni baz vektörü olur ve rütbe \(1\) artar. Aksi halde mevcut satır saklanan baz satırıyla xor yapılarak küçültülür; satır ya tamamen yok olur ya da yeni bir pivot elde eder.
Tüm satırlar işlendikten sonra uygulama \(r\)'yi bilir, \(n-r\)'yi hesaplar ve
$$2^{n-r}-1 \pmod{10^9+7}$$
değerini hızlı modüler üs alma ile döndürür.
\(B=b\) ve \(n=b-a+1\) olsun. \(B\)'ye kadar en küçük asal bölen süzgecini kurmak \(O(B\log\log B)\) zaman ve \(O(B)\) bellek ister. Bu tabloyla \(n\) adet aralık elemanını çarpanlara ayırmak pratikte lineere yakındır ve ortalama büyüklük olarak \(O(n\log\log B)\) düzeyindedir.
Eliminasyon aşaması seyrek taşıyıcıların toplam boylarına ve xor sırasında oluşan sadeleşme miktarına bağlıdır. Bu problemde seyrek gösterim, \(B\)'ye kadar olan her asal için sütun içeren yoğun bir matrise göre çok daha küçüktür. Bu nedenle toplam maliyeti süzgeç ile seyrek eliminasyon belirler; bellek kullanımı da süzgeç için \(O(B)\) ile saklanan seyrek bazın toplamından oluşur.
Para un intervalo \([a,b]\), sea \(C(a,b)\) el número de subconjuntos no vacíos de \(\{a,a+1,\dots,b\}\) cuyo producto es un cuadrado perfecto. Debemos calcular
$$C(10^6,1234567)\bmod(10^9+7).$$
Valores de control como \(C(5,10)=3\) y \(C(40,55)=15\) aclaran la interpretación correcta. El intervalo es demasiado grande para enumerar subconjuntos directamente, así que hay que reformular el problema como álgebra lineal sobre \(\mathbb F_2\).
Escribimos los elementos del intervalo como \(x_1,\dots,x_n\), donde \(n=b-a+1\). La observación clave es que un producto es cuadrado si y solo si cada exponente primo de ese producto es par, y la paridad se codifica de forma natural en \(\mathbb F_2\).
Si
$$x=\prod_p p^{e_p},$$
entonces solo importan los residuos \(e_p\bmod 2\). Definimos un vector binario \(v_x\) mediante
$$v_x(p)=e_p\bmod 2.$$
De manera equivalente, todo entero puede escribirse como \(x=q^2s\) con \(s\) libre de cuadrados, y \(v_x\) registra exactamente los primos que dividen a \(s\). Por ejemplo, \(12=2^2\cdot 3\) deja solo el primo \(3\), mientras que \(18=2\cdot 3^2\) deja solo el primo \(2\).
Para un subconjunto \(S\subseteq \{a,a+1,\dots,b\}\), el producto vale
$$\prod_{x\in S}x=\prod_p p^{\sum_{x\in S}e_p(x)}.$$
Ese producto es un cuadrado perfecto si y solo si toda suma de exponentes es par. En lenguaje vectorial, eso equivale a
$$\bigoplus_{x\in S} v_x=0.$$
Si introducimos coeficientes \(\lambda_i\in\{0,1\}\) que indican si \(x_i\) se elige o no, la condición queda
$$\lambda_1v_{x_1}\oplus \lambda_2v_{x_2}\oplus\cdots\oplus \lambda_nv_{x_n}=0.$$
Por tanto, los subconjuntos cuyo producto es cuadrado son exactamente las relaciones lineales entre los vectores de paridad.
Sea \(r\) el rango de la familia \(v_{x_1},\dots,v_{x_n}\) sobre \(\mathbb F_2\). La aplicación lineal que envía \((\lambda_1,\dots,\lambda_n)\) a la xor-suma anterior tiene imagen de dimensión \(r\), de modo que su núcleo contiene
$$2^{n-r}$$
vectores. Cada vector del núcleo corresponde a un subconjunto cuyo producto es cuadrado, y el vector nulo representa al subconjunto vacío. En consecuencia,
$$C(a,b)=2^{n-r}-1.$$
Una vez conocido el rango, el problema de conteo queda resuelto.
Un vector denso tendría una coordenada por cada primo hasta \(b\), pero la mayoría de los enteros solo dejan unas pocas primas con exponente impar. Por eso cada fila es naturalmente dispersa. Sobre \(\mathbb F_2\), sumar filas es hacer xor, y en los soportes eso coincide con la diferencia simétrica.
Esto permite que la implementación trabaje con listas ordenadas de índices primos en lugar de matrices de bits enormes. Los números que ya son cuadrados perfectos producen inmediatamente el vector nulo, lo cual encaja con el hecho de que esos subconjuntos unitarios ya son soluciones válidas.
Los seis elementos del intervalo producen los soportes de paridad
$$5\mapsto\{5\},\quad 6\mapsto\{2,3\},\quad 7\mapsto\{7\},\quad 8\mapsto\{2\},\quad 9\mapsto\varnothing,\quad 10\mapsto\{2,5\}.$$
Las cuatro filas no nulas de \(5,6,7,8\) son independientes, mientras que
$$\{2,5\}=\{2\}\oplus\{5\}.$$
Así, el rango es \(r=4\). Como \(n=6\), la nulidad es \(6-4=2\), y por tanto
$$C(5,10)=2^2-1=3.$$
Los tres subconjuntos no vacíos cuyo producto es cuadrado son \(\{9\}\), \(\{5,8,10\}\) y \(\{5,8,9,10\}\), exactamente el valor de control usado por la implementación.
Las implementaciones en C++, Python y Java construyen primero una tabla del menor factor primo hasta el extremo superior del intervalo. Eso hace que la factorización repetida de todos los números entre \(a\) y \(b\) sea lo bastante rápida.
Luego cada elemento del intervalo se factoriza y se conservan solo los primos cuyo exponente es impar, almacenados en una lista dispersa. La lista queda ordenada por índice primo, de modo que la reducción por xor se realiza fusionando dos soportes ordenados y eliminando las entradas que aparecen dos veces.
Durante la eliminación gaussiana sobre \(\mathbb F_2\), la implementación usa como pivote el mayor índice primo que todavía queda en la fila actual. Si ninguna fila de la base posee todavía ese pivote, la fila actual pasa a ser un nuevo vector base y el rango aumenta en \(1\). En caso contrario, la fila actual se reduce con xor usando la fila base almacenada, y el proceso continúa hasta que la fila desaparece o conquista un pivote nuevo.
Cuando todas las filas han sido procesadas, la implementación ya conoce \(r\), calcula \(n-r\) y devuelve
$$2^{n-r}-1 \pmod{10^9+7}$$
mediante exponenciación modular rápida.
Sean \(B=b\) y \(n=b-a+1\). Construir la criba del menor factor primo hasta \(B\) cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. Factorizar los \(n\) elementos del intervalo con esa tabla es casi lineal en la práctica y tiene orden medio \(O(n\log\log B)\).
La fase de eliminación depende del tamaño total de los soportes dispersos y del grado de cancelación que aparece durante las reducciones xor. En este problema, la representación dispersa es mucho menor que una matriz densa con una columna por cada primo hasta \(B\). Por ello, el coste global queda dominado por la criba y la eliminación dispersa, mientras que la memoria permanece en \(O(B)\) para la criba más la base dispersa almacenada.
对于区间 \([a,b]\)，记 \(C(a,b)\) 为集合 \(\{a,a+1,\dots,b\}\) 的所有非空子集中，元素乘积为完全平方数的那些子集个数。题目要求计算
$$C(10^6,1234567)\bmod(10^9+7).$$
像 \(C(5,10)=3\) 和 \(C(40,55)=15\) 这样的校验值说明了题意的精确含义。由于区间非常大，不可能直接枚举所有子集，所以必须把问题改写成 \(\mathbb F_2\) 上的线性代数问题。
把区间中的数写成 \(x_1,\dots,x_n\)，其中 \(n=b-a+1\)。核心观察是：一个乘积是完全平方数，当且仅当这个乘积里每个素数的指数都是偶数，而“奇偶性”正好适合用 \(\mathbb F_2\) 来表示。
若
$$x=\prod_p p^{e_p},$$
那么真正重要的只有 \(e_p\bmod 2\)。因此定义二进制向量 \(v_x\) 为
$$v_x(p)=e_p\bmod 2.$$
也可以等价地写成 \(x=q^2s\)，其中 \(s\) 是平方自由数，而 \(v_x\) 恰好记录 \(s\) 被哪些素数整除。例如 \(12=2^2\cdot 3\) 只留下素数 \(3\)，而 \(18=2\cdot 3^2\) 只留下素数 \(2\)。
对任意子集 \(S\subseteq \{a,a+1,\dots,b\}\)，其乘积可以写成
$$\prod_{x\in S}x=\prod_p p^{\sum_{x\in S}e_p(x)}.$$
这个乘积是完全平方数，当且仅当每个素数的指数和都是偶数。用向量语言表达，这正是
$$\bigoplus_{x\in S} v_x=0.$$
如果用 \(\lambda_i\in\{0,1\}\) 表示 \(x_i\) 是否被选入子集，那么条件就变成
$$\lambda_1v_{x_1}\oplus \lambda_2v_{x_2}\oplus\cdots\oplus \lambda_nv_{x_n}=0.$$
因此，乘积为平方数的子集，等价于这些奇偶向量之间的所有线性关系。
设向量族 \(v_{x_1},\dots,v_{x_n}\) 在 \(\mathbb F_2\) 上的秩为 \(r\)。把 \((\lambda_1,\dots,\lambda_n)\) 映射到上面异或和的线性变换，其像空间维数就是 \(r\)，因此核空间大小为
$$2^{n-r}.$$
核中的每个向量都对应一个乘积为平方数的子集，而零向量对应空集。所以最终有
$$C(a,b)=2^{n-r}-1.$$
也就是说，问题真正需要做的只是把这些奇偶向量的秩算出来。
如果用稠密向量表示，就需要给每个不超过 \(b\) 的素数都分配一个坐标。但实际上，大多数整数在去掉平方因子后，只剩很少几个素数带有奇数次幂，所以每一行天然都是稀疏的。在线性空间 \(\mathbb F_2\) 中，行相加就是 xor，而在“支持集”的层面，这正好等于对称差。
因此，实现时没有必要维护庞大的稠密位矩阵，只需保存按素数编号排序的稀疏支持列表即可。特别地，若某个数本身就是完全平方数，那么它立刻对应零向量，这也与“单元素子集已经是合法解”完全一致。
区间中的六个数对应的奇偶支持集为
$$5\mapsto\{5\},\quad 6\mapsto\{2,3\},\quad 7\mapsto\{7\},\quad 8\mapsto\{2\},\quad 9\mapsto\varnothing,\quad 10\mapsto\{2,5\}.$$
其中 \(5,6,7,8\) 对应的四个非零行彼此线性无关，而
$$\{2,5\}=\{2\}\oplus\{5\}.$$
所以秩 \(r=4\)。由于 \(n=6\)，零化度为 \(6-4=2\)，于是
$$C(5,10)=2^2-1=3.$$
这三个非空平方子集分别是 \(\{9\}\)、\(\{5,8,10\}\) 和 \(\{5,8,9,10\}\)。它与实现中使用的校验值完全一致。
C++、Python 和 Java 实现都会先做到区间上界为止的最小素因子筛。这样一来，从 \(a\) 到 \(b\) 的每个整数都可以被快速重复分解。
随后，程序对区间中的每个数做质因数分解，只保留那些指数为奇数的素数，并把它们按素数编号存成稀疏支持列表。因为列表是有序的，所以 xor 约化可以通过合并两条有序支持并删去重复项来完成。
在 \(\mathbb F_2\) 上进行高斯消元时，程序总是取当前行里最大的素数编号作为主元。如果这个主元还没有对应的基行，那么当前行就成为新的基向量，秩加 \(1\)。如果这个主元已经被某条基行占据，当前行就与那条基行做 xor 约化，直到整行消失或者获得一个新的主元位置。
当所有区间元素都处理完后，程序已经知道秩 \(r\)，于是计算 \(n-r\)，最后返回
$$2^{n-r}-1 \pmod{10^9+7}$$
其中幂运算用的是快速模幂。
记 \(B=b\)，\(n=b-a+1\)。建立到 \(B\) 为止的最小素因子筛需要 \(O(B\log\log B)\) 时间和 \(O(B)\) 空间。借助这张表，对区间中 \(n\) 个整数进行分解，在平均意义上接近线性，规模大致为 \(O(n\log\log B)\)。
消元阶段的代价取决于所有稀疏支持的总长度，以及 xor 约化时出现了多少抵消。在本题里，稀疏表示远小于“每个不超过 \(B\) 的素数都占一列”的稠密矩阵，因此整体开销主要由筛法和稀疏消元组成，而内存则保持在筛表的 \(O(B)\) 加上稀疏基向量存储这一量级。
Для интервала \([a,b]\) обозначим через \(C(a,b)\) число непустых подмножеств множества \(\{a,a+1,\dots,b\}\), произведение элементов которых является полным квадратом. Требуется вычислить
$$C(10^6,1234567)\bmod(10^9+7).$$
Небольшие контрольные значения \(C(5,10)=3\) и \(C(40,55)=15\) показывают, как именно следует понимать задачу. Интервал слишком велик для прямого перебора подмножеств, поэтому задачу нужно переписать в терминах линейной алгебры над \(\mathbb F_2\).
Обозначим элементы интервала через \(x_1,\dots,x_n\), где \(n=b-a+1\). Ключевое наблюдение таково: произведение является квадратом тогда и только тогда, когда показатель каждой простой в этом произведении четен, а четность естественно кодируется полем \(\mathbb F_2\).
Если
$$x=\prod_p p^{e_p},$$
то важны только остатки \(e_p\bmod 2\). Поэтому определим бинарный вектор \(v_x\) формулой
$$v_x(p)=e_p\bmod 2.$$
Эквивалентно можно записать \(x=q^2s\), где \(s\) квадратсвободно, а \(v_x\) фиксирует ровно те простые, которые делят \(s\). Например, \(12=2^2\cdot 3\) оставляет только простое \(3\), а \(18=2\cdot 3^2\) оставляет только простое \(2\).
Для подмножества \(S\subseteq \{a,a+1,\dots,b\}\) имеем
$$\prod_{x\in S}x=\prod_p p^{\sum_{x\in S}e_p(x)}.$$
Это произведение является полным квадратом тогда и только тогда, когда каждая сумма показателей четна. В векторной форме это ровно условие
$$\bigoplus_{x\in S} v_x=0.$$
Если ввести коэффициенты \(\lambda_i\in\{0,1\}\), показывающие, выбрано ли \(x_i\), то получаем
$$\lambda_1v_{x_1}\oplus \lambda_2v_{x_2}\oplus\cdots\oplus \lambda_nv_{x_n}=0.$$
Следовательно, подмножества с квадратным произведением - это в точности линейные соотношения между паритетными векторами.
Пусть \(r\) - ранг семейства \(v_{x_1},\dots,v_{x_n}\) над \(\mathbb F_2\). Линейное отображение, переводящее \((\lambda_1,\dots,\lambda_n)\) в указанную xor-сумму, имеет образ размерности \(r\), а значит, его ядро содержит
$$2^{n-r}$$
элементов. Каждый вектор из ядра соответствует подмножеству, произведение которого является квадратом, а нулевой вектор соответствует пустому подмножеству. Поэтому
$$C(a,b)=2^{n-r}-1.$$
Как только ранг найден, задача подсчета полностью решена.
Плотный вектор имел бы координату для каждого простого числа до \(b\), но у большинства чисел после удаления квадратной части остается лишь несколько простых с нечетным показателем. Значит, строки изначально разрежены. Над \(\mathbb F_2\) сложение строк - это xor, а на уровне носителей это просто симметрическая разность.
Поэтому реализации достаточно хранить отсортированные списки индексов простых, а не гигантскую плотную битовую матрицу. Числа, которые уже являются полными квадратами, немедленно дают нулевую строку, и это точно соответствует тому, что одноэлементные подмножества такого вида уже являются допустимыми решениями.
Шесть элементов интервала дают следующие паритетные носители:
$$5\mapsto\{5\},\quad 6\mapsto\{2,3\},\quad 7\mapsto\{7\},\quad 8\mapsto\{2\},\quad 9\mapsto\varnothing,\quad 10\mapsto\{2,5\}.$$
Четыре ненулевые строки для \(5,6,7,8\) линейно независимы, а
$$\{2,5\}=\{2\}\oplus\{5\}.$$
Значит, ранг равен \(r=4\). Так как \(n=6\), размер ядра определяется нулевой размерностью \(6-4=2\), и потому
$$C(5,10)=2^2-1=3.$$
Три непустых подмножества с квадратным произведением таковы: \(\{9\}\), \(\{5,8,10\}\) и \(\{5,8,9,10\}\). Это в точности совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java сначала строят таблицу наименьших простых делителей до верхней границы интервала. Благодаря этому повторная факторизация каждого числа от \(a\) до \(b\) выполняется достаточно быстро.
Затем каждое число раскладывается на простые, и в разреженном списке остаются только те простые, у которых показатель нечетен. Список упорядочен по индексам простых, поэтому xor-редукция выполняется как слияние двух упорядоченных носителей с удалением элементов, встретившихся дважды.
Во время исключения Гаусса над \(\mathbb F_2\) реализация берет текущим ведущим столбцом наибольший оставшийся индекс простого. Если ни одна строка базиса еще не владеет этим ведущим столбцом, текущая строка становится новым базисным вектором и ранг увеличивается на \(1\). Иначе текущая строка xor-редуцируется с уже сохраненной базисной строкой, пока не исчезнет совсем или не получит новый ведущий столбец.
После обработки всех строк реализация знает \(r\), вычисляет \(n-r\) и возвращает
$$2^{n-r}-1 \pmod{10^9+7}$$
с помощью быстрого возведения в степень по модулю.
Пусть \(B=b\), \(n=b-a+1\). Построение решета наименьших простых делителей до \(B\) требует \(O(B\log\log B)\) времени и \(O(B)\) памяти. Факторизация \(n\) элементов интервала с помощью этой таблицы на практике близка к линейной и имеет средний порядок \(O(n\log\log B)\).
Стоимость этапа исключения зависит от суммарной длины разреженных носителей и от того, насколько сильно они сокращаются при xor-редукции. В данной задаче разреженное представление намного меньше плотной матрицы с одним столбцом на каждый простой до \(B\). Поэтому общий расход определяется решетом и разреженным исключением, а память остается порядка \(O(B)\) для решета плюс хранение разреженного базиса.
للفترة \([a,b]\)، ليكن \(C(a,b)\) هو عدد المجموعات الجزئية غير الفارغة من \(\{a,a+1,\dots,b\}\) التي يكون حاصل ضرب عناصرها مربعًا كاملاً. المطلوب هو حساب
$$C(10^6,1234567)\bmod(10^9+7).$$
قيم الفحص الصغيرة مثل \(C(5,10)=3\) و\(C(40,55)=15\) توضّح المقصود بدقة. وبما أن المجال كبير جدًا فلا يمكن تعداد جميع المجموعات الجزئية مباشرة، لذلك يجب تحويل المسألة إلى جبر خطي فوق \(\mathbb F_2\).
لنكتب عناصر المجال على صورة \(x_1,\dots,x_n\)، حيث \(n=b-a+1\). الفكرة الأساسية هي أن حاصل الضرب يكون مربعًا كاملاً إذا وفقط إذا كان أس كل عدد أولي في ذلك الحاصل زوجيًا، وتمثيل الزوجية يتم بصورة طبيعية داخل \(\mathbb F_2\).
إذا كان
$$x=\prod_p p^{e_p},$$
فإن المهم فقط هو البواقي \(e_p\bmod 2\). لذلك نعرّف متجهًا ثنائيًا \(v_x\) بالعلاقة
$$v_x(p)=e_p\bmod 2.$$
وبصورة مكافئة يمكن كتابة كل عدد على صورة \(x=q^2s\) حيث \(s\) خالٍ من المربعات، والمتجه \(v_x\) يسجّل بالضبط الأعداد الأولية التي تقسم \(s\). مثلًا \(12=2^2\cdot 3\) يترك فقط العدد الأولي \(3\)، بينما \(18=2\cdot 3^2\) يترك فقط العدد الأولي \(2\).
لأي مجموعة جزئية \(S\subseteq \{a,a+1,\dots,b\}\)، يكون حاصل الضرب
$$\prod_{x\in S}x=\prod_p p^{\sum_{x\in S}e_p(x)}.$$
ويكون هذا الحاصل مربعًا كاملاً إذا وفقط إذا كانت كل مجاميع الأسس زوجية. وبصيغة المتجهات فهذا يكافئ تمامًا
$$\bigoplus_{x\in S} v_x=0.$$
إذا أدخلنا معاملات \(\lambda_i\in\{0,1\}\) لتحديد ما إذا كان \(x_i\) مختارًا أم لا، يصبح الشرط
$$\lambda_1v_{x_1}\oplus \lambda_2v_{x_2}\oplus\cdots\oplus \lambda_nv_{x_n}=0.$$
إذًا فالمجموعات الجزئية التي تعطي مربعًا كاملاً هي بالضبط العلاقات الخطية بين متجهات التكافؤ هذه.
لتكن \(r\) رتبة العائلة \(v_{x_1},\dots,v_{x_n}\) فوق \(\mathbb F_2\). إن التحويل الخطي الذي يرسل \((\lambda_1,\dots,\lambda_n)\) إلى xor السابق له صورة بُعدها \(r\)، ولذلك فإن نواته تحتوي
$$2^{n-r}$$
عنصرًا. كل عنصر في النواة يقابل مجموعة جزئية حاصل ضربها مربع كامل، بينما المتجه الصفري يقابل المجموعة الفارغة. ومن ثم نحصل على
$$C(a,b)=2^{n-r}-1.$$
وبذلك تنتهي جهة العد كلها بمجرد معرفة الرتبة.
لو استُخدم تمثيل كثيف لاحتجنا إلى إحداثي لكل عدد أولي حتى \(b\)، لكن معظم الأعداد لا تترك بعد حذف المربعات إلا عددًا قليلًا من العوامل الأولية ذات الأس الفردي. لهذا تكون الصفوف متناثرة بطبيعتها. وفوق \(\mathbb F_2\)، جمع الصفوف هو xor، وعلى مستوى مجموعات الدعم يصبح ذلك مجرد فرق متماثل.
لهذا تستطيع الخوارزمية العمل بقوائم مرتبة من فهارس الأعداد الأولية بدل مصفوفات بتية ضخمة. والأعداد التي هي مربعات كاملة أصلًا تعطي المتجه الصفري مباشرة، وهو ما ينسجم مع كون المجموعة الأحادية لها حلًا صحيحًا من البداية.
تعطي العناصر الستة في المجال مجموعات الدعم التالية:
$$5\mapsto\{5\},\quad 6\mapsto\{2,3\},\quad 7\mapsto\{7\},\quad 8\mapsto\{2\},\quad 9\mapsto\varnothing,\quad 10\mapsto\{2,5\}.$$
الصفوف الأربعة غير الصفرية الخاصة بـ \(5,6,7,8\) مستقلة خطيًا، بينما
$$\{2,5\}=\{2\}\oplus\{5\}.$$
إذن الرتبة هي \(r=4\). وبما أن \(n=6\)، فإن البعد الصفري يساوي \(6-4=2\)، ومن ثم
$$C(5,10)=2^2-1=3.$$
والمجموعات الجزئية غير الفارغة الثلاث التي تعطي مربعًا كاملاً هي \(\{9\}\) و\(\{5,8,10\}\) و\(\{5,8,9,10\}\)، وهذا يطابق قيمة الفحص التي تعتمدها الخوارزمية.
تبدأ تطبيقات C++ وPython وJava ببناء جدول لأصغر قاسم أولي حتى الحد الأعلى للمجال. هذا يجعل تحليل كل عدد بين \(a\) و\(b\) إلى عوامله الأولية سريعًا بما يكفي.
بعد ذلك يُحلَّل كل عنصر في المجال، وتُحفَظ فقط الأعداد الأولية التي يظهر لها أس فردي ضمن قائمة دعم متناثرة. وتكون القائمة مرتبة حسب فهرس العدد الأولي، ولذلك يمكن تنفيذ الاختزال بـ xor عبر دمج قائمتين مرتبتين وحذف العناصر التي تظهر مرتين.
أثناء الحذف الغاوسي فوق \(\mathbb F_2\)، تستخدم الخوارزمية أكبر فهرس أولي باقٍ في الصف الحالي بوصفه محورًا. إذا لم يكن هناك صف أساسي يملك هذا المحور بعد، يصبح الصف الحالي متجهًا أساسيًا جديدًا وتزداد الرتبة بمقدار \(1\). وإلا فيجري اختزال الصف الحالي بـ xor مع الصف الأساسي المخزّن حتى يختفي الصف بالكامل أو يحصل على محور جديد.
بعد الانتهاء من جميع الصفوف، تعرف الخوارزمية قيمة \(r\)، وتحسب \(n-r\)، ثم تعيد
$$2^{n-r}-1 \pmod{10^9+7}$$
باستخدام الأس السريع بترديد معياري.
لنكتب \(B=b\) و\(n=b-a+1\). إن بناء غربال أصغر قاسم أولي حتى \(B\) يكلف \(O(B\log\log B)\) زمنًا و\(O(B)\) ذاكرة. أما تحليل \(n\) عنصرًا من المجال اعتمادًا على هذا الجدول فهو قريب من الخطي عمليًا، ومتوسط رتبته \(O(n\log\log B)\).
تعتمد كلفة مرحلة الحذف على المجموع الكلي لأطوال قوائم الدعم المتناثرة وعلى مقدار الإلغاء الذي يحدث أثناء اختزالات xor. في هذه المسألة تكون البنية المتناثرة أصغر بكثير من مصفوفة كثيفة تملك عمودًا لكل عدد أولي حتى \(B\). لذلك يهيمن الغربال مع الحذف المتناثر على الكلفة الكلية، بينما تبقى الذاكرة في حدود \(O(B)\) للغربال مع ما يلزم لتخزين الأساس المتناثر.