F(n) = (n % 1) + (n % 2) + (n % 3) + … (n % n)。其中%表示Mod，也就是余数。
例如F(6) = 6 % 1 + 6 % 2 + 6 % 3 + 6 % 4 + 6 % 5 + 6 % 6 = 0 + 0 + 0 + 2 + 1 + 0 = 3。
给出n，计算F(n), 由于结果很大，输出Mod 1000000007的结果即可。
输入
输入1个数N(2 <= N <= 10^12)。
输出
输出F(n) Mod 1000000007的结果。
输入样例
6
输出样例
3

余数 = n - n/i*i

很显然n/i只会有n的因子个数那么多

而且n/i在连续的一段区间内都是一样的。

这个用一个等差序列去维护i就好了

然后就可以在sqrtn的复杂度解决这道题了。

注意爆long long

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int main() {
	long long n, inv = 500000004;
	cin >> n;
	long long ans = (n % mod) * (n % mod) % mod;
	for (long long i = 1,j; i <= n; i = j + 1) {
		j = n/(n/i);
		ll x = n/i*(j + i)%mod;
		ll y = (j - i + 1)%mod * inv % mod;
		ans -= x * y;
		ans = (ans % mod + mod) % mod;
	}
	cout << ans << endl;
	return 0;
}