Description
作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数,即C君应看到的学生人数。
Sample Input
Sample Output
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]仪仗队(欧拉函数)的更多相关文章
-
BZOJ 2190: [SDOI2008]仪仗队( 欧拉函数 )
假设C君为(0, 0), 则右上方为(n - 1, n - 1). 一个点(x, y) 能被看到的前提是gcd(x, y) = 1, 所以 answer = ∑ phi(i) * 2 + 2 - 1 ...
-
2190: [SDOI2008]仪仗队(欧拉函数)
2190: [SDOI2008]仪仗队 Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 3235 Solved: 2089 Description 作 ...
-
P2158 [SDOI2008]仪仗队 &;&; 欧拉函数
P2158 [SDOI2008]仪仗队 题目描述 作为体育委员,C君负责这次运动会仪仗队的训练.仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线 ...
-
BZOJ2190 [SDOI2008]仪仗队 [欧拉函数]
题目描述 作为体育委员,C君负责这次运动会仪仗队的训练.仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图 ...
-
【bzoj2190】[SDOI2008]仪仗队 欧拉函数
题目描述 作为体育委员,C君负责这次运动会仪仗队的训练.仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图 ...
-
P2158 [SDOI2008]仪仗队 欧拉函数模板
题目描述 作为体育委员,C君负责这次运动会仪仗队的训练.仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图 ...
-
luogu2158 [SDOI2008]仪仗队 欧拉函数
点 $ (i,j) $ 会看不见当有 $ k|i $ 且 $ k|j$ 时. 然后就成了求欧拉函数了. #include <iostream> #include <cstring&g ...
-
洛谷P2158 [SDOI2008]仪仗队 欧拉函数的应用
https://www.luogu.org/problem/P2158 #include<bits/stdc++.h> #define int long long using namesp ...
-
[SDOI2008]仪仗队 (欧拉函数)
题目描述 作为体育委员,C君负责这次运动会仪仗队的训练.仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图 ...
-
[bzoj2190][SDOI2008]仪仗队 ——欧拉函数
题解 以c点为(0, 0)建立坐标系,可以发现, 当(x,y)!=1,即x,y不互素时,(x,y)点一定会被点(x/n, y/n)遮挡. 所以点(x, y)被看到的充分必要条件是Gcd(x, y) = ...
随机推荐
-
遍历map的四种方法
方法一 在for-each循环中使用entries来遍历这是最常见的并且在大多数情况下也是最可取的遍历方式.在键值都需要时使用.注意:for-each循环在Java 5中被引入所以该方法只能应用于j ...
-
*HDU3047 并查集
Zjnu Stadium Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Tota ...
-
js-DOM,DOM扩展
DOM: 1. 了解节点的信息:nodeName(属性的标签名),nodeValue两个属性 在取得信息之前要进行判断是不是节点,节点类型由12个数值常量进行表示 2.每个节点都有一个childNod ...
-
git “bad index file sha1 signature fatal: index file corrupt”错误
在执行commit或revert等操作时,提示“bad index file sha1 signature fatal: index file corrupt”错误,导致操作失败.这是由于git的in ...
-
【.net 深呼吸】自定义应用程序配置节
实际上,应用程序配置文件 App.config,是由各个节(Configuration Section)组成的,通常,配置节是按功能划分的,比如我们很熟悉的 appSettings.connectio ...
-
centos 7 部署 汉化版 gitlab
=============================================== 2017/11/12_第6次修改 ccb_warlock 更 ...
-
Magic Stones CodeForces - 1110E (思维+差分)
E. Magic Stones time limit per test 1 second memory limit per test 256 megabytes input standard inpu ...
-
运维监控-Zabbix Server 使用QQ SMTP发送邮件报警及定制报警内容
运维监控-Zabbix Server 使用QQ SMTP发送邮件报警及定制报警内容 作者:尹正杰 版权声明:原创作品,谢绝转载!否则将追究法律责任. 本篇博客采用腾讯邮箱,想必大家都对QQ很了解,所以 ...
-
unity中制作模拟第一人称视角下的指南针
private int zRotation; public GameObject obj; public void Update() { //obj = GameObject.Find("C ...
-
基于tensorflow的MNIST手写识别
这个例子,是学习tensorflow的人员通常会用到的,也是基本的学习曲线中的一环.我也是! 这个例子很简单,这里,就是简单的说下,不同的tensorflow版本,相关的接口函数,可能会有不一样哟.在 ...