题目描述

blablabla

样例

blablabla

算法1

(埃氏筛) $O(nlogn)$

时间复杂度分析：显然

C++ 代码

//时间复杂度O(Nlog(N)) 
#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=(a);i<=(b);++(i))
int ou[1010];

int main()
{
  //fin;
  go(i,1,1005)ou[i]=i;
  go(i,2,1005){
    if(ou[i]==i)//如果是质因数 
        for(int j=i;j<=1005;j+=i) ou[j]=ou[j]/i*(i-1);//筛去它的倍数 
    }//埃氏筛(nlogn) 
    int T;read(T);
    go(t,1,T){
      int n;read(n);
        int ans=0;
        go(i,2,n)ans+=ou[i];
        printf("%d %d %d\n",t,n,ans*2+3);
    }
}