Let \(X_0=1\) and let the sequence decay by independent random factors \(U_1,U_2,\dots\), each uniformly distributed on \((0,1)\), so that
$$X_n=\prod_{k=1}^{n} U_k.$$
The target constant \(c\) is defined by the probability condition
$$\Pr\!\left(X_n\le \frac{1}{c}\right)=0.25\qquad\text{for }n=10^7,$$
and the required output is \(\log_{10} c\). The key observation is that products of independent uniform variables become sums after taking logarithms, which turns the problem into a gamma-distribution quantile computation.
The implementations reduce the random-product statement to a single equation involving the regularized incomplete gamma function. Once that equation is inverted, the answer follows immediately.
Take minus logarithms and define
$$S_n=-\ln X_n=-\sum_{k=1}^{n}\ln U_k=\sum_{k=1}^{n}(-\ln U_k).$$
Therefore the event in the problem becomes
$$X_n\le \frac{1}{c}\iff -\ln X_n\ge \ln c\iff S_n\ge \ln c.$$
So the original probability condition is equivalent to
$$\Pr(S_n\ge \ln c)=0.25.$$
If \(U\sim \operatorname{Uniform}(0,1)\), then \(Y=-\ln U\) has density
$$f_Y(y)=e^{-y}\qquad (y\ge 0),$$
which is the exponential distribution with rate \(1\). Because the factors are independent, the variables \(Y_1,\dots,Y_n\) are independent as well, and hence
$$S_n=Y_1+\cdots+Y_n\sim \operatorname{Gamma}(n,1),$$
meaning shape \(n\) and scale \(1\).
For a gamma variable with shape \(n\) and scale \(1\), the lower and upper regularized incomplete gamma functions are
$$P(n,x)=\frac{\gamma(n,x)}{\Gamma(n)},\qquad Q(n,x)=\frac{\Gamma(n,x)}{\Gamma(n)}=1-P(n,x).$$
They satisfy
$$\Pr(S_n\le x)=P(n,x),\qquad \Pr(S_n\ge x)=Q(n,x).$$
Therefore the defining condition for \(c\) becomes
$$Q(n,\ln c)=0.25,$$
or equivalently
$$P(n,\ln c)=0.75.$$
When \(n\) is a positive integer, the upper tail can also be written as
$$Q(n,x)=e^{-x}\sum_{k=0}^{n-1}\frac{x^k}{k!},$$
but for \(n=10^7\) this identity is conceptually useful rather than computationally attractive.
Set
$$x=\ln c.$$
Then \(x\) is exactly the 75th percentile of the \(\operatorname{Gamma}(n,1)\) distribution:
$$x=P^{-1}(n,0.75).$$
Once \(x\) is known, the requested quantity is not \(c\) itself but its base-10 logarithm, so
$$\log_{10} c=\frac{\ln c}{\ln 10}=\frac{x}{\ln 10}.$$
This is numerically important because \(c\) is astronomically large, while \(\log_{10} c\) is easy to store and print.
The C++ implementation computes the gamma quantile directly. The Python and Java implementations instead use the Wilson-Hilferty approximation for a large gamma quantile:
$$x\approx n\left(1-\frac{1}{9n}+\frac{z}{3\sqrt{n}}\right)^3,$$
where
$$z=\Phi^{-1}(0.75)\approx 0.6744897501960817.$$
Because \(n=10^7\) is enormous, this approximation is already very sharp for a result that is ultimately printed to two decimal places.
Using the same approximation with \(n=100\), we get
$$x\approx 100\left(1-\frac{1}{900}+\frac{0.6744897502}{30}\right)^3\approx 106.52.$$
Hence
$$\log_{10} c\approx \frac{106.52}{\ln 10}\approx 46.27.$$
This matches the numerical checkpoint used by the exact computation to two decimal places. It also explains why the asymptotic formula is trusted for the much larger target value \(n=10^7\).
All three implementations first translate the probability question into the gamma-quantile problem \(P(n,x)=0.75\) with \(x=\ln c\), and then return \(x/\ln 10\).
The C++ implementation evaluates that quantile directly with a special-function routine for the inverse lower regularized incomplete gamma function. It also performs two sanity checks: one at \(n=100\), where the expected printed value is \(46.27\) to two decimals, and one at \(n=10^7\), where substituting the computed \(x\) back into the upper regularized gamma function must recover \(0.25\) to high precision.
The Python and Java implementations take the asymptotic route. They hard-code the 75th percentile of the standard normal distribution, plug it into the Wilson-Hilferty cubic approximation for the gamma quantile, and finally divide by \(\ln 10\). That replaces a special-function inversion by a short sequence of elementary floating-point operations.
For the single target input \(n=10^7\), all implementations use \(O(1)\) memory. The Python and Java versions run in \(O(1)\) time with only a handful of arithmetic operations. The C++ version is also \(O(1)\) at the algorithmic level for a fixed \(n\), but its constant factor is larger because it performs a numerical inversion of a special function and then verifies the result with another special-function evaluation.
Sei \(X_0=1\) und die Folge zerfalle durch unabhängige Zufallsfaktoren \(U_1,U_2,\dots\), die jeweils gleichverteilt auf \((0,1)\) sind, also
$$X_n=\prod_{k=1}^{n} U_k.$$
Gesucht ist die Konstante \(c\), die durch
$$\Pr\!\left(X_n\le \frac{1}{c}\right)=0.25,\qquad n=10^7.$$
definiert ist; auszugeben ist \(\log_{10} c\). Der entscheidende Trick besteht darin, das Produkt per Logarithmus in eine Summe umzuwandeln. Danach ist das Problem keine direkte Zufallssimulation mehr, sondern die Inversion eines Gamma-Quantils.
Die Implementierungen führen die Aufgabenstellung auf eine einzige Gleichung mit der regularisierten unvollständigen Gammafunktion zurück. Ist diese Gleichung gelöst, erhält man die gesuchte Zehnerlogarithmus-Ausgabe sofort.
Wir betrachten den negativen Logarithmus:
$$S_n=-\ln X_n=-\sum_{k=1}^{n}\ln U_k=\sum_{k=1}^{n}(-\ln U_k).$$
Damit gilt für das Ereignis aus der Aufgabe
$$X_n\le \frac{1}{c}\iff -\ln X_n\ge \ln c\iff S_n\ge \ln c.$$
Die gesuchte Wahrscheinlichkeit lässt sich also schreiben als
$$\Pr(S_n\ge \ln c)=0.25.$$
Für \(U\sim \operatorname{Uniform}(0,1)\) besitzt \(Y=-\ln U\) die Dichte
$$f_Y(y)=e^{-y}\qquad (y\ge 0),$$
also eine Exponentialverteilung mit Rate \(1\). Wegen der Unabhängigkeit der Faktoren sind auch \(Y_1,\dots,Y_n\) unabhängig, und daher folgt
$$S_n=Y_1+\cdots+Y_n\sim \operatorname{Gamma}(n,1).$$
Die Summe der logarithmischen Zerfallsschritte ist somit gammaverteilt mit Formparameter \(n\) und Skalenparameter \(1\).
Für eine \(\operatorname{Gamma}(n,1)\)-verteilte Zufallsvariable definieren wir
$$P(n,x)=\frac{\gamma(n,x)}{\Gamma(n)},\qquad Q(n,x)=\frac{\Gamma(n,x)}{\Gamma(n)}=1-P(n,x).$$
Dann gilt
$$\Pr(S_n\le x)=P(n,x),\qquad \Pr(S_n\ge x)=Q(n,x).$$
Die Bedingung der Aufgabe wird also zu
$$Q(n,\ln c)=0.25,$$
beziehungsweise äquivalent
$$P(n,\ln c)=0.75.$$
Für ganzzahliges \(n\) existiert zusätzlich die Darstellung
$$Q(n,x)=e^{-x}\sum_{k=0}^{n-1}\frac{x^k}{k!},$$
die die Verbindung zu einer Poisson-Summe zeigt, aber für \(n=10^7\) nicht die praktischste Rechenform ist.
Setzen wir
$$x=\ln c,$$
dann ist \(x\) genau das 75%-Quantil der Verteilung \(\operatorname{Gamma}(n,1)\):
$$x=P^{-1}(n,0.75).$$
Danach muss nicht \(c\) selbst ausgegeben werden, sondern nur sein Zehnerlogarithmus:
$$\log_{10} c=\frac{\ln c}{\ln 10}=\frac{x}{\ln 10}.$$
Gerade dieser Schritt verhindert den Umgang mit einer gigantischen Zahl \(c\) und reduziert alles auf eine gut skalierte Fließkommazahl.
Die C++-Implementierung bestimmt das Gamma-Quantil direkt. Die Python- und Java-Implementierungen verwenden stattdessen die Wilson-Hilferty-Näherung
$$x\approx n\left(1-\frac{1}{9n}+\frac{z}{3\sqrt{n}}\right)^3,$$
wobei
$$z=\Phi^{-1}(0.75)\approx 0.6744897501960817.$$
Da \(n=10^7\) extrem groß ist, ist diese Approximation für eine Ausgabe mit zwei Nachkommastellen bereits sehr präzise.
Mit derselben Formel erhält man für \(n=100\)
$$x\approx 100\left(1-\frac{1}{900}+\frac{0.6744897502}{30}\right)^3\approx 106.52.$$
Daraus folgt
$$\log_{10} c\approx \frac{106.52}{\ln 10}\approx 46.27.$$
Genau dieser Wert wird als Kontrollpunkt verwendet. Das direkte Gamma-Quantil und die asymptotische Formel stimmen hier bereits auf die ausgegebenen zwei Dezimalstellen überein.
Alle drei Implementierungen führen zunächst die Wahrscheinlichkeitsaussage auf das Quantilproblem \(P(n,x)=0.75\) mit \(x=\ln c\) zurück und geben anschließend \(x/\ln 10\) aus.
Die C++-Implementierung verwendet dafür eine Spezialfunktionsroutine, die das inverse untere regularisierte Gamma direkt berechnet. Anschließend wird das Ergebnis zweimal plausibilisiert: einmal für \(n=100\), wo der auszugebende Wert \(46.27\) beträgt, und einmal für \(n=10^7\), wo das zurückeingesetzte \(x\) den oberen Gamma-Anteil \(0.25\) mit hoher Genauigkeit reproduzieren muss.
Die Python- und Java-Implementierungen verzichten auf diese direkte Inversion. Sie setzen stattdessen das 75%-Quantil der Standardnormalverteilung in die Wilson-Hilferty-Formel ein, erhalten so eine Näherung für \(x=\ln c\) und teilen dann durch \(\ln 10\). Rechnerisch bleibt damit nur eine sehr kleine Anzahl elementarer Gleitkommaoperationen.
Für den einzelnen Zielwert \(n=10^7\) benötigen alle Implementierungen \(O(1)\) Speicher. Python und Java laufen in \(O(1)\) Zeit mit nur wenigen arithmetischen Operationen. Auch die C++-Variante ist algorithmisch \(O(1)\) für festes \(n\), hat aber einen größeren konstanten Aufwand, weil ein numerisches Spezialfunktions-Quantil berechnet und anschließend noch überprüft wird.
\(X_0=1\) olsun ve dizi, \((0,1)\) aralığında bağımsız ve düzgün dağılan \(U_1,U_2,\dots\) rastgele çarpanlarıyla azalsın:
$$X_n=\prod_{k=1}^{n} U_k.$$
Aranan sabit \(c\),
$$\Pr\!\left(X_n\le \frac{1}{c}\right)=0.25,\qquad n=10^7.$$
koşuluyla tanımlanır; çıktı olarak \(\log_{10} c\) istenir. Temel fikir, devasa bir rastgele çarpımı doğrudan incelemek yerine logaritma alıp problemi gamma dağılımının bir yüzdelik noktasına çevirmektir.
Uygulamalar, çarpım formundaki olasılık koşulunu regularized incomplete gamma fonksiyonuyla yazılan tek bir denkleme indirger. O denklem çözüldüğünde cevap doğrudan elde edilir.
Eksi logaritma alalım:
$$S_n=-\ln X_n=-\sum_{k=1}^{n}\ln U_k=\sum_{k=1}^{n}(-\ln U_k).$$
Böylece problemdeki olay
$$X_n\le \frac{1}{c}\iff -\ln X_n\ge \ln c\iff S_n\ge \ln c$$
şeklini alır. Dolayısıyla aranan koşul
$$\Pr(S_n\ge \ln c)=0.25$$
olur.
\(U\sim \operatorname{Uniform}(0,1)\) ise \(Y=-\ln U\) değişkeninin yoğunluğu
$$f_Y(y)=e^{-y}\qquad (y\ge 0)$$
olur; bu da oranı \(1\) olan üstel dağılımdır. Çarpanlar bağımsız olduğundan \(Y_1,\dots,Y_n\) da bağımsızdır. Bu yüzden
$$S_n=Y_1+\cdots+Y_n\sim \operatorname{Gamma}(n,1)$$
elde edilir. Yani toplam, şekil parametresi \(n\), ölçek parametresi \(1\) olan gamma dağılımına uyar.
Alt ve üst regularized incomplete gamma fonksiyonlarını
$$P(n,x)=\frac{\gamma(n,x)}{\Gamma(n)},\qquad Q(n,x)=\frac{\Gamma(n,x)}{\Gamma(n)}=1-P(n,x)$$
diye tanımlayalım. Gamma dağılımı için
$$\Pr(S_n\le x)=P(n,x),\qquad \Pr(S_n\ge x)=Q(n,x)$$
olduğundan problem koşulu
$$Q(n,\ln c)=0.25$$
ve eşdeğer olarak
$$P(n,\ln c)=0.75$$
haline gelir. \(n\) tam sayı olduğunda ayrıca
$$Q(n,x)=e^{-x}\sum_{k=0}^{n-1}\frac{x^k}{k!}$$
yazılabilir; fakat \(n=10^7\) için doğrudan kullanılacak en uygun form bu değildir.
$$x=\ln c$$
dersek, \(x\) tam olarak \(\operatorname{Gamma}(n,1)\) dağılımının %75 yüzdelik noktasıdır:
$$x=P^{-1}(n,0.75).$$
Bundan sonra \(c\)'nin kendisini üretmek gerekmiyor; soru zaten \(\log_{10} c\) istediği için
$$\log_{10} c=\frac{\ln c}{\ln 10}=\frac{x}{\ln 10}$$
hesaplanması yeterlidir. Böylece astronomik büyüklükte bir sayı yerine rahatça yazdırılabilen bir logaritma ile çalışırız.
C++ uygulaması gamma yüzdelik noktasını doğrudan hesaplar. Python ve Java uygulamaları ise Wilson-Hilferty yaklaşımını kullanır:
$$x\approx n\left(1-\frac{1}{9n}+\frac{z}{3\sqrt{n}}\right)^3,$$
burada
$$z=\Phi^{-1}(0.75)\approx 0.6744897501960817.$$
\(n=10^7\) çok büyük olduğundan bu yaklaşım iki ondalık basamaklık son çıktı için oldukça keskindir.
Aynı yaklaşım \(n=100\) için
$$x\approx 100\left(1-\frac{1}{900}+\frac{0.6744897502}{30}\right)^3\approx 106.52$$
verir. O halde
$$\log_{10} c\approx \frac{106.52}{\ln 10}\approx 46.27.$$
Bu değer, doğrudan gamma terslemesiyle yapılan sayısal kontrolle aynı iki ondalık çıktıyı verir. Bu da çok daha büyük olan \(n=10^7\) için yaklaşımın neden güvenilir olduğunu açıklar.
C++, Python ve Java uygulamalarının ortak noktası, önce olasılık sorusunu \(P(n,x)=0.75\) biçimindeki gamma yüzdelik denklemine çevirmeleri ve sonra \(x/\ln 10\) döndürmeleridir.
C++ uygulaması bunu bir özel fonksiyon kütüphanesi aracılığıyla doğrudan çözer. Ardından iki kontrol yapar: \(n=100\) için yazdırılması gereken değerin \(46.27\) olması ve hedef durumda bulunan \(x\) değeri tekrar üst regularized gamma içine yerleştirildiğinde \(0.25\) sonucunun yüksek doğrulukla geri gelmesi.
Python ve Java uygulamaları ise özel fonksiyon terslemesine gitmez. Standart normal dağılımın %75 yüzdelik noktasını sabit olarak alır, bunu Wilson-Hilferty kübik formülüne koyar, yaklaşık \(x=\ln c\) değerini elde eder ve son olarak \(\ln 10\)'a böler. Böylece işlem maliyeti birkaç temel kayan nokta işlemiyle sınırlı kalır.
Hedef giriş yalnızca tek bir \(n=10^7\) değeri olduğu için tüm uygulamalarda bellek kullanımı \(O(1)\)'dir. Python ve Java sürümleri sabit sayıda aritmetik işlem yaptığı için zaman karmaşıklığı da \(O(1)\)'dir. C++ sürümü de sabit giriş için \(O(1)\) düzeyindedir; ancak gamma yüzdelik terslemesi ve ardından doğrulama hesapları yaptığı için sabit katsayısı daha büyüktür.
Sea \(X_0=1\) y supongamos que la secuencia decae multiplicando por factores aleatorios independientes \(U_1,U_2,\dots\), cada uno uniforme en \((0,1)\), de modo que
$$X_n=\prod_{k=1}^{n} U_k.$$
La constante buscada \(c\) queda definida por
$$\Pr\!\left(X_n\le \frac{1}{c}\right)=0.25,\qquad n=10^7.$$
y lo que se debe imprimir es \(\log_{10} c\). La idea esencial es transformar el producto aleatorio en una suma mediante logaritmos; así el problema se vuelve un cálculo de cuantiles de una distribución gamma.
Las implementaciones convierten la condición probabilística original en una sola ecuación con la función gamma incompleta regularizada. Una vez invertida esa ecuación, el resultado pedido sale de forma inmediata.
Tomemos logaritmos con signo negativo:
$$S_n=-\ln X_n=-\sum_{k=1}^{n}\ln U_k=\sum_{k=1}^{n}(-\ln U_k).$$
Entonces el evento de interés se reescribe como
$$X_n\le \frac{1}{c}\iff -\ln X_n\ge \ln c\iff S_n\ge \ln c.$$
Por tanto, la condición del problema equivale a
$$\Pr(S_n\ge \ln c)=0.25.$$
Si \(U\sim \operatorname{Uniform}(0,1)\), entonces \(Y=-\ln U\) tiene densidad
$$f_Y(y)=e^{-y}\qquad (y\ge 0),$$
es decir, una distribución exponencial de tasa \(1\). Como los factores son independientes, también lo son \(Y_1,\dots,Y_n\), y en consecuencia
$$S_n=Y_1+\cdots+Y_n\sim \operatorname{Gamma}(n,1).$$
La suma de los pasos de decaimiento en escala logarítmica sigue, por tanto, una gamma con parámetro de forma \(n\) y escala \(1\).
Definamos
$$P(n,x)=\frac{\gamma(n,x)}{\Gamma(n)},\qquad Q(n,x)=\frac{\Gamma(n,x)}{\Gamma(n)}=1-P(n,x).$$
Para una variable \(\operatorname{Gamma}(n,1)\), se cumple
$$\Pr(S_n\le x)=P(n,x),\qquad \Pr(S_n\ge x)=Q(n,x).$$
Así, la ecuación que determina \(c\) es
$$Q(n,\ln c)=0.25,$$
o de forma equivalente
$$P(n,\ln c)=0.75.$$
Cuando \(n\) es entero positivo también puede escribirse
$$Q(n,x)=e^{-x}\sum_{k=0}^{n-1}\frac{x^k}{k!},$$
lo cual aclara la estructura algebraica del problema, aunque no es la vía más cómoda para \(n=10^7\).
Si definimos
$$x=\ln c,$$
entonces \(x\) es exactamente el percentil 75 de la distribución \(\operatorname{Gamma}(n,1)\):
$$x=P^{-1}(n,0.75).$$
Una vez hallado \(x\), no hace falta reconstruir \(c\) explícitamente; basta con usar
$$\log_{10} c=\frac{\ln c}{\ln 10}=\frac{x}{\ln 10}.$$
Eso evita trabajar con un número gigantesco y deja todo en una magnitud logarítmica estable.
La implementación en C++ calcula el cuantil gamma de forma directa. Las implementaciones en Python y Java usan la aproximación de Wilson-Hilferty:
$$x\approx n\left(1-\frac{1}{9n}+\frac{z}{3\sqrt{n}}\right)^3,$$
donde
$$z=\Phi^{-1}(0.75)\approx 0.6744897501960817.$$
Como \(n=10^7\) es enorme, esta fórmula ya es suficientemente precisa para un resultado final redondeado a dos decimales.
Aplicando la misma aproximación con \(n=100\), obtenemos
$$x\approx 100\left(1-\frac{1}{900}+\frac{0.6744897502}{30}\right)^3\approx 106.52.$$
Por tanto,
$$\log_{10} c\approx \frac{106.52}{\ln 10}\approx 46.27.$$
Ese valor coincide con el control numérico de la versión exacta a dos decimales, lo que da confianza adicional para el caso objetivo \(n=10^7\).
Las implementaciones en C++, Python y Java comparten el mismo objetivo matemático: resolver \(P(n,x)=0.75\) con \(x=\ln c\) y luego devolver \(x/\ln 10\).
La implementación en C++ usa una rutina de funciones especiales para invertir directamente la gamma regularizada inferior. Después valida el resultado en dos niveles: con \(n=100\), donde la salida esperada es \(46.27\), y con \(n=10^7\), donde al sustituir el \(x\) calculado en la cola superior regularizada debe recuperarse \(0.25\) con alta precisión.
Las implementaciones en Python y Java optan por la aproximación asintótica. Toman el percentil 75 de la normal estándar, lo insertan en la fórmula cúbica de Wilson-Hilferty, obtienen una aproximación para \(x=\ln c\) y finalmente dividen entre \(\ln 10\). El cálculo completo se reduce así a muy pocas operaciones elementales.
Para el único valor de entrada \(n=10^7\), todas las implementaciones consumen \(O(1)\) memoria. Las versiones en Python y Java ejecutan \(O(1)\) operaciones aritméticas. La versión en C++ también es \(O(1)\) para un \(n\) fijo, pero con una constante mayor porque realiza una inversión numérica de una función especial y luego una comprobación adicional.
设 \(X_0=1\)，并且序列每一步都乘上一个独立的随机衰减因子 \(U_1,U_2,\dots\)，其中每个 \(U_k\) 都在 \((0,1)\) 上服从均匀分布，于是
$$X_n=\prod_{k=1}^{n} U_k.$$
题目要求的常数 \(c\) 由下式定义：
$$\Pr\!\left(X_n\le \frac{1}{c}\right)=0.25,\qquad n=10^7.$$
最终输出的不是 \(c\) 本身，而是 \(\log_{10} c\)。真正的难点不在于模拟这个随机过程，而在于把随机乘积改写成一个可以稳定求解的分布分位数问题。
三份实现都把原始概率条件化成一个关于正则化不完全伽马函数的方程。只要把这个方程反解出来，答案就已经得到。
对乘积取负对数，定义
$$S_n=-\ln X_n=-\sum_{k=1}^{n}\ln U_k=\sum_{k=1}^{n}(-\ln U_k).$$
于是题目中的事件可以改写为
$$X_n\le \frac{1}{c}\iff -\ln X_n\ge \ln c\iff S_n\ge \ln c.$$
因此原条件完全等价于
$$\Pr(S_n\ge \ln c)=0.25.$$
这一步很关键，因为乘积的分布不直观，而和的分布可以直接识别。
若 \(U\sim \operatorname{Uniform}(0,1)\)，令 \(Y=-\ln U\)。容易验证 \(Y\) 的密度为
$$f_Y(y)=e^{-y}\qquad (y\ge 0),$$
也就是参数为 \(1\) 的指数分布。因为各个 \(U_k\) 相互独立，所以对应的 \(Y_1,\dots,Y_n\) 也相互独立，从而
$$S_n=Y_1+\cdots+Y_n\sim \operatorname{Gamma}(n,1).$$
换句话说，衰减过程在对数尺度下变成了 \(n\) 个独立指数变量之和，也就是形状参数为 \(n\)、尺度参数为 \(1\) 的伽马分布。
对 \(\operatorname{Gamma}(n,1)\) 分布，定义下侧与上侧正则化不完全伽马函数
$$P(n,x)=\frac{\gamma(n,x)}{\Gamma(n)},\qquad Q(n,x)=\frac{\Gamma(n,x)}{\Gamma(n)}=1-P(n,x).$$
它们正好满足
$$\Pr(S_n\le x)=P(n,x),\qquad \Pr(S_n\ge x)=Q(n,x).$$
于是决定 \(c\) 的方程就是
$$Q(n,\ln c)=0.25,$$
等价地写成
$$P(n,\ln c)=0.75.$$
若 \(n\) 是正整数，还可以写出
$$Q(n,x)=e^{-x}\sum_{k=0}^{n-1}\frac{x^k}{k!}.$$
这个公式说明了尾概率与有限级数之间的关系，但当 \(n=10^7\) 时，真正适合计算的方式仍然是直接求分位数，而不是显式展开这一和式。
令
$$x=\ln c,$$
那么 \(x\) 就是 \(\operatorname{Gamma}(n,1)\) 分布的 75% 分位点：
$$x=P^{-1}(n,0.75).$$
一旦求出 \(x\)，题目所需的量并不是 \(c\) 本身，而是它的常用对数，因此
$$\log_{10} c=\frac{\ln c}{\ln 10}=\frac{x}{\ln 10}.$$
这一步避免了直接处理一个极其巨大的 \(c\)，而只保留数量级信息。
C++ 实现直接求伽马分布分位点；Python 和 Java 实现则利用 Wilson-Hilferty 近似，把大参数伽马分布分位点写成
$$x\approx n\left(1-\frac{1}{9n}+\frac{z}{3\sqrt{n}}\right)^3,$$
其中
$$z=\Phi^{-1}(0.75)\approx 0.6744897501960817.$$
由于目标参数 \(n=10^7\) 极大，这个近似在最终只保留两位小数的场景下已经足够精确。它本质上把伽马分布分位点与标准正态分位点联系起来，从而省掉了专门的特殊函数反演。
把 \(n=100\) 代入同一个近似式，得到
$$x\approx 100\left(1-\frac{1}{900}+\frac{0.6744897502}{30}\right)^3\approx 106.52.$$
于是
$$\log_{10} c\approx \frac{106.52}{\ln 10}\approx 46.27.$$
这个结果与精确分位数计算在两位小数上吻合，因此也解释了为什么在更大的 \(n=10^7\) 下，渐近公式仍然可以作为有效实现方案。
C++、Python 和 Java 实现虽然数值路线不同，但共同目标完全一致：先求解 \(P(n,x)=0.75\) 中的 \(x=\ln c\)，再输出 \(x/\ln 10\)。
C++ 实现走的是精确数值路线。它调用特殊函数库直接反解下侧正则化不完全伽马函数，然后做两类校验：一类是 \(n=100\) 时结果应打印为 \(46.27\)；另一类是目标参数 \(n=10^7\) 下，把算出的 \(x\) 代回上侧正则化不完全伽马函数后，必须高精度地返回 \(0.25\)。
Python 和 Java 实现则选择近似路线。它们把标准正态分布的 75% 分位点当作常数，代入 Wilson-Hilferty 三次公式得到 \(x\approx \ln c\)，然后除以 \(\ln 10\) 并按两位小数格式输出。这样整套计算只需要很少的浮点运算。
对于唯一的目标输入 \(n=10^7\)，三种实现的空间复杂度都是 \(O(1)\)。Python 和 Java 版本只做常数次基本运算，因此时间复杂度也是 \(O(1)\)。C++ 版本对固定 \(n\) 同样可以视为 \(O(1)\)，只是常数项更大，因为它需要执行一次特殊函数的数值反演，并在此后再做一次高精度验证。
Пусть \(X_0=1\), а затем последовательность убывает за счёт независимых случайных множителей \(U_1,U_2,\dots\), каждый из которых равномерно распределён на \((0,1)\). Тогда
$$X_n=\prod_{k=1}^{n} U_k.$$
Искомая константа \(c\) определяется условием
$$\Pr\!\left(X_n\le \frac{1}{c}\right)=0.25,\qquad n=10^7.$$
а вывести нужно \(\log_{10} c\). Главная идея решения состоит в том, чтобы заменить случайное произведение суммой логарифмов и тем самым свести задачу к вычислению квантили гамма-распределения.
Все реализации переводят исходное вероятностное условие в одно уравнение с регуляризованной неполной гамма-функцией. После инверсии этого уравнения ответ получается напрямую.
Возьмём отрицательный логарифм и введём
$$S_n=-\ln X_n=-\sum_{k=1}^{n}\ln U_k=\sum_{k=1}^{n}(-\ln U_k).$$
Тогда событие из условия переписывается так:
$$X_n\le \frac{1}{c}\iff -\ln X_n\ge \ln c\iff S_n\ge \ln c.$$
Следовательно, исходное требование эквивалентно равенству
$$\Pr(S_n\ge \ln c)=0.25.$$
Если \(U\sim \operatorname{Uniform}(0,1)\), то случайная величина \(Y=-\ln U\) имеет плотность
$$f_Y(y)=e^{-y}\qquad (y\ge 0),$$
то есть экспоненциальное распределение с параметром \(1\). Независимость множителей означает независимость \(Y_1,\dots,Y_n\), поэтому
$$S_n=Y_1+\cdots+Y_n\sim \operatorname{Gamma}(n,1).$$
Итак, логарифм случайного затухания оказывается суммой \(n\) независимых экспоненциальных величин.
Обозначим
$$P(n,x)=\frac{\gamma(n,x)}{\Gamma(n)},\qquad Q(n,x)=\frac{\Gamma(n,x)}{\Gamma(n)}=1-P(n,x).$$
Тогда для распределения \(\operatorname{Gamma}(n,1)\)
$$\Pr(S_n\le x)=P(n,x),\qquad \Pr(S_n\ge x)=Q(n,x).$$
Значит, определяющее условие для \(c\) принимает вид
$$Q(n,\ln c)=0.25,$$
или, что то же самое,
$$P(n,\ln c)=0.75.$$
Для целого \(n\) есть также формула
$$Q(n,x)=e^{-x}\sum_{k=0}^{n-1}\frac{x^k}{k!},$$
но при \(n=10^7\) её удобно рассматривать скорее как теоретическую, чем как вычислительную.
Положим
$$x=\ln c.$$
Тогда \(x\) есть ровно 75%-квантиль распределения \(\operatorname{Gamma}(n,1)\):
$$x=P^{-1}(n,0.75).$$
После этого остаётся только перейти к десятичному логарифму:
$$\log_{10} c=\frac{\ln c}{\ln 10}=\frac{x}{\ln 10}.$$
Это особенно удобно, потому что само число \(c\) чудовищно велико, а его логарифм остаётся вполне управляемой величиной.
Реализация на C++ вычисляет гамма-квантиль напрямую. Реализации на Python и Java вместо этого используют приближение Уилсона-Хилферти:
$$x\approx n\left(1-\frac{1}{9n}+\frac{z}{3\sqrt{n}}\right)^3,$$
где
$$z=\Phi^{-1}(0.75)\approx 0.6744897501960817.$$
Поскольку здесь \(n=10^7\), эта асимптотическая формула уже даёт очень точный результат для ответа, который печатается лишь с двумя знаками после запятой.
Подставляя \(n=100\), получаем
$$x\approx 100\left(1-\frac{1}{900}+\frac{0.6744897502}{30}\right)^3\approx 106.52.$$
Следовательно,
$$\log_{10} c\approx \frac{106.52}{\ln 10}\approx 46.27.$$
Именно это значение используется как проверка. Оно совпадает с точным численным вычислением на уровне двух печатаемых десятичных знаков.
Реализации на C++, Python и Java опираются на одну и ту же математику: сначала решается уравнение \(P(n,x)=0.75\) для \(x=\ln c\), после чего возвращается \(x/\ln 10\).
Реализация на C++ идёт по точному пути и вызывает специальную численную процедуру для обращения нижней регуляризованной гамма-функции. Затем выполняются две проверки: при \(n=100\) печатаемое значение должно быть \(46.27\), а при \(n=10^7\) подстановка найденного \(x\) в верхнюю регуляризованную гамма-функцию должна вернуть \(0.25\) с высокой точностью.
Реализации на Python и Java используют асимптотику. Они берут 75%-квантиль стандартного нормального распределения, подставляют его в формулу Уилсона-Хилферти, получают приближение для \(x=\ln c\), делят на \(\ln 10\) и форматируют результат до двух десятичных знаков.
Для единственного целевого входа \(n=10^7\) все реализации требуют \(O(1)\) памяти. В версиях на Python и Java время работы равно \(O(1)\), поскольку там выполняется лишь константное число элементарных операций. Версия на C++ также является \(O(1)\) для фиксированного \(n\), но её константный множитель больше из-за численного обращения специальной функции и последующей проверки результата.
لنفرض أن \(X_0=1\)، وأن المتتالية تتناقص في كل خطوة بضربها في عوامل عشوائية مستقلة \(U_1,U_2,\dots\)، حيث كل عامل موزع بانتظام على الفترة \((0,1)\). عندئذ
$$X_n=\prod_{k=1}^{n} U_k.$$
الثابت المطلوب \(c\) يحدده الشرط
$$\Pr\!\left(X_n\le \frac{1}{c}\right)=0.25,\qquad n=10^7.$$
والمطلوب في النهاية هو \(\log_{10} c\) وليس \(c\) نفسه. الفكرة الأساسية هي أن الضرب العشوائي يصبح جمعًا بعد أخذ اللوغاريتم، وبهذا تتحول المسألة إلى مسألة إيجاد رتبة مئوية لتوزيع غاما.
كل التطبيقات تختزل الشرط الاحتمالي الأصلي إلى معادلة واحدة تحتوي على دالة غاما غير التامة المنتظمة. وبعد عكس هذه المعادلة يصبح الجواب مباشرًا.
نأخذ اللوغاريتم السالب ونعرف
$$S_n=-\ln X_n=-\sum_{k=1}^{n}\ln U_k=\sum_{k=1}^{n}(-\ln U_k).$$
وعندها يصبح الحدث في المسألة
$$X_n\le \frac{1}{c}\iff -\ln X_n\ge \ln c\iff S_n\ge \ln c.$$
إذن الشرط المطلوب يكافئ
$$\Pr(S_n\ge \ln c)=0.25.$$
إذا كان \(U\sim \operatorname{Uniform}(0,1)\)، فإن المتغير \(Y=-\ln U\) يملك الكثافة
$$f_Y(y)=e^{-y}\qquad (y\ge 0),$$
وهذا هو التوزيع الأسي ذو المعدل \(1\). وبما أن العوامل مستقلة، فإن \(Y_1,\dots,Y_n\) مستقلة أيضًا، وبالتالي
$$S_n=Y_1+\cdots+Y_n\sim \operatorname{Gamma}(n,1).$$
أي إن مجموع خطوات التناقص على المقياس اللوغاريتمي يتبع توزيع غاما بمعامل شكل \(n\) ومعامل قياس \(1\).
نعرّف
$$P(n,x)=\frac{\gamma(n,x)}{\Gamma(n)},\qquad Q(n,x)=\frac{\Gamma(n,x)}{\Gamma(n)}=1-P(n,x).$$
وعندئذ لتوزيع \(\operatorname{Gamma}(n,1)\) نحصل على
$$\Pr(S_n\le x)=P(n,x),\qquad \Pr(S_n\ge x)=Q(n,x).$$
ومن ثم يصبح شرط المسألة
$$Q(n,\ln c)=0.25,$$
أو بصورة مكافئة
$$P(n,\ln c)=0.75.$$
وعندما يكون \(n\) عددًا صحيحًا موجبًا يمكن أيضًا كتابة
$$Q(n,x)=e^{-x}\sum_{k=0}^{n-1}\frac{x^k}{k!},$$
لكن هذه الصيغة مفيدة للفهم أكثر من كونها الصيغة الأنسب للحساب عندما يكون \(n=10^7\).
لنكتب
$$x=\ln c.$$
عندها يكون \(x\) هو تمامًا الرتبة المئوية \(75\%\) لتوزيع \(\operatorname{Gamma}(n,1)\):
$$x=P^{-1}(n,0.75).$$
وبعد إيجاد \(x\)، لا نحتاج إلى تكوين \(c\) نفسه، لأن المطلوب أصلًا هو
$$\log_{10} c=\frac{\ln c}{\ln 10}=\frac{x}{\ln 10}.$$
وهذا يوفر التعامل مع عدد هائل جدًا ويُبقي الحساب في صورة لوغاريتمية مستقرة.
تطبيق C++ يحسب رتبة غاما المئوية مباشرة. أما تطبيقا Python وJava فيستخدمان تقريب ويلسون-هيلفرتي:
$$x\approx n\left(1-\frac{1}{9n}+\frac{z}{3\sqrt{n}}\right)^3,$$
حيث
$$z=\Phi^{-1}(0.75)\approx 0.6744897501960817.$$
وبما أن \(n=10^7\) كبير جدًا، فإن هذا التقريب يكون دقيقًا بما يكفي لنتيجة نهائية ستُطبع مع منزلتين عشريتين فقط.
عند التعويض بـ \(n=100\) في الصيغة نفسها نحصل على
$$x\approx 100\left(1-\frac{1}{900}+\frac{0.6744897502}{30}\right)^3\approx 106.52.$$
ومن ثم
$$\log_{10} c\approx \frac{106.52}{\ln 10}\approx 46.27.$$
وهذه هي قيمة التحقق المعتمدة في الحساب الدقيق أيضًا، ولذلك فهي تعطي ثقة إضافية في استخدام الصيغة التقريبية عندما يكون \(n=10^7\).
تتفق تطبيقات C++ وPython وJava في الجوهر الرياضي: أولًا يُحل الشرط \(P(n,x)=0.75\) من أجل \(x=\ln c\)، ثم يُعاد الناتج على صورة \(x/\ln 10\).
تطبيق C++ يسلك الطريق العددي الدقيق، فيستخدم أداة دوال خاصة لعكس دالة غاما المنتظمة السفلية مباشرة. بعد ذلك يجري تحققين: تحققًا عند \(n=100\) حيث يجب أن تكون القيمة المطبوعة \(46.27\)، وتحققًا عند \(n=10^7\) بحيث تؤدي إعادة إدخال \(x\) في ذيل غاما العلوي المنتظم إلى استرجاع \(0.25\) بدقة عالية.
أما تطبيقا Python وJava فيسلكان طريق التقريب. فهما يأخذان الرتبة المئوية \(75\%\) للتوزيع الطبيعي المعياري، ويضعانها في صيغة ويلسون-هيلفرتي التكعيبية للحصول على تقريب لـ \(x=\ln c\)، ثم يقسمان على \(\ln 10\) ويطبعان الناتج حتى منزلتين عشريتين.
للقيمة المستهدفة الوحيدة \(n=10^7\)، تحتاج جميع التطبيقات إلى ذاكرة \(O(1)\). تطبيقا Python وJava ينفذان عددًا ثابتًا من العمليات الحسابية، لذا زمنهما \(O(1)\). أما تطبيق C++ فهو أيضًا \(O(1)\) عند اعتبار \(n\) ثابتًا، لكن معامل الزمن الثابت فيه أكبر لأنه يتضمن عكسًا عدديًا لدالة خاصة ثم خطوة تحقق إضافية.