[SDOI2008] 仪仗队
题目大意：
有一个N*N的方阵，鑫宝在左后方，根据其视线所及的学生人数来判断队是否整齐。当队伍整齐时能看到的学生人数？
分析及求解
- 题意转换：通过对题目的分析总结，发现鑫宝所能看见的学生的坐标x与y互质，即：题目转换为求解N*N的矩阵中横纵坐标互质的点的个数。
- 题目求解：首先先将鑫宝周围三个点拿走，其次再以主对角线为分界线，可以得到剩余的点关于主对角线对称，最后注意一个易错点，横纵坐标轴从0开始。
- 链接知识点：线性筛、积性函数（欧拉函数）
-
代码分析：
#include <bits/stdc++.h> using namespace std; int N,pi[40010],v[40010],prime[40010],cnt; long long ans; int main() { scanf("%d",&N); N--; for (int i = 2;i <= N;i++){ if (!v[i]) v[i] = i,pi[i] = i - 1,prime[++cnt] = i; for (int j = 1;j <= cnt;j++){ if (prime[j] > v[i] || i * prime[j] > N) break; v[i * prime[j]] = prime[j]; if(v[i] == prime[j]) pi[v[i] * i] = v[i] * pi[i]; //定义求解欧拉函数 else pi[prime[j] * i] = pi[prime[j]] * pi[i]; //积性函数的性质求解欧拉函数 } ans += pi[i]; } ans *= 2; ans += 3; cout << ans; return 0; }
投递谷歌等公司10个岗位 >
