题目描述

给你n，表示一个（0,0）到（n,n）的网格图，求从(0,0)可以看到多少个点

样例

输入样例：

4
2
4
5
231

输出样例：

1 2 5
2 4 13
3 5 21
4 231 32549

算法1

(埃氏筛+欧拉函数计算式) $O(n log log n)$

具体代码见上下楼(复杂度太高不想写)

算法2

(线性筛+欧拉函数的基本性质) $O(n)$

但有一定常数，过小数据不太香，但复杂度肯定更优

对于一个质数p，若i是p的倍数，则φ(i x p)=φ(i) x p。否则φ(i x p)=φ(i) x φ(p)=φ(i) x (p-1);

C++ 代码

#include<bits/stdc++.h>
#define ri register int
#define ll long long
const int maxn=1005;
using namespace std;
int phi[maxn],v[maxn],p[maxn],m=0,n,T;
int main(){
    scanf("%d",&T);
    phi[1]=1;
    memset(v,0,sizeof(v));
    for(int i=2;i<=maxn;i++){
        if(v[i]==0){
            p[++m]=i;v[i]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=m;j++){
            if(p[j]>v[i]||p[j]*i>maxn) break;
            v[i*p[j]]=p[j];
            if(i%p[j]==0) phi[i*p[j]]=phi[i]*p[j];
            else phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
    for(ri j=1;j<=T;j++){
        ll ans=0;
        scanf("%d",&n);
        for(ri i=2;i<=n;i++) ans+=phi[i];
        ans=ans*2+3;
        if(n==0){
            cout<<j<<' '<<n<<' '<<0<<endl;
            continue;
        }
        cout<<j<<' '<<n<<' '<<ans<<endl;
    }
    return 0;
}