1. 题目

传送门= ̄ω ̄=

题意:
给出 n,k,求:
$$\sum_{i=1}^{n}k\ mod\ i$$
$$n,k\in [1,10^9]$$

2. 题解

以我这智障脑袋都想得出的题。。。
$$k\ mod\ i=k-\left \lfloor k\div i\right \rfloor \times i$$
所以:
$$\sum_{i=1}^{n}k\ mod\ i$$
就等于:
$$\sum_{i=1}^{n}k-\left \lfloor k\div i\right \rfloor \times i$$
等于:
$$n\times k-\sum_{i=1}^{n}\left \lfloor k\div i\right \rfloor \times i$$

那么答案很显然了,$\left \lfloor k\div i\right \rfloor$的值当 i 在一定范围内是相同的。
那我们把这个值相同的 i 放在同一个块中,设当前块的首部的 i 的值为 a,尾部的 i 的值为 b,这一块所有的 $\left \lfloor k\div i\right \rfloor$的值都为 c,那么显然这一块的总和为:
$$c\times (a+b)\times (b-a+1)\div 2$$
其中 $(a+b)\times (b-a+1)\div 2$就是个等差数列求和公式,因为这一块的首部为 a,尾部为 b,元素个数为 b-a+1,且前一项比后一项大 1
然后我们一块块求出每一块的总和,加起来就得到了 $$\sum_{i=1}^{n}\left \lfloor k\div i\right \rfloor \times i$$的值,用 n×k 减去这个值就行了

求每块的值的复杂度是 O(1) 的,然后共有 $\sqrt{n}$块,复杂度为 $\sqrt{n}$。

注意计算出的块尾可能超过 n,要特判(即块尾=min(块尾,n))
还有,如果n>k 的话是没有意义的,直接把 n 强行改为 k 即可

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,k,ans;
int main()
{
  scanf("%lld%lld",&n,&k),ans=n*k;
  if(n>k)n=k;
  for(LL i=1,j;i<=n;i=j+1)
    j=min(k/(k/i),n),ans-=((k/i)*(i+j)*(j-i+1))>>1;
  printf("%lld\n",ans);
  return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注