M_sea

洛谷2158 [SDOI2008]仪仗队
题目描述作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整...
扫描右侧二维码阅读全文
01
2018/08

洛谷2158 [SDOI2008]仪仗队

题目描述

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

img

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

传送门

算法

先不看$(0,1)$,$(1,0)$,$(1,1)$这三个点。

容易发现,对于剩下的点$(x,y)$,若它能被看到,则$gcd(x,y)=1$。

而且剩下的点关于直线$y=x$对称,所以只需考虑一半即可。

考虑所有的点$(x,y)$,其中$1\leq x<y$,我们要统计有多少个点满足$gcd(x,y)=1$。

容易发现,这样的$x$的数量就是$\varphi(y)$。

那么最后的答案就是:

$$2\times \sum_{i=2}^{n-1}\varphi(i)+3$$

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

int v[40040],prime[40010];
int phi[40010];

inline int Get_Phi(int n) {
    int s=0;
    for (re int i=2;i<=n;i++) {
        if (!v[i]) v[i]=i,prime[++s]=i,phi[i]=i-1;
        for (re int j=1;j<=s;j++) {
            if (prime[j]>v[i] || prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
    }
    return s;
}

int main() {
    int n; scanf("%d",&n);
    if (n==1) { printf("0\n"); return 0; }
    Get_Phi(n); int ans=0;
    for (re int i=2;i<n;i++) ans+=phi[i];
    printf("%d\n",2*ans+3);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 54 PM

发表评论