2190: [SDOI2008]仪仗队
2024-09-09 10:54:46
Description
作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。
其实就是在数一个n*n的网格可以数出多少条线,然后就是y=kx, 如果在同一条线上一定满足 y*a=k(x*a), 则这里的gcd(y,x)=1,通过观察的在这个红色三角形内可以发现每一个y值对应着小于它的x
则就是一个欧拉函数。
#include<iostream>
#include<cstdio>
using namespace std;
#define N int(4e4+10)
int phi[N], prime[N],tot;
bool mark[N];
void getphi()
{
int i, j;
phi[] = ;
for (i = ; i <= N; i++)
{
if (!mark[i]) { prime[++tot] = i; phi[i] = i - ; }
for (j = ; j <= tot; j++)
{
if (i*prime[j]>N) break;
mark[i*prime[j]] = ;
if (i%prime[j] == )
{
phi[i*prime[j]] = phi[i] * prime[j]; break;
}
else phi[i*prime[j]] = phi[i] * (prime[j] - );
}
}
}
int main()
{
getphi();
int n, ans = ;
scanf("%d", &n);
for (int i = ; i < n; ++i)
ans += phi[i];
printf("%d\n", ans * + );
return ;
}
最新文章
- HTML5-电影影评网
- Linux环境下Oracle数据库启动停止命令
- [html]兼容 IE6 IE7 的简单网页框架
- 用Quartz进行作业调度(转)
- swift系统学习控件篇:UIbutton+UIlabel+UITextField+UISwitch+UISlider
- O-C相关-06:对象与对象的关系
- <;微信应用开发系列>;定时刷新AccessToken
- 简单实现contentOS下开机自动启动tomcat
- iOS:判断昨天,今天,今年
- 通过游戏认识 --- JQuery与原生JS的差异
- iOS视频直播
- SharePoint2016: 使用powerShell启用project web app
- Docker入门(一)用hello world入门docker
- 使用jquery.more.js上滑加载更多
- Mongo 常用操作
- 20135239 益西拉姆 linux内核分析 进程的切换和系统的一般执行过程
- Nginx 安装与使用
- Lvs IP负载均衡技术
- centos中java安装跟配置
- r.js的build.js的详细配置解析