E. Sum of Remainders
time limit per test
memory limit per test
input
output
Calculate the value of the sum: n mod 1 + n mod 2 + n mod 3 + ... + n mod m. As the result can be very large, you should print the value modulo 109 (the remainder when divided by 109).
The modulo operator a mod b stands for the remainder after dividing a by b. For example 10 mod 3 = 1.
Input
The only line contains two integers n, m (1 ≤ n, m ≤ 1013) — the parameters of the sum.
Output
Print integer s — the value of the required sum modulo 109.
Examples
input
3 4
output
4
input
4 4
output
1
input
1 1
output
0
这道题分三步来做:
1.当m > n时 ans += n * (m - n); m = n - 1;
2.当m < n && m > 1e6时,分块取模,比如 m > n / 2那么(n / 2, m]的取模为等差数列求和 = (n % (n/2+1) + n % m) * (m - n + 1)/ 2; m = n / 2;以此类推
3.当 m <= 1e6时for(i = 2; i <= m; i++) ans += n % i;
#include <bits/stdc++.h>
#define maxn 200005
#define MOD 1000000007
using namespace std;
typedef long long ll;
int main(){
// freopen("in.txt", "r", stdin);
ll n, m, ans = 0;
scanf("%I64d%I64d", &n, &m);
if(m > n){
ans += (m - n) % MOD * (n % MOD) % MOD;
}
m = min(n - 1, m);
int cnt = 2;
while(m > 1000000){
ll d = n / cnt + 1;
if(m >= d){
ll p1 = n % d;
ll p2 = n % m;
ans += (p1 + p2) % MOD * ((m - d + 1) % MOD) % MOD * 500000004 % MOD;//2 * 500000004 % MOD == 1
ans %= MOD;
if(n % cnt == 0)
m = n / cnt - 1;
else
m = n / cnt;
}
cnt++;
}
for(int i = 2; i <= m; i++){
ans += n % i;
ans %= MOD;
}
cout << ans << endl;
return 0;
}