数论函数筛法模板+TG的实用工具整理

· · 个人记录

数论函数筛法模板+TG的实用工具整理

标签（空格分隔）：数论

本博客与数学定义共同使用效果更佳

目录

线性筛约数个数

声明：借鉴 genshy 博客

对于每一个数都有唯一分解定理

p=p_1^{k1}\times p_2^{k2}\times p_3^{k3}\times …\times p_n^{kn}

维护两个数组 g_i 表示 i 的最小质因子的次数， f_i 表示 i 的约数个数和

这个数的约数个数可以写为 f_i=\prod^{n}_{i=1}(k_i+1)

1、当 n 是质数时， g_n=1,f_n=2

对于性质 2 和 3 来说 设 i=\dfrac{n}{prime_j},其中 prime_j 为 n 的最小质因子。

2、当 prime_j 是 i 的某个质因子时，则有 g_n=g_i+1,f_n=\dfrac{f_i\times (g_i+2)}{g_i+1}

这里做一下解释说明:

首先，现行筛的终止条件是i \bmod prime_j=0,那么当 prime_j 达到这个条件的时候，就会立即终止，而因为这是第一个可以整除 i 的，所以说 prime_j 一定是 i 的最小质因子，而且质数是从小到大枚举的，一旦到达 i\times prime_j=n 的条件是，那么 prime_j 一定是 n 的最小质因数，那么就可以得到:

g_n=g_i+1

继续看下一个，根据定义可以知道 f_n =\prod_{i=1} (k_i+1)，通过展开来找找规律：

f_i=\prod_{j=1}(k_j+1)=(g_i+1)\times k_2 \times … \times k_{\infty} f_n=\prod_{j=1}(k_j+1)=(g_n+1)\times k_2\times … \times k_{\infty} f_n=(g_i+2)\times k_2 \times …\times k_{\infty} \text{由 i } \times \text{prime}_j =n\ \text{得出 i 与 n只差一个最小质因子的次数，其余质因子的次数完全一样} \text{通过上下类比可得} f_n=\frac{(g_i+2)\times f_i}{g_i+1}

3、当 p 与 d 互质时，g_n=1 , f_n=f_d\times f_p

void get_prime()
{
    g[1]=1;
    f[1]=1;
    for(int i=2;i<=N-5;i++)
    {
        if(!check[i])
        {
            prime[++tot]=i;
            g[i]=1;
            f[i]=2;
        }
        for(int j=1;j<=tot&&i*prime[j]<=N-5;j++)
        {
            //最先枚举到的prime一定是这个数的最小质因子 
            check[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                g[i*prime[j]]=g[i]+1;
                //因为prime[j]可以整除i。
                //说明当前prime[j]也是i的最小
                //质因子
                f[i*prime[j]]=f[i]*(g[i*prime[j]]+1)/(g[i]+1);
                break;
            }
            else
            {
                g[i*prime[j]]=1;//因为最小质因子只有一个prime[j]
                f[i*prime[j]]=f[i]*f[prime[j]];//积性函数 
            }
        }
    }
}

求单个值的欧拉函数

首先，根据唯一分解定理可得：

p=p_1^{k1}\times p_2^{k2}\times p_3^{k3}\times …\times p_n^{kn}

可以得到：

\varphi(p)=p\times (1-\frac{1}{p_1})\times (1-\frac{1}{p_2}\times) … \times (1-\frac{1}{p_n})

那么在OI中运算可以化为

p\times (1-\frac{1}{p_1})=\frac{p}{p_1}\times (p_1-1) 
void get_phi(int x)
{
    phi=x;
    int prime=x;
    for(int i=2;i*i<=x;i++)
    {
        if(prime%i==0)
            phi=phi/i*(i-1);
        while(prime%i==0)
            prime/=i;

    }
    if(prime>1) 
        phi=phi/prime*(prime-1);
}

线性筛欧拉函数

首先我们由定义知道 \varphi(1)=1

其次，根据积性函数的性质又可以知道

\varphi(ab)=\varphi(a)\times \varphi(b) \ \ (a\perp b)

那么对于一个数 a 和他的最小质因子 prime_j 我们可以得到：

\varphi(a)=\varphi(\frac{a}{prime_j})\times prime_j

那么就可以推出如何线性筛欧拉函数了

void get_phi()
{
    phi[1]=1;//
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=n&&prime[j]<=n/i;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*phi[prime[j]];
            //互质直接用积性函数的性质 
        }
    }
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+phi[i]; 
}

线性筛莫比乌斯函数

由定义可以知道 \mu(1)=1

当一个数含有平方因子时，\mu(a)=0

当一个数为质数时，\mu(a)=-1

根据这个性质就可以用线性筛来求莫比乌斯函数了

void get_mu()
{
    mu[1]=1;
    for(int i=2;i<=M;i++)
    {
        if(!vis[i])
            prime[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&prime[j]<=M/i;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else
                mu[i*prime[j]]=-mu[i];
        }
    }
}

快速幂原理介绍

听说过快速幂的应该都知道他可以在 O(\log \ n) 的时间内求一个 p^k 的值，那么你真的了解他的原理么？

首先快速幂是建立在二进制运算的基础上，其实我们可把次数看做是一个二进制数，就比如说 p^{10} 的次数的二进制为 1010。

这个快速幂的原理其实就是把次数转换成二进制来进行加法运算。

只有在有 1 的位置上进行计算，其他时候就预处理要乘的数。

以上面的例子来说：

p^{10}=p^2 \times p^8

转换成二进制来看就是 :

p^{({1010})_2}=p^{({1000})_2}\times p^{({10})_2}

由此可以看到其实就是一个实行次数二进制加法的过程，就可以快速求出一个次数巨大的数的值了qwq

int quick(int x,int p,int mod)//mod其实可以宏定义
{
    //求 x^p%mod ;
    int ret=1;
    while(p)
    {
        if(p&1) ret=x*ret%mod;//遇到1了，进行二进制加法
        x=x*x%mod;//实际上就是将次数<<1的过程
        p>>=1;
    }
    return ret%mod;
}

取模神器

像我这种一遇到取模就头疼的孩子，自从有了这个就再也不怕了/cy

namespace Mod {
    long long mul(long long a,long long b,long long mod) {
        long long tmp = a * b - (long long)((long double)a * b / mod + 0.5) * mod;
        return tmp < 0 ? tmp + mod : tmp;
    }
    int P;
    void Build_Mod(int v) {P = v;}
    inline int cH(long long x) {return (x % P + P) % P;}
    int Pow_M(long long x, long long y) {long long ret = 1; x = cH(x);while (y) {if (y & 1) ret = mul(ret , x , P);x = mul(x , x , P), y >>= 1;}return cH(ret);}
    int inv(long long x) {return Pow_M(x, P - 2);}
    struct modint {
        int x;
        modint(int x = 0) : x(x) {}
        modint operator = (const modint a) {x = a.x; return *this;}
        modint operator = (const int a) {x = cH(a); return *this;}
    };
    inline modint operator + (modint a, modint b) {return modint(a.x + b.x >= P ? a.x + b.x - P : a.x + b.x);}
    inline modint operator + (modint a, long long b) {return modint(cH((long long)a.x + b));}
    inline modint operator - (modint a, modint b) {return modint(a.x < b.x ? a.x - b.x + P : a.x - b.x);}
    inline modint operator - (modint a, long long b) {return modint(cH((long long)a.x - b));}
    inline modint operator * (modint a, modint b) {return modint(mul(a.x , b.x , P));}
    inline modint operator * (modint a, long long b) {return modint(cH(mul(a.x , b , P)));}
    inline modint operator / (modint a, modint b) {return modint(mul(a.x , inv(b.x) , P));}
    inline modint operator / (modint a, long long b) {return modint(mul(a.x , inv(b) , P));}
    inline int operator == (modint a, modint b) {return a.x == b.x;}
    inline modint operator += (modint &a, modint b) {a = a + b; return a;}
    inline modint operator += (modint &a, long long b) {a = a + b; return a;}
    inline modint operator -= (modint &a, modint b) {a = a - b; return a;}
    inline modint operator -= (modint &a, long long b) {a = a - b; return a;}
    inline modint operator *= (modint &a, modint b) {a = a * b; return a;}
    inline modint operator *= (modint &a, long long b) {a = a * b; return a;}
    inline modint operator /= (modint &a, modint b) {a = a / b; return a;}
    inline modint operator /= (modint &a, long long b) {a = a / b; return a;}
    inline istream & operator >> (istream &in, modint &a) {in >> a.x; return in;}
    inline ostream & operator << (ostream &out, modint b) {out << b.x; return out;}
    inline modint operator ^ (modint x, long long y) {return Pow_M(x.x, y);}
    inline modint Ch(int x) {return modint(cH(x));}
    inline void read(modint &x) {long long t; scanf("%lld", &t), x = t % P;}
    inline void print(modint x) {printf("%d", x.x);}
    inline void print(modint x, char c) {printf("%d%c", x.x, c);}
    modint One = 1, Two = 2;
};