洛谷P2158 [SDOI2008]仪仗队

题目描述

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。现在，C君希望你告诉他队伍整齐时能看到的学生人数。

输入输出格式

输入格式：

共一个数N

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【数据规模和约定】

对于 100% 的数据，1 ≤ N ≤ 40000

http://www.cnblogs.com/SilverNebula/p/5894679.html

和上面这道题一个样。

求(N-1)(N-1)矩阵内的互质坐标个数。

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 const int mxn=40010;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 int phi[mxn];
16 int pri[mxn],cnt=0;
17 bool vis[mxn];
18 int n;
19 int sum[mxn];
20 void Euler(){
21     phi[1]=1;
22     int i,j;
23     for(i=2;i<mxn;i++){
24         if(!vis[i]){
25             vis[i]=1;pri[++cnt]=i;phi[i]=i-1;
26         }
27         for(j=1;j<=cnt && i*pri[j]<mxn;j++){
28             vis[i*pri[j]]=1;
29             if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}
30             else phi[i*pri[j]]=phi[i]*(pri[j]-1);
31         }
32     }
33     for(i=1;i<mxn;i++)
34         sum[i]+=sum[i-1]+phi[i];
35     return;
36 }
37 int main(){
38     Euler();
39     n=read();
40     printf("%d
",sum[n-1]*2+1);
41     return 0;
42 }