求欧拉函数值 && 打表O(n)

在数论，对正整数n，欧拉函数是1~n的数中与n互质的数的数目，我们记为$\phi (n)$，(后面欧拉定理中会用到)。此函数以其首名研究者欧拉命名。例如$\phi (8)=4$，因为1,3,5,7均和8互质。

$\phi (n)$求解公式： 现假设$n$有$r$个质因子p₁、p₂、p₃、、、p_r，则：

即$\phi (n)=n{\prod }_{i=1}^r(1-\frac{1}{pi})$

欧拉函数的两个性质：来自欧拉函数及其证明（这两个性质可以推出上面的公式）

欧拉函数既然是积性函数，就说明如果n可以分解成两个互质的整数之积，$n=p1\times p2$，则 $\phi (n)=\phi (p1p2)=\phi (p1)\phi (p2)$如果n是质数的某一个次方，即n = p^k (p为质数，k为大于等于1的整数)，则 $\phi (n)=p^k-p^{k-1}=p^{k-1}\ast (p-1)$

1、单独求某个欧拉函数值代码：$O(\sqrt{n})$

int fn(int x) { int ans=x; for(int i=2; i<=sqrt(x); i++) { if(x%i==0) { ans-=ans/i; while(x%i==0) x/=i; } } if(x>1) ans-=ans/x; return ans; }

2、埃氏筛、欧拉筛

$⟹$质数打表———埃氏筛&&欧拉筛

2.1 求1~n的欧拉函数值：$O(nloglogn)$ //埃氏筛法中每个合数会被它的每个质因子筛一遍，就完美地求出欧拉函数值了

bool vis[manx]; void make_prime(int n) { memset(vis,0,sizeof(vis)); vis[0]=vis[1]=1; for(int i=1;i<=n;i++) ans[i]=i; for(int i=2;i<=n;i++) { if(!vis[i]) { for(int j=i;j<=n;j+=i) { vis[j]=1; ans[j]=ans[j]*(i-1)/i;//主角在这里 } } } }

2.2 求1~n的欧拉函数值：$O(n)$ 原理：以下证明来自欧拉线性筛（筛质数，求欧拉函数）

那么，为了求可以在可以在线性时间内求出来所有的欧拉函数，需要事先知道三个性质： 对于一个质数$p$: 性质1：$\phi (p)=p-1$; 因为p为质数，而从1到$p$，只有$p$与$p$自本身不互质，其余的$(p-1)$个数字都与$p$互质，因此得出性质1； 性质2：对于$i$%$p==0,\phi (i\ast p)=p\ast \phi (i)$; 性质3：对于$i$%$p!=0$, $\phi (i\ast p)=\phi (i)\ast (p-1);$ 利用了欧拉函数的积性。而又通过性质1可知,$p-1=\phi (p)$,因此$\phi (i\ast p)=\phi (i)(p-1)=\phi (i)\ast \phi (p)$; 这个，本人才疏学浅，看了各种证明，但还是不明白性质2，性质3是怎么得出来的，所以先当作结论记住吧。 知道了这三个结论之后，在配合欧拉筛筛质数，就可以得出范围内所有的数字的欧拉函数。

---

2020.7.19对性质2的理解：对于$i\%p==0$（即p也是i的因子），与i互质的数肯定与 i*p互质。比如i=35，p=5时，与i互质的数有1，2，3，4，6…那么这些数肯定也与35 *5互质，而且将这些数分别加上35（或35 *2，35 *3，35 *4）后可以发现它们还是与35 *5互质，所以与35 *5的数的个数为φ(35) *5

---

代码：

void make_prime(int n) { int cou=0,ans[manx]; memset(prime,0,sizeof(prime)); memset(vis,0,sizeof(vis)); vis[0]=vis[1]=1; for(int i=2; i<=n; i++) { if(!vis[i]) { prime[cou++]=i; ans[i]=i-1;//改动部分1（对应性质1） } for(int j=0; j<cou; j++) { if(i*prime[j]>n) break; vis[i*prime[j]]=1; if(i%prime[j]==0) { ans[i*prime[j]]=ans[i]*prime[j];//改动部分2（对应性质2） break; } else ans[i*prime[j]]=ans[i]*ans[prime[j]];//改动部分3（对应性质3） //或者写成ans[i*prime[j]]=ans[i]*(prime[j]-1); } } }

例题：Farey Sequence 感想：质因子是个神奇的存在