CC

自然万物都趋向从有序变得无序

0%

洛谷P2261 [CQOI2007]余数求和（数论分块）

发表于 更新于 分类于 Valine：

题目链接

时空限制 1000ms / 128MB

Problem Description

题目背景

数学题，无背景

题目描述

给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29

输入格式：

两个整数n k

输出格式：

答案

输入输出样例
输入样例#1：

10 5

输出样例#1：

29

说明

30%: n,k <= 1000
60%: n,k <= 10^6
100% n,k <= 10^9

题意:

中文题目！！！

思路:

分块

对于题目求和的每一项我们知道， k % n = k - n × ( k / n );

那么题目的求和式转化为
$ans = \sum_{i=0}^{n} k % i = n × k - \sum_{i=0}^{n} i × \frac{k}{i} $。

那么对于$ \frac{k}{i} $，我们知道它其实是有很多连续的项是相同的，这个时候我们就可以用分块来处理。

对于这段连续的区间，我们假设当前项为$ i × \frac{k}{i} $，我们让x = k/i, 并i为使得k/i = x 的最小下标，那么为了快速的求 出这一段k/i值不变的区间对于答案的贡献，我们要找到最大的 i 满足 k / i = x;那么最大的应该是 k / x;最后数列求和即可。

时间复杂度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
34
35
36
37
/*************************************************************************
    > File Name: luogu-P2261.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年07月31日 星期二 21时07分52秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>

using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 1e9 + 7;
const int maxn = 1e5 + 10;

int main(){
    LL n, k;
    scanf("%lld %lld", &n ,&k);
    LL ans = n*k;
    for(int i = 1, j; i <= n; i = j+1){
        if(k/i) j = min(k/(k/i),n);
        else j = n;
        ans -= (k/i)*(i+j)*(j-i+1)/2;
    }printf("%lld\n", ans);
    return 0;
}