「BZOJ2190」[SDOI2008] 仪仗队
Description
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数，即C君应看到的学生人数。
Sample Input
4
Sample Output
9
HINT
「数据规模和约定」 对于 100% 的数据，1 ≤ N ≤ 40000
题解
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<cstdio> #define N 40000 using namespace std; int n; int phi[40005],prime[40005],tot,ans; bool mark[40005]; void getphi() { int i,j; phi[1]=1; for(i=2;i<=N;i++) { if(!mark[i]) {prime[++tot]=i;phi[i]=i-1;} for(j=1;j<=tot;j++) { if(i*prime[j]>N) break; mark[i*prime[j]]=1; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j];break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } int main() { scanf("%d",&n); getphi(); for(int i=1;i<n;i++) ans+=phi[i]; printf("%d",2*ans+1); return 0; } |
计数器 9313968
OI 课件=>
OI 课件=>
黄学长生日快乐！17岁的春天