题解 P2261 【[CQOI2007]余数求和】

# 分析 一道数论计数题。我们发现，对于$i\in[1,n]$，前半部分的数的$\left\lfloor \frac{k}{i} \right\rfloor$是单调递减且互不相同的，而后半部分的$\left\lfloor \frac{k}{i} \right\rfloor$是在一定区间范围内相同的。 因此，想到以$\left\lfloor\sqrt{k}\right\rfloor$为分界，考虑以下计数方法： 对于$i\in\left[1,\left\lfloor\sqrt{k}\right\rfloor\right]$，直接遍历统计； 对于$i\in\left[\left\lfloor\sqrt{k}\right\rfloor+1,n\right]$，存在$x$使得$k=ix+r(0\leq r<i)$，因此对于所有$\left\lfloor \frac{k}{i} \right\rfloor=x$的数，i的取值范围为 $$\left[\left\lfloor\frac{k}{x+1}\right\rfloor+1,\left\lfloor\frac{k}{x}\right\rfloor\right]$$ 记$l=\left\lfloor\frac{k}{x+1}\right\rfloor+1,r=\left\lfloor\frac{k}{x}\right\rfloor$，则这部分的余数和为 $$sum=k(r-l+1)-\sum_{i=l}^{r}ix$$ $$=k(r-l+1)-\frac{x(l+r)(r-l+1)}{2}$$ 倒序枚举$x$计算即可 总复杂度$O\left(\sqrt{n}\right)$. # 代码 ```cpp #include<cstdio> #include<algorithm> #include<cmath> #define int long long using namespace std; int n,k,ans; signed main(){ scanf("%lld%lld",&n,&k); int p=sqrt(k),q=k/p; p=min(p,n); for(int i=1;i<=p;i++)ans+=k%i;//1-sqrt(k)莽算 if(n>p)for(int x=q-1;x>=1;x--){ int l=k/(x+1)+1,r=min(k/x,n),len=(r-l+1); if(l<=r)ans+=k*len-x*len*(l+r)/2; if(r==n)break; } if(n>k)ans+=(n-k)*k;//对于n>k的部分，余数即k printf("%lld",ans); return 0; } /* * 对于k=ix+r(0<=r<i),i的取值范围为 * [l=k/(x+1)+1,r=k/x] * 这部分的余数和为k*(r-l+1)-x*(l+r)*(r-l+1)/2; */ ```