The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

积性函数(转)

这个文章主要介绍了3算法

1线性时间筛素数

2线性时间求前n个数的欧拉函数值

3线性时间求前n个数的约数个数

一、   首先介绍下积性函数。

下面是wiki的条目:

 

在非数论的领域,积性函数指有对于任何a,b都有性质f(ab)=f(a)f(b)的函数。

 

在数论中的积性函数。对于正整数n的一个算术函数f(n)当中f(1)=1且当a,b互质,f(ab)=f(a)f(b),在数论上就称它为积性函数。

若某算术函数f(n)符合f(1)=1,且就算a,b不互质,f(ab)=f(a)f(b),称它为完全积性的。

 

例子

φ(n) -欧拉φ函数,计算与n互质的正整数之数目

μ(n) -默比乌斯函数,关于非平方数的质因子数目

gcd(n,k) -最大公因子,当k固定的情况

d(n) n的正因子数目

σ(n) n的所有正因子之和

σk(n): 因子函数,n的所有正因子的k次幂之和,当中k可为任何复数。在特例中有:

σ0(n) = d(n)

σ1(n) = σ(n)

1(n) -不变的函数,定义为 1(n)=1 (完全积性)

Id(n) -单位函数,定义为 Id(n)=n (完全积性)

Idk(n) -幂函数,对于任何复数、实数k,定义为Idk(n) = nk (完全积性)

Id0(n) = 1(n)

Id1(n) = Id(n)

ε(n) -定义为:若n = 1,ε(n)=1;若n > 1,ε(n)=0。有时称为“对于狄利克雷回旋的乘法单位”(完全积性)

(n/p) -勒让德符号,p是固定质数(完全积性)

λ(n) -刘维尔函数,关于能整除n的质因子的数目

γ(n),定义为γ(n)=(-1)ω(n),在此加性函数ω(n)是不同能整除n的质数的数目

所有狄利克雷特性均是完全积性的

 

 

二、再介绍下线性筛素数方法

bool notp[mr];//素数判定

__int64 pr[670000],pn,ans;//pr存放素数,pn当前素数个数。

 

void getprime()

{

    pn=0;

    memset(notp,0,sizeof(notp));

    for(int i=2;i<mr;i++)

    {

        if(!notp[i])pr[pn++]=i;

        for(int j=0;j<pn && pr[j]*i<mr;j++)

        {

            notp[pr[j]*i]=1;

            if(i%pr[j]==0)break;

        }

    }

}

 

利用了每个合数必有一个最小素因子

每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。

代码中体现在:

if(i%pr[j]==0)break;

pr数组中的素数是递增的,i能整除pr[j],那么i*pr[j+1]这个合数肯定被pr[j]乘以某个数筛掉。

因为i中含有pr[j],pr[j]pr[j+1]小。接下去的素数同理。所以不用筛下去了。

在满足i%pr[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。

 

 

三、结合线性筛素数算法的优化算法

基于这个线性筛素数算法,我们可以很容易地得到某个数的最小素因子。

因为当i%pr[j]!=0的时候,最小素因子pr[j]i互质,满足积性函数的条件,可以直接得到f(i*pr[j])=f(i)*f(pr[j]).

不过当i%pr[j]==0时我们必须根据该积性函数本身的特性进行计算.或者在筛的同时保存并递推些附加信息.总之要O(1)求得f(i*pr[j])及完成递推附加信息.

 

下面的两个例子是欧拉函数phi和约数个数.这两个是最常用和最有优化价值的。

利用上面的性质都可以很容易地把前n个用O(n)时间推出来.

当然,利用这个性质还可以对其他积性函数进行优化,这里仅介绍两个常用和有优化价值的。

 

1)欧拉函数(phi)

传统的算法:

对于某素数pn|p(n能整除p)

if( (n/p) % i == 0 ) phi(n)=phi(n/p)*i;

else phi(n)=phi(n/p)*(i-1);

 

这个传统算法的性质正好用在筛素数算法中.

pn的最小素因子,n/p包含该因子p,phi(n)=phi(n/p)*i;否则phi(n)=phi(n/p)*(i-1);

ppr[j], n/pi, ni*pr[j].

 

 

2)约数个数(divnum)

约数不能像phi那么自然,但还是有不错的方法.

约数个数有个性质

divnum(n)=(e1+1)*(e2+1)...(ei表示n的第i个质因数的个数.)

传统方法就是对每个数分解质因数,获得各因数个数再用上式.

 

开一个空间e[i]表示最小素因子的次数

这次说直接点:

筛到i j个素数

 

对于divnum

如果i|pr[j] 那么 divnum[i*pr[j]]=divsum[i]/(e[i]+1)*(e[i]+2) //最小素因子次数加1

否则 divnum[i*pr[j]]=divnum[i]*divnum[pr[j]] //满足积性函数条件

 

对于e

如果i|pr[j] e[i*pr[j]]=e[i]+1; //最小素因子次数加1

否则 e[i*pr[j]]=1; //pr[j]1



转自:http://hi.baidu.com/cjhh314/blog/item/bfe13bce20fb7c3db600c85c.html

posted on 2009-11-03 13:46 abilitytao 阅读(466) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理