Jun 2020
1 / 1
Jun 2020
Jun 2020
priyankarai
Jun '20
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.