Problem

My approach:

The answer is \displaystyle\sum_{i \ = \ 1}^{n} i \ \Big\lfloor\dfrac{n}{i}\Big\rfloor\ \text{mod}\ 10^9+7.

A linear approach will time out.

Notice that \Big\lfloor\dfrac{n}{i}\Big\rfloor = 1,\ \forall \ i > \sqrt{n}. Let’s say \lfloor\sqrt{n}\rfloor = i for simplicity.

We have an AP of (n-i+1) terms starting from (i+1) to n. It’s sum will be \dfrac{n-i+1}{2} \Big[2i+(n-i)\Big] = (n-i+1)(n+i)(2^{-1}).

So the answer is \Bigg(\displaystyle\sum_{k \ = \ 1}^{i} k \ \Big\lfloor\dfrac{n}{k}\Big\rfloor\Bigg) + (n-i+1)(n+i)(2^{-1}) all \text{mod} \ 10^9+7.

My code:

```
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
int exp(int x, int y, int p)
{
x %= p;
int res = 1LL;
while (y > 0)
{
if (y & 1) res = (res * x) % p;
y >>= 1;
x = (x * x) % p;
}
return res;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, ans = 0;
cin >> n;
int i;
for (i = 1; i*i <= n; ++i)
{
ans += (i*(n/i));
ans %= mod;
}
ans += (((((n-i+1)%mod)*((n+i)%mod))%mod)*(exp(2, mod-2, mod)%mod))%mod;
cout << ans << '\n';
}
```

This passes the sample test case but gets WA for larger inputs. Although I’m not sure, it *might* be the modular inverse. Please let me know where I’m wrong.