题目描述

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;
}