【BZOJ】2190 [SDOI2008]仪仗队(欧拉函数)

时间:2022-09-28 20:45:48

Description

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

Input

  共一个数N。

Output

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

Sample Input

  4

Sample Output

  9

HINT

【数据规模和约定】   对于 100% 的数据,1 ≤ N ≤ 40000

-----------------------------------------------------------------------------------------------------

分析:第一眼看到题,突然想到扩欧(滑稽),但仔细分析一下,站在C君处,如果看见了一个坐标(x,y),此坐标后的(2x,2y)(3x,3y)(4x,4y)(5x,5y)都看不见了,换句话说,只要是x,y不互质的点都看不见。所以题目就变成了求n范围内的互质的数的组数。跑一边欧拉筛法即可。

 #include <cstdio>
#include <algorithm>
#include <cmath>
const int maxn=;
int phi[maxn];
int phis(int n)//筛法
{
for(int i=;i<=n;i++) phi[i]=;
phi[]=;
for(int i=;i<n;i++)
{
if(!phi[i])
for(int j=i;j<=n;j+=i)
{
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
return ;
}
int main()
{
int n;
long long sum=;
scanf("%d",&n);
phis(n);
for(int i=;i<=n-;i++)
{
sum+=phi[i];
}
printf("%lld",sum*+);//x,y对称,所以sum*2,加3是因为没算(1,0)(1,1)(0,1)
return ;
}

【BZOJ】2190 [SDOI2008]仪仗队(欧拉函数)的更多相关文章

  1. BZOJ 2190&colon; &lbrack;SDOI2008&rsqb;仪仗队&lpar; 欧拉函数 &rpar;

    假设C君为(0, 0), 则右上方为(n - 1, n - 1). 一个点(x, y) 能被看到的前提是gcd(x, y) = 1, 所以 answer = ∑ phi(i) * 2 + 2 - 1 ...

  2. 2190&colon; &lbrack;SDOI2008&rsqb;仪仗队&lpar;欧拉函数&rpar;

    2190: [SDOI2008]仪仗队 Time Limit: 10 Sec  Memory Limit: 259 MBSubmit: 3235  Solved: 2089 Description 作 ...

  3. P2158 &lbrack;SDOI2008&rsqb;仪仗队 &amp&semi;&amp&semi; 欧拉函数

    P2158 [SDOI2008]仪仗队 题目描述 作为体育委员,C君负责这次运动会仪仗队的训练.仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线 ...

  4. BZOJ2190 &lbrack;SDOI2008&rsqb;仪仗队 &lbrack;欧拉函数&rsqb;

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

  5. 【bzoj2190】&lbrack;SDOI2008&rsqb;仪仗队 欧拉函数

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

  6. P2158 &lbrack;SDOI2008&rsqb;仪仗队 欧拉函数模板

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

  7. luogu2158 &lbrack;SDOI2008&rsqb;仪仗队 欧拉函数

    点 $ (i,j) $ 会看不见当有 $ k|i $ 且 $ k|j$ 时. 然后就成了求欧拉函数了. #include <iostream> #include <cstring&g ...

  8. 洛谷P2158 &lbrack;SDOI2008&rsqb;仪仗队 欧拉函数的应用

    https://www.luogu.org/problem/P2158 #include<bits/stdc++.h> #define int long long using namesp ...

  9. &lbrack;SDOI2008&rsqb;仪仗队 &lpar;欧拉函数&rpar;

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

  10. &lbrack;bzoj2190&rsqb;&lbrack;SDOI2008&rsqb;仪仗队 ——欧拉函数

    题解 以c点为(0, 0)建立坐标系,可以发现, 当(x,y)!=1,即x,y不互素时,(x,y)点一定会被点(x/n, y/n)遮挡. 所以点(x, y)被看到的充分必要条件是Gcd(x, y) = ...

随机推荐

  1. 遍历map的四种方法

    方法一  在for-each循环中使用entries来遍历这是最常见的并且在大多数情况下也是最可取的遍历方式.在键值都需要时使用.注意:for-each循环在Java 5中被引入所以该方法只能应用于j ...

  2. &ast;HDU3047 并查集

    Zjnu Stadium Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  3. js-DOM,DOM扩展

    DOM: 1. 了解节点的信息:nodeName(属性的标签名),nodeValue两个属性 在取得信息之前要进行判断是不是节点,节点类型由12个数值常量进行表示 2.每个节点都有一个childNod ...

  4. git &OpenCurlyDoubleQuote;bad index file sha1 signature fatal&colon; index file corrupt”错误

    在执行commit或revert等操作时,提示“bad index file sha1 signature fatal: index file corrupt”错误,导致操作失败.这是由于git的in ...

  5. 【&period;net 深呼吸】自定义应用程序配置节

    实际上,应用程序配置文件 App.config,是由各个节(Configuration Section)组成的,通常,配置节是按功能划分的,比如我们很熟悉的 appSettings.connectio ...

  6. centos 7 部署 汉化版 gitlab

    =============================================== 2017/11/12_第6次修改                       ccb_warlock 更 ...

  7. Magic Stones CodeForces - 1110E (思维&plus;差分)

    E. Magic Stones time limit per test 1 second memory limit per test 256 megabytes input standard inpu ...

  8. 运维监控-Zabbix Server 使用QQ SMTP发送邮件报警及定制报警内容

    运维监控-Zabbix Server 使用QQ SMTP发送邮件报警及定制报警内容 作者:尹正杰 版权声明:原创作品,谢绝转载!否则将追究法律责任. 本篇博客采用腾讯邮箱,想必大家都对QQ很了解,所以 ...

  9. unity中制作模拟第一人称视角下的指南针

    private int zRotation; public GameObject obj; public void Update() { //obj = GameObject.Find("C ...

  10. 基于tensorflow的MNIST手写识别

    这个例子,是学习tensorflow的人员通常会用到的,也是基本的学习曲线中的一环.我也是! 这个例子很简单,这里,就是简单的说下,不同的tensorflow版本,相关的接口函数,可能会有不一样哟.在 ...