P2158 [SDOI2008]仪仗队

题目描述

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

错误日志：没有特判 $N = 1$ 的情况

Solution

除开 $(0,1) (1,0) (0,0)$ 这三个点不谈，可以发现一个点可以被看到，当且仅当 $gcd(x, y) = 1$

所以把目光放到互质上

类似埃式筛法，我们可以在 $O(n\log n)$ 的时间内求出 $1-n$ 的欧拉函数

void euler(int n){

    for(int i = 2;i <= n;i++)phi[i] = i;

    for(int i = 2;i <= n;i++){

        if(phi[i] == i){

            for(int j = i;j <= n;j += i){

                phi[j] = phi[j] / i * (i - 1);

                }

            }

        }

    }

发现这题左上部分与右下部分是对称的，因为 $y = x$ 这条线上的点被 $(1,1)$ 盖住了，所以欧拉函数实际上只累积到 $n - 1$

我们还要加上最开始除开的三个点

即所求为： $$2 * \sum_{i = 2}^{N - 1}{\phi(i)} + 3$$

注意特判 $N = 1$ 的情况

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

typedef long long LL;

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 40019;

int num, phi[maxn];

void euler(int n){

    for(int i = 2;i <= n;i++)phi[i] = i;

    for(int i = 2;i <= n;i++){

        if(phi[i] == i){

            for(int j = i;j <= n;j += i){

                phi[j] = phi[j] / i * (i - 1);

                }

            }

        }

    }

int main(){

    num = RD();

    if(num == 1){puts("0");return 0;}

    euler(num - 1);

    int ans = 0;

    for(int i = 2;i <= num - 1;i++)ans += phi[i];

    printf("%d\n", ans * 2 + 3);

    return 0;

    }

不知道有啥卵用的欧拉定理

若 $$a \perp n$$ 则

\[a^{\phi(n)\equiv}1(mod\ n)
\]

巴特西

P2158 [SDOI2008]仪仗队 && 欧拉函数

P2158 [SDOI2008]仪仗队

Solution

Code

不知道有啥卵用的欧拉定理

最新文章

热门文章