洛谷P2158 [SDOI2008] 仪仗队 题解

题目链接：P2158 [SDOI2008] 仪仗队

题意：作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N \times N$ 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。

现在，C 君希望你告诉他队伍整齐时能看到的学生人数。

稍微画一画图，可以发现我们只要求对角线以下的个数，然后把答案乘 $2$ 加 $1$ 即可

把连线看成直角三角形的斜边

可以发现图中对角线以下一共有 $9$ 个互不成比例的三角形 （ $(1,1)$ 那个算进去，$(1,0)$ 那个不算）

注：因为把 $(1,0)$ 和 $(1,1)$ 那个交换一下，答案不变（不太好讲，意会一下就行）

考虑怎样的三角形可以对答案有贡献

显然是满足底和高互质的三角形，而我们只要计算底>高的情况

问题就转化为了求 $\sum\limits_{i=1}^{n-1} \varphi(i)$ ，这里的 $\varphi(i)$ 表示欧拉函数

注意是 $n-1$ 哦！（边数=点数-1）

那么搞一个前缀和就好了，注意特判 $n=1$ 的情况

这题暴力可过，代码如下

时间复杂度 $O(n\sqrt{n})$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(4e4+15)
int Euler_phi(int n)
{
    int ans=n;
    for(int i=2; i<=n/i; i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int n,phi[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    if(n==1){cout << 0 << endl;return 0;}
    for(int i=1; i<=n; i++)
        phi[i]=phi[i-1]+Euler_phi(i);
    cout << phi[n-1]*2+1 << endl;
    return 0;
}

当然 $O(n)$ 的欧拉筛肯定快啦

代码在这

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(4e4+15)
bool ck[N];
int n,phi[N],prime[N],pcnt;
void Euler()
{
    if(n==1){cout << 0 << endl;exit(0);}
    ck[1]=1;phi[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(!ck[i])
        {
            prime[++pcnt]=i;
            phi[i]=i-1;
        }
        for(int j=1; j<=pcnt&&i*prime[j]<=n; j++)
        {
            int pos=i*prime[j];
            ck[pos]=1;
            if(i%prime[j])
            {
                phi[pos]=phi[i]*phi[prime[j]];
            }else
            {
                phi[pos]=phi[i]*prime[j];
                break;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;Euler();
    for(int i=1; i<=n; i++)
        phi[i]+=phi[i-1];
    cout << phi[n-1]*2+1 << endl;
    return 0;
}