清新的题解（正好写了

· · 题解

一个大概 \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;
}