UVa 10830 - A New Function

For n=100 on observation::

i  :  n/i

2   50
3   33
4   25
5   20
6   16
7   14
8   12
9   11
10   10
11   9
12   8
13   7
14   7
15   6
16   6
17   5
18   5
19   5
20   5
21   4
22   4
23   4
24   4
25   4
26   3
27   3
28   3
29   3
30   3
31   3
32   3
33   3
34   2
35   2
36   2
37   2
38   2
39   2
40   2
41   2
42   2
43   2
44   2
45   2
46   2
47   2
48   2
49   2
50   2

Count of n/i :

2 - 17
3 - 8
4 - 5
5 - 4
6 - 2
7 - 2
8 - 1
9 - 1
10 - 1
11 - 1
12 - 1
14 - 1
16 - 1
20 - 1
25 - 1
33 - 1
50 - 1

Case 1: 3150

First i numbers less than sqrt(n) ans can be calculated easily as (n/i-1)*i   (ie. the numbers from 2 to sqrt(n) in O(sqrt(n))).

For numbers from (sqrt(n) to n) it can be seen that intervals of constant n/i are formed,which can be calculated as

(n/i-1)*(Summation of all the numbers in interval).

On further observation it can be seen that that the intevals boundary need not to be calculated seperately as it can be observed above that range(34,50) has value 2 which is same as (n/3+1,n/2),,,

range(26,33) has value 2 which is same as (n/4+1,n/3),,,and so on..

Hence the solution can be written in O(sqrt(n))..

My code:

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pii;

typedef map<int,int> mi;

#define si(a) scanf("%lld",&a)

#define sii(a,b) scanf("%lld %lld",&a,&b)

#define siii(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define pi(a) printf("%d\n",a)

#define nl printf("\n");

#define pb push_back

#define mp make_pair

#define all(c) (c).begin(),(c).end()

#define f(i,a,b) for(i=a;i<b;i++)

#define rf(i,a,b) for(i=a;i>=b;i--)

#define clr(x,a) memset(x,a,sizeof(x))

#define MAX 1000100

#define MOD 1000000007

ll n,m;

map<ll,ll> mm;

int main(){

    ll r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;

    ll ans=0;string p;

    t=0;

    while(1){

        t++;

        si(n);

        if(n==0)

            break;

        ans=0;

        for(i=2;i*i<n;i++){

// For first i numbers less than sqrt(n)

            ans+=(n/i-1)*i;

//the interval (y,x) with n/i value=i can be calculated as discussed above with y>sqrt(n)

            x=n/i;

            y=n/(i+1)+1;

            if(y>i){

                z=(i-1)*(x*x+x-y*y+y)/2;

                ans+=z;

            }

        }

        if(i*i==n)

            ans+=(n/i-1)*i;

        printf("Case %lld: %lld\n",t,ans);

    }

    return 0;

}