欧拉函数
题 目:欧拉函数
给定n个正整数ai，请你求出每个数的欧拉函数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数ai。
输出格式
输出共n行，每行输出一个正整数ai的欧拉函数。
数据范围
1≤n≤100,
1≤ai≤2∗109
输入样例：
3
3
6
8
输出样例：
2
2
4
思 路：用公式求
定义：1 ~ N 中与 N 互质的数的个数被称为欧拉函数，记为ϕ(N)。
怎么求呢？？
有一个公式：
N = p1a1 X p2a2 X p3a3……X pkak ;
ϕ(N) = N(1 - 1/p1) X N(1 - 1/p2) X N(1 - 1/p3) ……X N(1 - 1/pk)；
例子：
N= 6 = 2 X 3；
ϕ(N) = 6 X （1 - 1/2）X (1 - 1/3) = 2
证明：容斥原理 。
1 ~ n 中n的质因子有 p1a1 X p2a2 X p3a3……X pkak ;
1、从1~ n中去掉 p1a1、 p2a2 、 p3a3……、 pkak 的倍数。
=>N - N / p1 - N / p2 - N / p3 …… N / pk
2、把所有重复减去的倍数加上。=> + N/(pi X pj…)
3、减去所有pipj…pk的倍数……
……
4、以此类推，得到ϕ(N) = N(1 - 1/p1) X N(1 - 1/p2) X N(1 - 1/p3) ……X N(1 - 1/pk)；
解 答
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
while(n --){
int a;
cin >> a;
int res = a;
for(int i = 2; i <= a / i; i ++)
if(a % i == 0){
res = res / i * (i - 1);
while (a % i == 0) a /= i;
}
if(a > 1)
res = res / a * (a - 1);
cout << res << endl;
}
return 0;
}
题 目：线性筛法求欧拉函数
给定一个正整数n，求1~n中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数n。
输出格式
共一行，包含一个整数，表示1~n中每个数的欧拉函数之和。
数据范围
1≤n≤106
输入样例：
6
输出样例：
12
思路：线性筛法。O(n) : 线性筛法模板，可以求出来很多东西。
线性筛法模板：
ll get_eulers(int n){
for(int i = 2; i <= n;i ++){
if(!st[i])//如果没被筛去，说明是质数
primes[cnt ++] = i;//将质数入队
for(int j = 0 ; primes[j] <= n / i;j ++){//干掉i的倍数
st[primes[j] * i] = 1;
if(i % primes[j] == 0)
break;
}
}
}
再进行更改：
ll get_eulers(int n){
phi[1] = 1;//1当中与1互质的只有1自己
for(int i = 2; i <= n;i ++){
if(!st[i]){
primes[cnt ++] = i;
phi[i] = i - 1;//如果一个数i是质数，那么它的欧拉函数值应该是 i-1
}
for(int j = 0 ; primes[j] <= n / i;j ++){
st[primes[j] * i] = 1;
if(i % primes[j] == 0){
phi[primes[j] * i] = phi[i] * primes[j];
/*
i % primes[j] == 0时， primes[j]是i的一个质因子
phi[i * primes[j]]只是比phi[i]多了一个primes[j]而已，
primes[j]是i的一个质因子，所以
phi[i]里面已经有一个（1-1/pj）了，
所以phi[primes[j] * i]是i的欧拉值乘上i的质因子primes[j]
*/
break;
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
/*
如果i % primes[j] ！= 0时， primes[j]是i的非质因子
那么 phi[primes[j] * i] = primes[j] * phi[i] * (1-(primes[j] - 1) / primes[j])
即 phi[primes[j] * i] = phi[i] * (primes[j] - 1);
*//
}
}
ll res = 0;
for(int i = 1; i <= n; i ++)
res += phi[i];
return res;
}
答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
int primes[N], cnt;
int phi[N];
bool st[N];
ll get_eulers(int n){
phi[1] = 1;
for(int i = 2; i <= n;i ++){
if(!st[i]){//
primes[cnt ++] = i;//
phi[i] = i - 1;
}
for(int j = 0 ; primes[j] <= n / i;j ++){//
st[primes[j] * i] = 1;//
if(i % primes[j] == 0){//
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
ll res = 0;
for(int i = 1; i <= n; i ++)
res += phi[i];
return res;
}
int main(){
int n;
cin >> n;
cout << get_eulers(n) << endl;
return 0;
}