首页 > 试题广场 >

牛牛算题

[编程题]牛牛算题

热度指数：526 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

任意一个正整数都可以表示为 $n = p\times k + m$ ( $k$ 为商， $m$ 为余数) 的方式，现在死脑筋的牛牛想要计算对于小于等于 $n$ 的每一个数 $p(p\geq 1)$ ，计算所有 $k \times m$ 的和。(由于答案可能过大，请对 $10^9+7$ 取模)

示例1

输入

输出

说明

1 = 1*1 + 0

示例2

输入

输出

说明

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

备注:

算法知识视频讲解

C++

祐巳

typedef long long ll;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回1-n的所有k*m的和
* @param num long长整型正整数 n
* @return long长整型
*/
ll mod=1e9+7;
public:
long long cowModCount(long long num) {
ll ans=0;
ll l=1,k,m,pre_k,dif;
while (true)
{
k=num/l;
if (l>1)
{
dif=pre_k-k;
ans+=(2*m+(l-1)*(dif-1))*dif/2*(l-1);
}
m=num%l;
ans+=k*m;
l+=1;
if (l*l>num)
{
if (l==k) ans+=(k-1)*m;
else if (l==k-1) ans+=(k-2)*(k-2);
break;
};
pre_k=k;
ans%=mod;
}
return ans%mod;
}
};

发表于 2021-07-23 04:03:27 回复(0)

巴巴厘

/**
 
>>> when p=1...N
=> ans = sum{ [ n/p ] * [ n%p ] } = sum{ [ n/p ] * (n - [ n/p ] * p ) }

>>> when p=[a...b)
let M = [n/p].
=> ans_part = sum{ M * (N - M * p) }
=> ans_part = sum{ MN - MM * p }
let c=count{[a...b)}
=> ans_part = MNC - MM * sum{p}
ans = sum{ ans_part }

 */
class Solution {
public:
	const long long BN = 1000000007;
	long long cowModCount(long long n) {
		// write code here
		long long sum = 0;
		long long a = n;
		do {
			long long m = n / a;
			long long b = n / (m+1);
			long long c = (a - b); // a > b
			long long sum_p = c * (a + b + 1) >> 1; // a + ... + (b+1)
			long long sum0 = m * n * c - m * m * (sum_p % BN);
			sum += (sum0 % BN);
			sum %= BN;
			a = b;
		} while(a > 0);
		
		return sum;
	}
};

思路：求和、算式变形、分段求和

发表于 2021-06-18 12:04:41 回复(0)