BZOJ 2190 欧拉函数
2024-08-29 22:57:00
思路:
递推出来欧拉函数
搞个前缀和
sum[n-1]*2+3就是答案
假设仪仗队是从零开始的
视线能看见的地方就是gcd(x,y)=1的地方
倒过来一样 刨掉(1,1) 就是ans*2+1 再加一下第零行第零列的两个
就是结果了
//By SiriusRen
#include <cstdio>
using namespace std;
#define N 40005
int n,prime[N],vis[N],phi[N],tot;
long long ans;
int main(){
scanf("%d",&n);
for(int i=2;i<n;i++){
if(!vis[i])phi[i]=i-1,prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<n;j++){
vis[i*prime[j]]=1,phi[i*prime[j]]=phi[i]*(prime[j]-1);
if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
}
ans+=(long long)phi[i];
}
ans=ans*2+3;
printf("%lld\n",ans);
}
最新文章
- XMPP客户端开发(1)--连接和登录
- 解决Eclipse启动Tomcat时报Error loading WebappClassLoader错误
- [Effective JavaScript 笔记]第4章:对象和原型--个人总结
- (转) Java读取文本文件中文乱码问题
- 终端、shell、bash的区别联系
- TypeScript学习指南第一章--基础数据类型(Basic Types)
- 在Sublime Text 3中配置编译和运行Java程序
- JS,JQuery杂谈
- eclipse 集成maven插件
- python发展史
- bzoj3702/bzoj2212 二叉树 (线段树合并)
- [Node.js] 08 - Web Server and REST API
- [转]table中设置tr行间距
- 【转载】MSXML应用总结 开发篇(上)
- Azkaban(二)CentOS7.5安装Azkaban
- bzoj 3298: [USACO 2011Open]cow checkers -- 数学
- gdb逆向调试
- add以及update
- 在 Range 对象中,Min (14)必须小于或等于 max (-1)。
- Pythonic和语法糖