[SDOI 2008]仪仗队

Description

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

Input

共一个数N

Output

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

Sample Input

4

Sample Output

9

HINT

【数据规模和约定】

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

题解

如图建系：

注意到“某人被挡住”即某人的坐标可以约分。

我们先不考虑坐标轴上的点。

那么先算出$1～n-1$这个范围内所有满足题意的点，先考虑$y<x$

$$\sum_{x=1}^{N-1}\sum_{y=1}^{x-1}[gcd(x,y)=1]$$
转化为

$$\sum_{x=1}^{N-1}φ(x)$$

做完之后我们将算出来的$ans×2$得到$y>x$的情况。

由于没考虑坐标轴上的点，我们再将$ans+2$，

由于没考虑$φ(1)=1$，我们再将$ans+1$。

 #include<map>

 #include<set>

 #include<ctime>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<cstdio>

 #include<string>

 #include<vector>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define LL long long

 #define RE register

 #define IL inline

 using namespace std;

 const int N=;

 int n;

 bool isprime[N+];

 int prime[N+],top;

 int phi[N+];

 IL void Pre();

 int main()

 {

     scanf("%d",&n);

     Pre();

     LL ans=;

     for (RE int i=;i<n;i++)

         ans+=phi[i];

     printf("%lld\n",ans*+);

     return ;

 }

 IL void Pre()

 {

     for (RE int i=;i<=n;i++)

     {

         if (!isprime[i]) phi[i]=i-,prime[++top]=i;

         for (RE int j=;j<=top&&i*prime[j]<=n;j++)

         {

             isprime[i*prime[j]]=;

             if (!(i%prime[j])) {phi[i*prime[j]]=phi[i]*prime[j];break;}

             else phi[i*prime[j]]=phi[i]*phi[prime[j]];

         }

     }

 }