清新的题解(正好写了
zhoutb2333
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 $ 大了跑得很慢,可能我人傻常数大。。)
超丑代码:
``` 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;
}
```