bzoj2190 仪仗队【欧拉函数+线性筛】

解题思路：

我们以左下角为原点，建立直角坐标系。

那么一个人 (x,y) 能被看到，当且仅当 x,y 互质。

也可以看做求从原点开始有多少个不共线的向量。如果 d=gcd(x,y)≠1 ,那么它会和 (xd,yd) 共线。

如果我们以 y=x 作为对称轴，那么两边情况相等，而 (1,0),(0,1),(1,1) 单独考虑，所以答案为： 2∑i=2n−1ϕ(i)+3 。

其中欧拉函数 ϕ 可以用线性筛求。

时间复杂度为 O(n)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<vector>
#include<set>
#include<complex>
#define ll long long
using namespace std;

int getint()
{
    int i=,f=;char c;
    for(c=getchar();c!='-'&&(c<'0'||c>'9');c=getchar());
    if(c=='-')f=-,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())i=(i<<)+(i<<)+c-'0';
    return i*f;
}

const int N=;
int n,m,ans;
int pri[N],phi[N];

void seive()
{
    for(int i=;i<=n;i++)
    {
        if(!phi[i])pri[++m]=i,phi[i]=i-;
        for(int j=;j<=m;j++)
        {
            int k=i*pri[j];
            if(k>n)break;
            if(i%pri[j]==)
            {
                phi[k]=phi[i]*pri[j];
                break;
            }
            else phi[k]=phi[i]*(pri[j]-);
        }
    }
}

int main()
{
    //freopen("lx.in","r",stdin);
    n=getint();
    seive();
    for(int i=;i<n;i++)
        ans+=phi[i];
    cout<<ans*+;
    return ;
}