啥啊，py-cpp不是20倍差距吗
by fjy666 @ 2022-06-24 16:31:11
by jwcub @ 2022-06-24 16:34:52
刚才那个问题我确实没有考虑位数问题，以为乘法复杂度是 $O(1)$ 的了 （实际是 $O(n \log(n)$ 注：n表示位数，使用FFT算法)。
但是假如楼上数据是准确的，python 慢 70 倍，那么一个平衡树问题，python 版splay 和c++的暴力能跑得数据感觉就差不多了（splay 自带巨大常数）。
by 郑朝曦zzx @ 2022-06-24 16:42:38
我似乎明白了为什么pascal被ban掉了
by Iwara_qwq @ 2022-06-24 16:44:01
显然，`str()` 占用了大部分的时间
by YuzhenQin @ 2022-06-24 16:45:05
我大概知道怎么弄了，等会
by YuzhenQin @ 2022-06-24 16:52:22
@[郑朝曦zzx](/user/425694) python自带高精度慢到离谱。在洛谷模板题里面，一个 $A\times B$ 可以跑19ms+
by Static_int @ 2022-06-24 16:53:58
@[郑朝曦zzx](/user/425694) python没那么聪明，用的是 $O(n^2)$ 暴力乘
by Static_int @ 2022-06-24 16:54:53
@[郑朝曦zzx](/user/425694) 最后我是这么写的，因为没有详细的数据规模，所以我也不知道会怎么样：
```python3
from typing import *
import math
def get_integer_places(n: int) -> int:
if n <= 999999999999997:
return int(math.log10(n)) + 1
else:
return 14 + get_integer_places(n // 10**14)
def get_digit(num: int, idx: int) -> int:
return (num // 10 ** (get_integer_places(num) - idx - 1)) % 10
if __name__ == "__main__":
n: int = int(input())
ans: List[int] = []
ans.append(1)
for i in range(1, 10001):
ans.append(ans[i - 1] * int(i))
for i in range(1, n):
a, b = (int(x) for x in input().split(" "))
print(get_digit(ans[a], b - 1))
```
by YuzhenQin @ 2022-06-24 17:31:00
但是还是很慢
by YuzhenQin @ 2022-06-24 17:32:13