数论2&莫&杜

积性函数:

积性函数定义ok

积性函数指对于所有互质的整数$a$和$b$有性质$f(ab)=f(a)f(b)$的数论函数

除数函数?

莫比乌斯函数$\mu$ok

\[\phi(i) =
\begin{cases}
1, & i==1 \\
(-1)^k, & i == \prod_{i=1}^{k}{p_i^1 {p}, p_i为所有质因子 \\
0, & otherwise
\end{cases}
\]

为什么是积性函数?

对任意$a,b,gcd(a,b)=1$, $ab$的质因子集合可以不重不漏分到$a,b$的质因子集合中

分类讨论一下,满足定义

欧拉函数$\phi$ok

小于等于$n$的数中与$n$互质的数的数目

通式:

\[\phi(n)=n*\prod_{i=1}^{k}(1-\frac{1}{p_i})\\
\]

通式的意义:把他展开, 相当于做容斥, 筛除的所有$n$因数

为什么是积性函数?

对任意$a,b,gcd(a,b)=1$, $a,b$没有不含有相同的$p$, 直接带入通式得证

反正关于欧拉函数的东西盯着这个通式就好了

幂函数$Id$ok

$id_k(n)=n^k$

$id(n)=id_1(n)=n$

显然是积性函数

单位函数$\epsilon$ok

$\epsilon(n)=[n=1]$

显然是积性函数

线性筛

核心:保证每个数只被他最小的质数筛到一次

int tot;

bool vis[MAXN];

int p[MAXN], phi[MAXN], mu[MAXN];

void filter()

{

	phi[1] = mu[1] = 1;

	for (int i = 2; i <= n; ++ i)

		{

			if (!vis[i]) p[++ tot] = i, phi[i] = i - 1, mu[i] = -1;

			for (int j = 1; j <= tot && i * p[j] <= n; ++ j)

				{

					vis[i * p[j]] = true;

					if (i % p[j] == 0)

						{

							phi[i * p[j]] = phi[i] * p[j]; mu[i * p[j]] = 0;

                        //没有增加质因子, 结合phi的通式可得

							break;

						}

					else

						{

							phi[i * p[j]] = phi[i] * phi[p[j]];

							mu[i * p[j]] = -mu[i];

						}

				}

			printf("%d %d\n", mu[i], phi[i]);

		}

}

Dirichlet卷积

\[(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})
\]

交换律 $f ∗ g = g ∗ f$

结合律 $(f ∗ g) ∗ h = f ∗ (g ∗ h)$

分配律 $f ∗ (g + h) = f ∗ g + f ∗ h$

单位元 $f ∗ ϵ = f$

若 $f,g$ 均为积性函数，则 $f*g$ 也是积性函数

证明：

对任意$a,b,gcd(a,b)=1$, $ab$的质因子集合可以不重不漏分到$a,b$的质因子集合中

$(f*g)(ab) = \sum_{d|ab}f(d)g(\frac{ab}{d})$

设$d=d_a*d_b$, $d_a,d_b$分别由$a,b$的因子组成, 显然组成的方式唯一, 并且$d$唯一分解成$d_a,d_b$

\[\begin{aligned}
(f*g)(ab)&=\sum_{d_a|a, d_b|b}f(d_a)f(d_b)g(\frac{a}{d_a})g(\frac{b}{d_b})\\
&=\sum_{d_a|a, d_b|b}f(d_a)g(\frac{a}{d_a})*f(d_b)g(\frac{b}{d_b})\\
&=(f*g)(a)*(f*g)(b)
\end{aligned}
\]

已知$f,g$,$O(nlog_2^n)$求$(f*g)$

for (int i = 1; i * i <= n; ++ i)

{

    (f*g)[i*j] += f[i] * g[i];

    for (int j = i + 1; i * j <= n; ++ j)

        (f*g)[i*j] += f[i] * g[j] + f[j] * g[i];

}

不会证

常见数论函数

$\sigma(n)$表示整数$n$的所有正因数的和

$\tau(n)$表示整数$n$的所有正因数的个数

$Id(i)=i$

以及前面的一些积性函数

常见狄利克雷卷积及其证明

$\epsilon = \mu *1$

证明:

$n$含有多个相同质因子或$=1$是显然成立

考虑$n=p_1*p_2*...*p_k$, $p_i$都是不同质因子

\[\begin{aligned}
\epsilon(n) & = \sum_{d|n}\mu(d) \\
& = \sum_{i=1}^{k}\binom{k}{i}*(-1)^k \\
\end{aligned}
\]

由于$(x+y)^k=\sum x^iy^{k-i}*\binom{k}{i}$, 带入$x=-1, y=1$, 凑进去

\[\begin{aligned}
\epsilon(n)&=\sum_{i=1}^{k}0^k\\
&=
\begin{cases}
1, & k=0\ so\ n=1 \\
0, & otherwise
\end{cases}
\end{aligned}
\]

$\sigma = Id*1$

$\tau=1*1$

显然

$\phi = \mu * Id$

证明:

\[\begin{aligned}
\phi(n) & = \sum_{d|n}\mu(d)id(\frac{n}{d}) \\
& = 1 \cdot n + \sum_{d=\prod p}\mu(d)id(\frac{n}{d}) + 0\cdot (...)\\
& = n + \sum_{i=1}^{k}(-1)^k*n*\frac{1}{\prod{p}} \\
& = n * \prod_{i=1}^{k}(1-\frac{1}{p_i})
\end{aligned}
\]

$\phi * 1= Id$

上面一个等式两边同乘以$1$

莫比乌斯Van演

定理:$\epsilon = \mu * 1$

若函数 $f, g$ 满足

$f(n) = \sum_{d|n}g(d)$

则

$g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d}) = \sum_{d|n}\mu(\frac{n}{d})f(d)$

证明:$

$f = g*1 \longleftrightarrow \mu * f = g$ $

左式同乘以$\mu$, 右式同乘以$1$

常用:

运用这个卷积:

$\epsilon = \mu * 1$ 即 $\sum_{d|n}\mu(d) = 1$

$[\gcd(i, j) == 1] = \sum_{k | \gcd(i,j)} \mu(k)$

例题:

NOI2015寿司

BZOJ1257: CQOI2007余数之和

题意:

$n, k(\le10^9)$, 求$\sum_{i=1}^{n}(k \mod i)$

Sol:

$\sum_{i=1}^{n}(k \mod i) = \sum_{i=1}^{n}(k - k / i * i) = nk - \sum_{i=1}^{n}(k/i)*i$

BZOJ1101: POI2007Zap

$T$ 组询问，$1 ≤ T, n, m , d≤ 50000$

\[\sum_{x=1}^{n}\sum_{y=1}^{m}[\gcd(x,y)=d]
\]

相当于求

\[\sum_{x=1}^{n/d}\sum_{y=1}^{m/d}[\gcd(x,y)=1]
\]

n /= d, m /= d 根据$\epsilon = \mu * 1$,即求

\[\begin{aligned}
& = \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d) \\
& = \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}\mu(d) \\
& = \sum_d\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
\end{aligned}
\]

除法分块$O(\sqrt{n})$

BZOJ2154: Crash的数字表格

$1\le n, m\le10^7$, 求

\[\sum_{i=1}^{n}\sum_{j=1}^{m} lcm(i,j)
\]

$i*j=\gcd(i,j) * lcm(i,j)$

\[\begin{aligned}
&= \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{\gcd(i,j)} \\
&= \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i}{\gcd(i,j)}\frac{j}{\gcd(i,j)}\gcd(i,j) \\
&= \sum_{g}g\sum_{i=1}^{n/g}\sum_{j=1}^{m/g}i*j*[\gcd(i,j)=1] \\
&= \sum_{g}g\sum_{i=1}^{n/g}\sum_{j=1}^{m/g}i*j*\sum_{d|gcd(i,j)}\mu(d) \\
&= \sum_{g}g\sum_{i=1}^{n/g}\sum_{j=1}^{m/g}i*j*\sum_{d|i,d|j}\mu(d) \\
&= \sum_{g}g\sum_{d}\sum_{i=1}^{n/gd}\sum_{j=1}^{m/gd}i*d*j*d*\mu(d) \\
&= \sum_{gd}gd\sum_{i=1}^{n/gd}\sum_{j=1}^{m/gd}i*j*d*\mu(d) \\
\end{aligned}
\]

设$p=g*d$

\[\begin{aligned}
&= \sum_{p}p*\sum_{d|p}d*\mu(d)\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}ij
\end{aligned}
\]

完了,然后怎么做?

大爷xyyxyyx说: $F(p)=\sum_{d|p}d*\mu(d)*p$是积性函数

为什么?

设$a,b,gcd(a,b)=1,d=da*db,da|a,db|b$

\[F(ab)=\sum_{da|a,db|b}da*\mu(da)*db*\mu(db)*a*b
\]

好了, 然后$O(n)$筛?然后暴力$O(n)$求答案?

观察$F(i)$的式子, 套用线性筛:

$i$为质数: $F(i)=(1*\mu(1)+i*\mu(i))*i$
用已经筛出来的质数$p[j]$去筛$i*p[j]$
- $i\mod p[j]!=0$, 互质!$F(i*p[j])=F(i)*F(p[j])$
- $i \mod p[j] == 0$,考虑对比$F(i)$,新加入的因数必须含有$p^2$, 而这样的因数$\mu{}$是等于0的!那么直接$F(i*p[j])=F(i)*p[j]$

然后少写了一个$mod$, WA了,然后又T了

整出分块!!注意到在一段区间里$(n/p, m/p)$是不变的, 所以可以对$F$直接区间求和(前缀和实现)

//空间注意一点

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 1e7 + 10;

const LL MOD = 20101009;

int n, m;

LL ans;

int tot;

bool vis[MAXN];

int mu[MAXN], p[664590];

LL f[MAXN];

int sum[MAXN], sumf[MAXN];

void filter()

{

    mu[1] = sumf[1] = f[1] = sum[1] = 1;

	LL tmp1 = 0;

    for (int i = 2; i <= m; ++ i)

        {

            tmp1 = 1LL * i * (i + 1) / 2 % MOD;

			sum[i] = tmp1;

            if (!vis[i]) mu[i] = -1, p[++ tot] = i, f[i] = 1LL * (1 + i * mu[i] % MOD + MOD) * i % MOD;

            for (int j = 1; j <= tot && i * p[j] <= m; ++ j)

                {

                    vis[i * p[j]] = true;

                    if (i % p[j] == 0) { mu[i * p[j]] = 0; f[i * p[j]] = f[i] * p[j] % MOD; break; }

                    else mu[i * p[j]] = -mu[i], f[i * p[j]] = f[i] * f[p[j]] % MOD;

                }

            sumf[i] = (sumf[i - 1] + f[i]) % MOD;

        }

}

int main()

{

    scanf("%d%d", &n, &m);

    if (n > m) swap(n, m);

    filter();

    for (int i = 1; i <= n; )

        {

            int r = min(n, min(n / (n / i), m / (m / i)));

            (ans += sum[n / i] % MOD * sum[m / i] % MOD * (sumf[r] - sumf[i - 1] + MOD) % MOD) %= MOD;

            i = r + 1;

        }

    printf("%lld\n", ans);

    return 0;

}

PE530: GCD of Divisors

Let f(n) be the sum of the greatest common divisor of d and n/d over all positive divisors d of n, that is $f(n)=\displaystyle\sum\limits_{d|n}\, \text{gcd}(d,\frac n d)$

Let F be the summatory function of f, that is $F(k)=\displaystyle\sum\limits_{n=1}^k \, f(n)$

You are given that $F(10)=32$ and $F(1000)=12776.$

Find $F(1015)$.

提交答案题

\[F(n) = \sum_{i=1}^{n}\sum_{d|i}{\gcd(d, \frac{i}{d})}
\]

相当于枚举$i$, 并将$i$分解成两个数的乘积, 求所有这样的$\gcd$的和

等价于枚举两个数, 他们乘积$\le n$, 求他们$\gcd$的乘积

所以:

\[\begin{aligned}
F(n)&=\sum_{i = 1}^{n}\sum_{j=1}^{n/i}{\gcd(i,j)} \\
&=\sum_gg\sum_i\sum_j[\gcd(i,j)==1][i*g*j*g\le n]
\end{aligned}
\]

注意不能像以前那样把两个$\sum{}$的上界除以$g$

从而认为$i*j\le n/g$

因为两个$\sum{}$是有关联的,只有当第一个确定时,才能枚举第二个, 如果这么做的话相当于同时枚举两个

例如$i*j\le n*n/i$显然不对

那么继续

\[\begin{aligned}
F(n) &= \sum_gg\sum_i\sum_j\sum_{d|i,d|j}\mu(d)*[i*j*g^2\le n] \\
&= \sum_gg\sum_d\mu(d)\sum_i\sum_j[i*j\le\frac{n}{g^2*d^2}] \\
\end{aligned}
\]

考虑把$g*d$并在一起, 然后康康这个和什么卷积比较像

\[p = gd\\
\phi(x)=\sum_{d|x}Id(x)*\mu(\frac{n}{x}) \\
\]

于是就化简成了

\[F(n)=\sum_p\phi(p)*\sum_i\sum_j[i*j\le\frac{n}{p^2}]
\]

什么,要求$10^{15}$?不会炸空间吗?

注意后面$\lfloor \frac{n}{p^2}\rfloor$, 可以缩小到$\sqrt{n}$

那么枚举$p$, 然后每次单独分块求就好了

\[F(n)=\phi(p)*\sum_i\lfloor\frac{n}{p^2i}\rfloor
\]

复杂度呢?前半个$O(\sqrt{n})$, 后半个$O(ln_n)$?不会证...

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 32e6 + 10;

const LL MOD = 20101009;

LL n;

LL ans;

int tot;

bool vis[MAXN];

LL p[MAXN], phi[MAXN];

LL f[MAXN];

void filter()

{

    phi[1] = 1;

    for (int i = 2; i < MAXN; ++ i)

        {

            if (!vis[i]) p[++ tot] = i, phi[i] = i - 1;

            for (int j = 1; j <= tot && i * p[j] < MAXN; ++ j)

                {

                    vis[i * p[j]] = true;

                    if (i % p[j] == 0) { phi[i * p[j]] = phi[i] * p[j]; break; }

                    else phi[i * p[j]] = phi[i] * phi[p[j]];;

                }

        }

}

LL calc(LL x)

{

	LL ret = 0;

	for (LL i = 1; i <= x; )

		{

			LL r = min(x / (x / i), x);

			ret += (r - i + 1) * (x / i);

			i = r + 1;

		}

	return ret;

}

int main()

{

    scanf("%lld", &n);

	n = 1e15;

    filter();

    for (LL i = 1; i * i <= n; ++ i)

        {

			ans += phi[i] * calc(n / (i * i));

        }

    printf("%lld\n", ans);

    return 0;

}

杜教筛

基本

目的:求$f(i)$的前缀和

套路:构造$h=g*f$

\[\begin{aligned}
\sum_{i=1}^{n}h(i)&=\sum_{i=1}^{n}\sum_{d|i}g(d)*f(\frac{d}{i}) \\
\end{aligned}
\]

即等同于枚举两个因数，他们乘积$\le n$,计算他们$g$和$f$的乘积的和

\[\begin{aligned}
&=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f({i}) \\
\end{aligned}
\]

设$S(n)=\sum f(i)$

\[\begin{aligned}
\sum_{i=1}^{n}h(i)&=\sum_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor) \\
\sum_{i=1}^{n}h(i)&=g(1)*S(n)+\sum_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor) \\
g(1)*S(n)&=\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)\\
\end{aligned}
\]

所以只要凑出方便的$h, g$就可以套用最后一行式子了

\[g(1)*S(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)
\]

求$\sum_{i=1}^{n}\mu(i)$

$\epsilon = \mu * 1, h=\epsilon,g=1$

\[S(n)=1-\sum_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor)
\]

求$\sum_{i=1}^{n}\phi(i)$

$Id=\phi*1, h=Id, g=1$

\[S(n)=\frac{n*(n+1)}{2}-\sum_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor)
\]

先看一道例题

例题BZOJ3944: Sum

$T(\le 10)$组数据, $N(\le 2^{31}-1)$, 求$\sum_{i=1}^{n}\mu(i), \sum_{i=1}^{n}\phi(i)$

两个长得很像可以一起做, $\lfloor\frac{n}{i}\rfloor$可以整除分块

递归实现, 但是要先预先筛一部分, 不然会$T$, 记忆化搜索用$map$记录

#include <cstdio>

#include <map>

using namespace std;

typedef long long LL;

typedef pair<int, LL> PIL;

#define mkpr make_pair

const int MAXN = 5e6 + 2;

inline LL in()

{

    LL x = 0, flag = 1; char ch = getchar();

    while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }

    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();

    return x * flag;

}

int n;

int tot;

bool vis[MAXN];

int p[348516], mu[MAXN]; //348513

LL phi[MAXN];

void filter()

{

	phi[1] = mu[1] = 1;

	for (int i = 2; i < MAXN; ++ i)

		{

			if (!vis[i]) { mu[i] = -1, phi[i] = i - 1, p[++ tot] = i; }

			for (int j = 1; j <= tot && i * p[j] < MAXN; ++ j)

				{

					vis[i * p[j]] = true;

					if (i % p[j] == 0)

						{ mu[i * p[j]] = 0, phi[i * p[j]] = phi[i] * p[j]; break; }

					else

						mu[i * p[j]] = -mu[i], phi[i * p[j]] = phi[i] * phi[p[j]];

				}

		}

	for (int i = 2; i < MAXN; ++ i) mu[i] += mu[i - 1], phi[i] += phi[i - 1];

}

map <LL, PIL> f; //92680

PIL solve(LL x) // Smu[x] = 1 - [2, n]Smu[x / i],

{

	if (x < MAXN) return mkpr(mu[x], phi[x]);

	if (f.count(x)) return f[x];

	int mu = 1; LL phi = x * (x + 1) / 2;

	for (LL i = 2, nex = i; i <= x; i = nex + 1)

		{

			nex = x / (x / i);

			PIL val = solve(x / i);

			mu -= (nex - i + 1) * val.first;

			phi -= (nex - i + 1) * val.second;

		}

	return f[x] = mkpr(mu, phi);

}

int main()

{

	filter();

	//	printf("%d\n", tot);

	int Test = in();

	while (Test --)

		{

			n = in();

			PIL ans = solve(n);

			printf("%lld %d\n", ans.second, ans.first);

		}

	return 0;

}

复杂度

不会证, 据说预处理$n^{\frac{2}{3}}$, 复杂度为$O(n^{\frac{2}{3}})$

巴特西

数论2&莫&杜

积性函数:

积性函数定义ok

莫比乌斯函数\(\mu\)ok

欧拉函数\(\phi\)ok

幂函数\(Id\)ok

单位函数\(\epsilon\)ok

线性筛

Dirichlet卷积

若 \(f,g\) 均为积性函数，则 \(f*g\) 也是积性函数

已知\(f,g\),\(O(nlog_2^n)\)求\((f*g)\)

常见数论函数

常见狄利克雷卷积及其证明

\(\epsilon = \mu *1\)

\(\sigma = Id*1\)

\(\tau=1*1\)

\(\phi = \mu * Id\)

\(\phi * 1= Id\)

莫比乌斯Van演

例题:

BZOJ1257: CQOI2007余数之和

BZOJ1101: POI2007Zap

BZOJ2154: Crash的数字表格

PE530: GCD of Divisors

杜教筛

基本

求\(\sum_{i=1}^{n}\mu(i)\)

求\(\sum_{i=1}^{n}\phi(i)\)

例题BZOJ3944: Sum

复杂度

最新文章

热门文章