[CQOI2007]余数之和sum Bzoj1257

首先考虑所有n>k的部分：k mod n=k，答案直接+k*(n-k)。

接下来考虑n属于区间[1,ceil(sqrt(k))]的情况。因为sqrt(k)只有5位数而已，可以按照题目要求朴素算一遍。

最后考虑n属于区间[ceil(sqrt(k)),k]的情况：因为k mod n=k-k div n*n，此时k div n最大为ceil(sqrt(k))，最小为1。如果我们知道某个k div n=a，那么我们就可以求出n的取值范围（因为n在这个范围内都满足k div n=a）：[k/n]=a等价于k>=an && k<(a+1)n。换句话来说k/(a+1) < n <= k/a。

得到n的取值区间[L,R]后，这部分k mod n的和就是Σ[i=L->R,(k-ai)]。

我们枚举所有的a，并累加各个部分的余数和，这就是答案。总的复杂度为O(sqrt(k))。 
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

/**************************************************************
    Problem: 1257
    User: abcdabcd987
    Language: C++
    Result: Accepted
    Time:8 ms
    Memory:1276 kb
****************************************************************/

#include <iostream>
#include <cmath>
using namespace std;

long long ans,n,k;
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>k;
  if (n>k) {
    ans+=k*(n-k);
    n=k;
  }
  long long sqrtk=ceil(sqrt(k));
  for (long long i=1;i<=sqrtk;++i) ans+=k%i;
  for (long long a=1;a<=sqrtk;++a) {
    long long L=floor(k/(a+1))+1;
    long long R=floor(k/a);
    if (L<=sqrtk) L=sqrtk+1;
    if (R>n) R=n;
    if (R<L) continue;
    ans+=((k<<1)-a*L-a*R)*(R-L+1)>>1;
  }
  cout<<ans;
}

2013-03-03 UPDATE: 发现一个更厉害的分段方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <cmath>
#include <cstdio>
#include <algorithm>

long long n, k, ans;
int main()
{
  scanf("%lld%lld", &n, &k);
  if (n > k)
  {
    ans += (n-k)*k;
    n = k;
  }
  ans += n * k;
  for (long long i = 1, last; i <= n; i = last+1)
  {
    last = std::min(n, k/(k/i));
    ans -= (k/i) * (i+last) * (last-i+1) / 2;
  }
  printf("%lld", ans);
}

Comments