积性函数（求欧拉函数和莫比乌斯函数的值）

利用素数筛法求欧拉函数和莫比乌斯函数的值：

如果函数f满足gcd(a,b)=1时，有f(ab)=f(a)*f(b),则f叫作积性函数

如果取消互质的条件，则叫完全积性函数。

前置知识：

1.欧拉函数：φ（n）表示1~n中与n互质的数的个数

　　计算公式为：φ（n）=n*(1-1/p1)*(1-1/p2)*...*(1-1/pk)

2.莫比乌斯函数：μ（n）

把n分解为：n=p1^k2*p2^k2*...*pr^kr(其中p均为质数)

有如下性质

　　1.当n=1时，μ（n）=1

　　2.当k1=k2=...=kr=1时，μ（n）=（-1）^r

　　3.其余情况μ（n）=0.

我们可以利用素数的线性筛法在O（n）的时间内求出欧拉函数和莫比乌斯函数的值

int prime[233],pcnt//pcnt代表几个质数 
bool not_prime[23333];

int phi[23333],mu[23333];
//phi是欧拉函数，mu是莫比乌斯函数。 

void xxs(int n)
{
    not_prime[1]=true;
    for(int a=2;a<=n;a++)
    {
        if(not_prime[a]==false)
        {
            prime[++pcnt]=a;
            phi[a]=a-1;
            mu[a]=-1;
            //如果a是质数，那么phi(a)=a*(1-1/a)=a-1
            //a=a^1,所以mu(a)=(-1)^1=-1    
        } 
        for(int b=1;b<=pcnt;b++)
        {
            int v=a*prime[b];
            if(v>n)
                 break;
            not_prime[v]=true;
            if(a%prime[b]==0)
            {
                phi[v]=phi[a]*prime[b];
                /*设(1-1/p1)*...*(1-1/pk)=C 
                则phi(a)=a*C;
                因为a是prime[b]的倍数，所以phi(a)的C中一定有一个p为prime[b] 
                v=a*prime[b],那么phi(v)的C与phi(a)的C相同
                原因是phi(a)中已经有prime[b]这一个质数
                所以a再乘上一个已经有的prime[b](也就是v),对分解出来的质因子种类没有影响
                举个例子，a能分解出p1,p2,prime[b],p4....pn这些质因数
                因为v=a*prime[b],所以v分解出来的也是p1,p2,prime[b],p4....pn这些质因数。 
                也就是说，phi(v)的C中没有跟phi(a)的C不一样的质数
                进而，phi(v)=v*C=a*prime[b]*C=prime[b]*phi(a).*/
                mu[v]=0;
                //a是prime[b]的倍数，v=a*prime[b]
                //所以v里至少有prime[b]的二次方，那么mu[v]=0 
            }
            else
            {
                phi[v]=phi[a]*phi[prime[b]];
                mu[v]=mu[a]*mu[prime[b]];
                //如果a%prime[b]!=0,
                //因为phi和mu都是积性函数，所以可以直接相乘 
            }
            if(a%prime[b]==0)
                break;
        }
    }
}