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; }
