数论杂谈

· · 算法·理论

数论分块

使得\left \lfloor \frac{n}{i} \right \rfloor=\left \lfloor \frac{n}{j} \right \rfloor成立的且满足i\le j \le n的最大的{\Large j=\left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor} \right \rfloor}

复杂度：\lfloor\frac{n}{i}\rfloor取到相等的段数只有O(\sqrt{n})段，因而复杂度是O(\sqrt{n})，枚举的点分别为 1,2,\dots,\sqrt{n},\lfloor\frac{n}{\sqrt{n}}\rfloor,\dots,\lfloor\frac{n}{2}\rfloor,\lfloor\frac{n}{1}\rfloor

线性求逆元

即O(n)时间对于i\in[1,n]，求出在模质数p意义下所有i^{-1}

考虑递推计算，假设要计算i^{-1}，那么设 x=\lfloor\frac{p}{i}\rfloor,y=p\bmod i，于是p=xi+y，那么

xi+y\equiv 0 \pmod p \\ i^{-1}y^{-1}(xi+y)\equiv 0\pmod p \\ xy^{-1}+i^{-1}\equiv 0\pmod p \\ i^{-1}\equiv -xy^{-1}\pmod p \\ i^{-1}\equiv \left(p-\lfloor\frac{p}{i}\rfloor\right)(p\bmod i)^{-1}\pmod p

于是可以递推计算，初值1^{-1}=1，时间复杂度O(n)

费马小定理：

a^{p-1}\equiv 1 \pmod p \\ 其中p\in P

欧拉定理：

a^{\varphi(n)}\equiv1\pmod n \\ 其中(a,n)=1

扩展欧拉定理

\left\{\begin{matrix} a^b\equiv a^{b\bmod \varphi(m)}\pmod m,b<\varphi(m) \\ a^b\equiv a^{b\bmod \varphi(m)+\varphi(m)}\pmod m,b\ge\varphi(m) \end{matrix}\right.

威尔逊定理

(n-1)!\equiv -1 \pmod n \\ 其中n\in P

莫比乌斯函数

性质：

[n=1]=\sum_{d|n}\mu(d)

Example

[n=1]=\sum_{d|n}\mu(d) \\ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] \\ =\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[\gcd(i,j)=1] \\ =\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|\gcd(i,j)}\mu(d) \\ =\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|i\wedge d|j}\mu(d) \\ =\sum_{d=1}^{n}\mu(d)\lfloor \frac{n}{kd} \rfloor \lfloor\frac{m}{kd} \rfloor \\

筛

void get_primes(int n)
{
    mu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!st[i]) 
        {
            primes[++cnt]=i;
            mu[i]=-1;
        }
        for (int j=1;primes[j]<=n/i;j++)
        {
            st[i*primes[j]]=true;
            if (i%primes[j]==0) break;
            mu[i*primes[j]]=-mu[i];
        }
    }
}

欧拉函数

性质：

n=\sum_{d|n}\varphi(d)

Example:

n=\sum_{d|n}\varphi(d) \\ \sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j) \\ \sum_{i=1}^{n}\sum_{i=1}^{m}\sum_{d|\gcd(i,j)}\varphi(d) \\ =\sum_{i=1}^{n}\sum_{i=1}^{m}\sum_{d|i\wedge d|j}\varphi(d) \\ =\sum_{d=1}^{n}\varphi(d)\lfloor \frac{n}{d} \rfloor \lfloor\frac{m}{d} \rfloor

筛

void get_primes(int n)
{
    phi[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!st[i]) 
        {
            primes[++cnt]=i;
            phi[i]=i-1;
        }
        for (int j=1;primes[j]<=n/i;j++)
        {
            st[i*primes[j]]=true;
            if (i%primes[j]==0)
            {
                phi[i*primes[j]]=phi[i]*primes[j];
                break;
            }
            phi[i*primes[j]]=phi[i]*(primes[j]-1);
        }
    }
}

\gcd容斥

为了计算出满足\gcd(...)=x的数量，可以计算出\gcd为x的倍数的数量，记为f_x，然后将x的倍数的容斥掉，从大到小处理，将

f_x\leftarrow f_x - \sum_{k>1}f_{kx}

然后f_x记录的就是满足\gcd(...)=x的数量

exgcd

裴蜀定理：对于不为0的整数a,b，存在整数x,y使得

ax+by=\gcd(a,b)

对于不定方程ax+by=c，设d=\gcd(a,b)，此时方程有解当且仅当d|c，可使用exgcd求出一组满足ax+by=d的解x,y，则可得原方程的一组解为x_0=\frac{c}{d}x,y_0=\frac{c}{d}y

而此时方程的通解为：

\left\{\begin{matrix} x=x_0+k\frac{b}{d} \\ y=y_0-k\frac{a}{d} \end{matrix}\right.

积性函数：

对于任意互质的整数a,b，都有f(ab)=f(a)f(b)，则称f为积性函数

几个积性函数：\epsilon , I , id

\epsilon(n)=[n=1] \\ I(n)=1 \\ id(n)=n

狄利克雷卷积

设f,g是两个积性函数，那么

(f*g)(n)=\sum_{d|n}f(d)g\left(\frac{n}{d}\right)

是其狄利克雷卷积

有结论：

\mu * I=\epsilon \\ \varphi * I=id \\ \mu * id=\varphi

杜教筛

杜教筛可以在亚线性复杂度内求出积性函数的前缀和

求积性函数f的前缀和S(n)，即求

S(n)=\sum_{i=1}^{n}f(i)

再搞一个积性函数g，考虑求f和g的狄利克雷卷积的前缀和，即

\sum_{i=1}^{n}(f*g)(i) \\ =\sum_{i=1}^{n}\sum_{d|i}f(d)g\left(\frac{i}{d}\right) \\ =\sum_{d=1}^{n}g(d)\sum_{d|i}f\left(\frac{i}{d}\right) \\ =\sum_{d=1}^{n}g(d)\sum_{i=1}^{\left \lfloor \frac{n}{d}\right\rfloor}f(i) \\ =\sum_{d=1}^{n}g(d)S\left(\left \lfloor \frac{n}{d}\right\rfloor\right)

接着我们考虑其中的g(1)S(n)是什么，用前缀和思想，有

g(1)S(n)=\sum_{d=1}^{n}g(d)S\left(\left \lfloor \frac{n}{d}\right\rfloor\right)-\sum_{d=2}^{n}g(d)S\left(\left \lfloor \frac{n}{d}\right\rfloor\right) \\ =\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d)S\left(\left \lfloor \frac{n}{d}\right\rfloor\right)

得到核心式子：

g(1)S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d)S\left(\left \lfloor \frac{n}{d}\right\rfloor\right)

只要选取合适的g，即可整除分块递归计算

直接算时间复杂度：

O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{i}+\sum_{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i}}\right)=O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i}}\right)=O\left(\int_{1}^{\sqrt{n}}\sqrt{\frac{n}{i}}\right)=O(n^{\frac{3}{4}})

考虑预处理出前n^c\space (c>\frac{1}{2})个答案，那么只需要计算\lfloor\frac{n}{n^{1-c}}\rfloor,\dots,\lfloor\frac{n}{2}\rfloor,\lfloor\frac{n}{1}\rfloor，时间复杂度：

O\left(n^c+\int_{1}^{n^{1-c}}\sqrt{\frac{n}{i}}\right)=O\left(n^c+n^{1-\frac{1}{2}c}\right)

取c=\frac{2}{3}，预处理前n^{\frac{2}{3}}的答案，时间复杂度为O (n^{\frac{2}{3}})

计算\mu的前缀和：

考虑\mu * I=\epsilon，于是取g=I，f*g=\epsilon，于是变成求\epsilon,I的前缀和，直接做

ll getSmu(ll n)
{
    if (n<N) return smu[n];
    if (Smu.count(n)) return Smu[n];
    ll res=1;
    for (ll l=2,r;l<=n;l=r+1)
    {
        if (n/l!=0) r=n/(n/l);
        else r=n;
        int x=n/l;
        res-=(r-l+1)*getSmu(x);
    }
    return Smu[n]=res;
}

计算\varphi的前缀和：

考虑\varphi*I=id，于是取g=I,f*g=id，于是求I,id的前缀和，也是简单的，直接做

ll getSphi(ll n)
{
    if (n<N) return sphi[n];
    if (Sphi.count(n)) return Sphi[n];
    ll res=1ll*n*(n+1)/2;
    for (ll l=2,r;l<=n;l=r+1)
    {
        if (n/l!=0) r=(n/(n/l));    
        else r=n;   
        int x=n/l;
        res-=1ll*(r-l+1)*getSphi(x);
    }
    return Sphi[n]=res;
}