首页 > 其他 > 详细

欧拉函数

时间:2016-01-27 14:26:29      阅读:147      评论:0      收藏:0      [点我收藏+]

在数论,对正整数n,欧拉函数是小于n的数中与n互质的数的数目。

 

首先我们给出欧拉函数的通式:

技术分享其中p1, p2……pk为n的所有质因数,n是不为0的整数。

 

以上式子是如何得到的呢?

 

下面给出证明:

先将n分解质因数为技术分享

然后利用容斥原理来减去p1、p2……pk的倍数的个数,即技术分享

然后我们加上同时时两个因数的倍数的数的个数,即技术分享

再减去同时为三个因数的数的个数……即可总结出如下公式

技术分享

接着便可变形为以上给出的欧拉函数的通式。

 

欧拉函数

原文:http://www.cnblogs.com/wls001/p/5163018.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!