题解 P2158 【[SDOI2008]仪仗队】

YoungLove · 2017-07-12 15:04:47 · 题解

Youngsc

首先我们会发现，在同一条视线上的点的横纵坐标约分后相同，且不在同一条视线上的两个点横纵坐标一定不同，所以问题转化为在一个（n-1）*（n-1）的网格上寻找横纵坐标互质的点的个数（暂时不考虑正右方和正上方以及对角线），这里就会用到欧拉函数，将2到n-1的累和乘二（关于对角线对称过去），然后再加上正右方和正上方以及对角线（3）既为答案。

代码奉上

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <string>
# include <cmath>
# include <queue>
# include <map>
# define R register
# define LL long long

using namespace std;

int prime[20000],p,phi[40010],n,ans;

bool v[40010];

void in(R int &a){
    char c = getchar(); R int x = 0,f = 1;
    while(c < '0'|| c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0'&&c <= '9') x = x*10+c-'0',c = getchar();
    a = x*f;
}

int main (){
    in(n);
    for(int i = 2;i <= n-1; ++i){
        if(!v[i]) prime[++p] = i,phi[i] = i-1;
        for(int j = 1;j <= p&&prime[j] * i < n;++j){
            v[i*prime[j]] = 1;
            if(i % prime[j] == 0){
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i*prime[j]] = phi[i] * (prime[j]-1);
        }
    }
    for(int i = 2;i < n; ++i) ans += phi[i];
    cout << ans*2+3;
}