SUMPRO – SUM OF PRODUCT

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 ≤ 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

Leave a Reply