Spoj DIVSUM2 Solution

Here,   (n² - 1) / (n - 1) = n+1;

Example  :  (7² -1) / (7 - 1) = 8

 when,   if(n > 1)

                       sum *= (pow(n, 2) - 1) / (n - 1),     you write in this code you get wrong answer because pow() function return double value and when n is big prime number sometimes it may be give double value so you get error. that reason we use  sum *= (n+1). 

#include<bits/stdc++.h>

#define ll long long

#define N 100000000

using namespace std;

 

bitset<N+10>flag;

vector<ll>p;

 

void seive()

{

    p.push_back(2);

 

    for(ll i=3; i<=N; i+=2)

    {

        if(flag[i] == 0)

        {

            p.push_back(i);

 

            if(i*i <= N)

            {

                for(ll j=i*i; j<=N; j+=i*2)

                    flag[j] = 1;

            }

        }

    }

}

 

ll Divisor_Sum(ll n)

{

    ll sum = 1;

 

    for(ll i=0; p[i]*p[i]<=n; i++)

    {

        if(n%p[i] == 0)

        {

            ll c = 1;

 

            while(n%p[i] == 0)

            {

                n = n/p[i];

                c++;

            }

 

            sum *= (pow(p[i], c) - 1)/(p[i] - 1);

        }

    }

 

    if(n > 1)

        sum *= n+1;

 

    return sum;

}

 

 

int main()

{

    seive();

 

    int t;

    cin >> t;

 

    while(t--)

    {

        ll n;

        cin >> n;

 

        cout << Divisor_Sum(n) - n << "\n";

    }

 

    return 0;

}