Write a positive integer \(n\) in decimal as \(d_{L-1}d_{L-2}\dots d_1d_0\), with \(d_{L-1}\neq0\). The problem associates to \(n\) the polynomial
$$P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0.$$
We must count how many integers \(1\le n\le10^{16}\) have the property that \(P_n(x)\) has at least one integer root.
Because every coefficient is a decimal digit, all coefficients are nonnegative and the leading coefficient is positive. Therefore \(P_n(r)>0\) for every positive integer \(r\). So positive roots are impossible.
By the rational-root theorem, any integer root must divide the constant term \(d_0\). Since \(d_0\in\{0,1,\dots,9\}\), the only possibilities are:
1. \(r=0\), which can happen only when \(d_0=0\),
2. \(r=-t\), where \(t\) is a positive divisor of \(d_0\), so \(1\le t\le 9\).
This is the first major reduction: the code never searches an unbounded root range.
Fix a candidate \(t\ge1\). The condition \(P_n(-t)=0\) is
$$\sum_{i=0}^{L-1} d_i(-t)^i=0.$$
Group digits in pairs from the least significant side:
$$e_j=d_{2j},\qquad o_j=d_{2j+1},$$
where a missing top odd digit is treated as \(0\). Then
$$P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}.$$
The whole task is now to make those pair contributions cancel exactly.
The implementation introduces carry values \(c_j\) and enforces
$$e_j-to_j=c_j-t^2c_{j+1},\qquad c_0=0.$$
Solving for the next carry gives the exact transition used in C++:
$$c_{j+1}=\frac{to_j+c_j-e_j}{t^2}.$$
This transition is valid only if the numerator is divisible by \(t^2\). That divisibility check is the key filter in the DP.
Why does this work? Summing over all processed pairs gives a telescoping identity:
$$\sum_{j=0}^{s-1}(e_j-to_j)t^{2j} =\sum_{j=0}^{s-1}(c_j-t^2c_{j+1})t^{2j} =c_0-t^{2s}c_s.$$
Since \(c_0=0\), we obtain \(P_n(-t)=0\) exactly when the final carry also returns to zero. So the DP only needs to remember the current carry, not the whole partial polynomial value.
Take \(n=121\). Then
$$P_n(x)=x^2+2x+1=(x+1)^2,$$
so \(r=-1\) is a root. Here \(t=1\), and the digit pairs from the right are
$$ (e_0,o_0)=(1,2),\qquad (e_1,o_1)=(1,0). $$
Starting from \(c_0=0\), the recurrence gives
$$c_1=\frac{1\cdot2+0-1}{1^2}=1,\qquad c_2=\frac{1\cdot0+1-1}{1^2}=0.$$
The final carry is \(0\), so the root condition is satisfied.
An even shorter example is \(n=24\), where \(P_n(x)=2x+4\) and \(r=-2\). With \(t=2\), \((e_0,o_0)=(4,2)\), and
$$c_1=\frac{2\cdot2+0-4}{2^2}=0.$$
Again the final carry is zero, so the DP accepts the number.
For a fixed length \(L\), fixed last digit \(d_0\), and fixed candidate root \(-t\), the next carry depends only on:
1. the current carry \(c_j\),
2. the chosen even digit \(e_j\),
3. the chosen odd digit \(o_j\).
Therefore the number of valid prefixes can be counted with a finite-state DP over carry values. This replaces a brute-force scan over all \(10^L\) numbers.
The code processes digits in pair-blocks. Whenever the most significant digit lies in the currently chosen even or odd slot, zero is removed from the allowed digit set so that leading zeros never occur.
For a fixed last digit \(d_0\neq0\), the possible positive divisors \(t\mid d_0\) form a very small set. The largest cases are \(d_0=6\) and \(d_0=8\), each having only four divisors, so there are at most \(2^4-1=15\) nonempty subsets to consider.
For each subset of candidate roots, the DP carries a whole vector
$$\bigl(c_j^{(t_1)},c_j^{(t_2)},\dots\bigr)$$
and counts numbers that satisfy all those root conditions simultaneously. Then inclusion-exclusion turns those intersection counts into the number of integers with at least one integer root.
A simple overlap example is \(n=132\):
$$P_n(x)=x^2+3x+2=(x+1)(x+2).$$
So the number belongs to the count for root \(-1\), also to the count for root \(-2\), and once more to their intersection. Inclusion-exclusion makes sure it is counted only once in the final union.
If \(d_0=0\), then \(x=0\) is automatically a root. The code handles this case directly instead of mixing it into the inclusion-exclusion over negative roots.
For length \(L\ge2\), the count of positive \(L\)-digit numbers ending in \(0\) is simply
$$9\cdot10^{L-2},$$
because the first digit has \(9\) choices, the middle \(L-2\) digits are free, and the last digit is fixed to \(0\).
The function solve(max_power) sums over all decimal lengths \(1,2,\dots,\texttt{max\_power}\). That counts exactly the integers from \(1\) up to \(10^{\texttt{max\_power}}-1\).
Then the code adds one more number:
$$10^{\texttt{max\_power}},$$
which always has root \(x=0\), because its last digit is \(0\).
The implementation validates itself with three checkpoints:
1. solve(3) must equal the brute-force count up to \(1000\), which is \(172\),
2. solve(4) must equal the brute-force count up to \(10000\), which is \(1754\),
3. solve(5) must equal \(14696\), the published value \(Z(10^5)\).
These checks confirm all layers of the method: root restriction, carry DP, inclusion-exclusion, and length accounting.
count_subset_for_length(length, last_digit, roots) runs the pairwise DP for one intersection of root conditions. Its state map stores vectors of current carries and the number of digit assignments reaching each state.
count_for_length(length) first adds the direct contribution from root \(0\), then loops over last digits \(1\) to \(9\), builds the divisor list of \(d_0\), iterates over all nonempty subsets of those divisors, and applies inclusion-exclusion.
solve(max_power) sums all lengths and finally adds \(10^{\texttt{max\_power}}\) itself.
The command line accepts --power=<k> and --skip-checkpoints.
The maximum number of decimal lengths is only \(16\). For each last digit, the divisor set has size at most \(4\), so subset enumeration is tiny. The real cost comes from how many carry states are reachable, but these state spaces stay small in practice.
That makes the algorithm vastly faster than any direct iteration over all numbers up to \(10^{16}\).
Schreibt man eine positive Zahl \(n\) dezimal als \(d_{L-1}d_{L-2}\dots d_1d_0\) mit \(d_{L-1}\neq0\), so gehört dazu das Polynom
$$P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0.$$
Gesucht ist die Anzahl der \(n\) mit \(1\le n\le10^{16}\), für die \(P_n(x)\) mindestens eine ganzzahlige Nullstelle besitzt.
Alle Koeffizienten sind Dezimalziffern, also nichtnegativ, und der führende Koeffizient ist positiv. Daher gilt \(P_n(r)>0\) für jedes positive ganze \(r\). Positive Nullstellen sind also unmöglich.
Nach dem Satz über rationale Nullstellen muss jede ganzzahlige Nullstelle den konstanten Term \(d_0\) teilen. Damit bleiben nur:
1. \(r=0\), nur möglich bei \(d_0=0\),
2. \(r=-t\) mit positivem Teiler \(t\mid d_0\), also \(1\le t\le9\).
Für festes \(t\ge1\) lautet die Gleichung
$$\sum_{i=0}^{L-1} d_i(-t)^i=0.$$
Wir gruppieren die Ziffern paarweise von rechts:
$$e_j=d_{2j},\qquad o_j=d_{2j+1},$$
wobei eine fehlende obere ungerade Ziffer als \(0\) behandelt wird. Dann wird
$$P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}.$$
Der Code führt Überträge \(c_j\) ein und verlangt
$$e_j-to_j=c_j-t^2c_{j+1},\qquad c_0=0.$$
Nach \(c_{j+1}\) aufgelöst ergibt das genau die C++-Transition:
$$c_{j+1}=\frac{to_j+c_j-e_j}{t^2}.$$
Diese Transition ist nur gültig, wenn der Zähler durch \(t^2\) teilbar ist.
Warum ist das korrekt? Über alle bearbeiteten Paare entsteht die Teleskopsumme
$$\sum_{j=0}^{s-1}(e_j-to_j)t^{2j} =\sum_{j=0}^{s-1}(c_j-t^2c_{j+1})t^{2j} =c_0-t^{2s}c_s.$$
Da \(c_0=0\), ist \(P_n(-t)=0\) genau dann erfüllt, wenn auch der letzte Übertrag wieder \(0\) ist.
Für \(n=121\) gilt
$$P_n(x)=x^2+2x+1=(x+1)^2,$$
also ist \(r=-1\) eine Nullstelle. Hier ist \(t=1\), und die Zifferpaare von rechts sind
$$ (e_0,o_0)=(1,2),\qquad (e_1,o_1)=(1,0). $$
Mit \(c_0=0\) folgt
$$c_1=\frac{1\cdot2+0-1}{1^2}=1,\qquad c_2=\frac{1\cdot0+1-1}{1^2}=0.$$
Der Endübertrag ist \(0\), also akzeptiert die DP die Zahl.
Für feste Länge \(L\), feste Endziffer \(d_0\) und festen Kandidaten \(-t\) hängt der nächste Übertrag nur ab von
1. dem aktuellen Übertrag \(c_j\),
2. der gewählten geraden Ziffer \(e_j\),
3. der gewählten ungeraden Ziffer \(o_j\).
Deshalb reicht eine zustandsbasierte DP über die erreichbaren Überträge; ein Vollscan über alle \(10^L\) Zahlen ist unnötig.
Für eine feste Endziffer \(d_0\neq0\) ist die Menge der positiven Teiler \(t\mid d_0\) sehr klein. Die größten Fälle sind \(d_0=6\) und \(d_0=8\) mit je vier Teilern, also höchstens \(2^4-1=15\) nichtleeren Teilmengen.
Für jede Teilmenge möglicher Wurzeln führt die DP einen ganzen Vektor von Überträgen mit:
$$\bigl(c_j^{(t_1)},c_j^{(t_2)},\dots\bigr).$$
So werden Schnittmengenbedingungen gezählt. Anschließend liefert Inklusion-Exklusion die Anzahl der Zahlen mit mindestens einer ganzzahligen Nullstelle.
Ein einfaches Überschneidungsbeispiel ist \(n=132\):
$$P_n(x)=x^2+3x+2=(x+1)(x+2).$$
Diese Zahl erfüllt also gleichzeitig die Bedingungen für \(-1\) und \(-2\); Inklusion-Exklusion sorgt dafür, dass sie insgesamt nur einmal gezählt wird.
Ist \(d_0=0\), dann ist \(x=0\) automatisch eine Nullstelle. Der Code behandelt diese Fälle direkt und mischt sie nicht in die Inklusion-Exklusion über negative Nullstellen.
Für Länge \(L\ge2\) gibt es genau
$$9\cdot10^{L-2}$$
positive \(L\)-stellige Zahlen, die auf \(0\) enden.
solve(max_power) summiert über alle Dezimallängen \(1,2,\dots,\texttt{max\_power}\). Damit sind genau die Zahlen von \(1\) bis \(10^{\texttt{max\_power}}-1\) erfasst.
Danach addiert der Code noch
$$10^{\texttt{max\_power}},$$
denn diese Zahl endet auf \(0\) und besitzt daher sicher die Nullstelle \(x=0\).
Die Implementierung prüft drei Werte:
1. solve(3) muss dem Brute-Force-Wert bis \(1000\) entsprechen, also \(172\),
2. solve(4) muss dem Brute-Force-Wert bis \(10000\) entsprechen, also \(1754\),
3. solve(5) muss \(14696\) ergeben, den bekannten Wert \(Z(10^5)\).
count_subset_for_length führt die paarweise DP für eine feste Schnittmenge von Wurzelbedingungen aus. Der Zustand ist ein Vektor aktueller Überträge.
count_for_length addiert zuerst die direkte \(x=0\)-Komponente, läuft dann über Endziffern \(1\) bis \(9\), bildet die Teilermenge von \(d_0\), iteriert über alle nichtleeren Teilmengen und verwendet Inklusion-Exklusion.
solve summiert die Längen und addiert zuletzt \(10^{\texttt{max\_power}}\) selbst.
Die Kommandozeile akzeptiert --power=<k> und --skip-checkpoints.
Es gibt höchstens \(16\) relevante Längen. Für jede Endziffer ist die Teilermenge sehr klein, und damit auch die Zahl der Teilmengen. Die eigentliche Laufzeit wird durch die Zahl der erreichbaren Übertragszustände bestimmt, die in der Praxis klein bleibt.
Damit ist die Methode um Größenordnungen schneller als ein direkter Durchlauf bis \(10^{16}\).
Pozitif bir \(n\) sayısını ondalık olarak \(d_{L-1}d_{L-2}\dots d_1d_0\) biçiminde yazalım; burada \(d_{L-1}\neq0\). Probleme göre bu sayıya
$$P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0$$
polinomu karşılık gelir. Amaç, \(1\le n\le10^{16}\) aralığında bu polinomun en az bir tamsayı kökü olan kaç sayı bulunduğunu saymaktır.
Bütün katsayılar ondalık basamak olduğu için negatif değildir ve baş katsayı pozitiftir. Bu yüzden her pozitif tamsayı \(r\) için \(P_n(r)>0\) olur. Yani pozitif kök hiç olamaz.
Rasyonel kök teoremine göre tamsayı kök, sabit terim \(d_0\)'ı bölmek zorundadır. O halde tek olasılıklar şunlardır:
1. \(r=0\), ama bu ancak \(d_0=0\) ise mümkündür,
2. \(r=-t\), burada \(t\) sayısı \(d_0\)'ın pozitif bir bölenidir; dolayısıyla \(1\le t\le9\).
Sabit bir \(t\ge1\) için kök koşulu
$$\sum_{i=0}^{L-1} d_i(-t)^i=0$$
şeklindedir. Basamakları sağdan ikili gruplara ayıralım:
$$e_j=d_{2j},\qquad o_j=d_{2j+1},$$
üstte eksik kalan tek basamak varsa \(o_j=0\) alınır. Böylece
$$P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}$$
olur.
Çözüm \(c_j\) taşıma değerlerini tanıtıp
$$e_j-to_j=c_j-t^2c_{j+1},\qquad c_0=0$$
koşulunu uygular. Buradan bir sonraki taşıma
$$c_{j+1}=\frac{to_j+c_j-e_j}{t^2}$$
olarak bulunur. C++ kodunda kullanılan geçiş tam olarak budur. Tabii bu adımın geçerli olması için payın her seferinde \(t^2\)'ye tam bölünmesi gerekir.
Neden bu doğru? Çünkü tüm çiftler toplandığında teleskopik bir ifade oluşur:
$$\sum_{j=0}^{s-1}(e_j-to_j)t^{2j} =\sum_{j=0}^{s-1}(c_j-t^2c_{j+1})t^{2j} =c_0-t^{2s}c_s.$$
\(c_0=0\) olduğundan, \(P_n(-t)=0\) olması için ve ancak son taşımanın da \(0\) olması gerekir. Böylece DP'nin tüm ara polinom değerini değil, yalnızca mevcut taşıma durumunu tutması yeterlidir.
\(n=121\) için
$$P_n(x)=x^2+2x+1=(x+1)^2,$$
dolayısıyla \(r=-1\) köktür. Burada \(t=1\) ve sağdan ikili basamaklar
$$ (e_0,o_0)=(1,2),\qquad (e_1,o_1)=(1,0) $$
şeklindedir. \(c_0=0\) ile başlarsak
$$c_1=\frac{1\cdot2+0-1}{1^2}=1,\qquad c_2=\frac{1\cdot0+1-1}{1^2}=0$$
elde edilir; son taşıma \(0\) olduğu için sayı kabul edilir.
Daha kısa bir örnek olarak \(n=24\) alınabilir. Burada \(P_n(x)=2x+4\) ve kök \(r=-2\)'dir. \(t=2\), \((e_0,o_0)=(4,2)\) olduğundan
$$c_1=\frac{2\cdot2+0-4}{2^2}=0$$
çıkar ve yine koşul sağlanır.
Sabit uzunluk \(L\), sabit son basamak \(d_0\) ve sabit kök adayı \(-t\) için bir sonraki taşıma yalnızca şu üç şeye bağlıdır:
1. mevcut taşıma \(c_j\),
2. seçilen çift-indeksli basamak \(e_j\),
3. seçilen tek-indeksli basamak \(o_j\).
Bu nedenle geçerli kısmi sayılar, taşıma durumları üzerinde sonlu durumlu bir DP ile sayılabilir. Böylece tüm \(10^L\) sayıların brute-force taraması gereksiz hale gelir.
Sabit bir \(d_0\neq0\) için \(d_0\)'ı bölen pozitif \(t\) kümesi çok küçüktür. En büyük durumlar \(d_0=6\) ve \(d_0=8\) olup sadece dört bölen verir; bu yüzden en fazla \(2^4-1=15\) boş olmayan altküme vardır.
Her kök altkümesi için DP şu taşıma vektörünü tutar:
$$\bigl(c_j^{(t_1)},c_j^{(t_2)},\dots\bigr).$$
Böylece aynı anda tüm bu kök koşullarını sağlayan sayılar sayılır. Sonrasında dahil etme-dışlama ile en az bir tamsayı kökü olan sayı sayısı elde edilir.
Buna güzel bir örnek \(n=132\)'dir:
$$P_n(x)=x^2+3x+2=(x+1)(x+2).$$
Yani aynı sayı hem \(-1\) hem \(-2\) kök koşuluna girer; inclusion-exclusion bu çift sayımı düzelterek sayıyı yalnızca bir kez bırakır.
Eğer \(d_0=0\) ise \(x=0\) zaten otomatik köktür. Kod bu durumu negatif köklerin inclusion-exclusion hesabına karıştırmadan doğrudan sayar.
Uzunluk \(L\ge2\) için sonu \(0\) ile biten pozitif \(L\) basamaklı sayı sayısı
$$9\cdot10^{L-2}$$
olur; çünkü ilk basamağın 9 seçeneği vardır, ortadaki \(L-2\) basamak serbesttir ve son basamak sabit olarak \(0\)'dır.
solve(max_power) fonksiyonu önce uzunlukları \(1,2,\dots,\texttt{max\_power}\) olan sayıları toplar. Bu, tam olarak \(1\) ile \(10^{\texttt{max\_power}}-1\) arasındaki sayıları kapsar.
Ardından
$$10^{\texttt{max\_power}}$$
sayısını ayrıca ekler; çünkü bu sayı da sonu \(0\) olduğu için kesin olarak \(x=0\) köküne sahiptir.
Uygulama üç kontrol yapar:
1. solve(3) ile \(1000\)'e kadar brute-force sayımı aynı olmalı; bu değer \(172\)'dir,
2. solve(4) ile \(10000\)'e kadar brute-force sayımı aynı olmalı; bu değer \(1754\)'tür,
3. solve(5) sonucu \(14696\) olmalı; bu da yayınlanmış \(Z(10^5)\) değeridir.
Bu üçü birlikte kök adaylarının sınırlandırılmasını, carry-DP'yi, inclusion-exclusion'ı ve uzunluk muhasebesini aynı anda doğrular.
count_subset_for_length(length, last_digit, roots), tek bir kök-kesişimi için çiftli basamak DP'sini çalıştırır. Durum haritası, mevcut taşıma vektörlerini ve bu duruma kaç farklı basamak atamasının ulaştığını saklar.
count_for_length(length) önce \(x=0\) kökünden gelen doğrudan katkıyı ekler, sonra \(1\) ile \(9\) arasındaki son basamakları dolaşır, \(d_0\)'ın bölenlerini çıkarır, tüm boş olmayan altkümeleri gezer ve dahil etme-dışlama uygular.
solve(max_power) tüm uzunlukları toplar ve son olarak \(10^{\texttt{max\_power}}\) sayısını ekler.
Komut satırında --power=<k> ve --skip-checkpoints seçenekleri vardır.
En fazla \(16\) basamak uzunluğu vardır. Her son basamak için bölen kümesi en fazla \(4\) elemanlı olduğundan altküme enumerasyonu çok küçüktür. Gerçek maliyeti belirleyen unsur erişilebilir taşıma durumlarının sayısıdır; bu da pratikte küçüktür.
Dolayısıyla yöntem, \(10^{16}\)'ya kadar doğrudan taramaya kıyasla çok büyük bir hız kazancı sağlar.
Escribamos un entero positivo \(n\) en decimal como \(d_{L-1}d_{L-2}\dots d_1d_0\), con \(d_{L-1}\neq0\). El problema asocia a \(n\) el polinomio
$$P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0.$$
Debemos contar cuántos enteros \(1\le n\le10^{16}\) hacen que \(P_n(x)\) tenga al menos una raíz entera.
Todos los coeficientes son cifras decimales, por lo que son no negativos y el coeficiente líder es positivo. Así, \(P_n(r)>0\) para todo entero positivo \(r\). Por tanto, no puede haber raíces positivas.
Por el teorema de la raíz racional, cualquier raíz entera debe dividir al término independiente \(d_0\). Solo quedan entonces:
1. \(r=0\), posible solo si \(d_0=0\),
2. \(r=-t\), donde \(t\) es un divisor positivo de \(d_0\), es decir \(1\le t\le9\).
Fijado \(t\ge1\), la condición es
$$\sum_{i=0}^{L-1} d_i(-t)^i=0.$$
Agrupamos las cifras por parejas desde la derecha:
$$e_j=d_{2j},\qquad o_j=d_{2j+1},$$
tomando \(o_j=0\) si falta la última cifra impar superior. Entonces
$$P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}.$$
La implementación introduce acarreos \(c_j\) y exige
$$e_j-to_j=c_j-t^2c_{j+1},\qquad c_0=0.$$
Despejando el siguiente acarreo se obtiene exactamente la transición del C++:
$$c_{j+1}=\frac{to_j+c_j-e_j}{t^2}.$$
Esta transición solo es válida cuando el numerador es divisible por \(t^2\).
La razón profunda es la identidad telescópica
$$\sum_{j=0}^{s-1}(e_j-to_j)t^{2j} =\sum_{j=0}^{s-1}(c_j-t^2c_{j+1})t^{2j} =c_0-t^{2s}c_s.$$
Como \(c_0=0\), la condición \(P_n(-t)=0\) equivale a exigir que el acarreo final también sea \(0\).
Si \(n=121\), entonces
$$P_n(x)=x^2+2x+1=(x+1)^2,$$
así que \(r=-1\) es raíz. Aquí \(t=1\), y las parejas de cifras desde la derecha son
$$ (e_0,o_0)=(1,2),\qquad (e_1,o_1)=(1,0). $$
Con \(c_0=0\), la recurrencia da
$$c_1=\frac{1\cdot2+0-1}{1^2}=1,\qquad c_2=\frac{1\cdot0+1-1}{1^2}=0.$$
El acarreo final es \(0\), así que la condición se cumple.
Para una longitud fija \(L\), una última cifra fija \(d_0\) y una raíz candidata fija \(-t\), el siguiente acarreo depende solo de:
1. el acarreo actual \(c_j\),
2. la cifra par elegida \(e_j\),
3. la cifra impar elegida \(o_j\).
Por eso podemos contar prefijos válidos con una DP finita sobre estados de acarreo, en lugar de recorrer todos los \(10^L\) números.
Para una última cifra fija \(d_0\neq0\), el conjunto de divisores positivos \(t\mid d_0\) es muy pequeño. Los casos máximos son \(d_0=6\) y \(d_0=8\), con solo cuatro divisores, así que hay como mucho \(2^4-1=15\) subconjuntos no vacíos.
Para cada subconjunto de raíces, la DP transporta un vector completo
$$\bigl(c_j^{(t_1)},c_j^{(t_2)},\dots\bigr),$$
y cuenta los números que satisfacen simultáneamente todas esas condiciones. Después, inclusión-exclusión transforma esas intersecciones en el número de enteros con al menos una raíz entera.
Un ejemplo sencillo de solapamiento es \(n=132\):
$$P_n(x)=x^2+3x+2=(x+1)(x+2).$$
El número pertenece a la vez al conteo para la raíz \(-1\), al de la raíz \(-2\), y al de su intersección. Inclusión-exclusión garantiza que al final cuente solo una vez.
Si \(d_0=0\), entonces \(x=0\) es automáticamente raíz. El código maneja ese caso directamente, sin mezclarlo con la inclusión-exclusión de las raíces negativas.
Para longitud \(L\ge2\), el número de enteros positivos de \(L\) cifras que terminan en \(0\) es
$$9\cdot10^{L-2}.$$
La función solve(max_power) suma todas las longitudes decimales \(1,2,\dots,\texttt{max\_power}\). Eso cuenta exactamente los números desde \(1\) hasta \(10^{\texttt{max\_power}}-1\).
Luego el código añade también
$$10^{\texttt{max\_power}},$$
que siempre tiene la raíz \(x=0\) porque termina en \(0\).
La implementación valida tres puntos:
1. solve(3) debe coincidir con el conteo brute-force hasta \(1000\), que vale \(172\),
2. solve(4) debe coincidir con el brute-force hasta \(10000\), que vale \(1754\),
3. solve(5) debe dar \(14696\), el valor publicado \(Z(10^5)\).
count_subset_for_length ejecuta la DP por parejas de cifras para una intersección fija de condiciones de raíces. El estado es un vector de acarreos actuales.
count_for_length añade primero la contribución directa de la raíz \(0\), luego recorre las últimas cifras \(1\) a \(9\), construye el conjunto de divisores de \(d_0\), itera sobre todos los subconjuntos no vacíos y aplica inclusión-exclusión.
solve suma todas las longitudes y finalmente añade \(10^{\texttt{max\_power}}\).
La línea de comandos acepta --power=<k> y --skip-checkpoints.
Solo hay hasta \(16\) longitudes relevantes. Para cada última cifra, el conjunto de divisores tiene tamaño a lo sumo \(4\), así que la enumeración de subconjuntos es minúscula. El coste real depende del número de estados de acarreo alcanzables, que en la práctica es pequeño.
Eso hace que el método sea enormemente más rápido que iterar directamente hasta \(10^{16}\).
把一个正整数 \(n\) 写成十进制形式 \(d_{L-1}d_{L-2}\dots d_1d_0\)，其中 \(d_{L-1}\neq0\)。题目把它对应为多项式
$$P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0.$$
我们要统计 \(1\le n\le10^{16}\) 中，使得 \(P_n(x)\) 至少有一个整数根的整数个数。
所有系数都是十进制数字，因此都是非负数，而首项系数严格为正。所以对任意正整数 \(r\)，都有 \(P_n(r)>0\)。这说明正整数根根本不可能出现。
再由有理根定理可知，任何整数根都必须整除常数项 \(d_0\)。因此只剩下两类可能：
1. \(r=0\)，这只会在 \(d_0=0\) 时发生，
2. \(r=-t\)，其中 \(t\) 是 \(d_0\) 的正因子，所以 \(1\le t\le9\)。
固定一个候选 \(t\ge1\)，则根条件为
$$\sum_{i=0}^{L-1} d_i(-t)^i=0.$$
把数字从低位开始两两分组：
$$e_j=d_{2j},\qquad o_j=d_{2j+1},$$
如果最高位缺少对应的奇数位置，就把该 \(o_j\) 视为 \(0\)。于是
$$P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}.$$
程序引入进位 \(c_j\)，并要求
$$e_j-to_j=c_j-t^2c_{j+1},\qquad c_0=0.$$
解出下一步进位，就得到 C++ 代码实际使用的转移：
$$c_{j+1}=\frac{to_j+c_j-e_j}{t^2}.$$
当然，只有当分子能被 \(t^2\) 整除时，这个转移才合法。
为什么这样做是对的？因为所有已处理的数位对加起来会望文生义地望见一个望远镜求和：
$$\sum_{j=0}^{s-1}(e_j-to_j)t^{2j} =\sum_{j=0}^{s-1}(c_j-t^2c_{j+1})t^{2j} =c_0-t^{2s}c_s.$$
由于 \(c_0=0\)，因此 \(P_n(-t)=0\) 当且仅当最终进位也回到 \(0\)。所以 DP 只需要记住当前进位，而不必保存完整的部分多项式值。
取 \(n=121\)。这时
$$P_n(x)=x^2+2x+1=(x+1)^2,$$
所以 \(r=-1\) 是根。此处 \(t=1\)，从低位开始的数位对为
$$ (e_0,o_0)=(1,2),\qquad (e_1,o_1)=(1,0). $$
从 \(c_0=0\) 出发，递推得到
$$c_1=\frac{1\cdot2+0-1}{1^2}=1,\qquad c_2=\frac{1\cdot0+1-1}{1^2}=0.$$
最终进位回到 \(0\)，因此根条件成立。
对固定长度 \(L\)、固定末位 \(d_0\)、固定候选根 \(-t\) 来说，下一步进位只依赖于：
1. 当前进位 \(c_j\)，
2. 选到的偶数位数字 \(e_j\)，
3. 选到的奇数位数字 \(o_j\)。
因此合法前缀的数量可以通过“进位状态”上的有限状态 DP 来统计，而不需要暴力扫描所有 \(10^L\) 个数。
对固定的末位 \(d_0\neq0\)，其正因子集合非常小。最大情况是 \(d_0=6\) 或 \(d_0=8\)，也不过四个因子，所以非空子集最多只有 \(2^4-1=15\) 个。
对于每个候选根子集，DP 同时携带一个进位向量
$$\bigl(c_j^{(t_1)},c_j^{(t_2)},\dots\bigr),$$
从而统计“同时满足这些根条件”的数字个数。然后再用容斥把这些交集数量合成为“至少有一个整数根”的总数。
一个简单的重叠例子是 \(n=132\)：
$$P_n(x)=x^2+3x+2=(x+1)(x+2).$$
所以它同时属于根 \(-1\) 的计数、根 \(-2\) 的计数，以及二者交集；容斥保证它最后只被算一次。
若 \(d_0=0\)，则 \(x=0\) 自动是根。代码把这类情况直接单独计数，而不是混入负根的容斥框架中。
当长度 \(L\ge2\) 时，以 \(0\) 结尾的正 \(L\) 位数共有
$$9\cdot10^{L-2}$$
个。
solve(max_power) 会把长度 \(1,2,\dots,\texttt{max\_power}\) 的情况全部累加起来，这正好覆盖从 \(1\) 到 \(10^{\texttt{max\_power}}-1\) 的所有整数。
最后程序再额外加上
$$10^{\texttt{max\_power}},$$
因为它末位是 \(0\)，所以一定有根 \(x=0\)。
程序使用三个 checkpoint 验证自身：
1. solve(3) 必须等于到 \(1000\) 为止的 brute-force 结果，即 \(172\)，
2. solve(4) 必须等于到 \(10000\) 为止的 brute-force 结果，即 \(1754\)，
3. solve(5) 必须等于 \(14696\)，也就是公布的 \(Z(10^5)\) 值。
count_subset_for_length 对某个固定的根条件交集运行“按两位一组”的 DP。状态映射保存当前进位向量以及到达该状态的数字方案数。
count_for_length 先加上根 \(0\) 的直接贡献，然后枚举末位 \(1\) 到 \(9\)，构造 \(d_0\) 的因子集合，遍历所有非空子集，并应用容斥。
solve 汇总所有长度，最后再加上 \(10^{\texttt{max\_power}}\) 本身。
命令行支持 --power=<k> 和 --skip-checkpoints。
相关十进制长度最多只有 \(16\) 个。对每个末位，因子集合大小最多是 \(4\)，因此子集枚举成本很低。真正的成本来自可达进位状态的数量，而它在实践中保持很小。
因此该算法远快于对所有 \(10^{16}\) 个整数逐个检查。
Пусть положительное число \(n\) записано в десятичном виде как \(d_{L-1}d_{L-2}\dots d_1d_0\), где \(d_{L-1}\neq0\). Ему сопоставляется полином
$$P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0.$$
Нужно посчитать, сколько чисел \(1\le n\le10^{16}\) имеют хотя бы один целый корень этого полинома.
Все коэффициенты являются десятичными цифрами, значит, неотрицательны, а старший коэффициент строго положителен. Поэтому \(P_n(r)>0\) для любого положительного целого \(r\). Следовательно, положительных целых корней быть не может.
По теореме о рациональных корнях любой целый корень обязан делить свободный член \(d_0\). Остаются только два типа:
1. \(r=0\), что возможно лишь при \(d_0=0\),
2. \(r=-t\), где \(t\) является положительным делителем \(d_0\), то есть \(1\le t\le9\).
Для фиксированного \(t\ge1\) требование имеет вид
$$\sum_{i=0}^{L-1} d_i(-t)^i=0.$$
Сгруппируем цифры по парам справа налево:
$$e_j=d_{2j},\qquad o_j=d_{2j+1},$$
а если верхней нечётной цифры нет, считаем соответствующее \(o_j=0\). Тогда
$$P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}.$$
Решение вводит переносы \(c_j\) и требует
$$e_j-to_j=c_j-t^2c_{j+1},\qquad c_0=0.$$
Отсюда следующий перенос выражается так:
$$c_{j+1}=\frac{to_j+c_j-e_j}{t^2}.$$
Именно эту формулу использует C++-код. Она допустима только тогда, когда числитель делится на \(t^2\).
Почему это правильно? Потому что при суммировании по всем обработанным парам возникает телескопическая формула
$$\sum_{j=0}^{s-1}(e_j-to_j)t^{2j} =\sum_{j=0}^{s-1}(c_j-t^2c_{j+1})t^{2j} =c_0-t^{2s}c_s.$$
Так как \(c_0=0\), условие \(P_n(-t)=0\) эквивалентно тому, что конечный перенос тоже равен нулю.
Возьмём \(n=121\). Тогда
$$P_n(x)=x^2+2x+1=(x+1)^2,$$
поэтому \(r=-1\) является корнем. Здесь \(t=1\), а пары цифр справа таковы:
$$ (e_0,o_0)=(1,2),\qquad (e_1,o_1)=(1,0). $$
При \(c_0=0\) рекурсия даёт
$$c_1=\frac{1\cdot2+0-1}{1^2}=1,\qquad c_2=\frac{1\cdot0+1-1}{1^2}=0.$$
Последний перенос равен \(0\), значит число принимается.
Для фиксированных длины \(L\), последней цифры \(d_0\) и кандидата \(-t\) следующий перенос зависит только от:
1. текущего переноса \(c_j\),
2. выбранной чётной цифры \(e_j\),
3. выбранной нечётной цифры \(o_j\).
Значит, число допустимых префиксов можно считать конечной DP по состояниям переносов, не перебирая все \(10^L\) чисел.
Для фиксированной последней цифры \(d_0\neq0\) множество положительных делителей \(t\mid d_0\) очень мало. Максимальные случаи \(d_0=6\) и \(d_0=8\) дают всего четыре делителя, а значит не более \(2^4-1=15\) непустых подмножеств.
Для каждого такого подмножества DP несёт целый вектор переносов
$$\bigl(c_j^{(t_1)},c_j^{(t_2)},\dots\bigr),$$
и считает числа, удовлетворяющие всем этим условиям одновременно. Затем включение-исключение превращает эти пересечения в количество чисел с хотя бы одним целым корнем.
Простой пример пересечения: \(n=132\), потому что
$$P_n(x)=x^2+3x+2=(x+1)(x+2).$$
Это число удовлетворяет условиям и для корня \(-1\), и для \(-2\), и для их пересечения; включение-исключение оставляет его в итоговом ответе ровно один раз.
Если \(d_0=0\), то \(x=0\) автоматически является корнем. Код обрабатывает этот случай напрямую, не смешивая его с включением-исключением по отрицательным корням.
Для длины \(L\ge2\) количество положительных \(L\)-значных чисел, оканчивающихся на \(0\), равно
$$9\cdot10^{L-2}.$$
Функция solve(max_power) суммирует все длины \(1,2,\dots,\texttt{max\_power}\), то есть считает числа от \(1\) до \(10^{\texttt{max\_power}}-1\).
После этого код добавляет ещё
$$10^{\texttt{max\_power}},$$
поскольку это число оканчивается на \(0\) и обязательно имеет корень \(x=0\).
В программе есть три контрольные проверки:
1. solve(3) должно совпадать с brute-force до \(1000\), то есть давать \(172\),
2. solve(4) должно совпадать с brute-force до \(10000\), то есть давать \(1754\),
3. solve(5) должно равняться \(14696\), опубликованному значению \(Z(10^5)\).
count_subset_for_length запускает DP по парам цифр для одного фиксированного пересечения корневых условий. Состояние карты есть вектор текущих переносов.
count_for_length сначала добавляет прямой вклад корня \(0\), затем перебирает последние цифры от \(1\) до \(9\), строит множество делителей \(d_0\), проходит по всем непустым подмножествам и применяет включение-исключение.
solve суммирует все длины и в конце добавляет \(10^{\texttt{max\_power}}\).
Командная строка понимает --power=<k> и --skip-checkpoints.
Рассматривается не более \(16\) десятичных длин. Для каждой последней цифры множество делителей имеет размер максимум \(4\), так что перебор подмножеств очень мал. Основные затраты определяются числом достижимых состояний переносов, а оно на практике невелико.
Поэтому метод на порядки быстрее прямого перебора всех чисел до \(10^{16}\).
لنكتب العدد الموجب \(n\) بالصورة العشرية \(d_{L-1}d_{L-2}\dots d_1d_0\) مع \(d_{L-1}\neq0\). عندئذ يعرّف السؤال كثير الحدود
$$P_n(x)=d_{L-1}x^{L-1}+d_{L-2}x^{L-2}+\cdots+d_1x+d_0.$$
المطلوب هو عدّ الأعداد \(1\le n\le10^{16}\) التي يملك فيها هذا كثير الحدود جذرًا صحيحًا واحدًا على الأقل.
جميع المعاملات أرقام عشرية، أي غير سالبة، كما أن المعامل الرئيس موجب. لذلك فإن \(P_n(r)>0\) لكل عدد صحيح موجب \(r\). إذن لا يمكن أن يوجد جذر صحيح موجب.
وبحسب نظرية الجذر النسبي، فإن أي جذر صحيح يجب أن يقسم الحد الثابت \(d_0\). لذلك تبقى حالتان فقط:
1. \(r=0\)، وهذا لا يحدث إلا إذا كان \(d_0=0\)،
2. \(r=-t\)، حيث \(t\) قاسم موجب لـ \(d_0\)، وبالتالي \(1\le t\le9\).
عند تثبيت \(t\ge1\)، يصبح الشرط
$$\sum_{i=0}^{L-1} d_i(-t)^i=0.$$
نجمع الأرقام في أزواج بدءًا من اليمين:
$$e_j=d_{2j},\qquad o_j=d_{2j+1},$$
وإذا لم توجد الخانة الفردية العليا نأخذ \(o_j=0\). عندها يصبح
$$P_n(-t)=\sum_{j\ge0}(e_j-to_j)t^{2j}.$$
يدخل الحل قيم حمل \(c_j\) ويفرض
$$e_j-to_j=c_j-t^2c_{j+1},\qquad c_0=0.$$
ومنها نحصل على انتقال الحالة التالي، وهو نفسه الموجود في C++:
$$c_{j+1}=\frac{to_j+c_j-e_j}{t^2}.$$
وطبعًا لا تكون هذه الخطوة صحيحة إلا إذا كان البسط قابلًا للقسمة على \(t^2\) في كل مرة.
سبب صحة هذه الفكرة هو التلسكوب التالي:
$$\sum_{j=0}^{s-1}(e_j-to_j)t^{2j} =\sum_{j=0}^{s-1}(c_j-t^2c_{j+1})t^{2j} =c_0-t^{2s}c_s.$$
وبما أن \(c_0=0\)، فإن \(P_n(-t)=0\) يتحقق إذا وفقط إذا عاد الحمل النهائي أيضًا إلى الصفر.
خذ \(n=121\). عندئذ
$$P_n(x)=x^2+2x+1=(x+1)^2,$$
ومن ثم فالجذر \(r=-1\) موجود. هنا \(t=1\)، وأزواج الأرقام من اليمين هي
$$ (e_0,o_0)=(1,2),\qquad (e_1,o_1)=(1,0). $$
بدءًا من \(c_0=0\) نحصل على
$$c_1=\frac{1\cdot2+0-1}{1^2}=1,\qquad c_2=\frac{1\cdot0+1-1}{1^2}=0.$$
ولأن الحمل النهائي يساوي \(0\)، فإن الشرط محقق.
عند تثبيت الطول \(L\)، والرقم الأخير \(d_0\)، والجذر المرشح \(-t\)، فإن الحمل التالي يعتمد فقط على:
1. الحمل الحالي \(c_j\)،
2. الرقم الزوجي المختار \(e_j\)،
3. الرقم الفردي المختار \(o_j\).
ولهذا يمكن عدّ السوابق الصحيحة بواسطة DP على حالات الحمل بدلًا من فحص جميع الأعداد الممكنة وعددها \(10^L\).
عند رقم أخير ثابت \(d_0\neq0\)، تكون مجموعة القواسم الموجبة \(t\mid d_0\) صغيرة جدًا. أكبر حالتين هما \(d_0=6\) و\(d_0=8\)، ولكل منهما أربعة قواسم فقط، أي بحد أقصى \(2^4-1=15\) مجموعة جزئية غير فارغة.
لكل مجموعة جزئية من الجذور المحتملة، تحمل DP متجهًا كاملًا من الحمولات
$$\bigl(c_j^{(t_1)},c_j^{(t_2)},\dots\bigr),$$
وبذلك تعدّ الأعداد التي تحقق جميع هذه الشروط معًا. ثم يحول مبدأ الاشتمال والاستبعاد هذه التقاطعات إلى عدد الأعداد التي لها جذر صحيح واحد على الأقل.
ومثال جميل على التداخل هو \(n=132\):
$$P_n(x)=x^2+3x+2=(x+1)(x+2).$$
إذن هذا العدد يحقق الجذر \(-1\) ويحقق أيضًا الجذر \(-2\)، كما ينتمي إلى تقاطعهما. ويضمن الاشتمال والاستبعاد أن يُحسب مرة واحدة فقط في النهاية.
إذا كان \(d_0=0\)، فإن \(x=0\) جذر تلقائيًا. لذلك يعامل الكود هذه الحالة مباشرة، من غير إدخالها في حسابات الاشتمال والاستبعاد الخاصة بالجذور السالبة.
وعندما يكون الطول \(L\ge2\)، فإن عدد الأعداد الموجبة ذات \(L\) خانة والمنتهية بـ \(0\) يساوي
$$9\cdot10^{L-2}.$$
تجمع الدالة solve(max_power) جميع الأطوال العشرية \(1,2,\dots,\texttt{max\_power}\)، وهذا يحصي الأعداد من \(1\) حتى \(10^{\texttt{max\_power}}-1\) تمامًا.
بعد ذلك يضيف الكود العدد
$$10^{\texttt{max\_power}},$$
لأنه ينتهي بصفر، وبالتالي يملك يقينًا الجذر \(x=0\).
يستخدم التنفيذ ثلاث نقاط تحقق:
1. يجب أن يساوي solve(3) العدّ brute-force حتى \(1000\)، أي \(172\)،
2. يجب أن يساوي solve(4) العدّ brute-force حتى \(10000\)، أي \(1754\)،
3. يجب أن يعطي solve(5) القيمة \(14696\)، وهي القيمة المنشورة \(Z(10^5)\).
count_subset_for_length يشغل DP على أزواج الأرقام لتقاطع واحد ثابت من شروط الجذور. حالة الخريطة هي متجه الحمولات الحالية.
count_for_length يضيف أولًا مساهمة الجذر \(0\)، ثم يمر على الأرقام الأخيرة من \(1\) إلى \(9\)، ويبني مجموعة قواسم \(d_0\)، ويمر على جميع المجموعات الجزئية غير الفارغة، ثم يطبق الاشتمال والاستبعاد.
solve يجمع جميع الأطوال ثم يضيف \(10^{\texttt{max\_power}}\) في النهاية.
تقبل الواجهة الوسيطين --power=<k> و--skip-checkpoints.
عدد الأطوال ذات الصلة لا يتجاوز \(16\). ولكل رقم أخير مجموعة قواسم لا يزيد حجمها على \(4\)، لذا فإن تعداد المجموعات الجزئية صغير جدًا. أما الكلفة الفعلية فتتحدد بعدد حالات الحمل القابلة للوصول، وهذا العدد يبقى صغيرًا عمليًا.
لذلك فهذه الطريقة أسرع بكثير من المرور المباشر على جميع الأعداد حتى \(10^{16}\).