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