洛谷 P2158 【仪仗队】

题库：洛谷
题号：2158
题目：仪仗队
link：https://www.luogu.com.cn/problem/P2158

思路：

首先给每个点设一个坐标，规定左下角第一个点的坐标为 $(0,$ $0)$，然后其他点的坐标依次递增。

设一个点的坐标为 $(x,$ $y)$，容易发现，如果 $x$ 与 $y$ 互质，那么它就能被C君看到，反之则不然，因为一定存在一个人 $(x$ $/$ $gcd(x,y),$ $y$ $/$ $gcd(x,$ $y))$ 将它挡住。

因此我们只需计算 $0$ ~ $n$ $-$ $1$ 中有多少对数互质，因为其中 $0$ 比较特殊，而第 $0$ 行与第 $0$ 列能看到的又只有一个人，所以我们先不做考虑，最后将答案加 $2$ 即可。

将上面的文字转化为代码就是

for(int i = 1; i <= n - 1; ++i) for(int j = 1; j <= n - 1; ++j) ans += (gcd(i, j) == 1)
ans += 2;//特殊的

然而这个复杂度会超时，因此考虑其他做法。

首先容易得出，如果要求的是

for(int i = 1; i <= n - 1; ++i) for(int j = 1; j <= i; ++j) ans += (gcd(i, j) == 1)

容易看出，第二个循环就是 $φ(i)$ ，而由于 $φ(i)$ 是积性函数，可以线性递推求出，因此求第二个式子的复杂度就是$O(n)$。

而第二个式子和第一个式子的关系很容易看出是二倍 $-$ $1$（不算那个 $+$ $2$ ）（ $-$ $1$ 是因为最中间的那一斜行被多算了一次）

$code$：

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, pri[1000010], phi[1000010], vis[1000010], num, ans;
 5 void oular()
 6 {
 7     for(int i = 1; i <= n; ++i) vis[i] = 1;
 8     vis[1] = 0, phi[1] = 1;
 9     for(int i = 2; i <= n; ++i)
10     {
11         if(vis[i]) pri[++num] = i, phi[i] = i - 1;
12         for(int j = 1; j <= num && i * pri[j] <= n; ++j)
13         {
14             vis[i * pri[j]] = 0;
15             if(i % pri[j] == 0) {phi[i * pri[j]] = phi[i] * pri[j]; break;}
16             else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
17         }
18     }
19     return;
20 }
21 int main()
22 {
23     scanf("%d", &n);
24     if(n == 1) {putchar('0'); return 0;}
25     oular();
26     for(int i = 1; i <= n - 1; ++i) ans += phi[i];
27     printf("%d", ans * 2 - 1 + 2);
28     return 0;
29 }