题解 P2158 【[SDOI2008]仪仗队】
hongzy
2018-01-23 13:42:30
核心是欧拉函数
1. 建立平面直角坐标系，以此人的位置作为原点(0,0)，x向右，y向上
1. 坐标(x, y)满足gcd(x,y) == 1，就可以被看见(即与原点的连线上无整点)（这个如果不清楚，可以先做P1170）
1. 沿着对角线(y=x函数)分成两个直角三角形，可以看出成轴对称.计算出左上方直角三角形上的答案，乘以2，+1(对角线上有一点可以被看见)
1. 求左上方直角三角形的答案
- 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是质因子)
------------
```cpp
#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;
}
```