bzoj2190 仪仗队

题目传送门

思路：

　　哪些点能被人看到，其实就是哪些点不会被其他点挡住，只要顶点的坐标互质就可以了，互质用欧拉函数算。特殊考虑一下n=1和0的情况。

　　欧拉函数，Φ（x）=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身），代码中为了保持精度，式子应该要化简一下，

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const int maxn=;

bool vis[maxn];

int prim[maxn],tot;

int n;

ll ans=;

double tmp=;

int main() {

    vis[]=;

    for(int i=; i<=maxn; i++) {

        if(!vis[i]) {

            for(int j=i*; j<maxn; j+=i) {

                vis[j]=;

            }

        }

    }

    for(int i=; i<=maxn-; i++) {

        if(!vis[i])prim[++tot]=i;

    }

    cin>>n;

    if(n==) {

        puts("");

        return ;

    }

    if(n==) {

        puts("");

        return ;

    }

    n--;

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

        tmp=i;

        for(int j=; j<=tot; j++) {

            if(i%prim[j]==) {

                tmp=tmp*(prim[j]-)/prim[j];

            } else if(prim[j]>i)break;

        }

        ans+=tmp;

    }

    printf("%lld\n",ans*+);

}

2190: [SDOI2008]仪仗队

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 4138  Solved: 2760
[Submit][Status][Discuss]

Description

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

Input

　　共一个数N。

Output

　　共一个数，即C君应看到的学生人数。

Sample Input

　　4

Sample Output

　　9

HINT

【数据规模和约定】 　　对于 100% 的数据，1 ≤ N ≤ 40000