Warning


由于本博客作者实在是太弱啦,本篇文章可能存在大量的错误,漏洞,不规范,不合法之处。若您发现本文章所存在的任何问题,请您尽快在评论区指出,十分感谢!

另外,本文随意转载,但请注明出处。

问题


给出一个正整数 n,求出 n 的欧拉函数值\(\varphi (n)\) 

n≤1015

解答


求单个欧拉函数值的时间复杂度是 \(O(\sqrt n)\)

不需要很多的知识前置储备,我们只需要知道欧拉函数的通式为:$$\varphi (n)=n\prod_{p|n }^{n}\left ( 1-\frac{1}{p} \right )$$

(证明未完成)

代码如下:

 

新的问题


给出一个正整数 n,求出$$\sum_{i=1}^{n}\varphi (i)$$在十进制下的最后 7 位。

n≤107

解答


很明显,当我们求 n 个欧拉函数值时,上述方法的复杂度为$$O(n\sqrt{n})$$我们无法接受。

所以我们考虑一个能在线性时间内求出多个欧拉函数值的方法。

在解答这个问题之前,你需要掌握如下的前置知识:

  1. 筛法求素数 (链接未完成)
  2. 欧拉函数 (它的相关知识将在本文给出 )

什么是欧拉函数呢?简单的说,在 数论 中,对 正整数 n, 欧拉函数 是小于或等于 n 的数中与 n 互质的数的数目。它是一个 积性函数 ,同时,它具有如下的性质:(令 p 为质数)

  1. 显然的$$\varphi (p)=p-1$$
  2. 若 p 与 x 互质$$\varphi (x*p)=\varphi (x)*\varphi (p)=\varphi (x)*(p-1)$$
  3. 若 p 与 x 不互质$$\varphi (x*p)=\varphi (x)*p$$

证明未完成

代码是很简单的,下面直接给出,注释很详尽:

新的问题


给出一个正整数 n,求出$$\sum_{i=1}^{n}\varphi (i)$$在十进制下的最后 7 位。

n≤1011

解答


未完成

应 dalao 要求,可以先去看这个 http://www.cnblogs.com/lkhll/p/6668489.html


一个非常弱的准退役OIER