Description
给出一个数字N
Input
第一行为一个正整数T,表示数据组数。
接下来T行为询问,每行包含一个正整数N。
T<=5000,N<=10^7
Output
按读入顺序输出答案。
Sample Input
1
10
Sample Output
136
题目分析
以上是我看错题了= = 还推导了一番
当时 (也就是这道题)
这样的话这题就写完了
时
令
然后快筛即可
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,t;
long long prime[10000020],phi[10000020],f[10000020];
bool vis[10000020];
void init()
{
f[1]=phi[1]=1;
for(int i=2;i<=10000000;i++)
{
if(!vis[i]) prime[++prime[0]]=i,phi[i]=i-1;
for(int j=1;j<=prime[0]&&i*prime[j]<=10000000;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
for(int i=1;i<=10000000;i++) f[i]=f[i-1]+phi[i];
}
void slove(int x)
{
int last=0;
long long ans=0;
for(int i=1;i<=x;i=last+1)
{
last=x/(x/i);
ans+=(f[last]-f[i-1])*f[x/i];
}
printf("%lld\n",2*ans-f[x]);
}
int main()
{
init();
scanf("%d",&t);
while(t--)
scanf("%d",&n),slove(n);
return 0;
}