当我们的首席数学家正在准备答案时，这里有一个有点愚蠢（由于适应Numba）的代码，它使用加速Numba.njit在 6 秒内计算出所需的值。 （如果没有Numba达到 1 亿，它会在 1.5 分钟内完成脱粒，这仍然比用 Python 无限 -s 计算要好得多int。）确实，它对结果的绝对准确性留下了一些疑问，因为计算是在浮点数中完成的点数。在某些特殊情况下，...999999所需的结果可能出现在数字的末尾，或者可能找不到。尽管可以在最后一位（这是什么？）数字上加 1，然后修剪数字。好吧，你可以写得更通用，速度更快，但看起来这已经很正常了。

import math
from numba import njit

@njit
def fact(n):
    f = 1
    i = 2
    flag1 = True
    flag2 = True
    flag3 = True
    flag4 = True
    flag5 = True
    while i <= n:
        f *= i
        while f >= 10:
            f /= 10
        if flag1 and math.floor(f * 10000) == 11533:
            print(f'{i}!', f)
            flag1 = False
        if flag2 and math.floor(f * 10000) == 51261:
            print(f'{i}!', f)
            flag2 = False
        if flag3 and math.floor(f * 100000) == 113131:
            print(f'{i}!', f)
            flag3 = False
        if flag4 and math.floor(f * 100000) == 131091:
            print(f'{i}!', f)
            flag4 = False
        if flag5 and math.floor(f * 100000000) == 151192033:
            print(f'{i}!', f)
            flag5 = False
        i += 1

fact(100_000_000)

结论：

16641! 1.153311564705438
46978! 5.126194982442562
266538! 1.3109139672369952
323172! 1.1313167610953019
37773304! 1.5119203331946358

数字总是被简化为 的形式x.xxxxxx，这样稍后您就不必在比较之前计算需要乘以多少位数字。因此，输出具有相同的外观。

PS 在纯Python中，我也显示了名称，但Numba我很挑剔，我不喜欢原生Python类型，特别是我无法立即赢得字典。这就是为什么它如此笨拙。

PPSC++也许一切都会在一秒钟内计算出来。

解决方案

让我们使用区间运算来计算阶乘。间隔由三个非负数指定

I(m, d, e) = [m·10 ^e , (m + d)·10 ^e ]。

整数n对应于区间I(n, 0, 0) = [n·10 ⁰ , (n + 0)·10 ⁰ ] = [n, n]。

将间隔乘以整数：I(m, d, e) f = I(m f, d f, e)。

将间隔四舍五入10 ^r。请注意
⌊ ^m / _{10 ^r} ⌋·10 ^r ≤ m
m + d ≤ ⌈ ^{(m + d)} / _{10 ^r} ⌉·10 ^r

它从哪里来？

I(m, d, e) ⊂ I(⌊ ^m / _{10 ^r} ⌋, ⌈ ^{(m + d)} / _{10 ^r} ⌉, e + r)。

需要四舍五入来限制尾数中的位数。如果尾数变得比某个阈值长，则对间隔进行四舍五入，尾数再次变短。

舍入的区间包含原来的区间。

该程序读取所需的阶乘前缀和尾数中的位数。然后，它将连续的阶乘计算为舍入间隔。例如尾数五位数的计算：

五位数足以计算100 的最高两位！。惊人的效率。

保证阶乘的精确值在区间内。在每次迭代中，都会检查间隔末尾的尾数前缀。如果两个前缀都与搜索到的前缀匹配，则找到答案。此外，还检查增量是否没有按顺序赶上尾数。如果发生这种情况，继续搜索就没有意义了：不够准确。

对于问题中的示例来说，二十个字符就足够了。

import time


class Interval:
    ''' [mantissa * 10 ** exponent, (mantissa + delta) * 10 ** exponent] '''

    def __init__(self, mantissa, delta=0, exponent=0):
        self.mantissa = mantissa
        self.delta = delta
        self.exponent = exponent

    def __mul__(self, f):
        return Interval(self.mantissa * f, self.delta * f, self.exponent)

    def rounded(self, m_digits):
        exp = max(0, len(str(self.mantissa + self.delta)) - m_digits)
        p = 10 ** exp
        m1 =  self.mantissa                       // p
        m2 = (self.mantissa + self.delta + p - 1) // p
        return Interval(m1, m2 - m1, self.exponent + exp)

    def __str__(self):
        if self.delta == 0:
            return f'{self.mantissa}e{self.exponent}'
        return f'({self.mantissa}+{self.delta})e{self.exponent}'


def main():
    p, m = input().split()
    m = int(m)
    c = 10 ** len(p)

    next_time = 0

    f = Interval(1)
    i = 1
    while True:
        f = (f * i).rounded(m)
        curr_time = time.time()
        if curr_time > next_time:
            print(i, f, end='\r')
            next_time = curr_time + 1
        if f.mantissa < f.delta * c:
            print(f'\n{i} {f}\nfailure')
            break
        if str(f.mantissa          ).startswith(p) and \
           str(f.mantissa + f.delta).startswith(p)     \
        :
            print(f'\n{i} {f}\n{f.mantissa}\n{f.mantissa + f.delta}\ndone')
            break
        i += 1


main()

$ echo 11533 20 | python factorial-prefix.py
16641 (11533115647054388190+7497)e63001
11533115647054388190
11533115647054395687
done

$ echo 51261 20 | python factorial-prefix.py
46978 (51261949824425729445+94135)e199057
51261949824425729445
51261949824425823580
done

$ echo 113131 20 | python factorial-prefix.py
323172 (11313167610953440853+142970)e1640127
11313167610953440853
11313167610953583823
done

$ echo 131091 20 | python factorial-prefix.py
266538 (13109139672370305808+136664)e1330399
13109139672370305808
13109139672370442472
done

$ time echo 151192033 20 | python factorial-prefix.py
37773304 (15119203331949324965+22322287)e2698105593
15119203331949324965
15119203331971647252
done

real  1m44.529s
user  1m44.520s
sys   0m0.000s

考试

让我们确保阶乘计算正确。这里有两个困难：阶乘本身的计算速度并不快，而且打印需要更长的时间。在 Python 中，打印长整数所需的时间是数字位数的二次方。为了解决这个困难，在打印之前，将阶乘除以 10 的幂，这样就剩下大约 20 位数字。

Nastin 阶乘大约需要一个半小时来检查，其余的不超过几秒钟：

import math

n = int(input())
f = math.factorial(n)
print(f // 10 ** (math.floor(math.log10(f)) - 20))

$ echo 16641 | python factorial-head.py
115331156470543919298

$ echo 46978 | python factorial-head.py
512619498244257763839

$ echo 323172 | python factorial-head.py
113131676109535123222

$ echo 266538 | python factorial-head.py
131091396723703741317

$ time echo 37773304 | python factorial-head.py
151192033319604853614

real  96m43.944s
user  96m35.068s
sys   0m2.688s

主要思想：计算高位数字时，不需要低位数字。

我们需要第一个n数字；在计算中我们将仅使用2n最高有效数字（假设这并不总是正确工作，但对于当前数据来说这是正确的）：

n = 151192033

nsize = len(str(n))
nstr = str(n)
n2size = nsize * 2

fact = 1
i = 1

while str(fact)[:nsize] != nstr:
    i += 1
    fact *= i

    fact = int(str(fact)[:n2size])

print(i, fact)

约 40 秒内完成。

str您可以通过将退出条件移至循环本身来减少循环中的函数调用次数：

while True:
    i += 1
    fact *= i

    sfact = str(fact)
    if sfact[:nsize] == nstr:
        break
    fact = int(sfact[:n2size])

现在~28秒。

我实现了同样的事情，不是用str，而是用十的幂除法并计算 through math.log10：

pow10 = [10**(i + 1) for i in range(n2size)] + [1] * 100
pow10_size = 10**nsize
while True:
    i += 1
    fact *= i

    fact //= pow10[int(math.log10(fact)) - n2size]
    if fact // pow10_size == n:
        break

〜26秒。有些参数只是不知从何而来，如果i它变得太大，那就不太好