清新的题解（正好写了

一个大概 $\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 $ 大了跑得很慢，可能我人傻常数大。。） 超丑代码： ``` cpp #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; } ```