## SUMPRO – SUM OF PRODUCT

#### 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 ≤ 5001 ≤ N ≤ 109`

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

1. When x is less than or equal to sqrt(N)
2. 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