Spoj - LCMSUM - LCM Sum

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

Idea : 

Code First Then See Solution

Code: 

#include <bits/stdc++.h>
using namespace std;

#define mx 1000008
#define ll long long

long long  a[mx+10];
long long res[mx+10];


void phi()
{
   memset(a,0,sizeof(a));
   a[1]=1;
   for(int i=2;i<=mx;i++)
   {
       if(a[i]==0)
       {
           a[i]=i-1;
           for(int j=i<<1;j<=mx;j+=i)
           {
               if(a[j]==0)
               {
                   a[j]=j;
               }
               a[j]=a[j]/i;
               a[j]*=(i-1);
           }
       }
   }
   //memset(res,0,sizeof(res));
   for(ll i=1;i<=mx;i++)
   {
       for(ll j=i;j<=mx;j+=i)
       {
           res[j]+=(i*a[i]);
       }
   }
}



int main()
{
    int t,f=0;
    //seive();
    phi();
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long sum=0;
        sum=res[n];
        sum++;
        sum*=n;
        sum/=2;
        cout<<sum<<endl;
    }
    return 0;
}