bzoj2190 仪仗队
2024-08-25 14:14:28
思路:
哪些点能被人看到,其实就是哪些点不会被其他点挡住,只要顶点的坐标互质就可以了,互质用欧拉函数算。特殊考虑一下n=1和0的情况。
欧拉函数,Φ(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本身),代码中为了保持精度,式子应该要化简一下,
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=;
bool vis[maxn];
int prim[maxn],tot;
int n;
ll ans=;
double tmp=;
int main() {
vis[]=;
for(int i=; i<=maxn; i++) {
if(!vis[i]) {
for(int j=i*; j<maxn; j+=i) {
vis[j]=;
}
}
}
for(int i=; i<=maxn-; i++) {
if(!vis[i])prim[++tot]=i;
}
cin>>n;
if(n==) {
puts("");
return ;
}
if(n==) {
puts("");
return ;
}
n--;
for(int i=; i<=n; i++) {
tmp=i;
for(int j=; j<=tot; j++) {
if(i%prim[j]==) {
tmp=tmp*(prim[j]-)/prim[j];
} else if(prim[j]>i)break;
}
ans+=tmp;
}
printf("%lld\n",ans*+);
}
2190: [SDOI2008]仪仗队
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 4138 Solved: 2760
[Submit][Status][Discuss]
Description
作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数,即C君应看到的学生人数。
Sample Input
4
Sample Output
9
HINT
【数据规模和约定】 对于 100% 的数据,1 ≤ N ≤ 40000
最新文章
- php js数组问题
- Android开发重点难点1:RelativeLayout(相对布局)详解
- 控制反转IOC的依赖注入方式
- Form认证的几点说明
- Simptip – 使用 Sass 制作的 CSS Tooltip 效果
- Top (参数)
- An unexpected error has occurred"; error appears when you try to create a SharePoint Enterprise Search Center on a Site Collection
- spinner下拉列表
- throw 语句
- bndtools教程
- ASP常用函数表
- (原+转)Eclipse中Android调用OpenCv
- pl sql 无法解析指定的连接标识符
- openStack 王者归来之 trivial matters
- Android dp和sp的用法汇总
- 三菱Ethernet工业以太网
- HDU 6200 2017沈阳网络赛 树上区间更新,求和
- [django]urls.py 中重定向
- x264源代码简单分析:熵编码(Entropy Encoding)部分
- Docker:搭建私有镜像仓储(image registry)(4)
热门文章
- cocos2D-x demo 的源码分析 #define ..##.. 的妙用.
- c语言实践 数字特征值
- Eclipse工具
- (转)用事实说话,成熟的ORM性能不是瓶颈,灵活性不是问题:EF5.0、PDF.NET5.0、Dapper原理分析与测试手记
- BZOJ3223 文艺平衡树(splay)
- XE改变图标颜色
- Sql 查询过慢,尝试重建索引
- C# Excel 操作
- 基于任务的异步编程模式(TAP)的错误处理
- ecliplse集成反编译插件