欧拉函数


。。。。好久没更新blog了。。。。
随便水水...

2015.10.07
公式。。
大概就是随便分解一下质因数咯。。

如果记不住。。看下面几个性质就记住了..

性质一:积性函数

性质二:关于质数

若p是指数有..
$$\varphi (p)=p-1$$
$$\varphi (p^k)=p^{k-1} * \varphi (p)$$
知道这两个性质大概就会求出n以内的所有函数值了。。。

2015.10.10

一些简单的应用..

1.求小于等于N的与N互质的数的和

额。。一般我们用的方法是分解质因数然后容斥。。(来算与N不互质的的数然后搞搞咯)..例题Co-prime..
然而对于这个特殊的范围确实可以利用欧拉函数搞搞。。
考虑一一对应的计算

proof
反证法
若此时 其中
所以 矛盾。。
因此原命题成立。

考虑到 之和为所以答案即为

2.求所有n整除的数

额。。看起来很庞大的工程?
我们从欧拉函数的公式入手。
$$ \varphi(n)=n \Pi _ {i=1} ^{n} \frac{pi-1}{pi}   (pi | n)$$
然后我们考虑所以
$$ \Pi _ {i=1} ^{n} (pi-1) | \Pi _ {i=1} ^{n} pi $$
即有两种情况,只包含因子2,包含2,3
所以可以写成其中

上面两个问题都比较简单。。如果实在不会。。随便打个表也是能搞出来的。。

3.欧拉函数降幂

大概这个东西叫做欧拉函数降幂吧。
$$ A^B = A ^{B \mod \varphi(C) + \varphi(C)} (mod C) $$
注意到才有降幂意义
如果B比较大的话这个东西可以做到O(位数)还是不错的。。比O(logB)要小的多..

应用:上帝与集合的正确用法

4.欧拉定理

$$ a ^ {\varphi(n)}= 1(mod n)$$

.PE432

Recent Posts

comments powered by Disqus