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

发表评论

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

你是机器人吗? =。= *