Problem Link – https://www.spoj.com/problems/SUMPRO/

#### Problem Statement :

Given a number **N**, find the sum of all products x*y such that N/x = y (**Integer Division**).

Since, the sum can be very large, please output this modulo **1000000007**.

Constraints :

1 ≤ T ≤ 500

1 ≤ N ≤ 10^{9}

Looking at the summation, we are asked to calculate the summation x*(N/x) , where 3/2 = 1 (integer division) or you can say floor(N/x).

The aim is to solve the above problem in O(sqrt(N)) complexity. We can think it as two cases

- When x is less than or equal to sqrt(N)
- When x is greater than sqrt(N), in this case floor(N/x) is less than sqrt(N).

Case 01 is simple, as we can simply iterate over all x till sqrt(N) and compute the sum.

For case 02, we need to check, if the value of floor(N/x) = v, then for which values of x, is this possible.

On observation, we will find out that for x in the range (N/v+1,N/v], this holds true. So, we want to compute x*floor(N/x) where floor(N/x) = v, and x varies from (N/v+1,N/v]. We can calculate this sum of products in constant time.

So, the overall complexity becomes O(sqrt(n))

```
void solve()
{
ll n;
cin >> n;
ll i = 0;
ll ans = 0;
for(i=1;i*i <= n;i++){
ans = (ans+ i*(n/i))%M1;
}
i = n/(ll)sqrt(n) - 1;
for(;i>=1;i--){
ll low = n/(i+1);
ll high = n/i;
if (low>=high) continue;
ans = (ans + ((high*(high+1))/2- (low*(low+1))/2)*i)%M1;
}
cout << ans << endl;
}
```

#### Want to try similar problem?

Try solving out https://codeforces.com/contest/616/problem/E