数论

发表于 更新于

唯一分解定理

n=∏ipiαiνp(i)(n)=αin=\prod_i p_i^{\alpha_i}\\ \nu_{p(i)}(n)=\alpha_i

素数

Fermat 素性检验：检验 an−1≡1(modn)a^{n-1}\equiv 1\pmod n。

二次探测定理：检验 x2≡1(modn)  ⟹  x≡1(modn)∨x≡n−1(modn)x^2\equiv 1\pmod n\implies x\equiv 1\pmod n\lor x\equiv n-1\pmod n。

上述检验若失败则说明 nn 必不是质数。

Miller Rabin

分解 Fermat 素性检验中的指数，n−1=u×2tn-1=u\times 2^t。

对于一个底数 aa，求出 v=au(modn)v=a^u\pmod n。进行至多 tt 次 v←v2v\gets v^2 过程中进行二次探测。

通过所有二次探测后进行 Fermat 素性检验。

Miller Rabin 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
inline ll qmul(ll a,ll b,ll m)
{
    return (ull(a)*b-ull(ld(a)/m*b)*m+m)%m;
}
inline ll qpow(ll x,ll y,ll m)
{
    ll r=1;
    for(;y;x=qmul(x,x,m),y/=2)if(y&1)r=qmul(r,x,m);
    return r;
}
constexpr ll A[7]={2,325,9375,28178,450775,9780504,1795265022};
// constexpr ll A[12]={2,3,5,7,11,13,17,19,23,29,31,37};
inline bool MillerRabin(ll n)
{
    if(n<3||n%2==0)return n==2;
    if(n%3==0)return n==3;
    ll u=n-1,t=0;
    while(u%2==0)u/=2,t++;
    for(int i=0;i<7;i++)
    {
        ll v=qpow(A[i]%n,u,n);
        if(v==0||v==1)continue;
        int s=0;
        for(;s<t;s++)
        {
            if(v==n-1)break;
            v=qmul(v,v,n);
        }
        if(s==t)return false;
    }
    return true;
}

筛

埃氏筛

1
2
3
4
5
6
7
8
std::vector<int> p;
std::bitset<V> np;
for(int i=2;i<=n;i++)if(!np[i])
{
    p.push_back(i);
    if(1ll*i*i>n)continue;
    for(int j=i*i;j<=n;j+=i)np[j]=true;
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
std::vector<int> p;
std::bitset<A> np;
for(int i=2;i<=n;i++)
{
    if(!np[i])p.push_back(i);
    for(int j:p)
    {
        if(1ll*i*j>n)break;
        np[i*j]=true;
        if(i%j==0)break;
    }
}

爱用哪个用哪个。级别在 10810^8 以下时埃氏筛可能有常数优势，10910^9 时线性筛更快。

欧几里得算法

若 p=kq+rp=kq+r，则 r=p mod q,k=⌊p/q⌋r=p\bmod q,k=\lfloor p/q\rfloor。

设 a>b,g=gcd⁡(a,b)a>b,g=\gcd(a,b)，则 g∣a,g∣bg\mid a,g\mid b，即 g∣(a−kb)g\mid (a-kb)，g∣a mod bg\mid a\bmod b。

可得 gcd⁡(a,b)=gcd⁡(b,a−b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a-b)=\gcd(b,a\bmod b)。

1
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

裴蜀定理

∃x,y∈Z,ax+by=gcd⁡(a,b)\exists x,y\in\mathbb{Z},ax+by=\gcd(a,b)。

显然可以在欧几里得算法过程中构造。

设 a=kb+r,gcd⁡(a,b)=bx+rya=kb+r,\gcd(a,b)=bx+ry，则 gcd⁡(a,b)=bx+(a−kb)y=ay+(x−ky)b\gcd(a,b)=bx+(a-kb)y=ay+(x-ky)b。

即 x′=y,y′=x−kyx'=y,y'=x-ky。

exCRT

为了求解线性同余方程 ax≡b(modm)ax\equiv b\pmod m，通过 exgcd 求解 gcd⁡(a,m)=ax′+my′\gcd(a,m)=ax'+my'。

可得

ax′bgcd⁡(a,m)+my′bgcd⁡(a,m)=ba\frac{x'b}{\gcd(a,m)}+m\frac{y'b}{\gcd(a,m)}=b

这样我们就解出了一个特解。发现若 x0x_0 是一个解，那么 x0+kmgcd⁡(a,m)x_0+k\dfrac{m}{\gcd(a,m)} 也是一个解。

ax′b+kmgcd⁡(a,m)+my′b−kagcd⁡(a,m)=ba\frac{x'b+km}{\gcd(a,m)}+m\frac{y'b-ka}{\gcd(a,m)}=b\\

即 x≡x0(modm/gcd⁡(a,m))x\equiv x_0\pmod{m/\gcd(a,m)}。

那么对于方程组

{a1x≡b1(modm1)a2x≡b2(modm2)⋮anx≡bn(modmn)\begin{cases} a_1x\equiv b_1\pmod{m_1}\\ a_2x\equiv b_2\pmod{m_2}\\ \qquad\vdots\\ a_nx\equiv b_n\pmod{m_n}\\ \end{cases}

解得

{x≡x1(modm1′)x≡x2(modm2′)⋮x≡xn(modmn′)\begin{cases} x\equiv x_1\pmod{m_1'}\\ x\equiv x_2\pmod{m_2'}\\ \qquad\vdots\\ x\equiv x_n\pmod{m_n'}\\ \end{cases}

然后每次合并两个方程。设 x=x1+m1′y1=x2+m2′y2x=x_1+m_1'y_1=x_2+m_2'y_2，可得 m1′y1=x2−x1+m2′y2≡x2−x1(modm2′)m_1'y_1=x_2-x_1+m_2'y_2\equiv x_2-x_1\pmod{m_2'}。解得 y1≡y0(modm2′/gcd⁡(m1′,m2′))y_1\equiv y_0\pmod{m_2'/\gcd(m_1',m_2')}。代回有 x=x1+m1′y1≡x1+m1′y0(modm1′m2′/gcd⁡(m1′,m2′)=lcm⁡(m1′,m2′))x=x_1+m_1'y_1\equiv x_1+m_1'y_0\pmod{m_1'm_2'/\gcd(m_1',m_2')=\operatorname{lcm}(m_1',m_2')}。

CRT

数论分块

数论函数

常见完全积性函数：

  • 元函数 ε(n)=[n=1]\varepsilon(n)=[n=1]
  • 单位函数 idk(n)=nkid_k(n)=n^k，恒等函数 I(n)=id0(n)=1I(n)=id_0(n)=1

常见积性函数：

  • 莫比乌斯函数 μ(n)=I−1\mu(n)=I^{-1}
  • 约数函数 σk(n)=∑d∣ndk\sigma_k(n)=\sum_{d\mid n}d^k，d(n)=σ0d(n)=\sigma_0
  • 欧拉函数 φ(n)=∑i=1n[i⊥n]\varphi(n)=\sum_{i=1}^{n}[i\perp n]

积性分解

f(n)=∏if(piνp(i)(n))f(n)=\prod_{i}f\left(p_i^{\nu_{p(i)}(n)}\right)

积性函数取值只与素数幂次处取值有关。

Dirichlet 卷积

(f∗g)(n)=∑d∣nf(d)g(n/d)(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)

Dirichlet 卷积有交换律，结合律，单位元 ε\varepsilon，逆元 f∗g=εf*g=\varepsilon。

Dirichlet 卷积的计算可以通过枚举倍数的方式枚举约数，做到线性对数。

求逆元，已知 f,g(1)=1f,g(1)=1，递推

(f∗g)(n)=ε(n)∑d∣nf(d)g(n/d)=0f(1)g(n)+∑d∣n,d≠1f(d)g(n/d)=0g(n)=−∑d∣n,d≠1f(d)g(n/d)\begin{aligned} (f*g)(n)&=\varepsilon(n)\\ \sum_{d\mid n}f(d)g(n/d)&=0\\ f(1)g(n)+\sum_{\mathclap{d\mid n,d\ne 1}}f(d)g(n/d)&=0\\ g(n)&=-\sum_{\mathclap{d\mid n,d\ne 1}}f(d)g(n/d) \end{aligned}

借助单位元非 11 函数值为零进行构造。

两积性函数的 Dirichlet 卷积仍为积性函数。积性函数的逆仍为积性函数。

莫比乌斯函数

μ=I−1  ⟺  ∑d∣nμ(d)=[n=1]\mu=I^{-1}\iff \sum_{d|n}\mu(d)=[n=1]

根据 μ∗I=ε\mu*I=\varepsilon，其在素数幂次处的取值

μ(1)=1μ(p)I(1)+μ(1)I(p)=0  ⟹  μ(p)=−1∑i=0kμ(pi)=0  ⟹  μ(pk)=0\mu(1)=1\\ \mu(p)I(1)+\mu(1)I(p)=0\implies\mu(p)=-1\\ \sum_{i=0}^k\mu(p^i)=0\implies\mu(p^k)=0

即可得到其定义

μ(n)={0∃d>1,d2∣n(−1)kk=∑i[pi∣n]\mu(n)= \begin{cases} 0&\exists d>1,d^2\mid n\\ (-1)^k&k=\sum_i[p_i\mid n] \end{cases}

本质上，将一个数论函数 ff 卷上 II 得到的 f∗If*I 即为约数意义下的前缀和。若将数的唯一分解视作高维点，前缀和即为所有偏序的点的函数值之和。相对应的 gg 卷上 μ\mu 即为差分，对于每个素因子容斥的结果。

f∗I=g  ⟺  f=g∗μg(n)=∑d∣nf(d)  ⟺  f(n)=∑d∣nμ(n/d)g(d)\begin{aligned} f*I=g&\iff f=g*\mu\\ g(n)=\sum_{d\mid n}f(d)&\iff f(n)=\sum_{d\mid n}\mu(n/d)g(d) \end{aligned}

神秘的倍数求和（后缀和）及倍数差分

g(n)=∑n∣df(d)f(n)=∑n∣dμ(d/n)g(d)\begin{aligned} g(n)&=\sum_{n\mid d}f(d)\\ f(n)&=\sum_{n\mid d}\mu(d/n)g(d) \end{aligned}

意思差不多。

gcd 卷积（？）

线性筛（？）

嵌入式莫比乌斯反演（？）

反演动机

[i⊥j]=[gcd⁡(i,j)=1]=ε(gcd⁡(i,j))=∑d∣gcd⁡(i,j)μ(d)=∑d∣i,d∣jμ(d)[i\perp j]=[\gcd(i,j)=1]=\varepsilon(\gcd(i,j))=\sum_{\mathclap{d\mid\gcd(i,j)}}\mu(d)=\sum_{\mathclap{d\mid i,d\mid j}}\mu(d)

用她来拆 φ\varphi 的定义式

φ(n)=∑i=1n[i⊥n]=∑i=1n∑d∣i,d∣nμ(d)=∑d∣n∑i=1n[d∣i]μ(d)=∑d∣n(n/d)μ(d)\begin{aligned} \varphi(n)&=\sum_{i=1}^n[i\perp n]\\ &=\sum_{i=1}^n\sum_{\mathclap{d\mid i,d\mid n}}\mu(d)\\ &=\sum_{\mathclap{d\mid n}}\sum_{i=1}^n[d\mid i]\mu(d)\\ &=\sum_{\mathclap{d\mid n}}(n/d)\mu(d)\\ \end{aligned}

可得 φ=id∗μ\varphi=id*\mu，即 φ∗I=id\varphi*I=id

∑d∣nφ(d)=n\sum_{d\mid n}\varphi(d)=n

上式可以通过枚举 gcd⁡\gcd 来理解

n=∑i=1n1=∑g∣n∑i=1n[gcd⁡(i,n)=g]=∑g∣n∑g∣i[gcd⁡(i/g,n/g)=1]=∑g∣nφ(n/g)=∑d∣nφ(d)\begin{aligned} n&=\sum_{i=1}^n1\\ &=\sum_{g\mid n}\sum_{i=1}^n[\gcd(i,n)=g]\\ &=\sum_{g\mid n}\sum_{g\mid i}[\gcd(i/g,n/g)=1]\\ &=\sum_{g\mid n}\varphi(n/g)\\ &=\sum_{d\mid n}\varphi(d)\\ \end{aligned}

带入 n=gcd⁡(a,b)n=\gcd(a,b) 可得

gcd⁡(a,b)=∑d∣gcd⁡(a,b)φ(d)=∑d∣a,d∣bφ(d)\gcd(a,b)=\sum_{\mathclap{d\mid\gcd(a,b)}}\varphi(d)=\sum_{\mathclap{d\mid a,d\mid b}}\varphi(d)

求和

∑i=1ngcd⁡(i,n)=∑i=1n∑d∣i,d∣nφ(d)=∑d∣n∑i=1n[d∣i]φ(d)=∑d∣n(n/d)φ(d)=(id∗φ)(n)\begin{aligned} \sum_{i=1}^n\gcd(i,n)&=\sum_{i=1}^n\sum_{\mathclap{d\mid i,d\mid n}}\varphi(d)\\ &=\sum_{d\mid n}\sum_{i=1}^n[d\mid i]\varphi(d)\\ &=\sum_{d\mid n}(n/d)\varphi(d)\\ &=(id*\varphi)(n)\\ \end{aligned}

同样的，我们可以枚举 gcd⁡\gcd

∑i=1ngcd⁡(i,n)=∑g∣ng∑i=1n[gcd⁡(i,n)=g]=∑g∣ng∑g∣i[gcd⁡(i/g,n/g)=1]=∑g∣ngφ(n/g)=(id∗φ)(n)\begin{aligned} \sum_{i=1}^n\gcd(i,n)&=\sum_{g\mid n}g\sum_{i=1}^n[\gcd(i,n)=g]\\ &=\sum_{g\mid n}g\sum_{g\mid i}[\gcd(i/g,n/g)=1]\\ &=\sum_{g\mid n}g\varphi(n/g)\\ &=(id*\varphi)(n)\\ \end{aligned}

借助 φ\varphi 代表 gcd⁡\gcd 为 11 进行化简。

欧拉函数的计算。考虑素数幂次 pkp^k 取值，想要与其互质当且仅当不含素因子 pp，其他（不互质）的数在 [1,pk][1,p^k] 共 pk/p=pk−1p^k/p=p^{k-1} 个，故 φ(pk)=pk−pk−1=(p−1)pk−1\varphi(p^k)=p^k-p^{k-1}=(p-1)p^{k-1}。

另一个形式 p∣n  ⟹  φ(pn)=p×φ(n)p\mid n\implies \varphi(pn)=p\times\varphi(n)。

约数函数相关结论

σk=idk∗I  ⟹  d=I∗Id(n)=∏id(piνp(i))=∏i(νp(i)+1)σ(n)=∏iσ(piνp(i))=∏i∑j=0νp(i)pj=∏ipiνp(i)+1−1pi−1d(n)=∑i=1n⌊ni⌋\begin{aligned} \sigma_k&=id_k*I\implies d=I*I\\\\ d(n)&=\prod_i d\left(p_i^{\nu_{p(i)}}\right)=\prod_i(\nu_{p(i)}+1)\\ \sigma(n)&=\prod_i\sigma\left(p_i^{\nu_{p(i)}}\right)=\prod_i\sum_{j=0}^{\nu_{p(i)}}p^j=\prod_i\dfrac{p_i^{\nu_{p(i)}+1}-1}{p_i-1}\\ d(n)&=\sum_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor \end{aligned}