题解 P3766 【核心密码B】

· · 题解

本题解只到精度1e-8

对于n \le 10^{12}的数据:

可以数学推导或打表观察得知，f(n)<1恒成立，证明如下:

对每个底数x，其对f(n)的贡献为\frac{1}{x^{2}}+\frac{1}{x^{3}}+...+\frac{1}{x^{k}}\left ( x^{k}\leq n \right ),

记p(x)为x对f(n)的贡献，易知\frac{1}{x}+p(x)<\frac{1}{x-1}则有\frac{1}{2}+p(2)+\frac{1}{3}+p(3)+...<1+\frac{1}{2}+\frac{1}{3}+...

移项即得f(n)=p(2)+p(3)+...<1

用这个性质，由于f(n)刚开始增长较快，可能的答案种数较多，由于f(n)显然不降，我们可以对于每个x计算出最小的n满足f(n)\geq x\times 10^{-8},对于每组询问我们只需要在计算出的表中二分即可。

在O(n\sqrt{n})时间内计算出各个x对应的n的方法较多，这里介绍一种。

先对于所有可能的底数i\left ( i\leq \sqrt{n} \right )将二元组(i^{2},i)放入优先队列中,每次取出i^{k}最小的(i^{k},i),统计n=i^{k}时的答案， 并将(i^{k+1},i)加回优先队列即可。

总复杂度约\sqrt{n}log n+T log n

对于10^{12} < n \le 10^{12}的数据:

在n=10^{12}时，f(n)约为0.99999899，剩下的答案只剩下100余种，我们暴力计算并打出常数表存在程序内提交即可。