用求欧拉方程通解函数求质数

对于正整数欧拉函数是小于等於的所有数中与互质的数的个数

(这个证明不是很显然这个链接里面有很多种证明方法)

,其中是的所有质因数

对于,可以用总数 減 的倍数的数量 (p是质数只有p的倍数与 不互质)

根据积性函数性质可得:

区间处理欧拉函数(筛法)

过程:对每个质数,对区间内包含這个质因子的数的欧拉函数值乘上.


  

题意:找到与n互质的第 k个数

开始┅看n是1e6 敲了个暴力结果tle了后来发现k达到了 1e8

所以需要用到欧拉函数。

我要回帖

更多关于 求欧拉方程通解 的文章

 

随机推荐