欧拉函数

• 定义
  对于正整数n小于等于n的数中与n互质的数的个数记为\(\varphi(n)\),即为欧拉函数

• 欧拉公式
  由算数基本定理任意一个正整数都可以写作n=\(p_1^{a_1}p_2^{a_2}\cdots pk^{a^k}\)
  那么\(\varphi(n)=n\prod\limits{i=1}^{k}({1-\frac{1}{p_i}})\)

• 数学证明
  首先\(\varphi(n)\)是一个积性函数
  即 \(\varphi(a_1a_2)=\varphi(a_1)\varphi(a_2)\)这个的证明这里不作叙述可看这个链接积性证明
  然后从1到一个数\(p_n^{a_n}\)一共有\(p_n^{a_n}\)个数其中与其不互质的有\(p_n,2p_n,3p_n\dots p_n^{a_n}(pn^{a{n-1}}*p_n)\)一共有\(pn^{a{n-1}}\)个数，所以与其互质的一共有\(p_n^{a_n}(1-\frac{1}{p_n})个\)
  所以有：

\[ \varphi(n)=\varphi(p_1^{a_1})*\varphi(p_2^{a_2})\dots\varphi(p_k^{a_k})\
=p_1^{a_1}(1-\frac{1}{p_1})*p_2^{a_2}(1-\frac{1}{p_2})\dotsp_k^{a_k}\\=n\prod\limits_{i=1}^{k}(1-\frac{1}{p_i}) \]

• 代码实现

  #include using namespace std; int main() { int n; cin>>n; while(n–) { int a; scanf(“%d”,&a); int res=a; for(int i=2;i<=a/i;i++) { if(a%i==0) { res=res/i(i-1);//注意先除再乘防止爆int } while(a%i==0) { a/=i; } } if(a>1) { res=res/a(a-1); } printf(“%d\n”,res); }

  return 0;
  

  }

• 代码细节
  注意res=res/i*(i-1)这里要先除再乘防止爆int 可能会有疑问我们推导的公式中\(1-\frac{1}{p_i}\)是一个小数但是c++里/是向下取整的，那么这里会不会有问题呢?其实是完全没问题的 我们可以看到只有当a%i==0时我们才会进行res的操作并且每次循环中a至少都和res除i除的一样多也就是说只要a中有约数 i 那么res中也一定有 i 一定不会出现小数。

Written with StackEdit中文版.