Define
$$P(m,n)=\#\{ab:1\le a\le m,\ 1\le b\le n\},$$
the number of distinct values appearing in the \(m\times n\) multiplication table. The goal is to compute \(P(m,n)\) for very large \(n\) without generating all \(mn\) products. The checked implementations use the published values
$$P(64,64)=1263,\qquad P(12,345)=1998,\qquad P(32,10^{15})=13826382602124302.$$
The key idea is to assign every distinct product to exactly one row, then count how many column indices survive in that row after excluding all products that also belong to a larger row.
Take any product \(x\) that appears in the table, so \(x=ab\) for some \(1\le a\le m\) and \(1\le b\le n\). Let \(d\) be the largest divisor of \(x\) with \(d\le m\). Then \(x=d\,c\) for some integer \(c\), and because \(d\ge a\), we get
$$c=\frac{x}{d}\le \frac{x}{a}=b\le n.$$
So \(x\) still appears in row \(d\), and by construction no larger row index up to \(m\) divides it. This makes the owner row unique.
Let \(C_d\) be the number of column values \(c\in[1,n]\) such that \(x=d\,c\) is owned by row \(d\). Then
$$P(m,n)=\sum_{d=1}^{m} C_d.$$
Fix a row \(d\). A larger row \(e>d\) steals the product \(d\,c\) exactly when \(e\mid d\,c\). Write
$$g=\gcd(e,d),\qquad e=g\,e',\qquad d=g\,d',$$
with \(\gcd(e',d')=1\). Then
$$e\mid d\,c \iff g\,e' \mid g\,d'\,c \iff e' \mid d'\,c \iff e' \mid c,$$
because \(e'\) is coprime to \(d'\). Therefore the higher row \(e\) forbids exactly the columns divisible by
$$q_{e,d}=\frac{e}{\gcd(e,d)}.$$
If \(q_{e,d}>n\), it can be ignored, since no positive \(c\le n\) is divisible by it.
For a fixed \(d\), consider all values \(q_{e,d}\) with \(d<e\le m\). Duplicates do not matter. More importantly, if one forbidden divisor is a multiple of another, the larger one is redundant: whenever \(q_2\) is a multiple of \(q_1\), every \(c\) divisible by \(q_2\) is already divisible by \(q_1\).
So we keep only a minimal set under divisibility:
$$Q_d=\{q_1,q_2,\dots,q_t\}.$$
Now \(C_d\) is simply the number of integers \(c\le n\) that are not divisible by any element of \(Q_d\).
For any subset \(S\subseteq Q_d\), the integers \(c\le n\) divisible by every element of \(S\) are exactly the multiples of \(\operatorname{lcm}(S)\). Hence
$$C_d=\sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor,$$
with the convention \(\operatorname{lcm}(\emptyset)=1\). Written out, this is
$$C_d=n-\sum_i\left\lfloor\frac{n}{q_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{\operatorname{lcm}(q_i,q_j)}\right\rfloor-\cdots.$$
Combining this with the row decomposition gives the final formula
$$\boxed{P(m,n)=\sum_{d=1}^{m}\ \sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor.}$$
For \(d=1\), the higher rows are \(2\) and \(3\), so the forbidden divisors are \(2\) and \(3\). Thus
$$C_1=4-\left\lfloor\frac{4}{2}\right\rfloor-\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{4}{6}\right\rfloor=4-2-1+0=1.$$
For \(d=2\), only row \(3\) is higher, and it forbids multiples of \(3\). Hence
$$C_2=4-\left\lfloor\frac{4}{3}\right\rfloor=3.$$
For \(d=3\), there is no higher row, so \(Q_3=\emptyset\) and \(C_3=4\).
Therefore
$$P(3,4)=C_1+C_2+C_3=1+3+4=8.$$
The eight distinct products are \(\{1,2,3,4,6,8,9,12\}\).
The C++, Python, and Java implementations all follow the same row-by-row counting strategy. For each row \(d\), the implementation generates the values \(e/\gcd(e,d)\) for all larger rows \(e\), discards values greater than \(n\), removes duplicates, and then removes any value that is a multiple of an already kept smaller divisor.
After that reduction, the implementation performs recursive inclusion-exclusion over the remaining forbidden divisors. At each recursive step it updates the running least common multiple using a gcd-based formula, and it immediately prunes the branch if the lcm would exceed \(n\) or overflow the allowed bound. The row counts are then summed to obtain \(P(m,n)\).
The C++ version also takes advantage of the fact that different rows are independent, so it can evaluate row contributions in parallel. The checked code further validates the method against the published checkpoints above and against small direct enumerations.
Let \(t_d=|Q_d|\). Building the raw forbidden list for row \(d\) takes \(O(m-d)\) gcd computations, followed by sorting and duplicate removal. The minimal-divisor filtering is quadratic in the size of that provisional list in the worst case, but \(m\) is small in the actual problem.
The inclusion-exclusion stage depends on how many subset lcms remain at most \(n\). In the worst case it is \(O(2^{t_d})\) for row \(d\), but the minimal-divisor reduction and the lcm cutoff prune many branches in practice. Overall, the method is dramatically smaller than generating all \(mn\) products, and its memory usage is modest: essentially one row's forbidden-divisor list plus the recursion stack.
Definiere
$$P(m,n)=\#\{ab:1\le a\le m,\ 1\le b\le n\},$$
also die Anzahl verschiedener Werte in der \(m\times n\)-Multiplikationstafel. Gesucht ist eine Methode, die \(P(m,n)\) auch für sehr große \(n\) berechnet, ohne alle \(mn\) Produkte zu erzeugen. Die geprüften Implementierungen verwenden dabei die veröffentlichten Kontrollwerte
$$P(64,64)=1263,\qquad P(12,345)=1998,\qquad P(32,10^{15})=13826382602124302.$$
Die zentrale Idee besteht darin, jedes verschiedene Produkt genau einer Zeile zuzuordnen. Danach zählt man für jede Zeile nur noch die Spaltenindizes, die nicht schon durch eine größere Zeile erklärt werden.
Sei \(x\) ein Produkt aus der Tabelle, also \(x=ab\) mit \(1\le a\le m\) und \(1\le b\le n\). Wähle nun den größten Teiler \(d\) von \(x\) mit \(d\le m\). Dann gilt \(x=d\,c\) für ein ganzzahliges \(c\), und weil \(d\ge a\), folgt
$$c=\frac{x}{d}\le \frac{x}{a}=b\le n.$$
Damit erscheint \(x\) weiterhin in Zeile \(d\), und per Konstruktion gibt es keine größere Zeile bis \(m\), die \(x\) ebenfalls teilt. Die Besitzerzeile ist also eindeutig.
Bezeichne mit \(C_d\) die Anzahl der Spaltenwerte \(c\in[1,n]\), für die \(x=d\,c\) der Zeile \(d\) gehört. Dann ist
$$P(m,n)=\sum_{d=1}^{m} C_d.$$
Fixiere eine Zeile \(d\). Eine größere Zeile \(e>d\) übernimmt das Produkt \(d\,c\) genau dann, wenn \(e\mid d\,c\). Schreibe
$$g=\gcd(e,d),\qquad e=g\,e',\qquad d=g\,d',$$
mit \(\gcd(e',d')=1\). Dann erhält man
$$e\mid d\,c \iff g\,e' \mid g\,d'\,c \iff e' \mid d'\,c \iff e' \mid c,$$
weil \(e'\) und \(d'\) teilerfremd sind. Daher verbietet die größere Zeile \(e\) genau die Spalten, die durch
$$q_{e,d}=\frac{e}{\gcd(e,d)}$$
teilbar sind. Falls \(q_{e,d}>n\), ist dieser Wert irrelevant, denn dann gibt es kein positives \(c\le n\), das dadurch teilbar wäre.
Für festes \(d\) betrachtet man alle Werte \(q_{e,d}\) mit \(d<e\le m\). Doppelte Werte sind bedeutungslos. Noch wichtiger ist: Ist ein verbotener Teiler ein Vielfaches eines kleineren verbotenen Teilers, dann ist er redundant. Wenn \(q_2\) ein Vielfaches von \(q_1\) ist, dann ist jedes durch \(q_2\) teilbare \(c\) bereits durch \(q_1\) teilbar.
Deshalb genügt eine minimale Menge bezüglich Teilbarkeit:
$$Q_d=\{q_1,q_2,\dots,q_t\}.$$
Nun ist \(C_d\) genau die Anzahl der Zahlen \(c\le n\), die durch kein Element von \(Q_d\) teilbar sind.
Für jede Teilmenge \(S\subseteq Q_d\) sind die Zahlen \(c\le n\), die durch alle Elemente von \(S\) teilbar sind, genau die Vielfachen von \(\operatorname{lcm}(S)\). Also gilt
$$C_d=\sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor,$$
wobei \(\operatorname{lcm}(\emptyset)=1\) gesetzt wird. Ausgeschrieben ist das
$$C_d=n-\sum_i\left\lfloor\frac{n}{q_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{\operatorname{lcm}(q_i,q_j)}\right\rfloor-\cdots.$$
Zusammen mit der Zeilensumme ergibt sich damit die Endformel
$$\boxed{P(m,n)=\sum_{d=1}^{m}\ \sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor.}$$
Für \(d=1\) sind die größeren Zeilen \(2\) und \(3\), also lauten die verbotenen Teiler \(2\) und \(3\). Damit
$$C_1=4-\left\lfloor\frac{4}{2}\right\rfloor-\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{4}{6}\right\rfloor=4-2-1+0=1.$$
Für \(d=2\) gibt es nur die größere Zeile \(3\), die Vielfache von \(3\) verbietet. Also
$$C_2=4-\left\lfloor\frac{4}{3}\right\rfloor=3.$$
Für \(d=3\) existiert keine größere Zeile, also ist \(Q_3=\emptyset\) und \(C_3=4\).
Folglich
$$P(3,4)=C_1+C_2+C_3=1+3+4=8.$$
Die acht verschiedenen Produkte sind \(\{1,2,3,4,6,8,9,12\}\).
Die C++-, Python- und Java-Implementierungen folgen alle derselben zeilenweisen Zählstrategie. Für jede Zeile \(d\) erzeugt die Implementierung die Werte \(e/\gcd(e,d)\) aller größeren Zeilen \(e\), verwirft Werte größer als \(n\), entfernt Duplikate und streicht anschließend jede Zahl, die ein Vielfaches eines bereits behaltenen kleineren Teilers ist.
Danach führt die Implementierung eine rekursive Inklusion-Exklusion über die verbleibenden verbotenen Teiler aus. In jedem Rekursionsschritt wird das aktuelle kgV mithilfe einer ggT-basierten Formel aktualisiert; sobald das kgV den Wert \(n\) überschreiten würde oder die Schranke nicht mehr sicher einhält, wird der entsprechende Ast sofort abgeschnitten. Anschließend werden alle Zeilenbeiträge addiert.
Die C++-Version nutzt außerdem aus, dass die Zeilen unabhängig sind, und kann sie parallel auswerten. Der geprüfte Code verifiziert die Methode zusätzlich mit den veröffentlichten Kontrollwerten und mit kleinen direkten Auszählungen.
Sei \(t_d=|Q_d|\). Das Aufbauen der rohen Verbotsliste für Zeile \(d\) benötigt \(O(m-d)\) ggT-Berechnungen, danach Sortierung und Duplikatentfernung. Das Filtern auf minimale Teiler ist im schlechtesten Fall quadratisch in der Größe dieser Zwischenliste, wobei \(m\) im eigentlichen Problem klein ist.
Die Inklusion-Exklusion hängt davon ab, wie viele Teilmengen-kgV-Werte höchstens \(n\) bleiben. Im schlechtesten Fall kostet Zeile \(d\) also \(O(2^{t_d})\), praktisch aber deutlich weniger, weil die Minimalisierung und der kgV-Abbruch viele Äste früh eliminieren. Insgesamt ist das Verfahren daher viel kleiner als eine vollständige Erzeugung aller \(mn\) Produkte und benötigt nur wenig Speicher: im Wesentlichen die Verbotsliste einer Zeile plus Rekursionsstack.
Şunu tanımlayalım:
$$P(m,n)=\#\{ab:1\le a\le m,\ 1\le b\le n\},$$
yani \(m\times n\) çarpım tablosunda görülen farklı değerlerin sayısı. Amaç, özellikle \(n\) çok büyükken, tüm \(mn\) çarpımı üretmeden bu değeri hesaplamaktır. Doğrulama için kullanılan yayımlanmış kontrol değerleri şunlardır:
$$P(64,64)=1263,\qquad P(12,345)=1998,\qquad P(32,10^{15})=13826382602124302.$$
Ana fikir, her farklı çarpımı tam olarak bir satıra atamak ve sonra o satırda daha büyük satırlara ait olan sütunları elemekten ibarettir.
Tabloda görünen herhangi bir \(x\) değeri için \(x=ab\) yazabiliriz; burada \(1\le a\le m\) ve \(1\le b\le n\). Şimdi \(x\)'in \(m\)'yi aşmayan en büyük böleni \(d\) olsun. O zaman \(x=d\,c\) biçiminde yazılır. Üstelik \(d\ge a\) olduğundan
$$c=\frac{x}{d}\le \frac{x}{a}=b\le n$$
elde edilir. Yani \(x\) değeri satır \(d\)'de de görünür ve tanım gereği \(m\)'ye kadar olan daha büyük hiçbir satır indeksi \(x\)'i bölmez. Böylece sahip satır tektir.
Satır \(d\)'ye ait sütun sayısını \(C_d\) ile gösterelim. O zaman
$$P(m,n)=\sum_{d=1}^{m} C_d$$
olur.
Şimdi bir \(d\) satırını sabitleyelim. Daha büyük bir \(e>d\) satırı, \(d\,c\) çarpımını ancak \(e\mid d\,c\) ise sahiplenebilir. Şunu yazalım:
$$g=\gcd(e,d),\qquad e=g\,e',\qquad d=g\,d',$$
ve burada \(\gcd(e',d')=1\) olsun. Bu durumda
$$e\mid d\,c \iff g\,e' \mid g\,d'\,c \iff e' \mid d'\,c \iff e' \mid c,$$
çünkü \(e'\) ile \(d'\) aralarında asaldır. Demek ki \(e\) satırının yasakladığı sütunlar tam olarak
$$q_{e,d}=\frac{e}{\gcd(e,d)}$$
sayısına bölünen sütunlardır. Eğer \(q_{e,d}>n\) ise bu yasak etkisizdir; çünkü \(1\) ile \(n\) arasında böyle bir kat yoktur.
Sabit \(d\) için tüm \(q_{e,d}\) değerlerine bakalım. Tekrar eden değerler gereksizdir. Daha önemlisi, bir yasak bölen başka bir yasak bölenin katıysa, büyük olan fazlalıktır. Çünkü \(q_2\), \(q_1\)'in katıysa \(q_2\)'ye bölünen her \(c\), zaten \(q_1\)'e de bölünür.
Bu yüzden bölünebilme açısından minimal bir küme yeterlidir:
$$Q_d=\{q_1,q_2,\dots,q_t\}.$$
Artık \(C_d\), \(Q_d\)'deki hiçbir elemana bölünmeyen \(c\le n\) sayısıdır.
\(S\subseteq Q_d\) herhangi bir altküme olsun. \(S\)'deki tüm bölenlere birden bölünen \(c\le n\) sayıları tam olarak \(\operatorname{lcm}(S)\)'nin katlarıdır. Dolayısıyla
$$C_d=\sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor,$$
ve burada \(\operatorname{lcm}(\emptyset)=1\) alınır. Açılmış haliyle
$$C_d=n-\sum_i\left\lfloor\frac{n}{q_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{\operatorname{lcm}(q_i,q_j)}\right\rfloor-\cdots.$$
Böylece toplam sonuç
$$\boxed{P(m,n)=\sum_{d=1}^{m}\ \sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor.}$$
\(d=1\) için daha büyük satırlar \(2\) ve \(3\) olduğundan yasak bölenler \(2\) ve \(3\)'tür. Bu nedenle
$$C_1=4-\left\lfloor\frac{4}{2}\right\rfloor-\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{4}{6}\right\rfloor=4-2-1+0=1.$$
\(d=2\) için yalnızca \(3\) satırı daha büyüktür ve \(3\)'ün katlarını yasaklar. Dolayısıyla
$$C_2=4-\left\lfloor\frac{4}{3}\right\rfloor=3.$$
\(d=3\) için daha büyük satır yoktur; yani \(Q_3=\emptyset\) ve \(C_3=4\).
Sonuç olarak
$$P(3,4)=C_1+C_2+C_3=1+3+4=8.$$
Bu tabloda farklı çarpımlar \(\{1,2,3,4,6,8,9,12\}\) kümesidir.
C++, Python ve Java uygulamaları aynı satır bazlı sayım fikrini izler. Her \(d\) satırı için uygulama, daha büyük satırlardan gelen \(e/\gcd(e,d)\) değerlerini üretir, \(n\)'den büyük olanları atar, tekrarları kaldırır ve sonra elde tutulmuş daha küçük bir bölenin katı olan her değeri siler.
Daha sonra kalan yasak bölenler üzerinde özyinelemeli bir dahil et-çıkar yürütülür. Her adımda güncel EKOK, EBOB tabanlı bir formülle yenilenir; EKOK değeri \(n\)'yi aşarsa ya da güvenli sınırı aşacaksa dal hemen budanır. Son aşamada tüm satır katkıları toplanarak \(P(m,n)\) elde edilir.
C++ sürümü, satırların birbirinden bağımsız olmasını kullanarak satır katkılarını paralel de hesaplayabilir. Denetlenmiş kod ayrıca yukarıdaki yayımlanmış kontrol değerlerini ve birkaç küçük doğrudan sayımı doğrulama amacıyla kullanır.
\(t_d=|Q_d|\) olsun. \(d\) satırı için ham yasak listesini kurmak \(O(m-d)\) adet EBOB hesabı gerektirir; ardından sıralama ve tekrar temizliği gelir. Minimal bölen süzmesi, en kötü durumda ara listenin boyutunda karesel olabilir; fakat asıl problemde \(m\) küçüktür.
Dahil et-çıkar kısmının maliyeti, EKOK'u hâlâ \(n\)'yi aşmayan altküme sayısına bağlıdır. En kötü durumda satır başına \(O(2^{t_d})\) olabilir; ancak minimalleştirme ve EKOK kesmesi pratikte çok sayıda dalı erken yok eder. Bu yüzden yöntem, tüm \(mn\) çarpımı üretmeye göre çok daha küçüktür ve bellek kullanımı da düşüktür: esas olarak tek satırın yasak listesi ile özyineleme yığını kadar.
Definimos
$$P(m,n)=\#\{ab:1\le a\le m,\ 1\le b\le n\},$$
es decir, la cantidad de valores distintos que aparecen en la tabla de multiplicar \(m\times n\). El objetivo es calcular \(P(m,n)\) incluso cuando \(n\) es enorme, sin construir explícitamente los \(mn\) productos. Las implementaciones verificadas usan como referencias
$$P(64,64)=1263,\qquad P(12,345)=1998,\qquad P(32,10^{15})=13826382602124302.$$
La idea principal es asignar cada producto distinto a una sola fila. Después, para cada fila, solo hay que contar qué columnas sobreviven una vez eliminados los productos que también pertenecen a alguna fila mayor.
Tomemos un producto \(x\) presente en la tabla, de modo que \(x=ab\) con \(1\le a\le m\) y \(1\le b\le n\). Sea \(d\) el mayor divisor de \(x\) tal que \(d\le m\). Entonces \(x=d\,c\) para cierto entero \(c\), y como \(d\ge a\), se cumple
$$c=\frac{x}{d}\le \frac{x}{a}=b\le n.$$
Por lo tanto, \(x\) sigue apareciendo en la fila \(d\), y por construcción ninguna fila mayor hasta \(m\) lo divide. Así, la fila propietaria es única.
Si \(C_d\) denota el número de columnas \(c\in[1,n]\) tales que \(x=d\,c\) pertenece a la fila \(d\), entonces
$$P(m,n)=\sum_{d=1}^{m} C_d.$$
Fijemos una fila \(d\). Una fila mayor \(e>d\) le quita el producto \(d\,c\) exactamente cuando \(e\mid d\,c\). Escribamos
$$g=\gcd(e,d),\qquad e=g\,e',\qquad d=g\,d',$$
con \(\gcd(e',d')=1\). Entonces
$$e\mid d\,c \iff g\,e' \mid g\,d'\,c \iff e' \mid d'\,c \iff e' \mid c,$$
porque \(e'\) y \(d'\) son coprimos. Por eso la fila superior \(e\) prohíbe exactamente las columnas divisibles por
$$q_{e,d}=\frac{e}{\gcd(e,d)}.$$
Si \(q_{e,d}>n\), puede ignorarse, ya que ningún \(c\le n\) positivo es múltiplo suyo.
Para un \(d\) fijo, consideramos todos los valores \(q_{e,d}\) con \(d<e\le m\). Los repetidos no aportan nada. Además, si un divisor prohibido es múltiplo de otro más pequeño, el grande es redundante: todo \(c\) divisible por \(q_2\) ya es divisible por \(q_1\) cuando \(q_2\) es múltiplo de \(q_1\).
Por tanto basta con una familia mínima respecto de la divisibilidad:
$$Q_d=\{q_1,q_2,\dots,q_t\}.$$
Ahora \(C_d\) es exactamente el número de enteros \(c\le n\) que no son divisibles por ningún elemento de \(Q_d\).
Para cualquier subconjunto \(S\subseteq Q_d\), los enteros \(c\le n\) divisibles por todos los elementos de \(S\) son exactamente los múltiplos de \(\operatorname{lcm}(S)\). Luego
$$C_d=\sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor,$$
donde \(\operatorname{lcm}(\emptyset)=1\). Desarrollado, esto es
$$C_d=n-\sum_i\left\lfloor\frac{n}{q_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{\operatorname{lcm}(q_i,q_j)}\right\rfloor-\cdots.$$
Combinando esto con la descomposición por filas obtenemos
$$\boxed{P(m,n)=\sum_{d=1}^{m}\ \sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor.}$$
Para \(d=1\), las filas superiores son \(2\) y \(3\), así que los divisores prohibidos son \(2\) y \(3\). Por tanto
$$C_1=4-\left\lfloor\frac{4}{2}\right\rfloor-\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{4}{6}\right\rfloor=4-2-1+0=1.$$
Para \(d=2\), solo la fila \(3\) es mayor y prohíbe los múltiplos de \(3\). Entonces
$$C_2=4-\left\lfloor\frac{4}{3}\right\rfloor=3.$$
Para \(d=3\), no existe fila mayor, luego \(Q_3=\emptyset\) y \(C_3=4\).
Así pues
$$P(3,4)=C_1+C_2+C_3=1+3+4=8.$$
Los ocho productos distintos son \(\{1,2,3,4,6,8,9,12\}\).
Las implementaciones en C++, Python y Java siguen la misma estrategia de conteo por filas. Para cada fila \(d\), la implementación genera los valores \(e/\gcd(e,d)\) de todas las filas superiores \(e\), descarta los que superan \(n\), elimina duplicados y después suprime cualquier valor que sea múltiplo de un divisor menor ya conservado.
Después ejecuta una inclusión-exclusión recursiva sobre los divisores prohibidos restantes. En cada paso actualiza el mínimo común múltiplo mediante una fórmula basada en el gcd y corta la rama en cuanto ese mcm superaría \(n\) o rebasaría el límite seguro. Finalmente suma las contribuciones de todas las filas para obtener \(P(m,n)\).
La versión en C++ además aprovecha que las filas son independientes y puede evaluarlas en paralelo. El código verificado también contrasta el método con los valores de referencia anteriores y con algunos conteos directos pequeños.
Sea \(t_d=|Q_d|\). Construir la lista bruta de divisores prohibidos para la fila \(d\) requiere \(O(m-d)\) cálculos de gcd, seguidos de ordenación y eliminación de repetidos. El filtrado para dejar solo divisores mínimos puede ser cuadrático en el tamaño de esa lista provisional en el peor caso, aunque \(m\) es pequeño en el problema real.
La fase de inclusión-exclusión depende de cuántos mcm de subconjuntos sigan siendo como mucho \(n\). En el peor caso, la fila \(d\) cuesta \(O(2^{t_d})\), pero en la práctica es mucho menor porque la reducción a divisores mínimos y el corte por mcm eliminan muchas ramas. En conjunto, el método es muchísimo más barato que generar los \(mn\) productos y usa poca memoria: básicamente la lista de divisores prohibidos de una fila y la pila recursiva.
定义
$$P(m,n)=\#\{ab:1\le a\le m,\ 1\le b\le n\},$$
也就是 \(m\times n\) 乘法表中不同乘积的个数。目标是在 \(n\) 很大的情况下，仍然能够计算 \(P(m,n)\)，而不是把全部 \(mn\) 个乘积显式生成出来。经过校验的实现会用到下列公开检查值：
$$P(64,64)=1263,\qquad P(12,345)=1998,\qquad P(32,10^{15})=13826382602124302.$$
核心思路不是直接数乘积，而是先给每个不同的乘积分配一个唯一的“归属行”，然后分别计算每一行中哪些列索引仍然有效，没有被更大的行重复覆盖。
设 \(x\) 是乘法表中出现的一个乘积，因此可以写成 \(x=ab\)，其中 \(1\le a\le m\)，\(1\le b\le n\)。现在取 \(x\) 的所有不超过 \(m\) 的因子中最大的那个，记为 \(d\)。于是 \(x=d\,c\) 对某个整数 \(c\) 成立，而且由于 \(d\ge a\)，便有
$$c=\frac{x}{d}\le \frac{x}{a}=b\le n.$$
这说明 \(x\) 仍然出现在第 \(d\) 行中；同时因为 \(d\) 被定义为最大的此类因子，所以在 \(1\) 到 \(m\) 范围内不存在更大的行号还能整除 \(x\)。因此每个不同乘积都恰好归属于一行。
记 \(C_d\) 为属于第 \(d\) 行的列数，也就是满足 \(x=d\,c\) 且该乘积归属于第 \(d\) 行的 \(c\in[1,n]\) 的个数，则
$$P(m,n)=\sum_{d=1}^{m} C_d.$$
固定某一行 \(d\)。如果某个更大的行 \(e>d\) 也能表示同一个乘积 \(d\,c\)，那么必然有 \(e\mid d\,c\)。设
$$g=\gcd(e,d),\qquad e=g\,e',\qquad d=g\,d',$$
其中 \(\gcd(e',d')=1\)。那么
$$e\mid d\,c \iff g\,e' \mid g\,d'\,c \iff e' \mid d'\,c \iff e' \mid c,$$
最后一步成立，是因为 \(e'\) 与 \(d'\) 互素。于是，更大的行 \(e\) 对第 \(d\) 行造成的唯一影响，就是禁止那些能被
$$q_{e,d}=\frac{e}{\gcd(e,d)}$$
整除的列值 \(c\)。如果 \(q_{e,d}>n\)，那它可以直接忽略，因为 \(1\le c\le n\) 中根本没有这样的倍数。
对于固定的 \(d\)，我们会得到所有 \(d<e\le m\) 对应的 \(q_{e,d}\)。重复值当然没有必要保留。更重要的是，如果某个禁止除数是另一个更小禁止除数的倍数，那么这个较大的除数就是冗余的。原因很简单：若 \(q_2\) 是 \(q_1\) 的倍数，则任何被 \(q_2\) 整除的 \(c\) 一定也被 \(q_1\) 整除。
因此只需要保留按整除关系极小的那一批数：
$$Q_d=\{q_1,q_2,\dots,q_t\}.$$
这样一来，\(C_d\) 就等于所有 \(c\le n\) 中，不被 \(Q_d\) 任何元素整除的那些整数的个数。
若 \(S\subseteq Q_d\) 是任意一个子集，那么同时被 \(S\) 中所有元素整除的 \(c\le n\)，恰好就是 \(\operatorname{lcm}(S)\) 的倍数。因此有
$$C_d=\sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor,$$
并约定 \(\operatorname{lcm}(\emptyset)=1\)。把它展开写出来，就是
$$C_d=n-\sum_i\left\lfloor\frac{n}{q_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{\operatorname{lcm}(q_i,q_j)}\right\rfloor-\cdots.$$
和按行求和结合起来，就得到最终公式
$$\boxed{P(m,n)=\sum_{d=1}^{m}\ \sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor.}$$
当 \(d=1\) 时，更大的行是 \(2\) 和 \(3\)，因此禁止除数为 \(2\) 和 \(3\)。于是
$$C_1=4-\left\lfloor\frac{4}{2}\right\rfloor-\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{4}{6}\right\rfloor=4-2-1+0=1.$$
当 \(d=2\) 时，只剩更大的行 \(3\)，它禁止的是 \(3\) 的倍数，所以
$$C_2=4-\left\lfloor\frac{4}{3}\right\rfloor=3.$$
当 \(d=3\) 时，已经没有更大的行，因此 \(Q_3=\emptyset\)，从而 \(C_3=4\)。
因此
$$P(3,4)=C_1+C_2+C_3=1+3+4=8.$$
对应的八个不同乘积是 \(\{1,2,3,4,6,8,9,12\}\)。这个小例子完整展示了“按行归属 + 容斥计数”的结构。
C++、Python 和 Java 实现都遵循同一套逐行计数方案。对于每一行 \(d\)，实现先枚举所有更大的行 \(e\)，计算 \(e/\gcd(e,d)\)，丢弃大于 \(n\) 的值，去重，然后继续删除那些已经是更小保留值倍数的元素，只留下真正需要参与容斥的极小禁止集合。
接下来，实现对这个缩减后的禁止集合做递归容斥。每进入一层递归，就用基于 gcd 的公式更新当前最小公倍数；如果新的最小公倍数会超过 \(n\)，或者会越过安全上界，就立刻剪枝，不再深入该分支。所有子集贡献累加后得到当前行的 \(C_d\)，再对所有行求和。
C++ 版本还利用了各行相互独立这一点，可以把不同行的贡献并行计算。经过检查的代码还会将结果与上面的公开检查值比较，并在几个很小的输入上与直接枚举结果交叉验证。
设 \(t_d=|Q_d|\)。对第 \(d\) 行来说，构造原始禁止列表需要 \(O(m-d)\) 次 gcd 计算，之后还有排序与去重。把列表进一步压缩成极小禁止集合，最坏情况下会在该临时列表大小上呈二次复杂度，不过在实际题目里 \(m\) 本身很小。
容斥部分的代价取决于有多少个子集的最小公倍数仍然不超过 \(n\)。最坏情况下，第 \(d\) 行可能需要 \(O(2^{t_d})\) 个状态；但由于先做了极小化，再加上 lcm 超界就立即剪枝，实际探索的状态数通常远小于这个上界。整体而言，这个方法远远优于直接生成全部 \(mn\) 个乘积，内存占用也很温和，主要就是一行的禁止列表和递归栈。
Определим
$$P(m,n)=\#\{ab:1\le a\le m,\ 1\le b\le n\},$$
то есть число различных значений в таблице умножения \(m\times n\). Нужно вычислять \(P(m,n)\) даже при очень большом \(n\), не порождая все \(mn\) произведений напрямую. Проверенные реализации используют опубликованные контрольные значения
$$P(64,64)=1263,\qquad P(12,345)=1998,\qquad P(32,10^{15})=13826382602124302.$$
Главная идея состоит в том, чтобы приписать каждое различное произведение ровно одной строке. После этого для каждой строки остаётся посчитать только те столбцы, которые не перехватываются никакой более крупной строкой.
Пусть \(x\) встречается в таблице, то есть \(x=ab\) для некоторых \(1\le a\le m\) и \(1\le b\le n\). Возьмём наибольший делитель \(d\) числа \(x\), удовлетворяющий условию \(d\le m\). Тогда \(x=d\,c\) для некоторого целого \(c\), причём из \(d\ge a\) следует
$$c=\frac{x}{d}\le \frac{x}{a}=b\le n.$$
Значит, \(x\) всё ещё присутствует в строке \(d\), а по определению никакая большая строка до \(m\) уже не делит это число. Следовательно, строка-владелец определена однозначно.
Обозначим через \(C_d\) количество столбцов \(c\in[1,n]\), для которых произведение \(x=d\,c\) принадлежит строке \(d\). Тогда
$$P(m,n)=\sum_{d=1}^{m} C_d.$$
Зафиксируем строку \(d\). Более крупная строка \(e>d\) отбирает произведение \(d\,c\) ровно тогда, когда \(e\mid d\,c\). Пусть
$$g=\gcd(e,d),\qquad e=g\,e',\qquad d=g\,d',$$
где \(\gcd(e',d')=1\). Тогда
$$e\mid d\,c \iff g\,e' \mid g\,d'\,c \iff e' \mid d'\,c \iff e' \mid c,$$
потому что \(e'\) и \(d'\) взаимно просты. Значит, строка \(e\) запрещает ровно те столбцы, которые делятся на
$$q_{e,d}=\frac{e}{\gcd(e,d)}.$$
Если \(q_{e,d}>n\), этим ограничением можно пренебречь, так как среди \(1\le c\le n\) нет положительных кратных такого числа.
Для фиксированного \(d\) рассмотрим все значения \(q_{e,d}\) при \(d<e\le m\). Повторы не нужны. Ещё важнее то, что если один запрещённый делитель кратен другому, то больший делитель избыточен: всякое \(c\), делящееся на \(q_2\), уже делится и на \(q_1\), когда \(q_2\) кратно \(q_1\).
Поэтому достаточно сохранить минимальный по делимости набор
$$Q_d=\{q_1,q_2,\dots,q_t\}.$$
Теперь \(C_d\) равно числу целых \(c\le n\), не делящихся ни на один элемент множества \(Q_d\).
Для любого подмножества \(S\subseteq Q_d\) числа \(c\le n\), делящиеся на все элементы \(S\), в точности являются кратными \(\operatorname{lcm}(S)\). Поэтому
$$C_d=\sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor,$$
где по соглашению \(\operatorname{lcm}(\emptyset)=1\). В развернутом виде это
$$C_d=n-\sum_i\left\lfloor\frac{n}{q_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{\operatorname{lcm}(q_i,q_j)}\right\rfloor-\cdots.$$
Совмещая это с суммированием по строкам, получаем формулу
$$\boxed{P(m,n)=\sum_{d=1}^{m}\ \sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor.}$$
Для \(d=1\) более крупные строки равны \(2\) и \(3\), поэтому запрещённые делители равны \(2\) и \(3\). Тогда
$$C_1=4-\left\lfloor\frac{4}{2}\right\rfloor-\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{4}{6}\right\rfloor=4-2-1+0=1.$$
Для \(d=2\) остаётся только строка \(3\), запрещающая кратные \(3\). Следовательно,
$$C_2=4-\left\lfloor\frac{4}{3}\right\rfloor=3.$$
Для \(d=3\) более крупных строк нет, значит \(Q_3=\emptyset\) и \(C_3=4\).
Итак,
$$P(3,4)=C_1+C_2+C_3=1+3+4=8.$$
Восемь различных произведений здесь равны \(\{1,2,3,4,6,8,9,12\}\).
Реализации на C++, Python и Java используют одну и ту же построчную схему подсчёта. Для каждой строки \(d\) реализация строит значения \(e/\gcd(e,d)\) для всех больших строк \(e\), отбрасывает числа больше \(n\), удаляет повторы, а затем исключает каждое значение, которое является кратным уже сохранённого меньшего делителя.
После этого выполняется рекурсивное включение-исключение по оставшемуся набору запрещённых делителей. На каждом шаге текущий НОК обновляется через формулу с gcd; если новый НОК превысил бы \(n\) или безопасную границу, ветвь немедленно отсекется. Затем вклады всех строк складываются, и получается \(P(m,n)\).
Версия на C++ дополнительно использует независимость строк и может вычислять их параллельно. Проверенный код также сравнивает результаты с контрольными значениями выше и с несколькими малыми случаями, где ответ можно получить прямым перебором.
Пусть \(t_d=|Q_d|\). Построение сырого списка запрещённых делителей для строки \(d\) требует \(O(m-d)\) вычислений gcd, после чего идут сортировка и удаление повторов. Фильтрация до минимального набора в худшем случае квадратична по размеру промежуточного списка, хотя в самой задаче \(m\) невелико.
Стоимость включения-исключения определяется числом подмножеств, чьи НОК всё ещё не превосходят \(n\). В худшем случае для строки \(d\) это \(O(2^{t_d})\), но на практике существенно меньше благодаря удалению избыточных делителей и ранней отсечке по НОК. В целом метод несравнимо дешевле полного построения всех \(mn\) произведений и требует мало памяти: по сути, список запрещённых делителей одной строки и стек рекурсии.
نعرّف
$$P(m,n)=\#\{ab:1\le a\le m,\ 1\le b\le n\},$$
وهو عدد القيم المختلفة التي تظهر في جدول الضرب \(m\times n\). المطلوب هو حساب \(P(m,n)\) حتى عندما تكون \(n\) كبيرة جدًا، من دون توليد جميع القيم \(mn\) صراحةً. وتستخدم التطبيقات المتحقَّق منها القيم المرجعية المنشورة
$$P(64,64)=1263,\qquad P(12,345)=1998,\qquad P(32,10^{15})=13826382602124302.$$
الفكرة الأساسية هي أن نُسنِد كل حاصل ضرب مختلف إلى صف واحد فقط، ثم نعدّ في كل صف الأعمدة التي تبقى بعد استبعاد كل ما يمكن أن ينتمي أيضًا إلى صف أكبر.
خذ أي قيمة \(x\) تظهر في الجدول، أي \(x=ab\) لبعض \(1\le a\le m\) و\(1\le b\le n\). ولتكن \(d\) أكبر قاسم لـ \(x\) بحيث \(d\le m\). عندئذٍ نستطيع كتابة \(x=d\,c\) لعدد صحيح \(c\)، وبما أن \(d\ge a\) فإن
$$c=\frac{x}{d}\le \frac{x}{a}=b\le n.$$
إذًا ما زالت القيمة \(x\) تظهر في الصف \(d\)، وبالتعريف لا يوجد صف أكبر من \(d\) وحتى \(m\) يقسم \(x\). لهذا يكون صف الملكية محددًا على نحو وحيد.
إذا رمزنا بـ \(C_d\) إلى عدد قيم الأعمدة \(c\in[1,n]\) التي يكون فيها \(x=d\,c\) مملوكًا للصف \(d\)، فسنحصل على
$$P(m,n)=\sum_{d=1}^{m} C_d.$$
ثبّت صفًا معينًا \(d\). إن الصف الأكبر \(e>d\) يسحب القيمة \(d\,c\) من الصف \(d\) إذا وفقط إذا كان \(e\mid d\,c\). اكتب
$$g=\gcd(e,d),\qquad e=g\,e',\qquad d=g\,d',$$
بحيث \(\gcd(e',d')=1\). عندئذٍ
$$e\mid d\,c \iff g\,e' \mid g\,d'\,c \iff e' \mid d'\,c \iff e' \mid c,$$
لأن \(e'\) و\(d'\) أوليان فيما بينهما. لذلك فإن الصف \(e\) يمنع بالضبط الأعمدة القابلة للقسمة على
$$q_{e,d}=\frac{e}{\gcd(e,d)}.$$
وإذا كان \(q_{e,d}>n\) فيمكن تجاهله، لأنه لا يوجد \(c\le n\) موجب يكون من مضاعفاته.
لصف ثابت \(d\)، ننظر إلى جميع القيم \(q_{e,d}\) عندما \(d<e\le m\). القيم المكررة لا تضيف شيئًا. والأهم من ذلك أنه إذا كان قاسم ممنوع ما مضاعفًا لقاسم ممنوع أصغر منه، فإن الأكبر يصبح زائدًا عن الحاجة: فكل \(c\) يقبل القسمة على \(q_2\) سيكون أصلًا قابلًا للقسمة على \(q_1\) إذا كان \(q_2\) مضاعفًا لـ \(q_1\).
لهذا يكفي الاحتفاظ بمجموعة صغرى بالنسبة إلى علاقة القسمة:
$$Q_d=\{q_1,q_2,\dots,q_t\}.$$
وعندها يصبح \(C_d\) هو عدد الأعداد \(c\le n\) التي لا تقبل القسمة على أي عنصر من عناصر \(Q_d\).
لكل مجموعة جزئية \(S\subseteq Q_d\)، فإن الأعداد \(c\le n\) القابلة للقسمة على جميع عناصر \(S\) هي بالضبط مضاعفات \(\operatorname{lcm}(S)\). ولذلك
$$C_d=\sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor,$$
مع الاتفاق على أن \(\operatorname{lcm}(\emptyset)=1\). وإذا كُتبت الصيغة بشكل مفصّل فهي
$$C_d=n-\sum_i\left\lfloor\frac{n}{q_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{\operatorname{lcm}(q_i,q_j)}\right\rfloor-\cdots.$$
وبضم ذلك إلى التجميع على الصفوف نحصل على الصيغة النهائية
$$\boxed{P(m,n)=\sum_{d=1}^{m}\ \sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor.}$$
عندما \(d=1\)، تكون الصفوف الأكبر هي \(2\) و\(3\)، ومن ثم تكون القواسم الممنوعة \(2\) و\(3\). لذلك
$$C_1=4-\left\lfloor\frac{4}{2}\right\rfloor-\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{4}{6}\right\rfloor=4-2-1+0=1.$$
وعندما \(d=2\)، لا يبقى إلا الصف \(3\)، وهو يمنع مضاعفات \(3\)، وبالتالي
$$C_2=4-\left\lfloor\frac{4}{3}\right\rfloor=3.$$
أما عندما \(d=3\)، فلا يوجد صف أكبر، ومن ثم \(Q_3=\emptyset\) و\(C_3=4\).
إذن
$$P(3,4)=C_1+C_2+C_3=1+3+4=8.$$
والقيم الثماني المختلفة هي \(\{1,2,3,4,6,8,9,12\}\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها صفًا صفًا. فلكل صف \(d\)، تُولِّد الشيفرة القيم \(e/\gcd(e,d)\) لجميع الصفوف الأكبر \(e\)، ثم تستبعد القيم الأكبر من \(n\)، وتحذف التكرارات، وبعد ذلك تزيل كل قيمة هي مضاعف لقاسم أصغر سبق الاحتفاظ به.
بعد هذا التقليص، تُنفَّذ عملية احتواء واستبعاد عودية على القواسم الممنوعة المتبقية. وفي كل خطوة يجري تحديث المضاعف المشترك الأصغر بصيغة تعتمد على gcd، ثم تُقصّ الشعبة مباشرة إذا كان هذا المضاعف سيتجاوز \(n\) أو سيتخطى الحد الآمن. وبعد جمع مساهمات جميع الصفوف نحصل على \(P(m,n)\).
ويستفيد إصدار C++ أيضًا من استقلال الصفوف، لذلك يمكنه حساب مساهمات الصفوف على التوازي. كما أن الشيفرة المتحقَّق منها تقارن النتائج بالقيم المرجعية المنشورة أعلاه وببعض الحالات الصغيرة التي يمكن عدّها مباشرةً.
ليكن \(t_d=|Q_d|\). إن بناء القائمة الخام للقواسم الممنوعة في الصف \(d\) يحتاج إلى \(O(m-d)\) من حسابات gcd، ثم إلى الفرز وإزالة التكرارات. أما ترشيح القائمة إلى مجموعة صغرى من القواسم فقد يكون تربيعيًا في أسوأ الأحوال بالنسبة إلى حجم القائمة المؤقتة، لكن \(m\) صغير في هذه المسألة.
وتعتمد كلفة مرحلة الاحتواء والاستبعاد على عدد المجموعات الجزئية التي يبقى فيها المضاعف المشترك الأصغر أصغر من أو مساويًا لـ \(n\). وفي أسوأ حالة قد تصل كلفة الصف \(d\) إلى \(O(2^{t_d})\)، لكن الواقع العملي أفضل بكثير لأن حذف القواسم الزائدة والقصّ المبكر عند تجاوز lcm يقللان عدد الفروع المستكشفة بشدة. وبصورة عامة فإن هذه الطريقة أصغر بكثير من توليد جميع القيم \(mn\)، كما أن الذاكرة المطلوبة متواضعة وتقتصر أساسًا على قائمة القواسم الممنوعة لصف واحد مع مكدس الاستدعاء العودي.