C&C++
发布时间：2022-04-01 发布网站：大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了P2158 [SDOI2008]仪仗队 题解，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
旅行传送门：https://www.luogu.com.cn/problem/P2158
题目描述
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
![P2158 [SDOI2008]仪仗队 题解](http://code.js-code.com/res/downimage/c++20220206/2297269-20210316153406232-1887205472.png "P2158 [SDOI2008]仪仗队 题解")
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
输入格式
输出格式
输入输出样例
解题思路
以左下角C君所在的点为原点，第一行为x轴，第一列为y轴建立平面直角坐标系。不难发现，一条直线上只有第一个点能被看见，而直线的斜率 k = y / x，即点(x , y)能被看见的条件为其与原点的连线的斜率是第一次出现；我们又知道，分数化为最简形式时有：gcd (x , y) = 1,即x与y互质，那么我们的问题就转化为了求有几对互质的x与y。
在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1)。因此，方阵下三角中互质的x与y的对数即为
![P2158 [SDOI2008]仪仗队 题解](http://code.js-code.com/res/downimage/c++20220206/2297269-20210316170328762-834659796.png "P2158 [SDOI2008]仪仗队 题解")
(方阵为n * n的大小，而坐标轴的起点是由0开始计算，所以只累加至n - 1)，由于方阵关于y = x对称，最后输出答案2 *
![P2158 [SDOI2008]仪仗队 题解](http://code.js-code.com/res/downimage/c++20220206/2297269-20210316170338005-688471935.png "P2158 [SDOI2008]仪仗队 题解")
+ 1即可(y = x 上
还有一点)。
欧拉函数
![P2158 [SDOI2008]仪仗队 题解](http://code.js-code.com/res/downimage/c++20220206/2297269-20210316170706517-1412580979.png "P2158 [SDOI2008]仪仗队 题解")
度娘与各大神犇对该函数的证明过程远远胜过本蒟蒻，在此就不过多赘述了。
AC代码
![P2158 [SDOI2008]仪仗队 题解](http://code.js-code.com/res/downimage/c++20220206/ContractedBlock.gif "P2158 [SDOI2008]仪仗队 题解")
![P2158 [SDOI2008]仪仗队 题解](http://code.js-code.com/res/downimage/c++20220206/ExpandedBlockStart.gif "P2158 [SDOI2008]仪仗队 题解")
@H_
197_81@
1 //打表版(3~6s)
2 #include <bits/stdc++.h>
3 #define MAXN 40000 + 10
4
5 int phI[MAXN],ans[MAXN];
6
7 void euler()
8 {
9 ans[
1] =
1;
10 for (
int i =
1; i <= MAXN; i++
)
11 {
12 int res = i, n =
i;
13 for (
int j =
2; j * j <= n; j++
)
14 {
15 if (!(n %
j))
16 res = res * (j -
1) /
j;
17 while (!(n %
j))
18 n /=
j;
19 }
20 if (n >
1)
21 res = res * (n -
1) /
n;
22 ph
I[i] =
res;
23 }
24 for (
int i =
2; i <= MAXN; i++
)
25 for (
int j =
1; j < i; j++
)
26 ans[i] +=
phI[j];
27 }
28
29 int main(
int argc,
char const *
argv[])
30 {
31 euler();
32 int n;
33 while (~scanf(
"%d", &
n))
34 {
35 if (n ==
1)
//方阵大小为1*1时特判，此时队列中只有自己，输出0
36 {
37 puts(
"0");
38 conTinue;
39 }
40 printf(
"%d\n",
2 * ans
[n] +
1);
41 }
42 return 0;
43 }
@H_
197_81@
1 //优化版(55±5ms)
2 #include <bits/stdc++.h>
3 #define MAXN 40000 + 10
4
5 int main(
int argc,
char const *
argv[])
6 {
7 int n, ans;
8 while (~scanf(
"%d", &
n))
9 {
10 ans =
0;
11 if (n ==
1)
12 {
13 printf(
"%d\n",
0);
14 conTinue;
15 }
16 for (
int i =
1; i < n; i++
)
17 {
18 int res = i, t =
i;
19 for (
int j =
2; j * j <= t; j++
)
20 {
21 if (!(t %
j))
22 res = res * (j -
1) /
j;
23 while (!(t %
j))
24 t /=
j;
25 }
26 if (t >
1)
27 res = res * (t -
1) /
t;
28 ans +=
res;
29 }
30 printf(
"%d\n",
2 * ans +
1);
31 }
32 return 0;
33 }
大佬总结
以上是大佬教程为你收集整理的P2158 [SDOI2008]仪仗队 题解全部内容，希望文章能够帮你解决P2158 [SDOI2008]仪仗队 题解所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
