P2158 [SDOI2008] 仪仗队题解

__vector__ · 2022-01-21 11:28:49 · 个人记录

难度：\color{blue}\text{提高+/省选-}

前言：

这题是蓝题但是很水

题目分析：

瞄一眼就能发现这个方阵可以被左下---右上对角线分成对称的两部分（中间的对角线是单独的一部分，单独计算）。就只看下面那半部分好了，可以发现，对于第 i 列（i \ge 2，从左数），能看到的人数就是 \phi(i-1)。所以这半部分总共能看到的人数就是 \Sigma_{i=2}^{n}\phi(i-1)。
另一部分和这一部分的答案一样。至于剩下的那个对角线，可以发现对角线上肯定只有第一个人能被看见。
所以上下两部分加上对角线总共能看到的人数就是：

复杂度：\Theta(n\sqrt{n})

特殊情况：

如果 n = 1，那么答案应该为 0，要特判一下。

欧拉函数：

设一个数为 x，欧拉函数就是求有多少个数 i (1 \le i \le x)，与 x 互质 (gcd(i,x)=1) 。 记作 \phi(x)。
放上个求 \phi(x) 的板子：

int eular(int n)
{
    int ret=1;
    for(reg int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n/=i;
            ret*=(i-1);
            while(n%i==0)
            {
                n/=i;
                ret*=i;
            }
        }
    }
    if(n>1)ret*=n-1;
    return ret;
}

\color{green}\text{AC代码：}

#include <bits/stdc++.h>
using namespace std;
#define reg register
int n;
int eular(int n)
{
    int ret=1;
    for(reg int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n/=i;
            ret*=(i-1);
            while(n%i==0)
            {
                n/=i;
                ret*=i;
            }
        }
    }
    if(n>1)ret*=n-1;
    return ret;
}
signed main()
{
    scanf("%lld",&n);
    if(n==1)
    {
        printf("0");
        return 0;
    }
    int ans=0;
    for(reg int i=2;i<=n;i++)
    {
        ans+=eular(i-1);
    }
    ans=(ans<<1)+1;
    if(ans<0)return -1;
    printf("%d",ans);
    return 0;
}