CodeForces 616E(数学规律)
题意:
输入n, m(1 ≤ n, m ≤ 10^13)，求 n%1 + n%2 + ... + n%m的值.
思路:
n%i = n - n/i(整除)*i;
所以 ∑(i=1, m) n%i 可以转化为 m*n - ∑(i=1, m) n/i*i;
易知：给定一个i，被n整除得c = n/i，另r = n/c，很容易可以得到n整除i到r范围内的所有数的值都是相同的，所以我们另i为下界，r为上界。那么我们求 ∑(i=1, m) n/i*i的时候就可以将它们分成若干组进行求和，另(n/i)相同的连续一段为一组。所以就可以利用等差数列求和公式对i到r范围内进行求和然后再乘上(n/i)就得到了这一段的ans，同理，其他段也是如此。
#include <algorithm>
#include <iostream>
#define LL long long
using namespace std;
const LL mod = 1e9+7;
LL n, m, ans, up, sum, r;
int main()
{
cin >> n >> m;
ans = (n%mod)*(m%mod)%mod;
up = min(n, m); //当n>m时, 只能求m个模; n<m时, 只能求n个模
sum = 0;
for(LL i = 1; i <= up; ++i)
{
r = min(n/(n/i), up);//如果上界超过up, 缩至up
LL a = i+r; //准备求和公式
LL b = r-i+1;
if(a&1) b /= 2;
else a /= 2;
sum = (sum + ((a%mod)*(b%mod)%mod)*(n/i)%mod)%mod;//获得此段的ans
i = r;
}
cout << (ans-sum+mod)%mod << endl;//防止mod之后相减变负数
return 0;
}