using namespace std;
vector <long> phi(1000001);
void fun()
{
phi[0]=0;
phi[1]=1;
for(long i=2;i<=1000000;i++)
{
phi[i]=i;
}
for(long i=2;i<=1000000;i++)
{
if(phi[i]==i)
for(long j=i;j<=1000000;j+=i)
{
phi[j]-=phi[j]/i;
}
}
// cout<<phi[1]<<" "<<phi[3]<<endl;
}
int main()
{
long t;
cin>>t;
fun();
for(long i=0;i<t;i++)
{
// cout<<phi[1]<<" "<<phi[3]<<endl;
long n;
cin>>n; long sum=0;
for(long j=1;j*j<=n;j++)
{
if(n%j==0)
{
long d1=j;
long d2=n/j;
sum=sum+(d1*(phi[d1]));
if(d1!=d2)
sum=sum+(d2*(phi[d2]));
}
}
sum=(sum+1)*n/2;
printf("%d\n",sum);
}
return 0;
}
getting TLE. Please help me with this.
