526互联

数论函数小计

发布时间 2023-08-12 23:08:47作者: g1ove

1.基础

数论函数

  • 定义: 数论函数,就是值域为整数(陪域为复数)的函数

狄利克雷卷积

两个数论函数的狄利克雷卷积是一个新的函数

比如 \(f(n)\),\(g(n)\) 它们的卷积就是 \(f * g\)

怎么卷呢？

定义: \(\large{(f*g)(n)=\sum\limits_{d|n}f(n)g(n/d)}\)

举个例子：

\((f*g)(12)=f(1)*g(12)+f(2)*g(6)+f(3)*g(4)…f(12)*g(1)\)

狄利克雷卷积满足交换律和结合律：

\(f*g\) = \(g*f\)

\(f*g*h\)=\(f*(g*h)\)

基本函数

  • 恒等函数：\(I(n)\) \(I(n)=1\) 无论n是什么，它永远等于\(1\)
  • 元函数：\(e(n)\) \(e(n)=[n=1]\) 只有\(n=1\)时为1，其余为0 满足\(e*f=f\)
  • 编号函数：\(id^x(n)=n^x\)

完全积性函数

  • 定义：对于完全积性函数 \(I\) 有任意整数\(a,b\)使\(I(a)*I(B)=I(ab)\)

\(I,e,id\)函数都是完全积性函数

积性函数

  • 定义：对于积性函数\(f\) 若\((a,b)==1\) 则\(f(a)*f(b)=f(ab)\)

完全积性函数是积性函数

后面的 \(\varphi(n)\)和\(\mu(n)\)都是积性函数

性质：

  • 对于任意积性函数 有 \(F(1)=1\)

\(\text{证明：}\)因为\(F(1)*F(1)=F(1)\) 所以\(F(1)=1\) 若\(F(1)=0\)这个积性函数无意义

  • 两个积性函数的卷积还是积性函数
  • 积性函数的逆元也是积性函数

\(\text{定义}\)：满足\(g*f = e\)时 \(g\)和\(f\)互逆

2.莫比乌斯函数

如果我们知道\(f\) 可以通过 \(F=I*f\) (\(I\)是恒等函数) 求出F

那如果我们知道 \(F\) 怎么求 \(f\)? 两边同时乘上\(I^{-1}\)就行

\(I^{-1}\)就是莫比乌斯函数 \(\mu\)

根据\(I\)是积性函数 所以\(\mu\)也是积性函数

那么\(\mu\)怎么算？

首先

  • \(\mu(1)=1\)

从素数开始考虑 设当前素数为\(k\)

根据\(e(k)=\sum\limits_{d|n}\mu(n)I(n/d)\) \(k\)还是素数

所以\(e(k)=\mu(1)I(k)+\mu(k)I(1)\)

所以\(0=1+f(k)\)

所以\(f(k)=-1\)

然后再想素数的多次方
\(e(k^x)=\mu(1)+\mu(k)+\mu(k^2)+\mu(k^3)…\mu(k^{x-1})\)

把\(k=2\)带入 \(0=1-1+\mu(k^2)\)

同理可得 \(\mu(k^x)=0\)

根据积性函数的性质，容易得到\(\mu\)的定义：

  • 得\(0\) 当\(x\)含有平方因子
  • 得\((-1)^k\) \(k\)为\(x\)的质因子个数

莫比乌斯反演

怎么反演呢？

当有这样的问题：

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

\([(i,j)==1] → \sum\limits_{d|n} \mu(d)\)

这样就能转化了

为什么？这其实就是\(\mu\)卷积呗 只有卷\(1\)才能为\(1\)

例题

链接 here

现在有这样的问题：
$\sum\limits_{i=1}^n \sum\limits_{j=1}^m[(i,j)==1] $

带入反演
\(→\sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{d|i,d|j} \mu(d)\)

往前提$→\sum\limits_{d=1}^{min(n,m)} \mu(d)\sum\limits_{i=1}^{n/d} \sum\limits_{j=1}^{m/d} $

再化简$→\sum\limits_{d=1}^{min(n,m)} \mu(d)(n/d)(m/d) $

这样就是\(O(n)\)的

整除分块一下就是\(O(\sqrt n)\)的

具体实现

线性筛

线性筛可以做到\(O(n)\)处理出\(n\)以内的\(\mu\)

特别地，如果单独求一个\(\mu\)，可以用\(\sqrt n\)枚举因数的做法

怎么线性筛呢？分类讨论

  • 在\(prime_j|i\)时 说明\(prime_j\)和\(i\)已经出现了重复因子 只需令\(\mu(prime_j * i)=0即可\)
  • 否则 可以根据积性函数的性质转移即可

code

void init()
{
	p[1]=1;
	mul[1]=1;
	for(int i=2;i<=MAXN-3;i++)
	{
		if(!p[i])
		{
			q[++l]=i;
			mul[i]=-1;
		}
		for(int j=1;j<=l&&i*q[j]<=MAXN-3;j++)
			if(i%q[j]==0)
			{
				p[i*q[j]]=1;
				mul[i*q[j]]=0;
				break;
			}
			else 
			{
				p[i*q[j]]=1;
				mul[i*q[j]]=mul[i]*mul[q[j]];
			}
	}
}

整除分块

观察公式$ \sum\limits_{d=1}^{min(n,m)} \mu(d)(n/d)(m/d) $

发现一定存在一段\((n/d)(m/d)\)是连续的\(d\)

这段重复算会浪费很多时间

把这些相同的分成一块块 加上前缀和一起算可以优化成\(O(\sqrt n)\)的

每次一块一块枚举即可

练习题：T1 和 T2

这些芝士结合一下就是例题的解

code

#include<bits/stdc++.h>
#define ll long long
#define MAXN 50005
using namespace std;
int g,mul[MAXN],p[MAXN];
int q[MAXN],l;
ll n,m,d,ans;
void init()
{
	p[1]=1;
	mul[1]=1;
	for(int i=2;i<=MAXN-3;i++)
	{
		if(!p[i])
		{
			q[++l]=i;
			mul[i]=-1;
		}
		for(int j=1;j<=l&&i*q[j]<=MAXN-3;j++)
			if(i%q[j]==0)
			{
				p[i*q[j]]=1;
				mul[i*q[j]]=0;
				break;
			}
			else 
			{
				p[i*q[j]]=1;
				mul[i*q[j]]=mul[i]*mul[q[j]];
			}
	}
	for(int i=2;i<=MAXN-3;i++)
		mul[i]+=mul[i-1];
}
void solve()
{
	for(int l=1,r=0;l<=min(n,m);l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		ans+=(n/l)*(m/l)*(mul[r]-mul[l-1]);
	}
}
int main()
{
	init();
	scanf("%d",&g);
	while(g--)
	{
		ans=0;
		scanf("%lld%lld%lld",&n,&m,&d);
		n/=d,m/=d;
		solve();
		printf("%lld\n",ans);
	}
	return 0;
}

例题2

链接：here

这道题题目让我们求\(\sum\limits_{i=1}^n \sum\limits_{j=1}^m (i,j)\)是质数的个数

首先 将题目转化成

\(\large\sum\limits_{k\in prime} \sum\limits_{i=1}^n \sum\limits_{j=1}^m (i,j)=k\)

\(=\large\sum\limits_{k\in prime} \sum\limits_{i=1}^{n/k} \sum\limits_{j=1}^{m/k} (i,j)=1\)

\(=\large\sum\limits_{k\in prime} \sum\limits_{i=1}^{n/k} \sum\limits_{j=1}^{m/k} \sum\limits_{d|i,d|j} \mu(d)\)

前提\(\mu\)得

$=\large\sum\limits_{k\in prime}\sum\limits_{d=1}^n \mu(d) \sum\limits_{i=1}^{n/k,d|n} \sum\limits_{j=1}^{m/k,d|m} $

$=\large\sum\limits_{k\in prime}\sum\limits_{d=1}^n \mu(d)(n/kd)(m/kd) $

如果此时直接按这个做时间复杂度为\(O(T*\sqrt n*n*\sqrt {nm})\)

过不了 当柿子无法优化时可以用另一个方法

\(\text{令T=kd}\)

$=\large\sum\limits_{k\in prime}\sum\limits_{d=1}^n \mu(T/k)(n/T)(m/T) $

$=\large\sum\limits_{T=1}^n (n/T)(m/T)\sum\limits_{k\in prime ,k|T}\mu(T/k) $

然后发现后面这$\sum\limits_{k\in prime ,k|T}\mu(T/k) \(一坨能\)O(nloglogn)$埃氏筛预处理

前面\(\sum\limits_{T=1}^n (n/T)(m/T)\)能整除优化

$=\large\sum\limits_{T=1}^n (n/T)(m/T)sum(T) $

因此 时间复杂度降至\(O(nloglogn + T\sqrt n)\) 能通过本题

Code

#include<bits/stdc++.h>
#define ll long long
#define MAXN 10000005
using namespace std;
int n,g,m;
int q[MAXN],l;
int p[MAXN],mul[MAXN],sum[MAXN];
ll ans;
void init()
{
	mul[1]=p[1]=1;
	for(int i=2;i<=MAXN-3;i++)
	{
		if(!p[i])
		{
			mul[i]=-1;
			q[++l]=i;
		}
		for(int j=1;j<=l&&q[j]*i<=MAXN-3;j++)
		{
			p[q[j]*i]=1;
			if(i%q[j]==0)
			{
				mul[q[j]*i]=0;
				break;
			}
			else mul[q[j]*i]=mul[q[j]]*mul[i];
		}
	}
	for(int i=1;i<=l;i++)
		for(int j=1;j*q[i]<=MAXN-3;j++)
			sum[j*q[i]]+=mul[j];
	for(int i=2;i<=MAXN-3;i++)
		sum[i]+=sum[i-1];
}
ll solve(int n,int m)
{
	ll s=0;
	for(int l=1,r=0;l<=min(n,m);l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		s+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
	}
	return s;
}
int main()
{
	init();
	scanf("%d",&g);
	while(g--)
	{
		scanf("%d%d",&n,&m);
		printf("%lld\n",solve(n,m));
	}
	return 0;
}

3 欧拉函数 \(\varphi\)

定义\(\varphi(x)\)表示\(1\to x\)中与\(x\)互质的数的个数

推导 借助容斥

\(\text{设}p_1,p_2,p_3,…p_k(p_i\le x) \in prime\)

则\(\phi(x)=x-x/p_1-x/p_2-x/p_3…+x/p_1p_2+x/p_2p_3…\)

\(=x(1-1/p_1-1/p_2-1/p_3…+1/p_1p_2+1/p_1p_3…)\)

上面左边的那一坨根据观察可以化简为

\(=x(1-1/p_1)(1-1/p_2)(1-1/p_3)…\)

\(=x*p_1/(p_1-1)*p_2/(p_2-1)*p_3/(p_3-1)…\)

借助这个东西我们可以通过\(O(\sqrt x)\)的时间复杂度分解质因数得出\(\varphi(x)\)

可是如果要求\(1\to n\)这些\(\varphi(i)\)咋办？

其实\(\varphi\)是积性函数 证明

\(\large\text{设}(n,m)=1\)

则\(\large\varphi(n)\varphi(m)=\sum\limits_{i=1}^n((n,i)=1)*\sum\limits_{j=1}^m((m,j)=1)\)

然后自行取百度吧后面我看不懂

最终得\(\large=\sum\limits_{i=1}^{nm}((nm,i)=1)=\varphi(nm)\)

口胡结束

其实也可以感性理解一下

\(\text{设}a_1,a_2,a_3…a_x (a_i\le n)\in prime\)

\(b_1,b_2,b_3…b_y (b_i\le m)\in prime\)

\(\varphi(n)=n*(1-1/a_1)*(1-1/a_2)*(1-1/a_3)…(1-1/a_x)\)

\(\varphi(m)=m*(1-1/b_1)*(1-1/b_2)*(1-1/b_3)…(1-1/b_y)\)

根据\(n,m\)互质 可知 \(n\)和\(m\)有\(n,m\)的所有质因子

因此 \(\varphi(n)\varphi(m)=nm*(1-1/a_1)*(1-1/a_2)*(1-1/a_3)…\)

\((1-1/a_x)*(1-1/b_1)*(1-1/b_2)*(1-1/b_3)…(1-1/b_y)=\varphi(nm)\)
二次口胡结束

好了你已经知道\(\varphi(x)\)是积性函数了 现在你只需要使用线性筛就可以了

怎么筛呢 还是分类

  • 当筛的时候 \(i\bmod prime_j=0\)时 说明\(i\)和\(prime_j\)中已经相同质因子 所以\(i\)已经包含\(i*prime_j\)所有质因子 因此\(\varphi(i*prime_j)=\varphi(i)*prime_j\) 这个证明拆公式就行

  • 否则\((i,prime_j)=1\) 直接使用积性函数的性质即可

Code

void init()
{
	phi[1]=p[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!p[i])
		{
			phi[i]=i-1;
			q[++l]=i;
		}
		for(int j=1;j<=l&&q[j]*i<=n;j++)
		{
			p[q[j]*i]=1;
			if(i%q[j]==0)
			{
				phi[q[j]*i]=phi[i]*q[j];
				break;
			}
			else phi[q[j]*i]=phi[q[j]]*phi[i];
		}
	}
}

例题

链接：here
题目让我们求

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

枚举d \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{d|i,d|j}d*((i,j)=d)\)

d的枚举提前\(\sum\limits_{d=1}^nd\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i,j)=d\)

优化 \(\sum\limits_{d=1}^nd\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{n/d}(i,j)=1\)

转化
\(\sum\limits_{d=1}^nd((2*\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{i}(i,j)=1)-1)\)

定睛一看 \(\sum\limits_{j=1}^{i}(i,j)=1\)不就\(\varphi(i)\)吗 直接优化原柿

转化
\(\sum\limits_{d=1}^nd((2*\sum\limits_{i=1}^{n/d}\varphi(i))-1)\)

发现后面的柿子可以前缀和优化 然后前面跑一遍可以\(O(n)\)过了本题

Code

#include<bits/stdc++.h>
#define ll long long
#define MAXN 100005
using namespace std;
int n;
int q[MAXN],l;
int p[MAXN],phi[MAXN];
ll ans,sum[MAXN];
void init()
{
	phi[1]=p[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!p[i])
		{
			phi[i]=i-1;
			q[++l]=i;
		}
		for(int j=1;j<=l&&q[j]*i<=n;j++)
		{
			p[q[j]*i]=1;
			if(i%q[j]==0)
			{
				phi[q[j]*i]=phi[i]*q[j];
				break;
			}
			else phi[q[j]*i]=phi[q[j]]*phi[i];
		}
	}
	for(int i=1;i<=n;i++)
		sum[i]=phi[i]+sum[i-1];
}
int main()
{
	scanf("%d",&n);
	init();
	for(int i=1;i<=n;i++)
		ans+=i*(2*sum[n/i]-1);
	printf("%lld",ans);
	return 0;
}

欧拉反演

首先要知道一条理论：

\[\sum\limits_{d|n}\varphi(d)=n \]

证明：

我们把\(1\to n\)分成

\[\frac{1}{n},\frac{2}{n},\frac{3}{n}…\frac{n}{n}, \]

其中 约分后分母相同为一类

同分母的数的个数为\(\phi(x)\)

举个例子 \(n=10\)

那么分母为\(10\)的数很明显是与\(10\)互质的 就是\(\varphi(10)\)

分母为\(5\)的数很明显是 \(1 \to 10\)去掉一个因数\(2\)与\(10\)互质的数个数

那么其实可以转化成 \(1\to 5\)与\(5\)互质的数个数 为\(\varphi(5)\)

\(1\),\(2\)同理 原柿得证

这种方法叫做映射法

根据这个性质可以得到：

\[\varphi*I=id \]

我们又知道 \(I=\mu^{-1}\)

所以\(\varphi=id*\mu\)

例题

还是

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

但是有了\(T(T\le 10^4)\)组数据 我们如果直接\(O(nT)\)搞肯定T

根据我们学习的欧拉反演 我们可以变换原柿

\(=\sum\limits_{i=1}^n \sum\limits_{j=1}^n \sum\limits_{d|i,d|j}\varphi(d)\)

前提d \(=\sum\limits_{d=1}^n\sum\limits_{i=1,i|d}^n \sum\limits_{j=1,j|d}^n \varphi(d)\)

然后发现柿子与\(i,j\)无关 可以优化为\(=\sum\limits_{d=1}^n(n/d)(n/d) \varphi(d)\)

合并\(=\sum\limits_{d=1}^n(n/d)^2\varphi(d)\)

然后整除分块可以优化成\(O(\sqrt n)\)

Code

#include<bits/stdc++.h>
#define ll long long
#define MAXN 100005
using namespace std;
int n;
int q[MAXN],l;
int p[MAXN],phi[MAXN];
ll ans,sum[MAXN];
void init()
{
	phi[1]=p[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!p[i])
		{
			phi[i]=i-1;
			q[++l]=i;
		}
		for(int j=1;j<=l&&q[j]*i<=n;j++)
		{
			p[q[j]*i]=1;
			if(i%q[j]==0)
			{
				phi[q[j]*i]=phi[i]*q[j];
				break;
			}
			else phi[q[j]*i]=phi[q[j]]*phi[i];
		}
	}
	for(int i=1;i<=n;i++)
		sum[i]=phi[i]+sum[i-1];
}
ll solve(int n)
{
	ll s=0;
	for(int l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		s+=1ll*(n/l)*(n/l)*(sum[r]-sum[l-1]);
	}
	return s;
}
int main()
{
	scanf("%d",&n);
	init();
	printf("%lld",solve(n));
	return 0;
}

练习题：here