解析数论入门

Arahc 11.0
  2021-12-10 08:00 2021-12-10 08:00 创建   2023-03-19 06:56 2023-03-19 06:56 更新      5.7k 字  30 分钟  

简介

数论是纯粹数学的分支之一，主要研究整数的性质。整数可以是方程式的解。有些解析函数中包括了一些整数、质数的性质，透过这些函数也可以了解一些数论的问题。

数论被高斯成为“数学皇后”，是一大必不可少的分支。

OI 里的解析数论主要研究的是狄利克雷卷积、积型函数、筛法。下面将会给出本博客介绍的东西：

  • 常见积性函数（欧拉函数和莫比乌斯函数）。
  • 线性筛。
  • 狄利克雷卷积。
  • 杜教筛和 min25 筛。
  • 欧拉反演。
  • 莫比乌斯反演。

在本文中，若无特殊说明，我们规定 pp 是质数。

积性函数

若对于一个函数 ff 满足对于两个互质的数 a,ba,b 满足 f(a)f(b)=f(ab)f(a)f(b)=f(ab)，则 ff 为积性函数。若其对于任意两个数 a,ba,b 满足 f(a)f(b)=f(ab)f(a)f(b)=f(ab)，则 ff 为完全积性函数。

积性函数有很多：φ,μ,id\varphi,\mu,\rm{id}……下面将会选取两个典型 φ,μ\varphi,\mu 来介绍。

欧拉函数

欧拉函数 φ(n)\varphi(n) 表示 [1,n][1,n] 的正整数中，与 nn 互质的数的个数。

欧拉函数有一些很美妙的性质。首先，根据定义，结合常识，因为质数与小于它的任何正整数都互质，所以有 φ(p)=p−1\varphi(p)=p-1。类似的，对于一个质数的幂，可以得到 φ(pk)=pk−pk−1\varphi(p^k) = p^k- p^{k-1}。这个式子做一个简单的变形，就可以得到 φ(p)=pk(1−1p)\varphi(p) = p^k (1-\frac{1}{p})。

φ(n)=n∏(1−1pi)\varphi(n) = n\prod(1-\frac{1}{p_i})

证明

把 nn 其都可以拆分成 ∏piki\prod p_i^{k_i} 的形式。由于 φ\varphi 是积性函数，p1k1,p2k2⋯p_1^{k_1},p_2^{k_2}\cdots 显然互质，因此有：

φ(n)=∏φ(piki)=∏[piki(1−1pi)]\varphi(n) = \prod \varphi(p_i^{k_i}) = \prod \left[ p_i^{k_i}(1-\frac{1}{p_i}) \right]

前者乘起来是 nn，因此：

φ(n)=n∏(1−1pi)\varphi(n) = n\prod(1-\frac{1}{p_i})

当然还有一些比较有趣的性质，例如如果你算一下 nn 所有因数的欧拉函数值然后加起来。发现其刚好等于 nn。

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

证明

写下分母为 nn 的所有分数 in\frac{i}{n}。然后给每个数约分。约分后的分数里，分母就是 nn 的所有因数，分子就其与其互质的数。

例如 16,26,36,46,56,66\frac{1}{6},\frac{2}{6},\frac{3}{6},\frac{4}{6},\frac{5}{6},\frac{6}{6}，约分变成 16,13,12,23,56,11\frac{1}{6},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{5}{6},\frac{1}{1}。分母为 6,3,2,16,3,2,1 的分别有 2,2,1,12,2,1,1 个，而 φ(6)=2,φ(3)=2,φ(2)=1,φ(1)=1\varphi(6)=2,\varphi(3)=2,\varphi(2)=1,\varphi(1)=1。

如果求出 [1,n][1,n] 中与 nn 互质的数字加起来？

∑d=1nd[gcd⁡(n,d)=1]=nφ(n)2\sum_{d=1}^n d[\gcd(n,d)=1] = \frac{n\varphi(n)}{2}

证明

若 gcd⁡(n,d)=1\gcd(n,d)=1，则根据辗转相除法，gcd⁡(n−i,n)=1\gcd(n-i,n)=1。因此与 nn 互质的数可以两两配对，每对的和都是 nn，一共有 φ(n)2\frac{\varphi(n)}{2} 对。

莫比乌斯函数

莫比乌斯函数 μ(n)\mu(n) 表示：若 nn 存在除 11 外的完全平方数因子，则 μ(n)=0\mu(n)=0，否则，若 nn 有 mm 个不同的质因子，μ(n)=(−1)m\mu(n)=(-1)^m。

和欧拉函数类似，探究一下它的性质，例如如果你求出 nn 的所有质因子的莫比乌斯函数值，然后加起来？

∑d∣nμ(d)=[n=1]\sum_{d\mid n} \mu(d) = [n=1]

证明

μ\mu 为 00 的数对答案没有影响。考虑对于有 kk 个不同质因数的数字 nn，由其中 rr 个相乘得到的就是 μ\mu 不为 00 的因数个数：

∑d∣nμ(d)=∑i=0k(−1)i(ki)\sum_{d\mid n}\mu(d) = \sum_{i=0}^k (-1)^i \binom{k}{i}

二项式定理：

∑i=0k(−1)i(ki)=(1−1)k=0k\sum_{i=0}^k (-1)^i\binom{k}{i} = (1-1)^k = 0^k

当 n=1n=1 时，k=n−1=0k=n-1=0，原式为 11，否则为 00。

莫比乌斯函数还有很多性质，由于涉及到后文的知识，此处先不提及。

线性筛

线性筛可以在 O(n)\mathcal O(n) 的时间内求出 [1∼n][1\sim n] 的素数，和 [1∼n][1\sim n] 每个数的某个积性函数值。其关键点在于，枚举筛子 ii 和质数 jj 时，如果 jj 是 ii 的最小质因子就不需要接着筛了。因为 jj 取更大时 ijij 会被另外一个 ii 更新到。

因此想要筛出一个积性函数 ff，必须要知道的是：

  • f(1)f(1) 的值和 f(p)f(p) 的值。
  • f(ij)f(ij) 如何计算，其中 jj 是 ii 的最小质因子。

例如线性筛欧拉函数，需要知道 φ(ij)\varphi(ij)（jj 是 ii 最小质因子）怎么算，手玩可以发现为 φ(i)j\varphi(i)j。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void GetPhi(int n){
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = 0, phi[1] = 1;
    for(register int i = 2; i <= n; ++i){
        if(isPrime[i]){
            Prime[++cnt] = i,
            phi[i] = i - 1;
        }
        for(register int j = 1; j <= cnt && i * Prime[j] <= n; ++j){
            isPrime[ i * Prime[j] ] = 0;
            if(i % Prime[j] == 0){
                phi[ i * Prime[j] ] = phi[i] * Prime[j]; 
                break; 
            }
            else phi[ i * Prime[j] ] = phi[i] * phi[Prime[j]];
        }
    }
}

再例如莫比乌斯函数，显然 μ(ij)\mu(ij)（jj 是 ii 的最小质因子）为 00：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void GetMu(int n){
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = 0, mu[1] = 1;
    for(register int i = 2; i <= n; ++i){
        if(isPrime[i]){
            Prime[++cnt] = i,
            mu[i] = -1;
        }
        for(register int j = 1; j <= cnt && i * Prime[j] <= n; ++j){
            isPrime[ i * Prime[j] ] = 0;
            if(i % Prime[j] == 0){
                mu[i*prime[j]]=0;
                break; 
            }
            else mu[ i * Prime[j] ] = mu[i] * mu[Prime[j]]
        }
    }
}

高级筛法

狄利克雷卷积

对于三个函数 f,g,hf,g,h，若 h(n)=∑d∣nf(d)g(nd)h(n) = \sum_{d\mid n} f(d)g(\frac{n}{d})，则记 f∗g=hf\ast g=h，hh 为 f,gf,g 的狄利克雷卷积。

狄利克雷卷积满足交换律，结合律，分配率。两个积性函数的狄利克雷卷积也是积性函数。

定义单位元函数 ε(n)=[n=1]\varepsilon(n) = [n=1]，显然对于任意函数有 ε∗f=f\varepsilon\ast f = f。定义函数 1(n)=1\mathrm{1}(n) = 1 和 id(n)=n\mathrm{id}(n) = n。显然这些函数都是积性函数，而且都是完全积性函数。

考虑 1\rm{1} 函数有什么性质，容易发现：

f∗1=∑d∣nf(d)f\ast \mathrm{1} = \sum_{d\mid n} f(d)

后面这一块前面提到过，结合欧拉函数和莫比乌斯函数的性质：

μ∗1=∑d∣nμ(d)=[n=1]=ε\mu\ast\mathrm{1} = \sum_{d\mid n}\mu(d) = [n=1] = \varepsilon

φ∗1=id\varphi\ast\mathrm{1} = \rm{id}

杜教筛

拥有这样的前置知识之后，考虑下面的问题：

给定 nn，求：

ans1=∑i=1nφ(i)ans_1 = \sum_{i=1}^n \varphi(i)

ans2=∑i=1nμ(i)ans_2 = \sum_{i=1}^n \mu(i)

多组数据，T≤10,n<231T\leq 10,n<2^{31}。

因为 nn 的范围很大，显然欧拉筛是筛不过去的。就算能卡进去别忘了还要求一波前缀和。而杜教筛就可以以一个较优秀的复杂度，处理这些函数的前缀和。

设要求的前缀和函数 S(n)=∑i=1nf(i)S(n) = \sum_{i=1}^n f(i)。找一个积性函数 gg，则 f∗gf\ast g 的前缀和为：

sum=∑i=1n(f∗g)(i)=∑i=1n∑d∣if(d)g(id)=∑d=1ng(d)∑i=1⌊nd⌋f(i)=∑d=1ng(d)S(⌊nd⌋)\begin{aligned} sum &= \sum_{i=1}^n (f\ast g)(i) \\ &= \sum_{i=1}^n \sum_{d\mid i} f(d)g(\frac{i}{d}) \\ &= \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\lfloor\frac{n}{d}\right\rfloor) \end{aligned}

因此有：

∑i=1n(f∗g)(i)=g(1)S(n)+∑d=2ng(d)S(⌊nd⌋)\sum_{i=1}^n (f\ast g)(i) = g(1)S(n) + \sum_{d=2}^n g(d) S(\left\lfloor\frac{n}{d}\right\rfloor)

g(1)S(n)=∑i=1n(f∗g)(i)−∑d=2ng(d)S(⌊nd⌋)g(1)S(n) = \sum_{i=1}^n (f\ast g)(i) - \sum_{d=2}^n g(d) S(\left\lfloor\frac{n}{d}\right\rfloor)

SS 为我们要求的函数，现在它可以用数论分块求出。现在只需要做到快速求出 f∗gf\ast g 和 gg 的前缀和。注意到 φ∗1=id,μ∗1=ε\varphi\ast\mathrm{1} = \mathrm{id}, \mu\ast\mathrm{1}=\varepsilon，而 ε,1,id\varepsilon,\mathrm{1},\mathrm{id} 的前缀和是显然的。因此令 g=1g=\rm{1} 即可。

实际递归时先用线性筛求出 10710^7 以内的前缀和会少一点递归层数。杜教筛的复杂度为 O(n23)\mathcal O(n^\frac{2}{3})。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10000000;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}

int n,p[N+1],m[N+1];

map<int,int> mu,ph;

inline int Mu(int n){
    if(n<=N) return m[n];
    if(mu.count(n)) return mu[n];
    int res=1;
    for(register int l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=(r-l+1)*Mu(n/l);
    }
    return mu[n]=res;
}
inline int Phi(int n){
    if(n<=N) return p[n];
    if(ph.count(n)) return ph[n];
    int res=n*(n+1)/2;
    for(register int l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=(r-l+1)*Phi(n/l);
    }
    return ph[n]=res;
}

bool isp[N+1];
int pr[N+1],cnt;

inline void init(int n){
    memset(isp,1,sizeof(isp)),isp[1]=0;
    p[1]=m[1]=1;
    for(register int i=2;i<=n;++i){
        if(isp[i]){
            pr[++cnt]=i;
            p[i]=i-1,m[i]=-1;
        }
        for(register int j=1;j<=cnt && pr[j]*i<=n;++j){
            isp[i*pr[j]]=0;
            if(i%pr[j]==0){
                p[i*pr[j]]=p[i]*pr[j],
                m[i*pr[j]]=0;
                break;
            }
            p[i*pr[j]]=p[i]*p[pr[j]],
            m[i*pr[j]]=-m[i];
        }
    }
    for(register int i=1;i<=n;++i)
        p[i]+=p[i-1],m[i]+=m[i-1];
}

signed main(){
    init(N);
	for(register int T=read();T>=1;--T){
	    n=read();
	    write(Phi(n)),putchar(' '),
	    write(Mu(n)),putchar('\n');
	}
	return 0;
}

min25 筛

对于积性函数 ff 满足 f(pk)=pk(pk−1)f(p^k) = p^k(p^k-1)。求 ∑i=1nf(i)\sum_{i=1}^n f(i)。

n≤1010n\leq 10^{10}，答案对大质数取模。

我们发现对于这样的函数，很难找到一个 gg 满足 gg 和 f∗gf\ast g 的前缀和比较好算。因此需要考虑另外一个筛法：min25 筛。

为了方便，设 P\mathbb{P} 为质数集。PiP_i 表示第 ii 个质数，P0=0P_0=0。不妨先考虑求出这个东西：

∑i=1nf(i)[i∈P]\sum_{i=1}^n f(i) [i\in\mathbb P]

设 g(n,j)g(n,j) 表示 [1,n][1,n] 中所有数的最小质因子里，大于 PjP_j 的合数的 ff 的和。对 jj 分类讨论：

  • 若 Pj2>nP_j^2>n，则区间 (Pj,n)(P_j,n) 中不存在这样的合数。g(n,j)=g(n,j−1)g(n,j) = g(n,j-1)。
  • 否则，g(n,j)g(n,j) 与 g(n,j−1)g(n,j-1) 相比，少了最小质因子恰好为 PjP_j 的贡献，相当于把 PjP_j 的贡献提出来：g(n,j)=g(n,j−1)−f(Pj)g(nPj,j)g(n,j) = g(n,j-1) - f(P_j)g(\frac{n}{P_j},j)。然而这种做法会算重 i∈[1,j)i\in[1,j) 这部分的 f(Pi)f(P_i) 的贡献，考虑到这段 PiP_i 只有 n\sqrt{n} 种，线性筛预处理，暴力减。

然后就得到了：

g(n,j)={g(n,j−1)Pj2>ng(n,j−1)−f(Pj)(g(nPj,j−1)−∑i=1j−1f(Pi))otherwiseg(n,j) = \begin{cases} g(n,j-1) & P_j^2>n \\ g(n,j-1) - f(P_j)(g(\frac{n}{P_j},j-1) - \sum_{i=1}^{j-1} f(P_i)) & \text{otherwise} \end{cases}

g(i,0)g(i,0) 的值显然，然后就可以枚举 jj 递推了。设 h(n,j)h(n,j) 表示最小质因子大于等于 PjP_j 的所有 ff 的和，考虑一些合数，可以枚举其最小质因子和次数：

h(n,j)=g(n,∣P∣)−∑i=1j−1f(Pi)+∑k≥j∑t≥1(f(Pkt+1)+f(Pkt)h(nPkt,k+1))h(n,j) = g(n,\left|\mathbb P\right|) - \sum_{i=1}^{j-1} f(P_i) + \sum_{k\geq j}\sum_{t\geq 1} ( f(P_k^{t+1})+f(P_k^t)h(\frac{n}{P_k^t},k+1) )

最后只需要求出 h(n,1)h(n,1) 即可。注意细节：前面都没有考虑 11，最后在答案里加上。

简单数论反演

欧拉反演

欧拉反演基于这样一个式子：

φ∗1=id\varphi\ast\mathrm{1} = \mathrm{id}

也就是 ∑d∣nφ(d)=n\sum_{d\mid n} \varphi(d) = n。

欧拉反演和莫比乌斯反演其实差不多，实际上，欧拉反演是莫比乌斯反演的基础。

Luogu3768 简单的数学题

求：

∑i=1n∑j=1nijgcd⁡(i,j)\sum_{i=1}^n \sum_{j=1}^n ij\gcd(i,j)

n≤1010n\leq 10^{10}。

题解

枚举 gcd⁡(i,j)\gcd(i,j) 的约数进行欧拉反演：

∑i=1∑j=1ij∑d∣i,jφ(d)\sum_{i=1}\sum_{j=1} ij \sum_{d\mid i,j} \varphi(d)

交换 ∑\sum：

∑d=1nd2φ(d)(∑i=1⌊nd⌋i)2\sum_{d=1}^n d^2\varphi(d) \left(\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor} i\right)^2

然后数论分块解决这个问题，后面这个根据小学奥数得到 [n(n+1)2]2[\frac{n(n+1)}{2}]^2。前面这个东西，考虑杜教筛，令 g=id2g=\mathrm{id}^2，有：

(f∗g)(n)=∑d∣nφ(d)d2(nd)2\begin{aligned}(f\ast g)(n) = \sum_{d\mid n} \varphi(d)d^2(\frac{n}{d})^2\end{aligned}

化简有：

(f∗g)(n)=n2∑d∣nφ(d)=n3(f\ast g)(n) = n^2\sum_{d\mid n}\varphi(d) = n^3

n3n^3 前缀和为 n(n+1)(2n+1)6\frac{n(n+1)(2n+1)}{6}。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10000000;int mod;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}

int n,inv2,inv6;

bool isp[N+1];
int pr[N+1],cnt,p[N+1];

inline void init(int n){
    memset(isp,1,sizeof(isp)),isp[1]=0;
    p[1]=1;
    for(register int i=2;i<=n;++i){
        if(isp[i]){
            pr[++cnt]=i;
            p[i]=i-1;
        }
        for(register int j=1;j<=cnt && pr[j]*i<=n;++j){
            isp[i*pr[j]]=0;
            if(i%pr[j]==0){
                p[i*pr[j]]=p[i]*pr[j];
                break;
            }
            p[i*pr[j]]=p[i]*p[pr[j]];
        }
    }
    for(register int i=1;i<=n;++i)
        p[i]=(p[i-1]+p[i]*i%mod*i%mod)%mod;
}

map<int,int> mp;

inline int S2(int n){
    n%=mod;
    return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
inline int S3(int n){
    n%=mod;
    return mi(n*(n+1)%mod*inv2%mod,2);
}

inline int Phi(int n){
    if(n<=N) return p[n];
    if(mp.count(n)) return mp[n];
    int res=S3(n);
    for(register int l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=(S2(r)-S2(l-1)+mod)%mod*Phi(n/l)%mod,
        res=(res+mod)%mod;
    }
    return mp[n]=(res+mod)%mod;
}

int ans;

signed main(){
	mod=read(),n=read();
	inv2=mi(2),inv6=mi(6),init(N);
	for(register int l=1,r;l<=n;l=r+1){
	    r=n/(n/l);
	    ans+=S3(n/l)*(Phi(r)-Phi(l-1)+mod)%mod,
	    ans=(ans%mod+mod)%mod;
	}
	write(ans);
	return 0;
}

莫比乌斯反演

记 F,fF,f 满足 F(n)=∑d∣nf(d)F(n) = \sum_{d\mid n} f(d)，也就是 F=f∗1F=f\ast\rm{1}，两边同时乘上一个 μ\mu 得到 F∗μ=1∗μ∗f=ε∗f=fF\ast\mu = \mathrm{1}\ast\mu\ast f = \varepsilon\ast f = f。

因此得到了莫比乌斯反演：

F(n)=∑d∣nf(d)⇒f(n)=∑d∣nF(d)μ(nd)F(n) = \sum_{d\mid n} f(d) \Rightarrow f(n) = \sum_{d\mid n} F(d)\mu(\frac{n}{d})

当然，更加常用的例子其实是下面两个：

  • μ∗id=φ\mu\ast\mathrm{id} = \varphi。
  • μ∗1=ε\mu\ast\mathrm{1} = \varepsilon。

不难发现这两个其实是莫比乌斯反演的特例。

Luogu6222 简单题

给定 kk，多组询问，每次给定 nn 求：

∑i=1∑j=1(i+j)kgcd⁡(i,j)μ2(gcd⁡(i,j))\sum_{i=1}\sum_{j=1} (i+j)^k \gcd(i,j) \mu^2(\gcd(i,j))

T≤104,k<231,n≤107T\leq 10^4,k<2^{31},n\leq 10^7。

题解

枚举约数除掉是莫反的经典操作：

∑d=1n∑i=1⌊nd⌋∑j=1⌊nd⌋d(di+dj)kμ2(d)[gcd⁡(i,j)=1]\sum_{d=1}^n \sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor} d(di+dj)^k\mu^2(d) [\gcd(i,j)=1]

然后交换 ∑\sum：

∑d=1nμ2(d)dk+1∑i=1⌊nd⌋∑j=1⌊nd⌋(i+j)k[gcd⁡(i,j)=1]\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor} (i+j)^k [\gcd(i,j)=1]

然后 μ∗1=ε\mu\ast\mathrm{1}=\varepsilon：

∑d=1ndk+1μ2(d)∑p=1⌊nd⌋μ(p)∑i=1⌊ndp⌋∑j=1⌊ndp⌋(pi+pj)k\sum_{d=1}^n d^{k+1}\mu^2(d)\sum_{p=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \mu(p) \sum_{i=1}^{\left\lfloor\frac{n}{dp}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{dp}\right\rfloor} (pi+pj)^k

换元，设 t=dpt=dp：

∑t=1n∑d∣tdk+1μ2(d)(td)kμ(td)∑i=1⌊nt⌋∑j=1⌊nt⌋(i+j)k\sum_{t=1}^n \sum_{d\mid t} d^{k+1}\mu^2(d)(\frac{t}{d})^k \mu(\frac{t}{d}) \sum_{i=1}^{\left\lfloor\frac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{t}\right\rfloor} (i+j)^k

记 S(n)=∑i=1n∑j=1n(i+j)kS(n) = \sum_{i=1}^n\sum_{j=1}^n (i+j)^k，显然 tkt^k 是完全积性函数可以筛，但是如何求 S(x)S(x) 呢？设 F(x)=∑i=1xik,G(x)=∑i=1xF(i)F(x) = \sum_{i=1}^x i^k,G(x) = \sum_{i=1}^x F(i)。

S(x)=G(2x)−2G(x)S(x) = G(2x)-2G(x)

证明

考虑数学归纳法，x=1x=1 时显然成立。当 S(n)=G(2n)−2G(n)S(n) = G(2n)-2G(n) 时：

S(n+1)=S(n)+2∑i=1n(i+n+1)k−(2n+2)k=G(2n)−2G(n)+F(2n+1)−2F(n+1)+F(2n+2)=∑i=12n+2F(i)−2∑i=1n+1F(i)=G(2n+2)−2G(n+1)\begin{aligned}S(n+1) &= S(n) + 2\sum_{i=1}^n (i+n+1)^k - (2n+2)^k \\&= G(2n)-2G(n) + F(2n+1)-2F(n+1)+F(2n+2) \\&=\sum_{i=1}^{2n+2} F(i) - 2\sum_{i=1}^{n+1} F(i) \\&= G(2n+2)-2G(n+1)\end{aligned}

然后考虑剩下的部分，设 f(t)=∑d∣tdμ2(d)μ(td)f(t) = \sum_{d\mid t} d\mu^2(d)\mu(\frac{t}{d})。因为它是积性函数狄利克雷卷积卷出来的，因此它也是一个积性函数。不难发现：

  1. f(1)=1,f(p)=p−1f(1)=1,f(p)=p-1。
  2. f(p2)=−pf(p^2)=-p。
  3. f(pk)=0f(p^k)=0（k>2k>2），因为 dd 和 td\frac{t}{d} 至少有一个能被 p2p^2 整除。

然后就可以线性筛了。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define int unsigned int
using namespace std;
const int max_n=20000007;
inline int read(){
	int x=0;char c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int mi(int a,int p){
    int res=1;
    while(p){
        if(p&1) res*=a;
        a*=a,p>>=1;
    }
    return res;
}

int n,k,f[max_n],s[max_n],ans;

bool isp[max_n];
int pr[max_n/100],cnt,t[max_n];

inline void init(int n){
    f[1]=t[1]=1;
    memset(isp,1,sizeof(isp)),isp[1]=0;
    for(register int i=2;i<=n;++i){
        if(isp[i]){
            pr[++cnt]=i,
            f[i]=i-1,t[i]=mi(i,k);
        }
        for(register int j=1;j<=cnt && i*pr[j]<=n;++j){
            isp[i*pr[j]]=0,
            t[i*pr[j]]=t[i]*t[pr[j]];
            if(i%pr[j]==0){
                if((i/pr[j])%pr[j]>0)
                    f[i*pr[j]]=-pr[j]*f[i/pr[j]];
                break;
            }
            f[i*pr[j]]=f[i]*(pr[j]-1);
        }
    }
    for(register int i=1;i<=n;++i)
        s[i]=s[i-1]+f[i]*t[i];
    for(register int i=1;i<=n;++i)
        f[i]=f[i-1]+t[i];
    for(register int i=1;i<=n;++i)
        f[i]=f[i-1]+f[i];
}

signed main(){
	int T=read();n=read(),k=read();
	init(n*2);
	while(T--){
	    n=read(),ans=0;
    	for(register int l=1,r;l<=n;l=r+1){
    	    r=n/(n/l);
    	    ans+=(s[r]-s[l-1])*(f[n/l*2]-f[n/l]*2);
    	}
    	write(ans),putchar('\n');
	}
	return 0;
}
  • 标题: 解析数论入门
  • 作者: Arahc
  • 创建于 : 2021-12-10 08:00:00
  • 更新于 : 2023-03-19 06:56:00
  • 链接: https://arahc.github.io/2021/12/10/【笔记】解析数论入门/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
解析数论入门
  1. 简介
  2. 积性函数
    1. 欧拉函数
    2. 莫比乌斯函数
  3. 线性筛
  4. 高级筛法
    1. 狄利克雷卷积
    2. 杜教筛
    3. min25 筛
  5. 简单数论反演
    1. 欧拉反演
    2. 莫比乌斯反演