[SDOI2008]仪仗队

https://ac.nowcoder.com/acm/problem/20313

题目描述

作为体育委员，C君负责这次运动会仪仗队的训练。

仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。

​

现在，C君希望你告诉他队伍整齐时能看到的学生人数。

输入描述

共一个数N。

输出描述

共一个数，即C君应看到的学生人数。

样例

#1

4

9

提示

• 对于 100% 的数据，$1\le N\le 40000$

解析

AC Code

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));static final int MAX = 40005;static int[] prime = new int[MAX];static int[] euler = new int[MAX];static boolean[] vis = new boolean[MAX];static int cnt;public static void main(String[] args) throws Exception {int n = nextInt();eulers(n);int ans = 0;for(int i = 1; i <= n - 1; i++) {ans += euler[i];}ans = ans * 2 + 1;System.out.println(ans);}public static void eulers(int n) {euler[1] = 1;for(int i = 2; i <= n; i++) {if(!vis[i]) { // 判断是不是素数prime[++cnt] = i;euler[i] = i - 1;}for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {vis[prime[j] * i] = true; // 将 prime[j] * i 标识为不是素数if(i % prime[j] == 0) { // 判断 prime[j] 是否为 i 的约数euler[prime[j] * i] = euler[i] * prime[j];break;} else {// prime[j] - 1 就是 euler[prime[j]]，利用了欧拉函数的积极性euler[prime[j] * i] = euler[i] * (prime[j] - 1);}}}}public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}public static String nextStr() throws Exception {st.nextToken();return st.sval;}
}

ring nextStr() throws Exception {
st.nextToken();
return st.sval;
}
}