Description
作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数,即C君应看到的学生人数。
Sample Input
4
Sample Output
9
HINT
【数据规模和约定】 对于 100% 的数据,1 ≤ N ≤ 40000
题解
线筛欧拉函数。主要基于“欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)。”
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> using namespace std; int n,prim[40005],tot,phi[40005],pd[40005]; int ans; void getphi() { int i,j; phi[1]=1; for(i=2;i<=n;i++) {if(!pd[i]) {prim[++tot]=i; phi[i]=i-1;} for(j=1;j<=tot&&prim[j]*i<=n;j++) {pd[prim[j]*i]=1; if(i%prim[j]==0) {phi[prim[j]*i]=phi[i]*prim[j]; break;} else phi[prim[j]*i]=phi[i]*(prim[j]-1); } } } void work() { int i; for(i=1;i<n;i++) ans+=phi[i]; printf("%d\n",(ans<<1)+1); } int main() { scanf("%d",&n); getphi(); work(); return 0; }