自动搬运

查看原文

来自洛谷，原作者为

	Pisces AFO || QwQ

搬运于2025-08-24 22:12:41，当前版本为作者最后更新于2019-11-09 09:34:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这其实也是原题，很早以前出公开赛准备用这个，只不过数据强太多了...不说了，上题解（加强版在此）

为了方便，以下我用$lg$来代替$\log_2$

我们容易得出$ans=F(n)=F(\lfloor n/2\rfloor )+F(\lceil n/2\rceil )+n-1(n>1)$，我们令$g(n)=g(\lfloor n/2\rfloor )+g(\lceil n/2\rceil )+a(n)(n>1)$，则有$\Delta g(n)=\Delta a(n)+\Delta g(\lfloor n/2\rfloor)$

我们有恒等式$\lceil lg2j\rceil=\lceil lgj\rceil+1$和$\lceil lg(2j-1)\rceil=\lceil lgj\rceil+[j>1](j\geq1)$，所以当$a(n)=n-1$时，$\lceil lg(n+1)\rceil$满足$\Delta f(n)=1+\Delta f(\lfloor n/2\rfloor)$

所以有结论若$F(1)=0,F(n)=F(\lfloor n/2\rfloor )+F(\lceil n/2\rceil )+n-1(n>1)$，$F(n)=\sum\limits_{k=1}^{n}\lceil lgk\rceil$，我们就可以暴力求$F(n)$，但此时暴力仍然是$O(n)$的，因为其中有一些连续相等的数，可以考虑数论分块，复杂度大概是$O(lgn)$的，在我的那道题中预计得分$10\sim20pts$

令$m=\lceil lgn\rceil$，我们考虑增加$2^m-n$项以简化运算：

$F(n)+(2^m-n)m=\sum\limits_{k=1}^{2^m}\lceil lgk\rceil=\sum\limits_{j,k}j[j=\lceil lgk\rceil][1\leq k\leq 2^m]=\sum\limits_{j,k}j[2^{j-1}\lt k\leq 2^j][1\leq j\leq m]=\sum\limits_{j=1}^{m}j2^{j-1}=2^m(m-1)+1$

所以我们得到$F(n)=nm-2^m+1$

但是还有一个问题：如何求$\lceil lgn\rceil$，由于$n$太大，只能使用高精度，考虑暴力求$2^k$，暴力找到$m$，暴力取模，复杂度仍为$O(lgn)$，在我的那道题中预计得分仍然为$10\sim20pts$

我们有换底公式$lgn=\log_{10}n/\log_{10}2=\log_{10}n*(1/\log_{10}2),\log_{10}n$可以用数位个数估算（偏小），$1/\log_{10}2$取估算值$3.32192809488736218170856773213$，此时就可以求得估算值$l$，考虑预处理出$2^{2^l}$，再把$l$用二进制法表示即可快速求出$2^l$，再用暴力即可（此时暴力最多算$4$次，因为$2^4\gt10$），复杂度$O(lglgn)$，预计得分$100pts$，但是此题数据范围达到$10^{100000}$，必须用$FFT$优化，否则得分只能是$50\sim80pts$（均指在我的那道题中）

另外，提供本题（较弱版的AC代码）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int qpow(int a,int b){
	int s=1;
	while(b){
		if(b&1) s*=a;
		a*=a,b>>=1;
	}
	return s;
}
signed main(){
	int n,m;
	cin>>n;m=ceil(log2(n));
	cout<<m*n-qpow(2,m)+1;
	return 0;
}