[Luogu P2261] [CQOI2007]余数求和
题面
传送门：洛谷
Solution
这题显然有一个$O(n)$的直接计算法，$60$分到手。 接下来我们就可以拿出草稿纸推一推式子了 首先，取模运算在这里很不和谐，我们得转换一下。 对于任意取模计算，我们都有： 
所以，我们可以做以下推算 
经过一些手算，我们发现$k/i$(向下取整)是由一段一段的区间组成的，如下图 
显然，每段区间的右端点可以通过二分的方法来找 对于每一段区间，我们可以把k/i提出来，括号里面就变成了（i+(i+1)+(i+2)+(i+3)+…+右端点） 直接用等差数列来算就好 时间复杂度我不会算XD
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<iostream>
#include<cstdio>
using namespace std;
int main(int argc, char **argv)
{
long long n,K;
scanf("%lld%lld",&n,&K);
long long ans=n*K;
for(long long i=1;i<=n;i++)
{
long long temp=K/i;
long long l=i,r=n,mid,nxt=i;
while(l<=r)
{
mid=(l+r)/2;
if(K/mid==temp)
nxt=max(nxt,mid),l=mid+1;
else
r=mid-1;
}
ans-=(((i+nxt)*(nxt-i+1))/2)*temp;
i=nxt;
}
printf("%lld",ans);
return 0;
}
|
