自动搬运

查看原文

来自洛谷，原作者为

	zhoutb2333 **

搬运于2025-08-24 22:04:41，当前版本为作者最后更新于2018-08-17 22:04:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一个大概 $\large O(\sqrt{N})$ 的算法

原式相当于 $\large \sum \limits _{i=1}^{B} \sum \limits _{j=1}^{i} (-1)^j \lfloor \frac{i}{j} \rfloor - \large \sum \limits _{i=1}^{A-1} \sum \limits _{j=1}^{i} (-1)^j \lfloor \frac{i}{j} \rfloor$

现在考虑计算 $\large \sum \limits _{i=1}^{N} \sum \limits _{j=1}^{i} (-1)^j \lfloor \frac{i}{j} \rfloor$

令 $\large k=\lfloor \frac{i}{j} \rfloor$ ，那么 $\large ans = \sum \limits _{k=1}^{N} k \left( \sum \limits _{j=1}^{\lfloor \frac{N}{k} \rfloor} (-1)^j \times (\text{存在多少个 } 1\le i \le N \text{ 满足 } \lfloor \frac{i}{j} \rfloor =k )\right) $

然后我们拆那个括号里的条件：

$\large \lfloor \frac{i}{j} \rfloor = k \Leftrightarrow j \times k \le i < j \times (k+1) $

所以当 $\large j \times (k+1) \le N$ 时，$\large i$ 的个数为 $\large j \times (k+1) - j \times k = j$

当 $\large j \times (k+1) > N$ 时，$\large i$ 的个数为 $\large N-j \times k +1$

故 $\large ans = \sum \limits _{k=1}^{N} k \left( \sum \limits _{j=1}^{\lfloor \frac{N}{k+1} \rfloor} (-1)^j \times j \ \ + \ \ \sum \limits _{j=\lfloor \frac{N}{k+1} \rfloor +1}^{\lfloor \frac{N}{k} \rfloor} (-1)^j \times (N-j \times k +1) \right)$

然后这两个 $\large sum$ 当固定上下界时都可以 $\large O(1)$ 计算，所以我们按照 $\large \lfloor \frac{N}{k} \rfloor$ 和 $\large \lfloor \frac{N}{k+1} \rfloor$ 对 $k$ 进行数论分块即可（$\large N$ 大了跑得很慢，可能我人傻常数大。。）

超丑代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int calc(int x){//计算最终式子前面的sum
    if(~x&1)
        return x>>1;
    return (x-1>>1)-x;
}
ll s1(int l,int r){//求自然数l~r的和
    return 1LL*(r+l)*(r-l+1)/2;
}
ll calc3(int r,int x,int k){
    ll ret=0;
    if(r&1)
        ret-=x+1;
    ret-=1LL*k*calc(r);
    return ret;
}
ll calc2(int l,int r,int x,int k){//计算后面的sum，用两个前缀减
    if(l>r)
        return 0;
    return calc3(r,x,k)-calc3(l-1,x,k);
}
ll solve(int x){
    ll ret=0;
    for(int k=1,pos;k+1<=x;k=pos+1){
        pos=x/(x/(k+1))-1;
        ret+=1LL*s1(k,pos)*calc(x/(k+1));
    }
    for(int k=1,pos;k+1<=x;k=pos+1){
        pos=min(x/(x/k),x/(x/(k+1))-1);
        ret+=1LL*s1(k,pos)*calc2(x/(k+1)+1,x/k,x,k);
    }
    ret+=1LL*x*calc2(1,1,x,x);//这是上一个循环k=x的情况，我的写法不特判会死循环
    return ret;
}
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%lld\n",solve(b)-solve(a-1));
    return 0;
}