仪仗队

【题目描述】

仪仗队是由学生组成的N*N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。现在，C君希望你告诉他队伍整齐时能看到的学生人数。

【输入描述】

一个数N。

【输出描述】

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

【输入样例】

4

【输出样例】

9

【数据范围及提示】

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

回放一下那些年，我与数论的旧时光（Euler函数镇楼！）：

源代码：

#include<cstdio>
int N,Num(0),Prime[10001];
bool Flag[30001]={0};
void Solve() //欧拉O(n)筛法。
{
    for (int a=2;a<=N;a++)
    {
        if (!Flag[a]) //没有被筛走，质数无疑。
          Prime[Num++]=a;
        for (int b=0;b<Num&&a*Prime[b]<=N;b++) //注意范围。
        {
            Flag[a*Prime[b]]=true;
            if (!(a%Prime[b])) //肯定就不是最小素因子啦。
              break;
        }
    }
}
int main() //输入一个数N，求出2~N之间素数的个数。
{
    scanf("%d",&N);
    Solve();
    printf("%d",Num);
    return 0;
}

/*
    利用了每一个合数必定有1个最小素因子的事实，每个合数被其对应的最小素因子筛去，O(n)无疑。
*/

正解：

源代码：

#include<cstdio>
int n,ans(0),Phi[40001]={0};
void Work()
{
    Phi[1]=1;
    for (int a=2;a<=n;a++)
      if (!Phi[a]) //质数无疑。
        for (int b=a;b<=n;b+=a) //由以下式子转换得来的。
        {
            if (!Phi[b])
              Phi[b]=b;
            Phi[b]=Phi[b]/a*(a-1);
        }
}
int main() //该算法在O(n)内筛素数的同时求出所有数的欧拉函数。
{
    scanf("%d",&n);
    Work();
    for (int a=1;a<n;a++)
      ans+=Phi[a];
    printf("%d",2*ans+1);
    return 0;
}

/*
    设P为质数。
    需要用到以下几个性质：
        (1)φ(P)=P-1；
        (2)如果i%P=0，则有φ(i*P)=P*φ(i)；（并不是完全积性函数）
        (3)如果i%P≠0，则有φ(i*P)=(P-1)*φ(i)；
    证明如下：
        (1)P的因数除了1以外只有P；
        (2)利用欧拉函数通式可证；
        (3)P为质数，i%P≠0可得i互质，利用欧拉函数的积性可得φ(i*P)=(P-1)*φ(i)；
*/