Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

05/10
09:56
数学其他

[bzoj 1257] CQOI2007 余数之和sum

♦♦♦♦♦♦   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

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

k mod i=k-k div i*i

因为可能的k div i只有O(sqrt(k))种,所以枚举所有可能的k div i,算出最小和最大可能的i然后加加减减就可以了

c++:

pascal:

 

[bzoj 1257] CQOI2007 余数之和sum