牛客编程巅峰赛：牛牛算题（整数分块）

整数分块）"/>

牛客编程巅峰赛：牛牛算题（整数分块）

链接：
来源：牛客网
 

题目描述

牛牛的数学老师教会了牛牛除法，牛牛十分开心，他知道任意一个正整数都可以表示为n=p×k+m (k 为商，m为余数) 的方式，现在死脑筋的牛牛想要计算对于小于等于n的每一个数p(p≥1)， 计算所有 k×m 的和。这可难倒了牛牛，请你来帮帮他吧。(由于答案可能过大，请对10^9+7取模)

示例1

输入

1

返回值

0

说明

1 = 1*1 + 0

示例2

输入

5

返回值

5

说明

5=1*5+0 , 5=2*2+1, 5=3*1+2,5=4*1+1,5=5*1+0 ;ans =5*0+2*1+1*2+1*1+1*0= 5

备注:

1≤n≤INTMAX1

思路：本题考查整数分块的知识。先盗用一张题解中的图【出处来自：=139471】：

对于n/p从1到n求和，我们发现这正是整数分块可以解决的东西，并且已经有博客证明，该复杂度是根号级别的。

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 返回1-n的所有k*m的和* @param num long长整型 正整数 n* @return long长整型*/private static final int mod=1000000007;public long cowModCount (long num) {// write code herelong ans=0,i,j,k,n=num;for(i=1;i<=n;i=j+1){k=n/i;j=n/k;ans=(ans+n*k%mod*(j-i+1)%mod)%mod;ans=(ans-k*k%mod*((i+j)*(j-i+1)/2%mod)%mod+mod)%mod;}return ans;}
}