当前位置:网站首页>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;
}
边栏推荐
- 所谓软件测试工作能力强,其实就是这 5 点
- Mini Program Navigation and Navigation Parameters
- 线程和线程间通信(C语言)
- Small program subcontracting and subcontracting pre-download
- 【网络迁移】Pytorch中的torch.no_grad对应MindSpore哪个方法
- Did not detect default resource location for test class xxxx
- Do you know these basic types of software testing?
- MySQL数据库初体验
- goland json.Marshal导致&变成\u0026
- Dynamic Web Development Fundamentals
猜你喜欢
随机推荐
mindspore gpu版本安装问题
order by注入与limit注入
数据库中数据的正确性和相容性是什么
【2022河南萌新联赛第(五)场:信息工程大学】【部分思路题解+代码解析】
TCP协议之《TSQ控制》
文件操作【c语言】
Take you to an in-depth understanding of the version update of 3.4.2, what does it bring to users?
线程执行测试效果
处理一些数据
PID与ADRC
2022年起重机械指挥操作证考试题库及模拟考试
数据库设计中反映用户对数据要求的模式叫什么
10个超赞的C语言开源项目,值得学习
golang gin 框架读取无法用 body 传递的表单参数
golang中的URL 的编码和解码(转)
TCP协议之《延迟ACK策略》
创意优选技术
itoa和aoti函数的自我实现
所谓软件测试工作能力强,其实就是这 5 点
ThreedLocal在单线程中的应用【获取在拦截器中登录的用户信息】