SPOJ - DIVSUM2 - Divisor Summation (Hard)


Problem Link: https://www.spoj.com/problems/DIVSUM2/en/


Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 100000008
#define ll long long

bitset <mx> b;
vector <ll> v;
void seive()
{
    b.set();
    b[0]=b[1]=false;
    for(ll i=0;i<mx;i++)
    {
        if(b[i])
        {
            v.push_back(i);
            for(ll j=i*i;j<=mx;j+=i)
                b[j]=false;
        }
    }
}


long long power(long long a, long long b)
{
    if(b==0)
        return 1;
    if(b==1)
        return a;
    long long res=1;
    while(b--)
        res*=a;
    return res;
}
int main()
{
    int t;
    seive();
    cin>>t;
    while(t--)
    {
        long long n,res=1,f;
        cin>>n;
        f=n;
        for(ll i=0;i<v.size()&&(v[i]*v[i])<=n;i++)
        {
            if(n%v[i]==0)
            {
                int cnt=0;
                while(n%v[i]==0)
                {
                    cnt++;
                    n/=v[i];
                }
                cnt++;
                res*=(((power(v[i],cnt))-1)/(v[i]-1));
            }
        }
        if(n!=1)
            res*=(1+n);
        cout<<res-f<<endl;
    }
    return 0;

}