当前位置:网站首页>874. 筛法求欧拉函数
874. 筛法求欧拉函数
2022-08-10 03:41:00 【Hunter_Kevin】
题目
给定一个正整数 n,求 1∼n 中每个数的欧拉函数之和。
输入格式
共一行,包含一个整数 n。
输出格式
共一行,包含一个整数,表示 1∼n 中每个数的欧拉函数之和。
数据范围
1≤n≤106
输入样例:
6
输出样例:
12
代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N], phi[N], cnt;
bool s[N];
LL getPhiSum(int n){
phi[1] = 1;
// 线性筛法筛质数的过程中求每个被筛掉的数的欧拉函数
for(int i = 2; i <= n; i++){
if(!s[i]){
primes[cnt++] = i;
phi[i] = i-1;//如果i是质数,那么根据欧拉函数定义,1~(i-1)都跟质数i互质,则phi[i] = i-1
}
for(int j = 0; primes[j] <= n/i; j++){
s[ primes[j] * i] = true;
if(i % primes[j] == 0){
phi[primes[j] * i] = primes[j] * phi[i];
break;
}
phi[primes[j] * i] = (primes[j]-1) * phi[i];
}
}
// 累加1~n中所有数的欧拉函数之和
LL res = 0;
for(int i = 1; i <= n; i++) res += phi[i];
return res;
}
int main()
{
int n;
cin >> n;
cout << getPhiSum(n) << endl;
return 0;
}
边栏推荐
猜你喜欢
MySQL数据库初体验
【Mindspore】【310推理】导入mindir文件出错
program internationalization
【MindSpore】在训练过程中的step代表什么?
【mindspore产品】【8卡分布式训练】davinci_model : load task fail, return ret
【2022河南萌新联赛第(五)场:信息工程大学】【部分思路题解+代码解析】
最牛最全的 Postman 实现 API 自动化测试教程
The so-called software testing ability is actually these 5 points
互联网家装驶入深水区:谁在求变,又有谁在裸泳?
YAPI使用
随机推荐
Redis 定长队列的探索和实践
C语言原码,反码,补码与大小端
微信小程序相互跳转如何携带参数
数据库中数据的正确性和相容性是什么
请问mindspore支持l1范数归一化吗
10个超赞的C语言开源项目,值得学习
【mindspore产品】【8卡分布式训练】davinci_model : load task fail, return ret
zabbix添加监控主机和自定义监控项
mindspore安装过程中报错cannot find zlib
mindspore gpu版本安装问题
TCP协议之《ACK状态4种详解》
【Verilog数字系统设计(夏雨闻)6-------模块的结构、数据类型、变量和基本运算符号2】
自定义训练,使用Generator dataset迭代数据报错
c语言进阶篇:动态内存管理(相关函数、常见错误、笔试题)
GBase 8s打开工具就报错“配置文件有误” !!!为什么
TCP协议之《ACK报文限速》
2022年P气瓶充装操作证考试题库及模拟考试
goland控制台显示重叠问题解决方案
js原型和原型链以及原型继承
【MindSpore】在训练过程中的step代表什么?