频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
bzoj2190仪仗队题解
2014-02-23 11:27:36         来源:bzoj2190仪仗队题解  
收藏   我要投稿

Description

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

Input

  共一个数N。

Output

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


终于A了!这个欧拉函数搞得我头昏脑涨!!

简介(欧拉函数的值 )通式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数,x是不为0的整数。φ(1)=1(唯一和1互质的数(小于等于1)就是1本身)。 (注意:每种质因数只一个。比如12=2*2*3


那么φ(12)=12*(1-1/2)*(1-1/3)=4)

经过观察发现这个仪仗队是对称的,我们可以求出左下角那一面;

再仔细观察,若(x,y)是可以看见的点,那么他们满足gcd(x,y)=1。

这时候,欧拉函数有用武之地啦!问题转化为:给定N,有数对(i,j),满足i>j,2

代码:

#include
#include
using namespace std;
long zhi[40001],n,cnt,i,j;
double ans;
long long max;
bool ok(long k)                      //判断质数
{
  for (long i=2;i<=trunc(sqrt(k));i++)
    if (k%i==0) return false;
  return true;
}
int main()
{
  scanf("%ld",&n);n--;              //N是人数个数,而边数要减1.
  zhi[1]=2;cnt=1;
  for (i=3;i<=n;i++) 
    if (ok(i)) zhi[++cnt]=i;       //预处理质数表
  for (i=1;i<=n;i++)
  {
    ans=i;
    for (j=1;j<=cnt;j++)
      if (i%zhi[j]==0) ans=ans*(zhi[j]-1)/zhi[j];     //欧拉函数
    max+=ans;
  }
  if (n<=0) printf("0");                               //特判0,1情况
  else printf("%ld",max*2+1);
  //scanf("%ld",&n);
  return 0;
}

点击复制链接 与好友分享!回本站首页
相关TAG标签 仪仗队 题解
上一篇:SDUT 1232 / POJ 1785 Binary Search Heap Construction
下一篇:POJ 3617 Best Cow Line ||POJ 3069 Saruman's Army贪心
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站