For the first \(10^9\) rows of Pascal's triangle, count how many binomial coefficients are not divisible by 7. If row \(n\) is written as \(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}\), then a brute-force approach would have to inspect an enormous number of entries, so the only viable route is to exploit the arithmetic structure of binomial coefficients modulo 7.
Let \(r(n)\) denote the number of entries in row \(n\) that are not divisible by 7, and let \(F(N)=\sum_{n=0}^{N-1} r(n)\). The required answer is \(F(10^9)\).
Write \(n\) and \(k\) in base 7 as
$$n=\sum_i d_i 7^i,\qquad k=\sum_i e_i 7^i.$$
Lucas' theorem states that for a prime \(p\),
$$\binom{n}{k}\equiv \prod_i \binom{d_i}{e_i}\pmod p.$$
With \(p=7\), the product is nonzero modulo 7 exactly when every digit satisfies \(e_i\le d_i\). For one fixed digit \(d_i\), there are \(d_i+1\) allowed choices for \(e_i\). Therefore the number of entries in row \(n\) that survive modulo 7 is
$$r(n)=\prod_i (d_i+1).$$
This is the central object of the problem: each row is reduced to a simple product of its base-7 digits plus one.
Consider all rows with \(0\le n<7^m\). Their base-7 representations use exactly \(m\) digits after padding with leading zeros, and each digit can be chosen independently from \(0\) through \(6\). Summing the row formula over the entire block factorizes:
$$F(7^m)=\sum_{d_{m-1}=0}^{6}\cdots\sum_{d_0=0}^{6}\prod_{i=0}^{m-1}(d_i+1)=\prod_{i=0}^{m-1}\sum_{d=0}^{6}(d+1)=28^m.$$
The number \(28\) is just \(1+2+\cdots+7\). That is why every unrestricted base-7 suffix of length \(m\) contributes a factor of \(28^m\).
Now write
$$N=a\cdot 7^m+b,\qquad 0\le a\le 6,\qquad 0\le b<7^m.$$
Rows whose leading base-7 digit is \(x<a\) form a complete block of size \(7^m\). Their leading digit contributes a factor of \(x+1\), and the remaining \(m\) digits contribute \(28^m\). The unfinished part keeps the leading digit \(a\), so every row there gets an additional factor of \(a+1\). Hence
$$F(N)=\sum_{x=0}^{a-1}(x+1)28^m+(a+1)F(b).$$
Using \(\sum_{x=0}^{a-1}(x+1)=a(a+1)/2\), this becomes
$$F(N)=\frac{a(a+1)}{2}\,28^m+(a+1)F(b).$$
This recurrence is the mathematical reason the problem can be solved digit by digit from the most significant base-7 digit to the least significant one.
The standard checkpoint value is the first 100 rows. Since \(100=202_7\), we split the interval into complete and partial leading-digit blocks:
$$F(202_7)=(1+2)\cdot 28^2+3\cdot F(2_7).$$
The first term counts all rows below \(200_7\): leading digit \(0\) contributes \(1\cdot 28^2\), and leading digit \(1\) contributes \(2\cdot 28^2\). For the remaining rows \(200_7\) and \(201_7\), the fixed leading digit \(2\) contributes a factor of \(3\), and the suffix count is
$$F(2_7)=1+2=3.$$
Therefore
$$F(100)=3\cdot 784+3\cdot 3=2361.$$
This is exactly the published sample total. It also clarifies the indexing: \(F(100)\) counts rows \(0\) through \(99\), because \(100\) is the upper bound, not an included row number.
If
$$N=(a_0a_1\cdots a_{L-1})_7$$
is written from most significant to least significant digit, then repeatedly applying the recurrence gives
$$F(N)=\sum_{i=0}^{L-1}\left(\prod_{j=0}^{i-1}(a_j+1)\right)\left(\sum_{x=0}^{a_i-1}(x+1)\right)28^{L-1-i}.$$
The empty product is 1. The prefix product records the contribution of the digits already fixed, while the power of 28 records the total contribution of the free suffix. This formula is exactly what the implementations accumulate.
The C++, Python, and Java implementations first convert \(10^9\) to base 7. In this problem, \(10^9=33531600616_7\), so the entire computation touches only 11 digits. They also precompute the powers \(28^t\), because a suffix of \(t\) unrestricted base-7 digits always contributes \(28^t\).
The main loop scans the base-7 digits from left to right. At a digit \(d\), the implementation adds the contribution of every smaller digit \(0,1,\dots,d-1\) placed at that position, multiplies each contribution by the prefix product from the already fixed higher digits, and multiplies again by the appropriate power of 28 for the remaining free suffix.
After those smaller-digit branches are counted, the actual digit \(d\) is folded into the prefix product by multiplying by \(d+1\). The inner loop is tiny because a base-7 digit has at most seven possible values, so the direct summation is still constant time. The three languages differ only in numeric representation: Python uses arbitrary-precision integers, Java uses big integers, and C++ uses a 128-bit integer so the final count is handled safely. One implementation also keeps the checkpoint values for the first 7 rows and the first 100 rows.
If \(L=\lfloor\log_7 N\rfloor+1\), the algorithm performs \(L\) digit steps, and each step checks at most 7 smaller digits. The running time is therefore \(O(L)=O(\log_7 N)\). For \(N=10^9\), this means only 11 iterations of the outer loop.
The memory usage is also \(O(L)\): one list of digits, one list of powers of 28, and a few integer accumulators. Compared with a naive sweep through every entry of every row, this is a complete collapse in problem size.
Gesucht ist die Anzahl der Binomialkoeffizienten in den ersten \(10^9\) Zeilen des Pascalschen Dreiecks, die nicht durch 7 teilbar sind. Schreibt man Zeile \(n\) als \(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}\), dann wäre ein direktes Durchzählen völlig unrealistisch. Entscheidend ist also, die Teilbarkeit modulo 7 in eine viel kleinere Struktur zu übersetzen.
Sei \(r(n)\) die Anzahl der Einträge in Zeile \(n\), die nicht durch 7 teilbar sind, und sei \(F(N)=\sum_{n=0}^{N-1} r(n)\). Gesucht ist somit \(F(10^9)\).
Schreibe \(n\) und \(k\) in Basis 7 als
$$n=\sum_i d_i 7^i,\qquad k=\sum_i e_i 7^i.$$
Nach dem Lucas-Theorem gilt für eine Primzahl \(p\)
$$\binom{n}{k}\equiv \prod_i \binom{d_i}{e_i}\pmod p.$$
Für \(p=7\) ist dieses Produkt genau dann ungleich 0 modulo 7, wenn in jeder Stelle \(e_i\le d_i\) gilt. Bei einem festen Digit \(d_i\) gibt es also \(d_i+1\) zulässige Möglichkeiten für \(e_i\). Damit erhält man für Zeile \(n\)
$$r(n)=\prod_i (d_i+1).$$
Die Anzahl der nicht durch 7 teilbaren Einträge einer Zeile hängt also nur von den Basis-7-Ziffern des Zeilenindex ab.
Betrachte alle Zeilen mit \(0\le n<7^m\). Nach Auffüllen mit führenden Nullen besitzen ihre Basis-7-Darstellungen genau \(m\) Stellen, und jede Stelle kann unabhängig von \(0\) bis \(6\) gewählt werden. Die Summe über den gesamten Block faktorisiert deshalb:
$$F(7^m)=\sum_{d_{m-1}=0}^{6}\cdots\sum_{d_0=0}^{6}\prod_{i=0}^{m-1}(d_i+1)=\prod_{i=0}^{m-1}\sum_{d=0}^{6}(d+1)=28^m.$$
Die Konstante \(28\) ist einfach \(1+2+\cdots+7\). Genau deshalb trägt ein freier Basis-7-Suffix der Länge \(m\) immer den Faktor \(28^m\) bei.
Schreibe nun
$$N=a\cdot 7^m+b,\qquad 0\le a\le 6,\qquad 0\le b<7^m.$$
Alle Zeilen mit führender Basis-7-Ziffer \(x<a\) bilden jeweils einen vollständigen Block der Größe \(7^m\). Die führende Ziffer liefert den Faktor \(x+1\), und die restlichen \(m\) Stellen liefern \(28^m\). Im unvollständigen Restblock ist die führende Ziffer fest gleich \(a\), daher entsteht dort ein zusätzlicher Faktor \(a+1\). Also
$$F(N)=\sum_{x=0}^{a-1}(x+1)28^m+(a+1)F(b).$$
Mit \(\sum_{x=0}^{a-1}(x+1)=a(a+1)/2\) folgt
$$F(N)=\frac{a(a+1)}{2}\,28^m+(a+1)F(b).$$
Diese Rekurrenz erklärt genau, warum man die Antwort Stelle für Stelle von links nach rechts berechnen kann.
Der klassische Kontrollwert betrifft die ersten 100 Zeilen. Da \(100=202_7\) ist, zerfällt das Intervall in vollständige und partielle Blöcke:
$$F(202_7)=(1+2)\cdot 28^2+3\cdot F(2_7).$$
Der erste Summand zählt alle Zeilen unterhalb von \(200_7\): führende Ziffer \(0\) trägt \(1\cdot 28^2\) bei, führende Ziffer \(1\) trägt \(2\cdot 28^2\) bei. Im Restblock sind nur noch \(200_7\) und \(201_7\) übrig; dort ist die führende Ziffer fest \(2\), also kommt ein Faktor \(3\) hinzu, und für den Suffix gilt
$$F(2_7)=1+2=3.$$
Damit ergibt sich
$$F(100)=3\cdot 784+3\cdot 3=2361.$$
Das ist genau der bekannte Stichprobenwert. Zugleich wird klar, dass \(F(100)\) die Zeilen \(0\) bis \(99\) zählt; die Zahl \(100\) ist nur die obere Grenze.
Ist
$$N=(a_0a_1\cdots a_{L-1})_7$$
von der höchstwertigen zur niedrigstwertigen Ziffer geschrieben, dann liefert wiederholtes Anwenden der Rekurrenz
$$F(N)=\sum_{i=0}^{L-1}\left(\prod_{j=0}^{i-1}(a_j+1)\right)\left(\sum_{x=0}^{a_i-1}(x+1)\right)28^{L-1-i}.$$
Das leere Produkt ist 1. Das Präfixprodukt sammelt die Beiträge der bereits festgelegten höheren Ziffern, während die Potenz von 28 die komplette Freiheit des verbleibenden Suffixes beschreibt. Genau diese Summe wird in den Implementierungen akkumuliert.
Die C++-, Python- und Java-Implementierungen wandeln zunächst \(10^9\) in Basis 7 um. In diesem Problem gilt \(10^9=33531600616_7\), also umfasst die gesamte Rechnung nur 11 Ziffern. Zusätzlich werden die Potenzen \(28^t\) vorab berechnet, weil ein freier Suffix aus \(t\) Basis-7-Ziffern immer genau \(28^t\) beiträgt.
Danach laufen die Programme von links nach rechts durch die Basis-7-Ziffern. Bei einer Ziffer \(d\) addiert die Implementierung den Beitrag aller kleineren Ziffern \(0,1,\dots,d-1\) an dieser Position, multipliziert ihn mit dem Präfixprodukt der bereits festgelegten höheren Stellen und anschließend mit der passenden Potenz von 28 für den freien Rest.
Wenn diese kleineren Zweige gezählt sind, wird die tatsächliche Ziffer \(d\) durch Multiplikation mit \(d+1\) in das Präfixprodukt übernommen. Die innere Schleife bleibt winzig, weil eine Basis-7-Ziffer höchstens sieben Werte annehmen kann. Unterschiede zwischen den drei Sprachfassungen gibt es nur bei den Zahltypen: Python verwendet beliebig große ganze Zahlen, Java große Ganzzahlen und C++ einen 128-Bit-Typ. Eine Implementierung prüft zusätzlich die bekannten Kontrollwerte für die ersten 7 und die ersten 100 Zeilen.
Für \(L=\lfloor\log_7 N\rfloor+1\) durchläuft der Algorithmus \(L\) Ziffernpositionen, und pro Position werden höchstens 7 kleinere Ziffern betrachtet. Die Laufzeit ist daher \(O(L)=O(\log_7 N)\). Für \(N=10^9\) bedeutet das nur 11 Iterationen der äußeren Schleife.
Auch der Speicherbedarf ist \(O(L)\): eine Ziffernliste, eine kleine Tabelle der Potenzen von 28 und einige Akkumulatoren. Gegenüber einem naiven Verfahren, das jeden Eintrag jeder Zeile besuchen müsste, ist das eine drastische Kompression des Problems.
İstenen şey, Pascal üçgeninin ilk \(10^9\) satırında 7'ye bölünmeyen binom katsayılarının toplam sayısını bulmaktır. \(n\). satır \(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}\) biçimindedir; dolayısıyla bütün girdileri tek tek yoklayan kaba kuvvet yaklaşımı pratik değildir. Çözüm, bu bölünebilirlik problemini 7 tabanındaki basamak yapısına indirir.
\(r(n)\), \(n\). satırdaki 7'ye bölünmeyen giriş sayısı; \(F(N)=\sum_{n=0}^{N-1} r(n)\) ise ilk \(N\) satırın toplamı olsun. Sorunun istediği değer \(F(10^9)\)'dir.
\(n\) ve \(k\) sayıları 7 tabanında
$$n=\sum_i d_i 7^i,\qquad k=\sum_i e_i 7^i$$
şeklinde yazılsın. Lucas teoremi, asal \(p\) için
$$\binom{n}{k}\equiv \prod_i \binom{d_i}{e_i}\pmod p$$
eşitliğini verir. \(p=7\) olduğunda bu çarpımın sıfır olmaması için her basamakta \(e_i\le d_i\) gerekir. Sabit bir \(d_i\) için izin verilen \(e_i\) sayısı \(d_i+1\) olduğundan, satır \(n\) içindeki 7'ye bölünmeyen giriş sayısı
$$r(n)=\prod_i (d_i+1)$$
olur. Böylece her satırın katkısı doğrudan satır numarasının 7 tabanındaki basamaklarından okunur.
\(0\le n<7^m\) aralığındaki bütün satırları ele alalım. Baştaki eksik basamakları sıfırla tamamladığımızda her satır tam \(m\) basamaklı bir 7 tabanı dizisi olur ve her basamak bağımsız olarak \(0\) ile \(6\) arasında değişir. Satır formülünü bütün blok üzerinde toplarsak çarpanlara ayrılır:
$$F(7^m)=\sum_{d_{m-1}=0}^{6}\cdots\sum_{d_0=0}^{6}\prod_{i=0}^{m-1}(d_i+1)=\prod_{i=0}^{m-1}\sum_{d=0}^{6}(d+1)=28^m.$$
Buradaki \(28\) sayısı yalnızca \(1+2+\cdots+7\)'dir. Bu yüzden serbest bırakılmış her \(m\) basamaklı 7 tabanı son eki toplamda \(28^m\) üretir.
Şimdi
$$N=a\cdot 7^m+b,\qquad 0\le a\le 6,\qquad 0\le b<7^m$$
şeklinde yazalım. İlk basamağı \(x<a\) olan satırlar, büyüklüğü \(7^m\) olan tam bloklar oluşturur. Bu blokta ilk basamak \(x+1\) çarpanını, kalan \(m\) basamak ise \(28^m\) katkısını verir. Eksik kalan son blokta ise ilk basamak sabit olarak \(a\) olduğundan ek çarpan \(a+1\) olur. Dolayısıyla
$$F(N)=\sum_{x=0}^{a-1}(x+1)28^m+(a+1)F(b).$$
\(\sum_{x=0}^{a-1}(x+1)=a(a+1)/2\) kullanılırsa
$$F(N)=\frac{a(a+1)}{2}\,28^m+(a+1)F(b)$$
elde edilir. Sorunun basamak basamak çözülebilmesinin nedeni tam olarak bu bağıntıdır.
Yaygın kontrol değeri ilk 100 satırdır. \(100=202_7\) olduğuna göre aralık tam ve kısmi ön-ek bloklarına ayrılır:
$$F(202_7)=(1+2)\cdot 28^2+3\cdot F(2_7).$$
İlk terim \(200_7\)'den küçük bütün satırları sayar: ilk basamak \(0\) için \(1\cdot 28^2\), ilk basamak \(1\) için \(2\cdot 28^2\) gelir. Geriye kalan \(200_7\) ve \(201_7\) satırlarında ilk basamak sabit \(2\) olduğu için çarpan \(3\) olur ve son ek için
$$F(2_7)=1+2=3$$
yazılır. Böylece
$$F(100)=3\cdot 784+3\cdot 3=2361$$
bulunur. Bu, bilinen örnek toplamla aynıdır. Aynı zamanda \(F(100)\)'ün \(0\) ile \(99\) arasındaki satırları saydığını da açıkça gösterir; \(100\) sadece üst sınırdır.
Eğer
$$N=(a_0a_1\cdots a_{L-1})_7$$
en anlamlı basamaktan en aza doğru yazılmışsa, özyinelemeyi tekrar tekrar açınca
$$F(N)=\sum_{i=0}^{L-1}\left(\prod_{j=0}^{i-1}(a_j+1)\right)\left(\sum_{x=0}^{a_i-1}(x+1)\right)28^{L-1-i}$$
elde edilir. Boş çarpım 1'dir. Önek çarpımı daha önce sabitlenmiş yüksek basamakların katkısını, \(28\) kuvveti ise serbest kalan son ekin toplam etkisini tutar. Uygulamalar tam olarak bu toplamı soldan sağa biriktirir.
C++, Python ve Java uygulamaları önce \(10^9\)'i 7 tabanına çevirir. Bu problemde \(10^9=33531600616_7\) olduğundan hesaplama sadece 11 basamağa dokunur. Ayrıca \(28^t\) değerleri önceden hazırlanır; çünkü uzunluğu \(t\) olan serbest bir 7 tabanı son eki her zaman \(28^t\) katkısı verir.
Ana döngü basamakları soldan sağa işler. Bir \(d\) basamağında, o konuma gelebilecek daha küçük tüm rakamların \(0,1,\dots,d-1\) katkısı eklenir; her katkı, daha önce sabitlenmiş üst basamaklardan gelen önek çarpımıyla ve geride kalan serbest son ek için uygun \(28\) kuvvetiyle çarpılır.
Bu dallar sayıldıktan sonra gerçek basamak \(d\), önek çarpımına \(d+1\) ile çarpılarak dahil edilir. İç döngü çok küçüktür; çünkü 7 tabanında en fazla yedi rakam seçeneği vardır. Üç dil arasındaki fark yalnızca kullanılan sayı türleridir: Python keyfi büyüklükte tam sayı kullanır, Java büyük tam sayı kullanır, C++ ise sonucu güvenle taşımak için 128 bitlik bir tamsayı kullanır. Uygulamalardan biri ayrıca ilk 7 ve ilk 100 satır için kontrol değerlerini de doğrular.
\(L=\lfloor\log_7 N\rfloor+1\) için algoritma \(L\) basamak adımı çalıştırır ve her adımda en fazla 7 küçük rakamı dener. Bu nedenle çalışma süresi \(O(L)=O(\log_7 N)\)'dir. \(N=10^9\) için bu, dış döngünün yalnızca 11 kez dönmesi demektir.
Bellek kullanımı da \(O(L)\)'dir: bir basamak dizisi, küçük bir \(28\) kuvvetleri tablosu ve birkaç biriktirici değişken yeterlidir. Her satırdaki her girdiyi yoklayan saf yaklaşımla karşılaştırıldığında, problem boyutu dramatik biçimde küçülmüş olur.
Hay que contar cuántos coeficientes binomiales de las primeras \(10^9\) filas del triángulo de Pascal no son divisibles por 7. La fila \(n\) contiene \(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}\), de modo que una enumeración directa sería gigantesca. La clave es transformar la divisibilidad módulo 7 en una descripción puramente digital en base 7.
Sea \(r(n)\) el número de entradas de la fila \(n\) que no son divisibles por 7, y sea \(F(N)=\sum_{n=0}^{N-1} r(n)\). El objetivo del problema es calcular \(F(10^9)\).
Escribimos \(n\) y \(k\) en base 7 como
$$n=\sum_i d_i 7^i,\qquad k=\sum_i e_i 7^i.$$
El teorema de Lucas afirma que, para un primo \(p\),
$$\binom{n}{k}\equiv \prod_i \binom{d_i}{e_i}\pmod p.$$
Tomando \(p=7\), el producto es distinto de cero módulo 7 exactamente cuando cada dígito cumple \(e_i\le d_i\). Para una posición fija, si el dígito de \(n\) es \(d_i\), entonces hay \(d_i+1\) elecciones válidas para el dígito correspondiente de \(k\). Por tanto, el número de coeficientes de la fila \(n\) que no son múltiplos de 7 es
$$r(n)=\prod_i (d_i+1).$$
Esto convierte toda la fila en un producto muy simple determinado solo por los dígitos en base 7 del índice de fila.
Consideremos todas las filas con \(0\le n<7^m\). Si completamos con ceros a la izquierda, cada índice tiene exactamente \(m\) dígitos en base 7 y cada dígito puede elegirse independientemente entre \(0\) y \(6\). Al sumar la fórmula de \(r(n)\) sobre todo el bloque, la suma se separa:
$$F(7^m)=\sum_{d_{m-1}=0}^{6}\cdots\sum_{d_0=0}^{6}\prod_{i=0}^{m-1}(d_i+1)=\prod_{i=0}^{m-1}\sum_{d=0}^{6}(d+1)=28^m.$$
El número \(28\) no es misterioso: simplemente es \(1+2+\cdots+7\). Por eso cualquier sufijo libre de longitud \(m\) en base 7 aporta en total \(28^m\).
Ahora escribimos
$$N=a\cdot 7^m+b,\qquad 0\le a\le 6,\qquad 0\le b<7^m.$$
Las filas cuyo primer dígito en base 7 es \(x<a\) forman bloques completos de tamaño \(7^m\). Ese primer dígito aporta un factor \(x+1\), mientras que los \(m\) dígitos restantes aportan \(28^m\). En el bloque parcial final, el primer dígito ya está fijado como \(a\), así que aparece un factor adicional \(a+1\). De este modo,
$$F(N)=\sum_{x=0}^{a-1}(x+1)28^m+(a+1)F(b).$$
Como \(\sum_{x=0}^{a-1}(x+1)=a(a+1)/2\), obtenemos también
$$F(N)=\frac{a(a+1)}{2}\,28^m+(a+1)F(b).$$
Esta es la recurrencia que permite recorrer el número límite dígito por dígito en lugar de procesar fila por fila.
El valor de control clásico corresponde a las primeras 100 filas. Como \(100=202_7\), separamos el intervalo en bloques completos y un bloque parcial:
$$F(202_7)=(1+2)\cdot 28^2+3\cdot F(2_7).$$
El primer término cuenta todas las filas por debajo de \(200_7\): con dígito inicial \(0\) aportan \(1\cdot 28^2\), y con dígito inicial \(1\) aportan \(2\cdot 28^2\). En el resto solo quedan \(200_7\) y \(201_7\); allí el primer dígito es fijo e igual a \(2\), lo que añade un factor \(3\), y para el sufijo tenemos
$$F(2_7)=1+2=3.$$
Por tanto,
$$F(100)=3\cdot 784+3\cdot 3=2361.$$
Ese resultado coincide con el valor de referencia del problema. Además, deja claro que \(F(100)\) cuenta las filas \(0,1,\dots,99\); el 100 es el límite superior, no una fila incluida.
Si
$$N=(a_0a_1\cdots a_{L-1})_7$$
está escrito de dígito más significativo a menos significativo, entonces al desplegar la recurrencia obtenemos
$$F(N)=\sum_{i=0}^{L-1}\left(\prod_{j=0}^{i-1}(a_j+1)\right)\left(\sum_{x=0}^{a_i-1}(x+1)\right)28^{L-1-i}.$$
El producto vacío vale 1. El producto prefijo representa el efecto de los dígitos altos ya fijados, mientras que la potencia de 28 resume toda la contribución del sufijo libre. Esa es exactamente la cantidad que las implementaciones acumulan.
Las implementaciones en C++, Python y Java convierten primero \(10^9\) a base 7. En este problema, \(10^9=33531600616_7\), así que toda la cuenta se reduce a 11 dígitos. También precalculan las potencias \(28^t\), porque un sufijo libre de longitud \(t\) en base 7 siempre aporta \(28^t\).
Después recorren los dígitos de izquierda a derecha. Cuando el dígito actual es \(d\), la implementación suma la contribución de todos los dígitos menores \(0,1,\dots,d-1\) colocados en esa posición, multiplica cada contribución por el producto prefijo acumulado en las posiciones anteriores y vuelve a multiplicar por la potencia de 28 correspondiente al sufijo todavía no restringido.
Una vez contadas esas ramas menores, el dígito real \(d\) se incorpora al producto prefijo multiplicando por \(d+1\). El bucle interior es minúsculo porque un dígito en base 7 solo tiene como máximo siete posibilidades. La diferencia entre los tres lenguajes está únicamente en los tipos numéricos: Python usa enteros de precisión arbitraria, Java usa enteros grandes y C++ usa un entero de 128 bits para mantener el conteo con seguridad. Una de las implementaciones también conserva los valores de control para las primeras 7 y 100 filas.
Si \(L=\lfloor\log_7 N\rfloor+1\), el algoritmo realiza \(L\) pasos de dígitos y en cada paso inspecciona a lo sumo 7 dígitos menores. Por ello, el tiempo de ejecución es \(O(L)=O(\log_7 N)\). Para \(N=10^9\), esto significa solo 11 iteraciones del bucle principal.
El uso de memoria también es \(O(L)\): una lista de dígitos, una lista pequeña de potencias de 28 y unos pocos acumuladores enteros. Frente a un recorrido ingenuo de todas las entradas del triángulo, la reducción es enorme.
题目要求统计帕斯卡三角形前 \(10^9\) 行中，多少个二项式系数不能被 7 整除。第 \(n\) 行包含 \(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}\)，如果逐项检查，规模大到完全不可行。真正可行的思路，是把“模 7 是否为零”转化成 7 进制数字上的结构问题。
记 \(r(n)\) 为第 \(n\) 行中不被 7 整除的项数，记 \(F(N)=\sum_{n=0}^{N-1} r(n)\)。题目最终要求的就是 \(F(10^9)\)。
把 \(n\) 和 \(k\) 写成 7 进制：
$$n=\sum_i d_i 7^i,\qquad k=\sum_i e_i 7^i.$$
Lucas 定理说明，对任意素数 \(p\)，都有
$$\binom{n}{k}\equiv \prod_i \binom{d_i}{e_i}\pmod p.$$
当 \(p=7\) 时，这个乘积模 7 不为 0，当且仅当每一位都满足 \(e_i\le d_i\)。对于固定的一位，如果 \(n\) 在该位上的数字是 \(d_i\)，那么 \(k\) 在该位上共有 \(d_i+1\) 种合法选择。因此，第 \(n\) 行中不被 7 整除的项数正好是
$$r(n)=\prod_i (d_i+1).$$
这一步非常关键：原本看起来复杂的整行计数，被压缩成了“把 7 进制各位加一后相乘”这样一个简单公式。
考虑所有满足 \(0\le n<7^m\) 的行。把这些行号都补齐为长度为 \(m\) 的 7 进制表示后，每一位都可以独立地在 \(0\) 到 \(6\) 之间取值。于是把上面的行公式在整个块上求和时，可以完全分离：
$$F(7^m)=\sum_{d_{m-1}=0}^{6}\cdots\sum_{d_0=0}^{6}\prod_{i=0}^{m-1}(d_i+1)=\prod_{i=0}^{m-1}\sum_{d=0}^{6}(d+1)=28^m.$$
这里的 \(28\) 只是 \(1+2+\cdots+7\)。这说明，只要某一段后缀的 7 进制数字可以自由变化，它对总计数的整体贡献就会收缩成一个 \(28\) 的幂。
把上界写成
$$N=a\cdot 7^m+b,\qquad 0\le a\le 6,\qquad 0\le b<7^m.$$
所有最高位小于 \(a\) 的行，会形成若干个完整块，每个块的大小都是 \(7^m\)。如果最高位取成 \(x\)，那一位会贡献因子 \(x+1\)，其余 \(m\) 位自由变化时贡献 \(28^m\)。至于最后那个不完整的块，最高位固定成 \(a\)，所以整体再乘上 \(a+1\)。因此有
$$F(N)=\sum_{x=0}^{a-1}(x+1)28^m+(a+1)F(b).$$
再把前面的等差和写出来：
$$F(N)=\frac{a(a+1)}{2}\,28^m+(a+1)F(b).$$
这就是整个算法的核心递推。它告诉我们：不需要逐行扫描，只要按 7 进制从高位到低位展开，就能把总答案一步一步累加出来。
经典校验值是前 100 行。因为 \(100=202_7\)，所以可以直接套用上面的分块思想：
$$F(202_7)=(1+2)\cdot 28^2+3\cdot F(2_7).$$
第一项统计的是所有小于 \(200_7\) 的行：最高位为 \(0\) 时贡献 \(1\cdot 28^2\)，最高位为 \(1\) 时贡献 \(2\cdot 28^2\)。剩下的部分只有 \(200_7\) 和 \(201_7\) 两行，它们的最高位固定是 \(2\)，因此带来因子 \(3\)，而后缀部分的计数是
$$F(2_7)=1+2=3.$$
于是
$$F(100)=3\cdot 784+3\cdot 3=2361.$$
这与题目常见的校验值完全一致。这个例子还顺带说明了一件容易混淆的事：\(F(100)\) 统计的是第 \(0\) 行到第 \(99\) 行，因为 100 是上界，不是被包含的行号。
若把 \(N\) 写成从高位到低位的 7 进制
$$N=(a_0a_1\cdots a_{L-1})_7,$$
不断展开递推后可得
$$F(N)=\sum_{i=0}^{L-1}\left(\prod_{j=0}^{i-1}(a_j+1)\right)\left(\sum_{x=0}^{a_i-1}(x+1)\right)28^{L-1-i}.$$
其中空乘积按 1 处理。前面的乘积记录已经固定下来的高位贡献，后面的 \(28^{L-1-i}\) 则表示所有自由后缀的总贡献。实现代码正是按这个公式从左到右累积答案。
C++、Python 和 Java 实现都先把 \(10^9\) 转成 7 进制。在本题中，\(10^9=33531600616_7\)，因此整个计算只需要处理 11 个数字位置。随后它们会预先计算 \(28^t\)，因为长度为 \(t\) 的自由 7 进制后缀，总贡献永远都是 \(28^t\)。
主循环按从高位到低位扫描每个数字。当前位为 \(d\) 时，程序会枚举这一位可以放置的更小数字 \(0,1,\dots,d-1\)，把这些分支的贡献全部加起来；每个分支都要乘上当前已经形成的前缀乘积，再乘上对应自由后缀的 \(28\) 的幂。
把这些更小分支统计完之后，真实数字 \(d\) 本身会通过乘上 \(d+1\) 并入前缀乘积。因为 7 进制每位最多只有 7 种取值，所以这个内层枚举始终是常数时间。三种语言的区别只在整数类型：Python 使用任意精度整数，Java 使用大整数，C++ 使用 128 位整数来安全容纳最终结果。其中一个实现还保留了前 7 行得到 28、前 100 行得到 2361 这两个校验点。
若 \(L=\lfloor\log_7 N\rfloor+1\)，算法只进行 \(L\) 次数字步骤，每一步最多检查 7 个更小数字，所以时间复杂度是 \(O(L)=O(\log_7 N)\)。对 \(N=10^9\) 而言，外层循环只有 11 次。
空间复杂度同样是 \(O(L)\)：保存一组 7 进制数字、一组 \(28\) 的幂，以及少量累加器即可。与逐行逐项扫描整座帕斯卡三角形相比，这个压缩是数量级上的改变。
Нужно посчитать, сколько биномиальных коэффициентов в первых \(10^9\) строках треугольника Паскаля не делятся на 7. В строке \(n\) стоят значения \(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}\), поэтому прямой перебор всех элементов невозможен. Решение появляется только после того, как делимость по модулю 7 переводится в структуру цифр в записи по основанию 7.
Обозначим через \(r(n)\) число элементов строки \(n\), не делящихся на 7, а через \(F(N)=\sum_{n=0}^{N-1} r(n)\) суммарное количество для первых \(N\) строк. Требуется найти \(F(10^9)\).
Запишем \(n\) и \(k\) в системе счисления по основанию 7:
$$n=\sum_i d_i 7^i,\qquad k=\sum_i e_i 7^i.$$
Теорема Лукаса утверждает, что для простого \(p\)
$$\binom{n}{k}\equiv \prod_i \binom{d_i}{e_i}\pmod p.$$
При \(p=7\) это произведение отлично от нуля по модулю 7 тогда и только тогда, когда для каждой цифры выполнено \(e_i\le d_i\). Если цифра строки равна \(d_i\), то допустимых вариантов для соответствующей цифры \(k\) ровно \(d_i+1\). Поэтому
$$r(n)=\prod_i (d_i+1).$$
То есть число ненулевых по модулю 7 элементов в строке полностью определяется цифрами номера строки в записи по основанию 7.
Рассмотрим все строки с \(0\le n<7^m\). Если дописать слева ведущие нули, каждая строка описывается \(m\) цифрами по основанию 7, причем каждая цифра независимо принимает значения от \(0\) до \(6\). Тогда сумма по всему блоку раскладывается в произведение:
$$F(7^m)=\sum_{d_{m-1}=0}^{6}\cdots\sum_{d_0=0}^{6}\prod_{i=0}^{m-1}(d_i+1)=\prod_{i=0}^{m-1}\sum_{d=0}^{6}(d+1)=28^m.$$
Число \(28\) здесь возникает естественно: это просто сумма \(1+2+\cdots+7\). Поэтому любой свободный суффикс длины \(m\) в системе счисления по основанию 7 дает суммарный вклад \(28^m\).
Теперь представим верхнюю границу в виде
$$N=a\cdot 7^m+b,\qquad 0\le a\le 6,\qquad 0\le b<7^m.$$
Все строки, у которых старшая цифра меньше \(a\), образуют полные блоки размера \(7^m\). Если старшая цифра равна \(x\), то она дает множитель \(x+1\), а оставшиеся \(m\) цифр суммарно дают \(28^m\). В последнем неполном блоке старшая цифра уже зафиксирована как \(a\), поэтому появляется множитель \(a+1\). Следовательно,
$$F(N)=\sum_{x=0}^{a-1}(x+1)28^m+(a+1)F(b).$$
Так как \(\sum_{x=0}^{a-1}(x+1)=a(a+1)/2\), получаем более компактно
$$F(N)=\frac{a(a+1)}{2}\,28^m+(a+1)F(b).$$
Именно эта рекурсия позволяет вычислять ответ по цифрам, не проходя по строкам по одной.
Классическая контрольная точка задачи относится к первым 100 строкам. Поскольку \(100=202_7\), интервал естественно распадается на полные и неполный блоки:
$$F(202_7)=(1+2)\cdot 28^2+3\cdot F(2_7).$$
Первое слагаемое считает все строки ниже \(200_7\): при старшей цифре \(0\) вклад равен \(1\cdot 28^2\), при старшей цифре \(1\) вклад равен \(2\cdot 28^2\). В остатке остаются только \(200_7\) и \(201_7\); там старшая цифра фиксирована как \(2\), то есть появляется множитель \(3\), а для суффикса имеем
$$F(2_7)=1+2=3.$$
Отсюда
$$F(100)=3\cdot 784+3\cdot 3=2361.$$
Это в точности совпадает с известным контрольным значением. Одновременно пример показывает, что \(F(100)\) считает строки от \(0\) до \(99\): число 100 служит только верхней границей.
Если число \(N\) записано в виде
$$N=(a_0a_1\cdots a_{L-1})_7$$
от старшего разряда к младшему, то после многократного раскрытия рекурсии получается
$$F(N)=\sum_{i=0}^{L-1}\left(\prod_{j=0}^{i-1}(a_j+1)\right)\left(\sum_{x=0}^{a_i-1}(x+1)\right)28^{L-1-i}.$$
Пустое произведение равно 1. Произведение по префиксу описывает вклад уже зафиксированных старших цифр, а степень 28 описывает полный вклад свободного хвоста. Именно эту сумму и накапливают реализации.
Реализации на C++, Python и Java сначала переводят \(10^9\) в систему счисления по основанию 7. В данной задаче \(10^9=33531600616_7\), так что вся работа идет всего по 11 цифрам. Затем заранее вычисляются степени \(28^t\), потому что любой свободный суффикс длины \(t\) всегда дает вклад \(28^t\).
Основной цикл идет слева направо по цифрам числа. Если текущая цифра равна \(d\), реализация добавляет вклад всех меньших цифр \(0,1,\dots,d-1\), которые можно поставить на эту позицию, умножая каждое такое ветвление на накопленное произведение префикса и на нужную степень 28 для оставшегося свободного суффикса.
После учета меньших ветвей настоящая цифра \(d\) включается в префиксное произведение множителем \(d+1\). Внутренний цикл очень мал, потому что в записи по основанию 7 у цифры максимум семь вариантов. Различие между версиями на трех языках касается только представления чисел: Python использует целые произвольной точности, Java использует большие целые числа, а C++ использует 128-битный целый тип. В одной из реализаций также сохранены контрольные значения для первых 7 и первых 100 строк.
Если \(L=\lfloor\log_7 N\rfloor+1\), алгоритм делает \(L\) шагов по цифрам, и на каждом шаге рассматривает не более 7 меньших цифр. Следовательно, время работы равно \(O(L)=O(\log_7 N)\). Для \(N=10^9\) это означает всего 11 проходов внешнего цикла.
Память также имеет порядок \(O(L)\): нужен массив цифр, небольшой массив степеней 28 и несколько целочисленных аккумуляторов. По сравнению с наивным перебором всех коэффициентов во всех строках это колоссальное сокращение объема вычислений.
المطلوب هو عدّ معاملات ذي الحدين في أول \(10^9\) صفوف من مثلث باسكال التي لا تقبل القسمة على 7. يحتوي الصف \(n\) على القيم \(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}\)، ولذلك فإن الفحص المباشر لكل القيم مستحيل عمليًا. الحل الحقيقي يأتي من تحويل شرط القسمة modulo 7 إلى بنية رقمية في التمثيل بالأساس 7.
لنعرّف \(r(n)\) بأنه عدد العناصر في الصف \(n\) غير القابلة للقسمة على 7، ولنعرّف \(F(N)=\sum_{n=0}^{N-1} r(n)\). القيمة المطلوبة في المسألة هي إذن \(F(10^9)\).
لنكتب \(n\) و\(k\) بالأساس 7 على الصورة
$$n=\sum_i d_i 7^i,\qquad k=\sum_i e_i 7^i.$$
تنص نظرية لوكاس على أنه لأي عدد أولي \(p\)
$$\binom{n}{k}\equiv \prod_i \binom{d_i}{e_i}\pmod p.$$
عندما نأخذ \(p=7\)، يكون هذا الحاصل غير صفري modulo 7 إذا وفقط إذا تحقق \(e_i\le d_i\) في كل منزلة. وإذا كانت منزلة من \(n\) تساوي \(d_i\)، فهناك \(d_i+1\) اختيارات ممكنة للمنزلة المناظرة في \(k\). لذلك يصبح عدد الحدود غير القابلة للقسمة على 7 في الصف \(n\)
$$r(n)=\prod_i (d_i+1).$$
وهكذا تنضغط بنية الصف كاملة إلى حاصل ضرب بسيط يعتمد فقط على أرقام رقم الصف في الأساس 7.
لننظر إلى جميع الصفوف التي تحقق \(0\le n<7^m\). بعد استكمال الأصفار على اليسار، يمتلك كل رقم صف تمثيلًا من \(m\) خانات في الأساس 7، وكل خانة يمكن اختيارها بحرية من \(0\) إلى \(6\). عند جمع صيغة \(r(n)\) على هذه الكتلة كلها، ينفصل المجموع إلى جداء:
$$F(7^m)=\sum_{d_{m-1}=0}^{6}\cdots\sum_{d_0=0}^{6}\prod_{i=0}^{m-1}(d_i+1)=\prod_{i=0}^{m-1}\sum_{d=0}^{6}(d+1)=28^m.$$
العدد \(28\) ليس شيئًا غامضًا؛ إنه فقط \(1+2+\cdots+7\). ولهذا السبب فإن أي لاحقة حرة طولها \(m\) في الأساس 7 تسهم بمقدار كلي يساوي \(28^m\).
نكتب الآن
$$N=a\cdot 7^m+b,\qquad 0\le a\le 6,\qquad 0\le b<7^m.$$
كل الصفوف التي تكون خانتها العليا \(x<a\) تشكّل كتلًا كاملة بحجم \(7^m\). هذه الخانة العليا تعطي عاملًا يساوي \(x+1\)، بينما الخانات \(m\) المتبقية تعطي مجتمعة \(28^m\). أما الكتلة الجزئية الأخيرة فخانتُها العليا ثابتة وتساوي \(a\)، ولذلك يظهر العامل \(a+1\). وعليه نحصل على
$$F(N)=\sum_{x=0}^{a-1}(x+1)28^m+(a+1)F(b).$$
وباستخدام \(\sum_{x=0}^{a-1}(x+1)=a(a+1)/2\) يمكن كتابة العلاقة أيضًا بالشكل
$$F(N)=\frac{a(a+1)}{2}\,28^m+(a+1)F(b).$$
هذه هي العلاقة الأساسية التي تجعل الحساب يسير منزلةً منزلةً بدلًا من المرور على كل صف على حدة.
قيمة الفحص المشهورة في هذه المسألة تتعلق بأول 100 صف. بما أن \(100=202_7\)، فإننا نقسم المجال إلى كتل كاملة وكتلة جزئية:
$$F(202_7)=(1+2)\cdot 28^2+3\cdot F(2_7).$$
الحد الأول يحسب كل الصفوف الأصغر من \(200_7\): عندما تكون الخانة العليا \(0\) يكون الإسهام \(1\cdot 28^2\)، وعندما تكون \(1\) يكون الإسهام \(2\cdot 28^2\). أما الصفوف المتبقية فهي \(200_7\) و\(201_7\) فقط، وفيها تكون الخانة العليا ثابتة وتساوي \(2\)، أي يظهر العامل \(3\)، وللاحقة لدينا
$$F(2_7)=1+2=3.$$
ومن ثم
$$F(100)=3\cdot 784+3\cdot 3=2361.$$
وهذه هي بالضبط قيمة التحقق المعروفة. كما يوضح المثال أيضًا أن \(F(100)\) يحسب الصفوف من \(0\) إلى \(99\)، لأن العدد 100 هو حد علوي وليس رقم صف داخل المجموع.
إذا كتبنا
$$N=(a_0a_1\cdots a_{L-1})_7$$
من الخانة الأعلى إلى الخانة الأدنى، فإن فك العلاقة العودية بالكامل يعطي
$$F(N)=\sum_{i=0}^{L-1}\left(\prod_{j=0}^{i-1}(a_j+1)\right)\left(\sum_{x=0}^{a_i-1}(x+1)\right)28^{L-1-i}.$$
يُفهم الجداء الفارغ على أنه 1. جداء البادئة يلتقط أثر الخانات العليا التي ثُبّتت بالفعل، بينما تمثل قوة \(28\) المساهمة الكلية للّاحقة الحرة. هذا هو التعبير نفسه الذي تجمعه التطبيقات فعليًا.
تبدأ تطبيقات C++ وPython وJava بتحويل \(10^9\) إلى الأساس 7. في هذه المسألة تحديدًا لدينا \(10^9=33531600616_7\)، أي إن الحساب كله يمر عبر 11 خانة فقط. بعد ذلك تُحسب قيم \(28^t\) مسبقًا، لأن أي لاحقة حرة طولها \(t\) في الأساس 7 تعطي دائمًا مساهمة كلية مقدارها \(28^t\).
تمر الحلقة الرئيسية على الخانات من اليسار إلى اليمين. عند خانة قيمتها \(d\)، تضيف الخوارزمية مساهمات كل الأرقام الأصغر \(0,1,\dots,d-1\) الممكنة في هذه الخانة، ثم تضرب كل مساهمة في جداء البادئة المتراكم من الخانات الأعلى، ثم في قوة \(28\) المناسبة للّاحقة التي ما زالت غير مقيّدة.
بعد حساب هذه الفروع الأصغر، تُدمج الخانة الحقيقية \(d\) في جداء البادئة بضربه في \(d+1\). الحلقة الداخلية صغيرة جدًا لأن الخانة في الأساس 7 لا تملك أكثر من سبع قيم ممكنة. الفروق بين اللغات الثلاث محصورة في نوع الأعداد: Python يستخدم أعدادًا صحيحة ذات دقة غير محدودة، وJava يستخدم أعدادًا كبيرة، وC++ يستخدم عددًا صحيحًا بعرض 128 بت لحمل الناتج النهائي بأمان. كما تحتفظ إحدى التطبيقات بقيمتي التحقق لأول 7 صفوف وأول 100 صف.
إذا كان \(L=\lfloor\log_7 N\rfloor+1\)، فإن الخوارزمية تنفذ \(L\) خطوات رقمية، وفي كل خطوة تفحص في أسوأ الأحوال 7 أرقام أصغر. لذلك يكون زمن التنفيذ \(O(L)=O(\log_7 N)\). وبالنسبة إلى \(N=10^9\)، فهذا يعني 11 دورة فقط في الحلقة الخارجية.
أما الذاكرة فهي أيضًا \(O(L)\): قائمة صغيرة للخانات، وقائمة صغيرة لقوى \(28\)، وبعض المجاميع الصحيحة. بالمقارنة مع المرور الساذج على كل عنصر في كل صف، فهذا اختزال هائل في حجم المسألة.