站外题，要求 $\sum\limits^n_{i=1}\varphi(i)$，其中 $1\le n \le 2 \times10^7$。

时限 1s，空间 512mb。

算法是对的，刚刚没开long long过了3个点。

#include<bits/stdc++.h>
#pragma GCC optimize (2)
using namespace std;
long long pr[20000005],p[20000005],eu[20000005],qz[20000005],pn;
void euler(int n)
{
	long long k=0;
	eu[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!p[i])pr[++pn]=i,eu[i]=i-1;
		for(int j=1;j<=pn&&k<=n;++j)
		{
			k=i*pr[j];
			p[k]=1;
			if(i%pr[j]==0)
			{
				eu[k]=eu[i]*pr[j];
				break;
			}
			eu[k]=(pr[j]-1)*eu[i];
		}
	}
}
int main()
{
	//freopen("visible.in","r",stdin);
	//freopen("visible.out","w",stdout);
	euler(20000000);
	for(int i=1;i<=20000000;++i)
		qz[i]=qz[i-1]+eu[i];
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		cout<<qz[n]*2+1<<endl;
		//另外有个小问题：这里为啥要*2+1
	}
	return 0;
}

球球了