2296 仪仗队 2008年省队选拔赛山东

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 大师 Master

题解

题目描述 Description

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

　　

　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

输入描述 Input Description

　　共一个数N。

输出描述 Output Description

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

样例输入 Sample Input

4

样例输出 Sample Output

9

数据范围及提示 Data Size & Hint

对于 30% 的数据，1≤N≤1000

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

分类标签 Tags

山东 省队选拔赛 2008年

/*

找斜率暴力n^3.

*/

#include<iostream>

#include<cstdio>

#include<map>

#define MAXN 20001

using namespace std;

bool g[MAXN][MAXN];

int ans,n;

int main()

{

    scanf("%d",&n);

    if(n==1)

    {

        printf("0");return 0;

    }

    ans=n*n-1-2*n+4-n+2;

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

      for(int j=2;j<=n;j++)

      g[i][j]=true;

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

      for(int j=2;j<i;j++)

      {

        if(g[i][j])

        {

            int xx=i-1,yy=j-1,k=i,l=j;

            while(k<=n&&l<=n)

            {

                if(g[k+xx][l+yy]) g[k+xx][l+yy]=false,ans-=2;

                k=k+xx,l=l+yy;

            }

        }

      }

      printf("%d",ans);

      return 0;

}

/*

坐标i,j互质时合法.

然后暴力gcd.

n^2logn.

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,ans;

int gcd(int a,int b)

{

    if(!b) return a;

    return gcd(b,a%b);

}

void slove()

{

    for(int i=2;i<=n-1;i++)

       for(int j=2;j<=n-1;j++)

       {

        if(gcd(i,j)==1)  ans++;

       }

}

int main()

{

    scanf("%d",&n);

    if(n==1)

      {

        printf("%d",0);return 0;

      }

    ans=2*n-1;

    slove();

    printf("%d",ans);

}

/*

o(n)欧拉函数.

刚开始暴力筛出素数

不会处理啊啊啊.

*/

#include<iostream>

#include<cstdio>

#define MAXN 40001

#define LL long long

using namespace std;

LL n,ans,p[MAXN];

void euler()

{

    p[1]=1;

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

    {

        if(!p[i])

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

            {

                if(!p[j]) p[j]=j;

                p[j]=p[j]/i*(i-1);

            }

        ans+=p[i];

    }

}

int main()

{

    scanf("%d",&n);

    ans=1;n--;

    euler();

    printf("%lld",ans*2+1);

    return 0;

}