玉树州wap网站建设公司,常州市工程建设招标网,网络软文营销,佛山优化公司推广欧拉函数
定义#xff1a;1 ∼ N 中与 N 互质的数的个数被称为欧拉函数#xff0c;记为 ϕ(N)
公式#xff1a;若 N p1^a1 * p2^a2 * … * pk^ak 所有的pi都是N的质因数
那么 ϕ(N) N * (p1-1)/p1 * (p2-1)/p2 * … *(pk-1)/pk; 性质 : 性质1#xff1a;如果n是质数1 ∼ N 中与 N 互质的数的个数被称为欧拉函数记为 ϕ(N)
公式若 N p1^a1 * p2^a2 * … * pk^ak 所有的pi都是N的质因数
那么 ϕ(N) N * (p1-1)/p1 * (p2-1)/p2 * … *(pk-1)/pk; 性质 : 性质1如果n是质数那么ϕ ( n ) n − 1 ,因为只有n本身与它不互质。
性质2如果pq都是质数那么ϕ ( p ∗ q ) ϕ ( p ) ∗ ϕ ( q ) ( p − 1 ) ∗ ( q − 1 )
性质3:根据性质2得出如果p是质数那么ϕ ( p ^k ) p ^k − p^ k − 1
1) 单个数的欧拉函数
原题链接873. 欧拉函数 - AcWing题库
核心代码 int res n;
//利用了分解质因子的代码for(int i2;in/i;i){if(n%i0){res res*(i-1)/i;while(n%i0)n/i;}}完整代码
#includeiostream
#define int long long using namespace std;signed main(){int t;cint;while(t--){int n;cinn;int res n;for(int i2;in/i;i){if(n%i0){res res*(i-1)/i;while(n%i0)n/i;}}if(n1)res res*(n-1)/n;coutresendl;}return 0;
}2通过欧拉筛求欧拉函数
原题链接874. 筛法求欧拉函数 - AcWing题库
问题 给定一个正整数 n, 求 1∼n 中每个数的欧拉函数之和
证明根据质因数定理 i p1^a1 * p1^a2 . . . pk^ak
那么 ϕ( i ) i*(a-1)/a * (a2-1)/a2 * … *(ak-1)/ak; (1) 若是i%p[ j ]0,那么说明p[ j ] 是 i 的一个质因子那么 i* p[ j ] 的质因子与 i 是一摸一样的区别只有i * p[ j ] 的质因子当中p[ j ] 的次数多一个
所以根据欧拉函数定义i与i* p[ j ] 的欧拉函数是相同的即phi[ i ] phi[ i* p[ j ] ]
2 若是 i% p [ j ] ! 0 那么说明i *p[ j ] , 这个数比i 多了一个质因子 那么
ϕ ( i * p [ j ]) p[ j ] * ϕ (i) * ( p[ j ] - 1 )/ p[ j ] ϕ (i) * ( p[ j ] - 1 )
即 phi[ i ] phi[ i* p[ j-1 ] ]
思路利用欧拉筛可以筛到所有的合数的性质我们求出可以求出每一位合数的欧拉函数
核心代码
void prime(const int n){ph[1] 1;for(int i2;in;i){if(!st[i]){p[res] i;st[i] true;ph[i] i-1;sumph[i];}for(int j0;p[j]n/i;j){st[i*p[j]] true;if(i%p[j]0){ph[i*p[j]] ph[i]*p[j];sum ph[i*p[j]];break;}ph[i*p[j]] ph[i]*(p[j]-1);sum ph[i*p[j]];}}}完整代码
#includeiostream
#define int long long
using namespace std;
const int N 1000100;
bool st[N];
int ph[N],p[N];
int res;
int sum 1;
void prime(const int n){ph[1] 1;for(int i2;in;i){if(!st[i]){p[res] i;st[i] true;ph[i] i-1;sumph[i];}for(int j0;p[j]n/i;j){st[i*p[j]] true;if(i%p[j]0){ph[i*p[j]] ph[i]*p[j];sum ph[i*p[j]];break;}ph[i*p[j]] ph[i]*(p[j]-1);sum ph[i*p[j]];}}}signed main(){int n;cinn;prime(n);coutsumendl;return 0;
}
