线性筛法与积性函数

秒速五厘米 2023-08-17 16:15 91阅读 0赞

欧拉函数：

\\(1.\\varphi(p)=p-1\\)

证明：显然

--------------------

\\(2.\\varphi(i\*p)=p\*\\varphi(i)\\) , \\(if\\space i \\bmod p = 0\\)

引理1：\\(\\varphi(p^a)=(p-1)\*p^\{a-1\}\\)

证明：比 \\(p^a\\) 小的数一共有 \\(p^a-1\\) 个，其中与 \\(p^a\\) 不互质的且小于 \\(p^a\\) 的  
，即 \\(p\\) 的倍数 \\(p\*t\\) 一共有 \\(p^\{a-1\}-1\\) 个，则 \\(\\varphi(p^a)=p^a-1-(p^\{a-1\}-1)=(p-1)\*p^\{a-1\}\\)

引理2：\\(\\varphi(n)=n\*(1-\\frac\{1\}\{p\_1\})\*(1-\\frac\{1\}\{p\_2\})\*···\*(1-\\frac\{1\}\{p\_k\})\\)

证明：

\\(\\varphi(n)\\)

\\(=\\varphi(p\_1^\{a\_1\})\*\\varphi(p\_2^\{a\_2\})\*···\*\\varphi(p\_k^\{a\_k\})\\)

\\(=(p\_1-1)\*p\_1^\{a\_1-1\}\*(p\_2-1)\*p\_2^\{a\_2-1\}\*···\*(p\_k-1)\*p\_k^\{a\_k-1\}\\)

\\(=(p\_1^\{a\_1\}-p\_1^\{a\_1-1\})\*···\*(p\_k^\{a\_k\}-p\_k^\{a\_k-1\})\\)

\\(=p\_1^\{a\_1\}\*(1-\\frac\{1\}\{p\_1\})\*···\*p\_k^\{a\_k\}\*(1-\\frac\{1\}\{p\_k\})\\)

\\(=(p\_1^\{a\_1\}\*p\_2^\{a\_2\}\*···\*p\_k^\{a\_k\})\*(1-\\frac\{1\}\{p\_1\})\*(1-\\frac\{1\}\{p\_2\})\*···\*(1-\\frac\{1\}\{p\_k\})\\)

\\(=n\*(1-\\frac\{1\}\{p\_1\})\*(1-\\frac\{1\}\{p\_2\})\*···\*(1-\\frac\{1\}\{p\_k\})\\)

#### 证明： ####

设 \\(i\\) 为正整数，且 \\(i=p\_1^\{k\_1\}\*p\_2^\{k\_2\}\*···\*p\_n^\{k\_n\}\\)

\\(\\varphi(i)=i\*(1-\\frac\{1\}\{p\_1\})\*···\*(1-\\frac\{1\}\{p\_n\})\\)

\\(\\because i\\bmod p=0\\)

\\(\\therefore p为i的质因子\\)

\\(\\therefore \\varphi(i\*p)=i\*p\*\\prod\_\{i=1\}^\{n\} (1-\\frac\{1\}\{p\_i\})=\\varphi(i)\*p\\)

--------------------

\\(3.\\varphi(i\*p)=\\varphi(i)\*(p-1)\\) , \\(if\\space i \\bmod p \\ne 0\\)

#### 证明： ####

\\(\\because i \\bmod p \\ne 0\\)

\\(\\therefore p不为i的质因子\\)

\\(\\therefore \\varphi(i\*p)=i\*p\*(1-\\frac\{1\}\{p\})\*\\prod\_\{i=1\}^n (1-\\frac\{1\}\{p\_i\})=i\*(p-1)\*\\prod\_\{i=1\}^n (1-\\frac\{1\}\{p\_i\})=\\varphi(i)\*(p-1)\\)

--------------------

于是可以通过这三个性质再配合上线性筛预处理处欧拉函数。

Code：

void Get(int listsize) { memset(isprime,1,sizeof(isprime)); isprime[1]=false; for(int i=2;i<=listsize;i++) { if(isprime[i]) { prime[++primesize]=i; phi[i]=i-1; } for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } } }

转载于:https://www.cnblogs.com/wwlwQWQ/p/11377343.html