题解 P2158 【[SDOI2008]仪仗队】

Zzh20011004 · 2017-08-14 16:41:48 · 题解

(i*k,j*k)一定会被(i,j)遮挡视野

因此可以认为是求(i,j)（gcd(i,j)=1,i<n,j<n）

对于每个i可以用欧拉函数求出小于i且与i互质的数的个数

把i<n的所有欧拉函数值相加记为ans

因为关于y=x对称,ans*=2;

然后加上(0.1),(1,0),(1,1)即为答案

附上代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
int n,b[40010],prime[40005],el[40005],p=0,ans;
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n-1;i++)
    {
        if(!b[i])
        {
            prime[++p]=i;
            el[i]=i-1;
        }
        for(int j=1;j<=p && i*prime[j]<=n-1;j++)
        {
            b[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                el[i*prime[j]]=el[i]*prime[j];
                break;
            }
            el[i*prime[j]]=el[i]*(prime[j]-1);
        }
    }
    for(int i=2;i<=n-1;i++)
        ans+=el[i];
    printf("%d",ans*2+3);
    return 0; 
}