2190: [SDOI2008]仪仗队
Description
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数，即C君应看到的学生人数。
Sample Input
4
Sample Output
9
思路：
gcd(i, j) = 1;特判x， y
// luogu-judger-enable-o2 #include <cstdio> #include <cstring> using namespace std; const int N = 1100000; bool np[N]; int pr[N], tot, phi[N]; void init() { phi[1] = 1; for(int i=2;i<N;i++) { if(!np[i]) { pr[++tot]=i; phi[i] = i-1; } for(int j=1;j<=tot&&i*pr[j]<N;j++) { np[i*pr[j]]=1; if(i%pr[j]) {phi[i*pr[j]] = phi[i]*(pr[j]-1);} else {phi[i*pr[j]]=phi[i]*pr[j];break;} } phi[i]+=phi[i-1]; } } int main() { int n; init(); while(scanf("%d", &n)!=EOF) printf("%d\n", n==1?0:phi[n-1]*2+1); }