函数定义

$$
\begin{aligned}
\
I(n)&=1\
\epsilon(n)&=[n=1]\
id(n)&=n
\end{aligned}
$$

卷积定义

$$
(f*g)(x)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})
$$

有以下性质：
$$
\begin{aligned}
fg&=gf\
(fg)h&=f(gh)\
(f+g)h&=fh+gh
\end{aligned}
$$
三个等式：
$$
\begin{aligned}
\muI=\epsilon\
\phiI=id\
\muid=\phi
\end{aligned}
$$

  • 证明：

  • 第一个等式：

    我们把式子展开：$(\mu* I)(n)=\sum\limits_{d|n}\mu(d)I(\dfrac{n}{d})=\sum\limits_{d|n}\mu(d)$，根据莫比乌斯函数的定义不难发现，我们可以认为 $n=p_1p_2…p_m$ ，即我们只保留指数的种类而非其指数，这是因为所有带指数的式子对答案都没有贡献。我们考虑每个因子选与不选两种情况，不难发现我选奇数个因子和偶数个因子的方案数都是 $2^{m-1}$ 次方。注意上面的讨论并不包括 $n=1$ ，所以根据莫比乌斯函数定义，当且仅当 $n=1$ 时，卷积值才为 $1$ 否则为 $0$ 。定理得证。

  • 第二个等式:

    $(\phi*I)(n)=\sum\limits_{d|n}\phi(d)I(\dfrac{n}{d})=\sum\limits_{d|n}\phi(d)$，令 $n=p_1^{m_1}p_2^{m_2}…p_k^{m_k}$，我们实际上是在枚举 $n$ 的某一个因子。根据 $\phi(n)$ 为一个积性函数，我们可以把所有的 $d$ 拆开，我们就可以得到 $\sum\limits_{d|n}\phi(d)=(\sum\limits_{i_1=0}^{m_1}\phi(p_1^{i_1}))\times …(\sum\limits_{i_k=0}^{m_k}\phi(p_k^{i_k}))$ ，不难发现 $\sum\limits_{i_j=0}^{m_j}\phi(p_j^{i_j})=(\sum\limits_{k=1}^{m_j}p_j^{k-1})(p_j-1)=p_j^{m_j}$ ，所以得证。

  • 第三个等式：

  • 首先证明这样一个等式： $(\epsilonf)(n)=\sum\limits_{d|n}\epsilon(d)f(\dfrac{n}{d})=\epsilon(1)f(n)=f(n)$，所以 $\epsilonf=f$，我们在第三个等式左边同时卷上一个 $\epsilon$ ，得证。

莫比乌斯反演

$$
\begin{aligned}
g(n)=\sum\limits_{d|n}f(d)\Leftrightarrow f(n)=\sum\limits_{d|n}\mu(d)g(\dfrac{n}{d})
\end{aligned}
$$

  • 证明：
  • 注意到上式可以写成 $g=fI\Leftrightarrow f=\mug$，两边同时卷 $I$ 就可以得证。

还有另一种形式：

$$
\begin{aligned}
g(n)=\sum\limits_{n|d}f(d)\Leftrightarrow f(n)=\sum\limits_{n|d}\mu(\dfrac{d}{n})g(d)
\end{aligned}
$$

例题 1

求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^mgcd(i,j)$

技巧 $1$：增加枚举量。
$$
\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)=\sum_{i=1}^n\sum_{j=1}^mid(gcd(i,j))=\sum_{i=1}^n\sum_{j=1}^m\sum\limits_{d|gcd(i,j)}\phi(d)
\end{aligned}
$$
技巧 $2$：交换枚举顺序
$$
\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^m\sum\limits_{d|gcd(i,j)}\phi(d)=\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{d}\right\rfloor}\phi(d)
\end{aligned}
$$
技巧 $3$ ：分离无关变量
$$
\begin{aligned}
\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{d}\right\rfloor}\phi(d)=\sum\limits_{d=1}^{\min(n,m)}\phi(d)\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{d}\right\rfloor}1=\sum\limits_{d=1}^{\min(n,m)}\phi(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor
\end{aligned}
$$

可以在 $O(n)$ 的复杂度内求解。

我们现在考虑这个问题，求：
$$
\begin{aligned}
\sum\limits_{i=1}^n\phi(i)\times\left\lfloor\dfrac{n}{i}\right\rfloor
\end{aligned}
$$
要求复杂度低于 $O(n)$。

考虑 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 怎么算，我们采用数论分块，可以在 $O{\sqrt n}$ 的复杂度下求上面式子的值。

原理如下：

  • 把 $i$ 分成 $i\leq\sqrt n$ 和 $i>\sqrt n$ 来讨论，我们发现 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 只有 $2\sqrt n$ 个取值。

    所以如果我们把 $i$ 取值中式子的值不变的放在一个块中，实际上只有大约 $\sqrt n$ 个块。

  • 所以我们的主要问题是确定一个 $i$ 找到一个 $j$ ，使得 $i$ 到 $j$ 中的所有数，$\left\lfloor\dfrac{n}{i}\right\rfloor$ 的值相同。

  • 首先可以二分，但这样复杂度不会很优秀。

  • 令 $x=\left\lfloor\dfrac{n}{i}\right\rfloor$ ，那么发现 $\left\lfloor\dfrac{n}{x}\right\rfloor$ 就应该等于 $j$ 。可以这么理解，我们实际上是要找到满足 $j\times x\leq n$ 的最大的 $j$ 。那么我们就可以得出 $j=\left\lfloor\dfrac{n}{x}\right\rfloor$ 的结论。

代码：

1
2
3
4
5
6
7
8
9
int get_ans(int n){
    int ans=0;
    for(int i=1;i<=n;){
        int n/(n/i);
        ans+=(n/i);
        i=j+1;
    }
    return ans;
}

如果是两个变量变化的话，我们可以看那个变量先发生变化，然后更新，去变化较早的，本质上是一样的。

例题

代码：

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
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define int long long
#define ull unsigned long long
#define N 1000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T>  inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int phi[N],sumphi[N],prime[N],tail;
bool not_prime[N];

inline void getphi(){
    not_prime[1]=1;phi[1]=1;sumphi[1]=1;
    for(int i=2;i<=N;i++){
        if(!not_prime[i]) prime[++tail]=i,phi[i]=i-1;
        for(int j=1;j<=tail&&prime[j]*i<=N;j++){
            not_prime[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[prime[j]*i]=prime[j]*phi[i];
                break;
            }
            else phi[prime[j]*i]=phi[i]*phi[prime[j]];
        }
    }
//    for(int i=1;i<=100;i++) printf("%d ",phi[i]);
    for(int i=1;i<=N;i++) sumphi[i]=sumphi[i-1]+phi[i];
}

signed main(){
    getphi();int n;
    while(scanf("%lld",&n)){
        if(n==0) break;
        int ans=0;
        for(int i=1;i<=n;){
            int j=n/(n/i);
            ans+=(sumphi[j]-sumphi[i-1])*(n/i)*(n/i);
            i=j+1;
        }
        ans-=(1+n)*n/2;
        printf("%lld\n",ans/2);
    }
    return 0;
}

例题 2

求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=1]$

不难发现：

$$
\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)=\sum_{i=1}^n\sum_{j=1}^m\epsilon(gcd(i,j))=\sum_{i=1}^n\sum_{j=1}^m\sum\limits_{d|gcd(i,j)}\mu(d)=\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor
\end{aligned}
$$

例题 3

对于 $1\le x\le n,1\le y\le n$ ，求解 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)\in Prime]$。

我们有一个非常奇怪的条件，我们考虑增加枚举量，但不是用卷积的形式。

$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)\in Prime]
&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{p\in Prime}[gcd(i,j)=p]\
&=\sum\limits_{p\in Prime}\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{p}\right\rfloor}[gcd(i,j)=1]
\end{aligned}
$$

这就转化成了类似于例题 $2$ 。

上式变成了：

$$
\begin{aligned}
\sum\limits_{p\in Prime}\sum\limits_{d=1}^{\min(\tfrac{m}{d},\tfrac{n}{d})}\mu(d)\left\lfloor\dfrac{n}{pd}\right\rfloor\left\lfloor\dfrac{m}{pd}\right\rfloor
\end{aligned}
$$

但是我们发现，我们还是有两重循环。

技巧 $4$ ：换元法：对于两个变量乘起来的换掉。

令 $x=pd$，则上式变成：
$$
\begin{aligned}
\sum\limits_{x=1}^{min(n,m)}\sum\limits_{p\in Prime,p|x}\mu(\dfrac{x}{p})\times\left\lfloor\dfrac{n}{x}\right\rfloor\left\lfloor\dfrac{m}{x}\right\rfloor=\sum\limits_{x=1}^{min(n,m)}\left\lfloor\dfrac{n}{x}\right\rfloor\left\lfloor\dfrac{m}{x}\right\rfloor\times\sum\limits_{p\in Prime,p|x}\mu(\dfrac{x}{p})
\end{aligned}
$$
而后面那个东西，实际上可以利用积性函数预处理出来。这个题就做完了。

关于后面这个式子预处理方法，我们有：

设 $p_1$ 为 $x$ 的最小素数，如果 $p_1$ 在 $x$ 中的出现次数出现了两次及以上，那么有： $f(x)=\mu(\frac{x}{p_1})$ ，否则有：$f(x)=\mu(\frac{x}{p_1})-f(\frac{x}{p_1})$

不过其实也可以枚举素数 $p$ 的倍数来做，但是这样复杂度不是很对，网上有人说那是埃筛的复杂度，似乎近似于 $O(n\log\log n)$ 。这个复杂度是接近 $O(n)$ 的 。

$\text{upd}:$

实测两种方法都是正确的，且线性做法比非线性快 $1$ 秒。

下面的代码中，注释掉的是非线性做法。

链接

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ld long double
#define ll long long
#define ull unsigned long long
#define N 10000101
#define M 700000
using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

inline int Min(int a,int b){
	return a>b?b:a;
}

int p[M],tail,mu[N],g[N],t,minfac[N];
bool vis[N];
ll ans=0;

int main(){
	mu[1]=1;minfac[1]=1;
	for(int i=2;i<=N-100;i++){
		if(!vis[i]) p[++tail]=i,mu[i]=-1,minfac[i]=i;
		for(int j=1;j<=tail&&i*p[j]<=N-100;j++){
			int v=i*p[j];
			vis[v]=1;
			minfac[i*p[j]]=p[j];
			if(i%p[j]!=0) mu[v]=mu[i]*mu[p[j]];
			else mu[v]=0;
			if(i%p[j]==0) break;
		}
	}
	// for(int i=1;i<=tail;i++)
	// 	for(int j=1;j*p[i]<=N-100;j++)
	// 		g[j*p[i]]+=mu[j];
	for(int i=2;i<=N-100;i++){
		g[i]+=mu[i/minfac[i]];
		if(i%(minfac[i]*minfac[i])!=0) g[i]=g[i]-g[i/minfac[i]];
	}
	for(int i=1;i<=N-100;i++) g[i]+=g[i-1];
	t=read();
	while(t--){
		int n,m;ans=0;
		n=read();m=read();
		for(int l=1,r=0;l<=Min(n,m);l=r+1){
			r=Min(n/(n/l),m/(m/l));
			ans+=(ll)(g[r]-g[l-1])*(ll)(n/l)*(ll)(m/l);
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}

之所以有后面这个式子，是因为我们考虑所有能对 $f$ 造成贡献的数原先有 $p_1$ ，现在没有了，所以符号变化了。

如果 $n=m$ ，我们有一种更优美的做法，从这里开始：

$$
\begin{aligned}
\sum\limits_{p\in Prime}\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}[gcd(i,j)=1]\
\end{aligned}
$$

考虑：

$$
\begin{aligned}
\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{i}[gcd(i,j)=1]\
\end{aligned}
$$

不难发现，如果我们把 $i$ 固定，后面这个东西实际上就是 $\phi(i)$ ，所以如果我们要计算这个式子：

$$
\begin{aligned}
\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}[gcd(i,j)=1]\
\end{aligned}
$$
实际上就是上面这个式子乘上 $2$ 再减去一些重复的部分，不难发现，只有 $i=j$ 的情况被重复枚举了，但只有 $i=j=1$ 的时候才会对答案造成贡献，所以我们直接乘 $2$ 减 $1$ 就可以。

例题

代码：

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
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define int long long
#define ull unsigned long long
#define N 14000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T>  inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int phi[N],sumphi[N],prime[N],tail;
bool not_prime[N];

inline void getphi(int n){
    not_prime[1]=1;phi[1]=1;sumphi[1]=1;
    for(int i=2;i<=n;i++){
        if(!not_prime[i]) prime[++tail]=i,phi[i]=i-1;
        for(int j=1;j<=tail&&prime[j]*i<=n;j++){
            not_prime[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[prime[j]*i]=prime[j]*phi[i];
                break;
            }
            else phi[prime[j]*i]=phi[i]*phi[prime[j]];
        }
    for(int i=1;i<=n;i++) sumphi[i]=sumphi[i-1]+phi[i];
}

int n,ans;

signed main(){
    scanf("%lld",&n);
    getphi(n);
    for(int i=1;i<=tail;i++){
        ans+=(sumphi[n/prime[i]]*2-1);
    }
    printf("%lld\n",ans);
    return 0;
}

数论分块

定理

$$
\left\lfloor\frac {\left\lfloor \frac{x}{b} \right\rfloor}{c} \right\rfloor=\left\lfloor\frac{x}{bc}\right\rfloor
$$

其中 $x\in\mathbb{R},b,c\in\mathbb{N}$

  • 证明：设 $x=kbc+r$，其中 $r\in[0,bc)$ ，我们把 $x$ 带入左边式子可以的得到：

    $$
    k+\left\lfloor\frac {\left\lfloor \frac{r}{b} \right\rfloor}{c} \right\rfloor
    $$

    因为：

    $$
    0\le \left\lfloor\frac {\left\lfloor \frac{r}{b} \right\rfloor}{c} \right\rfloor\le \left\lfloor\frac {r}{bc} \right\rfloor=0
    $$

    所以我们可以得到：

    $$
    \left\lfloor\frac {\left\lfloor \frac{r}{b} \right\rfloor}{c} \right\rfloor=k
    $$

    显然，右边式子也等于 $k$，所以结论成立。

算法讲解

其实数论分块（又被称为除法分块）是可以在 $\sqrt n$ 的复杂度内算出：

$$
\sum\limits_{i=1}^n\lfloor \frac{n}i \rfloor
$$

这是因为我们注意到和式求和的部分的取值只有 $2\sqrt n$ 中，证明这个结论只需要讨论 $i\le \sqrt n$ 和 $i> \sqrt n$​ 两种情况即可。

一般的，对于：

$$
\sum\limits_{i=1}^n\lfloor \frac{n}{f(i)}\rfloor
$$

我们要求其值相等的左右边界，只需要让：

$$
\lfloor\frac{n}{f(l)}\rfloor=\lfloor\frac{n}{f(r)}\rfloor
$$

由数论分块的正确性可以得到：

$$
f(r)=\left\lfloor \frac{n}{\lfloor \frac{n}{f(l)}\rfloor}\right\rfloor
$$

我们求解 $f(l)$ 并解方程解出 $r$ 为多少即可得出数论分块区间。

例题

P2261 [CQOI2007]余数求和

我们直接推式子：

$$
\begin{aligned}
\sum\limits_{i=1}^nk\bmod i=\sum\limits_{i=1}^nk-\lfloor \frac ki\rfloor\times i=nk-\sum\limits_{i=1}^ni\lfloor\frac ik\rfloor
\end{aligned}
$$

可以应用数论分块，注意后面要特判是否等于 $0$。

代码：

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
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N number
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

inline ll calc(int l,int r){
    return 1ll*(r+l)*(r-l+1)/2;
}

ll ans=0,n,k;

int main(){
    read(n);read(k);
    for(int i=1;i<=n;){
        int j;
        if(k/i>0) j=k/(k/i);
        else j=n;
        j=min((ll)j,n);
        ans+=(k/i)*calc(i,j);
        i=j+1;
    }
    printf("%lld\n",n*k-ans);
    return 0;
}

代码第 $31$ 行 $32$ 行为特判。

CF1485C Floor and Mod

推式子：

$$
\begin{aligned}
\left\lfloor \frac{a}{b} \right\rfloor=a\bmod b=a-\lfloor\frac{a}{b}\rfloor\times b
\Rightarrow \lfloor\frac{a}{b}\rfloor\times (b+1) =a\Rightarrow \lfloor\frac{a}{b}\rfloor=\frac{a}{b+1}
\end{aligned}
$$

所以我们只需要枚举 $b$ ，同时统计有多少 $a$ 是 $b+1$ 的倍数，这个数应该是 $\frac{x}{b+1}$ 。

但是需要注意的一点是，我们需要保证 $\lfloor\frac{a}{b}\rfloor=\frac{a}{b+1}<b$ ，所以我们有 $a<b^2+b$ ，所以上面这个式子应该变成：$\frac{\min(x,b^2+b-1)}{b+1}$。

我们根号分治并分开讨论，数论分块即可。复杂度为 $O(\sqrt n)$。

代码：

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
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define uint unsigned int
#define ull unsigned long long
#define N number
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int t;
ll x,y;

inline ll calc(ll x,ll y){
    ll ans=0;ll b=1;
    for(;b*b+b-1<=x&&b<=y;b++) ans+=(b*b+b-1)/(b+1);
    for(int i=b;i<=y;){
        int j=(x/(i+1)==0)?y:(x/(x/(i+1))-1);
        j=min((ll)j,y);
        ans+=(x/(i+1))*(j-i+1);
        i=j+1;
    }
    return ans;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(t);
    while(t--){
        read(x);read(y);
        printf("%lld\n",calc(x,y));
    }
    return 0;
}

常用公式

最大公因数，最小公倍数

$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^m\text{lcm}(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{\gcd(i,j)} \
&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j} [\gcd(\frac id,\frac jd)=1]\frac{ij}d\
&=\sum\limits_{d=1}^{\min(n,m)}d\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}[\gcd(i,j)=1]ij\
\end{aligned}
$$

令 $f(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]ij$，那么有：

$$
\begin{aligned}
f(n,m)&=\sum\limits_{i=1}^n\sum\limits_{i=1}^m\epsilon(\gcd(i,j))ij\
&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|\gcd(i,j)}\mu(d)ij\
&=\sum\limits_{d=1}^{\min(n,m)}\mu(d)d^2\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}ij\
\end{aligned}
$$

令 $g(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m ij$，显然，我们有 $g(n,m)=\frac{(n+1)n}{2}\frac{(m+1)m}{2}$ ，可以 $O(1)$ 计算，所以通过处理前缀和，$f(n,m)$ 可以在 $O(\sqrt n+\sqrt m)$ 的时间1复杂度算出，所以原式的复杂度可以做到 $O(n+m+\sqrt n+\sqrt m)$ 。

除数函数

  • $\sigma_k(n)=\sum\limits_{d|n}d^k$​​ ，令 $id_k(n)=n^k$​​ ，那么我们有 $\sigma_k=id_k*I$​​

  • $\sigma_0(xy)=\sum\limits_{i|x}\sum\limits_{j|y}[\gcd(i,j)=1]$

证明：我们考虑将 $xy$​​ 的每一个因子都与互质的 $i,j$​​ 意义映射。设 $xy$​​ 的因子为 $k$​​ ，设把 $k$​​ 唯一分解之后得到的式子为 $\prod\limits_{i=1}^mp_i^{\alpha_i}$​​​ 我们考虑每一个质数，设当前的质数为 $p$​​ ，设这个质数在 $k$​​ 中的指数为 $\alpha$​​ ，设在 $x$​​ 中的指数为 $a$​​ 设在 $y$​​ 中的指数为 $b$​​​ 。我们规定，如果 $\alpha \le a$​ ，那么令从 $x$​ 中拿取 $p^{\alpha}$​ ，否则就从 $y$​ 中拿取 $p^{\alpha -a}$​ 次方。这样，从 $x$​​ 中拿出来数就与从 $y$​​ 中拿出来的数互质。同时每一对互质的数，都可以映射到这么一个因子上。所以等式成立。证毕。

  • 除数函数是积性函数。

证明：如果 $x,y$ 互质，那么 $xy$ 的一个因子 $k$ ，$k$ 一定可以分解成两个数，这两个数互质。也就是说，$k$ 一部分来自 $x$ ，一部分来自 $y$​ 。证毕。

上面这个积性函数的性质，揭示我们除数函数也是可以线性筛的。不过我们有计算一些特殊除数函数前缀和更快的做法。

  • $\sum\limits_{i=1}^n\sigma_0(i)=\sum\limits_{j=1}^n\left\lfloor \frac{n}{j} \right\rfloor$​

证明：推导可知

$$
\begin{aligned}
\sum\limits_{i=1}^n\sigma_0(i)=\sum\limits_{i=1}^n\sum\limits_{j=1}^i[j|i]=\sum\limits_{j=1}^n\sum\limits_{i=1}^{\left\lfloor \frac{n}{j} \right\rfloor}1=\sum\limits_{j=1}^n \left\lfloor \frac{n}{j} \right\rfloor
\end{aligned}
$$

  • $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma_0(ij)=\sum\limits_{d=1}^{\min(n,m)}\mu(d)(\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\left\lfloor \frac{n}{xd} \right\rfloor)(\sum\limits_{y=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\left\lfloor \frac{m}{yd} \right\rfloor)$​

证明：

$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma_0(ij)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}\epsilon(\gcd(x,y))\
&=\sum\limits_{x=1}^n\sum\limits_{y=1}^m \epsilon(\gcd(x,y)) \sum\limits_{i=1}^{\left\lfloor \frac{n}{x} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{y} \right\rfloor}1\
&=\sum\limits_{x=1}^n\sum\limits_{y=1}^m\sum\limits_{d|\gcd(x,y)}\mu(d)\left\lfloor \frac{n}{x} \right\rfloor\left\lfloor \frac{m}{y} \right\rfloor\
&=\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{y=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\mu(d)\left\lfloor \frac{n}{xd} \right\rfloor\left\lfloor \frac{m}{yd} \right\rfloor\
&=\sum\limits_{d=1}^{\min(n,m)}\mu(d)(\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\left\lfloor \frac{n}{xd} \right\rfloor)(\sum\limits_{y=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\left\lfloor \frac{m}{yd} \right\rfloor)
\end{aligned}
$$

  • $\sigma_1(xy)=\sum\limits_{i|x}\sum\limits_{j|y}\frac{jx}{i}[\gcd(i,j)=1]$​​

证明：同样还是构造一一对应来证明，构造方法和上面证明 $2.1.2.2$ 相同，设：

$$
\begin{aligned}
x=\prod\limits_{i=1}^np_i^{\alpha_i},y=\prod\limits_{j=1}^np_j^{\beta_j}\
i=\prod\limits_{j=1}^kp_{i_j}^{a_{i_j}},j=\prod_{i=1}^{n-k}p_{j_i}^{a_{j_i}}
\end{aligned}
$$

我们看 $\frac{jx}i$​ 的值表示出来是多少，我们发现这个值是：

$$
\prod\limits_{j=1}^k p_{i_j}^{\alpha_{i_j}-a_{i_j}}\times \prod\limits_{i=1}^{n-k}p_{j_i}^{\alpha_{j_i}+a_{j_i}}
$$

这个 $i,j$​ 对应的因子是 $\prod_{j=1}^kp_{i_j}^{a_{i_j}}\prod_{p_{j_i}}^{n-k}p_{j_i}^{\alpha_{j_i}+a_{j_i}}$​，不难发现，这个因子与上面相比，右边相同，左边相乘是 $x$​​​ ，所以这两个因子是一一对应的。显然这个式子是正确的。

  • $\sum\limits_{i=1}^n\sigma_1(i)=\sum\limits_{i=1}^ni\left\lfloor \frac{n}{i} \right\rfloor$

证明：

$$
\begin{aligned}
\sum\limits_{i=1}^n\sigma_1(i)=\sum\limits_{i=1}^n\sum\limits_{j=1}^ij[j|i]=\sum\limits_{j=1}^n\sum\limits_{i=1}^{\left\lfloor \frac{n}{j} \right\rfloor}j=\sum\limits_{i=1}^nj\left\lfloor \frac{n}{j} \right\rfloor
\end{aligned}
$$

  • $\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sigma_1(ij)=\sum\limits_{d=1}^n\mu(d)d(\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sigma_1(i))^2$​

证明：

$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sigma_1(ij)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{x|i}\sum\limits_{y|j}\frac{jx}{y}[\gcd(x,y)=1]\
&=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^n\sum\limits_{i=1}^{\left\lfloor \frac{n}{x} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{y} \right\rfloor}jx\times \epsilon(\gcd(x,y))\
&=\sum\limits_{d=1}^n\mu(d)d \sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{y=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{i=1}^{\left\lfloor \frac{n}{xd} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{yd} \right\rfloor}jx\
&=\sum\limits_{d=1}^{n}\mu(d)d\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}x\left\lfloor \frac{n}{xd} \right\rfloor\sum\limits_{y=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{yd} \right\rfloor}j\
&=\sum\limits_{d=1}^{n}\mu(d)d\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sigma_1(x)\sum\limits_{y=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sigma_1(y)\
&=\sum\limits_{d=1}^{n}\mu(d)d(\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sigma_1(i))^2
\end{aligned}
$$

  • $\sum\limits_{i=1}^n\mu^2(i)=\sum\limits_{i=1}^{\sqrt n}\mu(i)\times\left\lfloor \frac{n}{i^2} \right\rfloor$

这个公式需要构造来证明，具体证明过程请参照例题。

  • $\sum\limits_{i=1}^n\mu^2(i)\left\lfloor \sqrt{\frac{n}{i}} \right\rfloor$​​

这个东西的证明和上面类似，我们同样考虑构造。考虑 $1$ 到 $n$ 内所有不能被完全平方数整除的数组成的集合 $P$ ，那么 $1$ 到 $n$ 内的每一个数都可以表示成 $xy^2$ 的形式，其中 $x\in P,y\le \sqrt{\frac nx}$，上面的式子其实等价于 $\sum\limits_{p\in P}\left\lfloor \sqrt{\frac{n}{i}} \right\rfloor$​，根据 $y$ 的取值范围，不难发现这个式子的正确性。

  • $\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=1]=\sum\limits_{d=1}^n\mu(d)\left\lfloor \frac{n}{d} \right\rfloor=2S_{\phi}(\left\lfloor \frac{n}{d} \right\rfloor)-1$

证明：

这里只证明后面的那个式子。

设 $f(n)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=1],g(n)=\sum\limits_{i=1}^n\sum\limits_{j=1}^i[\gcd(i,j)=1]$，那么 $g(n)=S_{\phi}(i)$，那么容易验证有：$f(n)=2g(n)-1$ ，减 $1$ 是因为 $(1,1)$ 被算重了。

  • $\prod\limits_{i=1}^n\prod\limits_{j=1}^n\gcd^2(i,j)=(\prod\limits_{i=1}^nd^{S_{\phi}(\left\lfloor \frac{n}{d} \right\rfloor)})$

证明：

$$
\begin{aligned}
\prod\limits_{i=1}^n\prod\limits_{j=1}^n\gcd{^2}(i,j)&=\prod\limits_{i=1}^nd^{\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=d]}\
&=\prod\limits_{i=1}^nd^{\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\gcd(i,j)=1}
\end{aligned}
$$

故该公式成立。

例题

洛谷P4318

不难发现，答案具有可二分性。我们规定，如果一个数不能被完全平方数整除，则称其合法，否则称其不合法。那么 $n$ 以内的合法的数一共有多少呢？不难发现，答案应该是：

$$
\sum\limits_{i=1}^n\mu^2(i)
$$

即为 $1$ 到 $n$ 中所有 $\mu(x)$ 不为 $0$ 的数。

我们考虑用容斥来计算这个东西，不难发现这个东西其实也是可以这样计算的：

含 $0$ 个质数的平方的倍数减去含 $1$ 个质数的平方的倍数加上含 $2$ 个质数平方的倍数……，考虑莫比乌斯函数的定义，我们发现上面这个式子其实也是：

$$
\sum\limits_{i=1}^{i\times i\le n}\mu(i)\times\left\lfloor \frac{n}{i^2} \right\rfloor
$$

所以我们就可以二分这个答案，然后在 $O(\sqrt n)$ 的时间复杂度内判断合不合法。

代码：

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
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 60010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int Prime[N],tail,Mu[N];
bool NotPrime[N];

inline void PreWork(int n){
    NotPrime[1]=1;Mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!NotPrime[i]) Prime[++tail]=i,Mu[i]=-1;
        for(int j=1,k;j<=tail&&(k=i*Prime[j])<=n;j++){
            NotPrime[k]=1;
            if(i%Prime[j]==0) break;
            else Mu[k]=-Mu[i];
        }
    }
}

int t;

inline bool Check(int mid,int k){
    int res=0;
    for(ll i=1;i*i<=mid;i++){
        res=res+Mu[i]*(mid/(i*i));
    }
    return res>=k;
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    PreWork(60000);
    read(t);
    while(t--){
        ll k;read(k);
        ll l=k,r=2*k;
        while(l<r){
            // cout<<"l"<<" "<<l<<endl;

            int mid=(l+r)>>1;
            if(Check(mid,k)) r=mid;
            else l=mid+1;
        }
        printf("%lld\n",l);
    }
}

SP5971 LCMSUM - LCM Sum

要求计算 $\sum_{i=1}^nlcm(i,n)$ ，我们尝试化简这个东西：

$$
\begin{aligned}
\sum\limits_{i=1}^nlcm(i,n)=\sum\limits_{i=1}^n\frac{in}{\gcd(i,n)}&=\sum\limits_{i=1}^n\sum\limits_{d|i,d|n}[\gcd(\frac di,\frac nd)=1]\times \frac{in}{d}\
&=\sum\limits_{d|n}\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}in[\gcd(i,\frac nd)=1]
\end{aligned}
$$

我们令 $g(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1]\times i$ 即在 $1$ 到 $x$ 总所有与 $x$ 互质的数的个数，因为 $\gcd(i,n)=1\Leftrightarrow\gcd(n-i,i)$ ，所以互质的数总是两两一对，且和为 $n$ 。

所以这个和应该是 $\frac{\phi(x)x}{2}$。

所以上面那个式子可以化简为：

$$
\begin{aligned}
n\sum\limits_{d|n}\frac{\phi(d)d}{2}
\end{aligned}
$$

我们可以用 $n\log n$ 的时间复杂度完成这个事情。

注：这个地方有一点不太严谨，当 $d=1$ 的时候注意 $g(1)=1$，这个是个特殊的。

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
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int Prime[N],tail,Phi[N];
ll g[N],f[N];
bool NotPrime[N];

inline void PreWork(int n){
    NotPrime[1]=1;Phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!NotPrime[i]) Prime[++tail]=i,Phi[i]=i-1;
        for(int j=1,k;j<=tail&&(k=i*Prime[j])<=n;j++){
            NotPrime[k]=1;
            if(i%Prime[j]==0){
                Phi[k]=Phi[i]*Prime[j];break;
            }
            else Phi[k]=Phi[i]*Phi[Prime[j]];
        }
    }
    // for(int i=1;i<=5;i++) printf("%d ",Phi[i]);puts("");
    g[1]=1;
    for(int i=2;i<=n;i++) g[i]=1ll*Phi[i]*i/2;
    // for(int i=1;i<=5;i++) printf("%lld ",g[i]);puts("");
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i) f[j]+=g[i];
    for(int i=1;i<=n;i++) f[i]*=i;
}

int t,n;

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    PreWork(1000000);
    read(t);
    while(t--){
        read(n);printf("%lld\n",f[n]);
    }
}//

P3768 简单的数学题

首先我们尝试化简式子：

$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j)&=\sum\limits_{k=1}^n\sum\limits_{k|i,i\le n}\sum\limits_{k|j,j\le n}ijk[\gcd(\left\lfloor \frac{k}{i} \right\rfloor,\left\lfloor \frac{k}{j} \right\rfloor)=1]\
&=\sum\limits_{k=1}^n\sum\limits_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{k} \right\rfloor}ijk^3[\gcd(i,j)=1]
\end{aligned}
$$

令 $g(n)=\sum_{i=1}^n\sum_{j=1}^nij[\gcd(i,j)=1]$，我们可以得到：

$$
\begin{aligned}
g(n)=\sum\limits_{i=1}^ni\sum\limits_{j=1}^nj[\gcd(i,j)=1]=[n\ge 1]+\sum\limits_{i=2}^n\frac{\phi(i)i}{2}
\end{aligned}
$$

所以原来的式子我们可以化简为：

$$
\begin{aligned}
\sum\limits_{k=1}^nk^3g(\left\lfloor \frac{n}{k} \right\rfloor)
\end{aligned}
$$

由于 $n$ 是 $1e9$ 级别的，所以我们可以用杜教筛筛一下 $g(n)$ 。然后用整除分块。因为杜教筛也是整除分块计算的，所以杜教筛外面套一个整除分块没有问题。

关于除数函数一些定理的其它证明方式

在上面的内容中，我们构造的方式推导了 $\sigma_0(ij)$ 和 $\sum\sum\sigma_1(ij)$，但其实他们也可以用代数推导的方式来推导。

$$
\sigma_0(xy)=\sum\limits_{d|xy} 1=\sum\limits_{i|x}\sum\limits_{j|y}[i=\gcd(x,ij)]=\sum\limits_{i|x}\sum\limits_{j|y}[\gcd(i,j)=1]
$$

其中第二步推导是因为：为了让 $d$ 不被重复枚举，我们让 $i$ 尽量多拿 $d$ 中的质因子。

同理，我们有：

$$
\sigma_1(xy)=\sum\limits_{d|xy} d=\sum\limits_{i|x}\sum\limits_{j|y}[i=\gcd(x,ij)]ij=\sum\limits_{i|x}\sum\limits_{j|y}[\gcd(i,j)=1]\frac{xj}{i}
$$

莫比乌斯函数扩展

莫比乌斯函数非卷积形式。

对于数论函数和完全积性函数 $t$ 且 $t(1)=1$ ，有以下等价式子：

$$
\begin{aligned}
f(n)=\sum\limits_{i=1}^nt(i)g(\left\lfloor \frac{n}{i} \right\rfloor)\Leftrightarrow g(n)=\sum\limits_{i=1}^nt(i)\mu(i)f(\left\lfloor \frac{n}{i} \right\rfloor)
\end{aligned}
$$

  • 证明：

$$
\begin{aligned}
g(n)&=\sum\limits_{i=1}^nt(i)\mu(i)f(\left\lfloor \frac{n}{i} \right\rfloor)\
&=\sum\limits_{i=1}^nt(i)\mu(i)\sum\limits_{j=1}^{\left\lfloor \frac{n}{i} \right\rfloor}t(j)g(\left\lfloor \frac{n}{ij} \right\rfloor)\
&=\sum\limits_{d=1}^n\sum\limits_{i|d} t(i)\mu(i)t(\frac{d}{i})g(\left\lfloor \frac{n}{d} \right\rfloor)\
&=\sum\limits_{d=1}^ng(\left\lfloor \frac{n}{d} \right\rfloor)t(d)\sum\limits_{i|d}t(i)\
&=\sum\limits_{d=1}^ng(\left\lfloor \frac{n}{d} \right\rfloor)t(d)\epsilon(d)
=g(n)
\end{aligned}
$$