对于正整数欧拉函数是小于等於的所有数中与互质的数的个数。
(这个证明不是很显然这个链接里面有很多种证明方法)
,其中是的所有质因数
对于,可以用总数 減 的倍数的数量 (p是质数只有p的倍数与 不互质)
根据积性函数性质可得:
过程:对每个质数,对区间内包含這个质因子的数的欧拉函数值乘上.
题意:找到与n互质的第 k个数
开始┅看n是1e6 敲了个暴力结果tle了后来发现k达到了 1e8
所以需要用到欧拉函数。