SPOJ SUMPRO – SUM OF PRODUCT


/*
User ID: tanmoy_13
Link : http://www.spoj.com/problems/SUMPRO/
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define getint2(a,b) scanf("%d%d",&a,&b)
#define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define mod 1000000007
#define I int

using namespace std;

/* Bits operation */
int Set(int n,int pos)  { return n = n | 1<<pos;}
bool check(int n,int pos) { return n & 1<<pos;}
int Reset(int n, int pos) { return n=n & ~(1<<pos);}
 /*----------------*/

 ll range_sum(ll a, ll b)
 {
     ll sa=a*(a+1)>>1;
     ll sb=b*(b+1)>>1;
     return (sa-sb)%mod;
 }

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    ll n;
    getint(t);
    TEST_CASE(t)
    {
        sc("%lld",&n);
        ll root=sqrt(n);
        ll low,up;
        ll sum=0;
        for(int i=1;i<=root;i++)
        {
            up=n/i;
            low=max(n/(i+1),root);
            sum+=(range_sum(up,low)*i)%mod;
            if(sum>=mod) sum-=mod;
            sum+=(i*(n/i))%mod;
            if(sum>=mod) sum-=mod;
        }
        pf("%lld\n",sum);
    }
    return 0;
}

Editorial for this problem :

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

Brute-force:
The simplest brute force solution involves iterating over all possible values of x and finding the corresponding value of y, and updating the running sum by adding x * y.

Unfortunately, this does not pass as the overall time complexity is O(T * N).

The Pattern:
If you tried to simulate the brute-force, you might observe the intriguing pattern of finding a lot of 1’s (approx N / 2) at the end.
The trick is to notice that many numbers, not only 1, are going to be repeated.
Let us consider an example of N = 10:

x = 1, y = 10
x = 2, y = 5
x = 3, y = 3
x = 4, y = 2
x = 5, y = 2
x = 6, y = 1
x = 7, y = 1
x = 8, y = 1
x = 9, y = 1
x = 10, y = 1

Observation 1: Note that not only 1, but 2 is also repeated. Rather, on simulating even bigger integers, you must notice that no more than O(sqrt(N)) distinct integers will ever occur.

Observation 2: All the repetitions will always to occuring together in a sequence such that they form an interval.

Now, we are getting closer to the solution, we can create chunks for each value of y and break our sum operation as follows:

10 * 1 + 5 * 2 + 3 * 3 + 2 * (4 + 5) + 1 * (6 + 7 + 8 + 9 + 10)

So, for each value y, if we find the lowest value of x (say, lo) and highest value of x(say, hi), we can find the entire summation in O(sqrt(N)).

I’d recommend you to go back to the problem and try to solve it with this much information only.

So as to complete the solution, we must find the way to compute values of lo and hi, for y = 1, lo = 6 and hi = 10
for y = 2, lo = 4 and hi = 5
for y = 3, lo = 3 and hi = 3

The other crucial observation is to notice that each pair of values (x,y) must have at least one value in [1, sqrt(N)].

Thus, we need not process the values of y any furthur..!!

But, aren’t we missing out on the pairs (1, 10) and (2, 5) ?

Well, these are exactly the pairs that have x * y = N, so we can compute them on-the-fly when y = 1 and y = 2. You might need to pay some attention while implementating, so as to avoid counting sqrt(N) twice and also to handle MOD correctly!!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s