奇怪的问题

学术版

Angxle_ @ 2024-11-01 21:29:04

怎么在时间限度为5s的情况下求十进制数n的二进制中有多少个一？

1<= n <= 10¹⁰⁰⁰⁰⁰⁰

by LY00000 @ 2024-11-01 21:33:29

da biao zhao gui lv

by 飞雨烟雁 @ 2024-11-01 21:56:56

@Angxle_ 时限 5s 的话，直接转二进制去数有几个 1 就行了。

具体而言，对于十进制数 n，取 2^k\approx \sqrt n，然后分别计算 \lfloor\frac n{2^k}\rfloor,n\bmod 2^k 中有几个 1。因为高精度除法可以做到 \Theta(m\log m)（m 为十进制位数），所以时间复杂度为：

T(m)=2T(m/2)+\Theta(m\log m)

解得：T(m)=\Theta(m\log ^2m)。在 5s 之内过 10^6 还是可以的。

by Angxle_ @ 2024-11-01 22:03:26

@飞雨烟雁

感谢

|