题解 P2158 【[SDOI2008]仪仗队】

hongzy · 2018-01-23 13:42:30 · 题解

核心是欧拉函数

1. 建立平面直角坐标系，以此人的位置作为原点(0,0)，x向右，y向上

2. 坐标(x, y)满足gcd(x,y) == 1，就可以被看见(即与原点的连线上无整点)（这个如果不清楚，可以先做P1170）

3. 沿着对角线(y=x函数)分成两个直角三角形，可以看出成轴对称.计算出左上方直角三角形上的答案，乘以2，+1(对角线上有一点可以被看见)

4. 求左上方直角三角形的答案

• y=0 只有原点(跳过)

• y=1 找(x, 1)满足x < 1 且x与1互质

• y=2 找(x, 2)满足x < 2 且x与2互质

• ...

• y=N 找(x, N)满足x < N 且x与N互质

欧拉函数正是求小于N且与N互质的数的个数。不过这个三角形中所有点一定满足 x < y, 所以直接求欧拉函数即可。

欧拉函数的求法可以根据公式 φ(n) = n(1-1/p1)(1-1/p2)..(1-1/pk) (pi是质因子)

#include <iostream>
#include <cmath>
using namespace std;

int N, ans;

int Phi(int N) {
    int m = (int)sqrt(N + 0.5), ans = N;
    for(int i=2; i<=m; 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 main() {
    cin >> N;
    if(N == 1) { //特判.没有对角线的存在
        cout << 0 << endl;
        return 0;
    }
    for(int i=1; i<N; i++) ans += Phi(i);
    cout << ans * 2 + 1 << endl;
    return 0;
}