筛素数

void shai()

{

    no[1]=true;no[0]=true;

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

    {

        if(!no[i])

            p[++p[0]]=i;

        int j=1,t=i*p[1];

        while(j<=p[0] && t<=r)

        {

            no[t]=true;

            if(i%p[j]==0) //每一个数字都有最小质因子。这里往后的数都会被筛过的，break

                break;

            t=i*p[++j];

        }

    }

}

O（n）筛欧拉函数

void find()

{

    phi[1]=1;

    for(int i=2;i<=maxn-1;i++)

    {

        if(!is_prime[i]){prime[++cnt]=i,phi[i]=i-1;}

        int j=1,t=2*i;

        while(j<=cnt&&t<=maxn-1)

        {

            is_prime[t]=1;

            if(i%prime[j]==0)

            {                        //欧拉函数公式是phi[i]=i*(1-1/p1)*(1-1/p2)..

                phi[t]=phi[i]*prime[j];//质因子同样，仅仅有i不同，且t=prime[j]*i，故作此

                break;

            }

            else phi[t]=phi[i]*(prime[j]-1);//质因子不一样，由于欧拉函数是积性函数，就是

            j++;t=prime[j]*i;     //=phi[i]*phi[j]

        }

    }

}

sqrt(n)求单个欧拉函数

long long phi(long long x)

{

    long long t=x,l=sqrt(x);

    for(long long i=2;i<=l;i++)

    if(x%i==0)

    {

        t=t/i*(i-1);   //欧拉函数公式，一定是先除再加

        while(x%i==0)

            x/=i;

    }

    if(x>1)     //对x大于sqrt(x)的质因子最多有1个

        t=t/x*(x-1);

    return t;

}

O（n）筛莫比乌斯函数

void shai()

{

    no[1]=1;mu[1]=1;

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

    {

        if(!no[i])

            p[++p[0]]=i,mu[i]=-1;//仅仅有1个质因数，所以为-1

        int j=1,t=p[1]*i;

        while(j<=p[0] && t<=maxl)

        {

            no[t]=1;

            if(i%p[j]==0)

            {

                mu[t]=0;//某质因数的指数不为1。依据定义=0

                break;

            }

            mu[t]=-mu[i];//依据定义，当x=p1*p2*..*pk,mu[x]=（-1）^k。

            t=p[++j]*i;  //这里多一个质因数，自然就多乘一个-1

        }

    }

}

O（n）求1到n对mod的逆元

转自http://blog.csdn.net/whyorwhnt/article/details/19169035

inv[i] = ( MOD - MOD / i ) * inv[MOD%i] % MOD

证明：

设t = MOD / i , k = MOD % i

则有 t * i + k == 0 % MOD

有 -t * i == k % MOD

两边同一时候除以ik得到

-t * inv[k] == inv[i] % MOD

即

inv[i] == -MOD / i * inv[MOD%i]

即

inv[i] == ( MOD - MOD / i) * inv[MOD%i]

证毕

适用于MOD是质数的情况。可以O(n)时间求出1~n对模MOD的逆元

inv[1]=1;

for(long long i=2;i<maxl && i<mod;i++)

    inv[i]=(mod-mod/i)*inv[mod%i]%mod;