【Luogu】P2158仪仗队（欧拉函数）

题目链接

首先来介绍欧拉函数。

设欧拉函数为f(n),则f(n)=1~n中与n互质的数的个数。

欧拉函数有三条引论：

1.若n为素数，则f(n)=n-1;

2.若n为p^a，则f(n)=(p-1)*(p^a-1)。

3.若gcd(a,b)=1，则f(a*b)=f(a)*f(b)。

下面代码给出欧拉函数的求法。可以和线性筛结合。

for(register int i=;i<n;++i){
        if(!f[i]){
            prime[++num]=i;
            phi[i]=i-;
        }
        for(int j=;j<=num&&prime[j]*i<n;++j){
            f[i*prime[j]]=;
            if(!(i%prime[j])){
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-);
        }
    }

phi数组是欧拉函数值。

那欧拉函数和本题有什么关系呢？

我们知道对于坐标点(i*k,j*k)，它一定会被点(i,j)阻挡。

换句话说设i*k=a,j*k=b。

只要gcd(a,b)!=1则会被阻挡。

因此要求的是范围内满足条件gcd(a,b)=1的点(a,b)有多少个。

因为正方形关于对角线对称，所以可以只算左下部分，右上部分是和左下部分相等的。

因为是左下部分，所以a>=b。

原题变成了求∑phi(i)，其中i=1~n。

代码如下。

#include<cstdio>
#include<cctype>
inline long long read(){
    long long num=,f=;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*+ch-'';
        ch=getchar();
    }
    return num*f;
}int prime[],num;
bool f[];
bool d[];
int phi[];
int ans;
int main(){
    int n=read();
    for(register int i=;i<n;++i){
        if(!f[i]){
            prime[++num]=i;
            phi[i]=i-;
        }
        for(int j=;j<=num&&prime[j]*i<n;++j){
            f[i*prime[j]]=;
            if(!(i%prime[j])){
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-);
        }
    }
    for(register int i=;i<n;++i) ans+=phi[i];
    printf("%d",ans*+);
    return ;
}