Spoj DIVSUM - Divisor Summation Solution

 

Algorithm Link : https://cp-algorithms.com/algebra/divisors.html

Problem Link: https://www.spoj.com/problems/DIVSUM/

Solve in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

#include<iostream>

using namespace std;

int main()

{

    long long t,n,i,s=0;

    cin>>t;

    while(t--)

    {

        s=0;

        cin>>n;

        for(i=1; i*i<n; i++)

        {

            if(n%i==0)

                s=s+i+n/i;

        }

        if(i*i==n)

            s=s+i;

        s=s-n;

        cout<<s<<endl;

    }

}

Another Solution :

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

#include <bits/stdc++.h>

using namespace std;

int main()

{

    long long n,a,b,count,i,p,t,cn,sum;

    cin>>t;

    while(t--)

    {

        cin>>n;

        cn=n;

        count = 0,sum=1;

        map<int,int>mp;

        while (!(n % 2))

        {

            n >>= 1;

            count++;

        }

        if (count>0)

            mp.insert(pair<int,int>(2,count));

            for (long long i = 3; i <= sqrt(n); i += 2)

            {

                count = 0;

                while (n % i == 0)

                {

                    count++;

                    n = n / i;

                }

                if (count)

                    mp.insert(pair<int,int>(i,count));

            }

        if (n > 2)

            mp.insert(pair<int,int>(n,1));

        map<int,int>::iterator it;

        for(it=mp.begin(); it!=mp.end(); it++)

        {

            p=it->first;

            a=it->second;

            sum*=(pow(p,a+1)-1)/(p-1);

        }

        cout<<sum-cn<<endl;

 

    }

    return 0;

}