SPOJ --- LCMSUM - LCM Sum

∑LCM(i, n) = ((∑(d * ETF(d)) + 1) * n) / 2 

where ETF(d) is Euler totient function of d and d belongs to the set of divisors of n.

Example: 

Let n be 5 then LCM(1, 5) + LCM(2, 5) + LCM(3, 5) + LCM(4, 5) + LCM(5, 5) 

= 5 + 10 + 15 + 20 + 5 

= 55

With Euler Totient Function: 

All divisors of 5 are {1, 5} 

Hence, ((1*ETF(1) + 5*ETF(5) + 1) * 5) / 2 = 55 

Bismillahir Rahmanir Rahim

///Author: Tanvir Ahmmad

///CSE,Islamic University,Bangladesh

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<iterator>

#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array

/*every external angle sum=360 degree

  angle find using polygon hand(n) ((n-2)*180)/n*/

///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b

using namespace std;

typedef long long ll;

ll phi[1000002],ans[1000002];

void totient()

{

    for(ll i=1; i<=1000000; i++)

        phi[i]=i;

    for(ll i=2; i<=1000000; i++)

        if(phi[i]==i)

            for(ll j=i; j<=1000000; j+=i)

                phi[j]-=(phi[j]/i);

}

void divisor()

{

    totient();

    for(ll i=1;i<=1000000;i++) ans[i]=0;

    for(ll i=1;i<=1000000;i++)

        for(ll j=i;j<=1000000;j+=i)

            ans[j]+=(i*phi[i]);

}

int main()

{

    divisor();

    ll tst,num;

    scanf("%lld",&tst);

    while(tst--)

    {

        scanf("%lld",&num);

        printf("%lld\n",((ans[num]+1)*num)/2);

    }

    return 0;

}

///Alhamdulillah

In Bengali:https://www.tushers.com/spoj-lcm-sum-solution/ 

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