数论

只有几道套路题，严谨证明请转 oi-wiki。

预处理

数论分块

简单来说就是求：

因为 \(\lfloor \frac{n}{i} \rfloor\) 最多有 \(2 \sqrt{n}\) 个取值，所以我们可以枚举答案，复杂度 \(O(\sqrt{n})\)。

• 证明：\(\forall d \in [1,n]\)
  1. 考虑 \(d \le \sqrt{n}\)，因为 \(d\) 只有 \(\sqrt{n}\) 种，所以最多只会有 \(\sqrt{n}\) 种。
  2. 考虑 \(d \ge \sqrt{n}\)，因为 \(\lfloor \frac{n}{d} \rfloor\) 小于 \(\sqrt{n}\)，所以答案不会超过\(\sqrt{n}\) 种。
  3. 综上，\(\forall d \in [1,n]\)，\(\lfloor \frac{n}{i} \rfloor\) 最多有 \(2 \sqrt{n}\)
• 证毕（根号分治初步应用？）

_易证，\(\lfloor \frac{n}{i} \rfloor\) 取值相同的一段的左右端点分别为 \(\lfloor \frac{n}{i} \rfloor ,\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor\)。

• 证明：设 \(r\) 为极大的满足 \(\lfloor \frac{n}{l} \rfloor=\lfloor \frac{n}{r} \rfloor\) 的值。

\(\begin{cases} \lfloor \dfrac{n}{l} \rfloor \le \dfrac{n}{r} \\ \lfloor \dfrac{n}{l} \rfloor \gt \dfrac{n}{r+1} \end{cases}\) $\Longrightarrow $ \(\begin{cases} \dfrac{n}{\lfloor \dfrac{n}{l} \rfloor} \ge \dfrac{n}{\dfrac{n}{r}} \\ \dfrac{n}{\lfloor \dfrac{n}{l} \rfloor} \lt \dfrac{n}{\dfrac{n}{r+1}} \end{cases}\) $\Longrightarrow $ \(r \le \dfrac{n}{\lfloor \dfrac{n}{l} \rfloor} \lt r+1\)

\(\because r \in \mathbb{Z},\ \therefore r \le \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor\)。

• 证毕

例题：余数求和

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL n,ans;

int main()
{
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	scanf("%lld",&n);
	for(int l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		ans+=1ll*(r-l+1)*(n/l);//这里求个数，所以是 r-l+1，根据题意替换成不同函数的区间和
	}
	printf("%lld\n",ans);
	return 0;
}

线性筛

线性筛最大的用处不只是线性求素数，而是筛积性函数。

几乎只要是积性函数，找到性质我们就可以筛。

积性函数：函数 \(f(x)\) 满足 \(\forall gcd(a,b)=1,f(a \times b)=f(a) \times f(b)\)

举例说明：

mu[1]=1;
for(int i=2;i<N;i++)
{
	if(!vs[i]) p[++p[0]]=i,mu[i]=-1;
	for(int j=1;j<=p[0]&&i*p[j]<N;j++)
	{
		vs[i*p[j]]=1;
		if(i%p[j]==0)
		{
			mu[i*p[j]]=0; break;
		}
		mu[i*p[j]]=-mu[i];
	}
}

phi[1]=1;
for(LL i=2;i<=n;i++) 
{
	if(!vs[i]) p[++p[0]]=i,phi[i]=i-1;
	for(LL j=1;j<=p[0]&&i*p[j]<=n;j++)
	{
		vs[i*p[j]]=1;
		if(i%p[j]==0)
		{
			phi[i*p[j]]=phi[i]*p[j]; break;
		}
		phi[i*p[j]]=phi[i]*(p[j]-1);
	}
}

F[1]=1;
for(int i=2;i<=n;i++)
{
	if(!vs[i]) F[i]=qpow(i,k),p[++p[0]]=i;
	for(int j=1;j<=p[0]&&i*p[j]<=n;j++)
	{
		vs[p[j]*i]=1; F[i*p[j]]=F[i]*F[p[j]]%mod;
		if(i%p[j]==0) break;
	}
}

f[1]=1;
for(int i=2;i<=n;i++)
{
	if(!vs[i]) f[i]=i-1,p[++p[0]]=i;
	for(int j=1;j<=p[0]&&i*p[j]<=n;j++)
	{
		vs[p[j]*i]=1;
		if(i%p[j]==0)
		{
			if((i/p[j])%p[j]) f[i*p[j]]=(mod-p[j])*f[i/p[j]]%mod;
			break;
		}
		f[p[j]*i]=f[i]*(p[j]-1)%mod;
	}
}

g[1]=1;
for(int i=2;i<N;i++)
{
	if(!vs[i]) p[++p[0]]=i,g[i]=(qpow(i,k)+mod-1)%mod;
	for(int j=1;j<=p[0]&&p[j]*i<N;j++)
	{
		vs[i*p[j]]=1;
		if(i%p[j]==0)
		{
			g[i*p[j]]=g[i]*(g[p[j]]+1)%mod;
			break;
		}
		g[i*p[j]]=g[i]*g[p[j]]%mod;
	}
}

这几天做的都放这里了。。。长得都差不多，以后有时间把推导写了，没时间先咕着。

常见的积性函数就几个，一堆积性函数的狄利克雷卷积的形式也是积性函数，就像最后两个例子。

对于这些复合的函数性质自己推，主要分别找质数时的计算式，然后推到非质数上。

推导

（性质的证明在最后）

以 公约数的和 为例。

求:

先转化成：

目标就是求：

先枚举 \(d=gcd(i,j)\):

然后我们发现后面一坨要求 \((d \mid i) \land (d \mid j)\)，所以我们直接令 \(i,j\) 除 \(d\)，剩下的:

根据莫比乌斯函数的性质：\(\sum_{d \mid n} \mu(d)=[n=1]\)，进行代换：

枚举 \(e\)，\(i,j\) 是 \(e\) 的倍数：

后面一坨就是求 \([1,n]\) 中多少 \(i\) 是 \(e\) 的倍数，显然有 \(\lfloor \frac{n}{ed} \rfloor\)：

设 \(T=ed\)，枚举 \(T\) 和 \(T\) 的因数 \(d\)：

根据性质 \(\sum_{d \mid n}\mu(\frac{n}{d})d=\varphi(n)\)

现在我们就得到了一个复杂度很优的式子，后面的 \(\varphi(T)\) 可以筛出来求前缀和，前面的数论分块。
预处理 \(O(n)\)，查询 \(O(\sqrt{n})\)。

性质证明

上文提到两个性质的证明：

• 证明：\(\sum_{d \mid n} \mu(d)=[n==1]\)
  考虑 \(\mu(d)\) 的定义：

1. \(n=1\) 显然 \(\sum_{d \mid n} \mu(d)=1\)。
2. \(n>1\)，根据唯一分解定理：$$n=\prod_{i}p_i^{c_i}$$
   对于具有平方因子的 \(d\)，也就是 \(c_i \gt 1\)，\(\mu(d)\)不用考虑，
   对于剩下的，就是在 \(k\) 个因子中任选若干个组成 \(d\)：$$\sum_{r=1}^{k} (-1)^r C_{k}^{r} $$
   二项式定理展开：$$(1+(-1))^k=0$$
3. 综上，当且仅当 \(n=1\) 时，\(\sum_{d \mid n} \mu(d)=1\)

• 证毕

• 证明：\(\sum_{d \mid n}\mu(\frac{n}{d})d=\varphi(n)\)
  莫比乌斯反演套欧拉反演，很显然。（施工中。。。）

（其实这个道题用欧拉反演更方便，具体过程不展开，都差不多。）