bzoj 1257: [CQOI2007]余数之和sum (数学)

1257: [CQOI2007]余数之和sum

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 3724  Solved: 1711
[Submit][Status][Discuss]

Description

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

Input

输入仅一行,包含两个整数n, k。

Output

输出仅一行,即j(n, k)。

Sample Input

5 3

Sample Output

7

HINT

50%的数据满足:1<=n, k<=1000 100%的数据满足:1<=n ,k<=10^9

思路:一开始的想法。。。很容易想到当n>k的部分。。时可以是可以O(1)出来的。。。

然后对于n<k的部分。。。对于大于i/2的部分。。。是递减的等差数列。。也可以O(1)出来。。。

剩下的一半没时间好想法。。。现在复杂度仍然有5E8…gg\

打了很多表。。。也看出规律2333

于是看了题解。。

正解:k%i可以写成 k-k/i*i

而k/i一共有sqrt(k)种,相同的k/i位置相邻,他们的k%i的值是一个等差数列。。。

这道题就是求Σ(kk/ii)i=1..n简化一下是nkΣ(k/ii)i=1..n,显然我们可以发现⌊k/i⌋的取值是一个不上升序列,且有很多取值相同(事实上,⌊k/i⌋的取值只有√k个),那么我们就可以对i中的一段区间求和(这段区间内⌊k/i⌋取值相同),⌊k/i⌋相同且i单调增加1,可以直接算出来,时间复杂度O(√k)

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz