P4863 题解

Solution

为了方便，我们定义 \(f_n=\sum_{i=1}^{n}\sum_{j=i}^{n} \lfloor\frac{i}{j} \rfloor \times (-1)^j\)。于是答案即为 \(f_b-f_{a-1}\)。

观察到如果我们直接计算这个式子而不做丝毫变形的话时间复杂度是 \(O(n^2)\) 的。

考虑把先枚举 \(j\)，计算 \(j\) 的贡献。此时就有了 \(O(n \sqrt n)\) 的做法。

然后继续手模一些小数据就可以发现，\(j\) 对答案的贡献应该是 \(j\) 个 \(1,2,3\dots (n-j)/j\)。于是计算出 \(n\) 在哪一块，计算出整块与单块的贡献即可。

ll calc(int l,int r){ return 1ll*(l+r)*(r-l+1)/2; }  
ll get(int n){ 
	ll ans=0; 
	for(int j=1;j<=n;j++){ 
		ll w=(j&1)?-1:1,id=(n-j)/j+1,r=id*j-1; //id 表示 n 所在的块，r 表示上一块的最后的位置
		ans+=1ll*w*j*calc(1,id-1); //整块的贡献
        ans+=1ll*w*(n-r)*id; // 单块的贡献
	} return ans; 
}