数论函数 数论函数: 定义域为正整数的函数。
积性函数: 对于任意两个互质的正整数 $a, b$,均满足 $f(ab)=f(a)\times f(b)$ 的函数 $f$
完全积性函数: 对于所有正整数 $a, b$,均满足 $f (ab)=f(a)\times f(b)$ 的函数 $f$
对于一个积性函数 $f$,$f(n)=f(\prod p_i^{a_i})=\prod f(p_i^{a_i})$,若 $f$ 还满足完全积性,则 $f(n)=\prod f(p_i)^{a_i}$
常见积性函数 欧拉函数 $\varphi(n)$
莫比乌斯函数 $\mu(n)$: 若 $n$ 有平方数因子,则 $\mu(n)=0$。否则若 $n$ 为 $k$ 个不同质数之积,则 $\mu(n)=(-1)^k$。
除数函数: $\sigma_k(n)$ 表示 $n$ 的所有正因子的 $k$ 次幂之和。
$d(n)=\sigma_0(n)$ 表示 $n$ 的正因子个数,$\sigma(n)=\sigma_1(n)$ 表示 $n$ 的所有正因子之和。
幂函数: $\operatorname{Id}_k(n)=n^k$,$1(n)=\operatorname{Id}_0(n)=1$,$\operatorname{Id}(n)=\operatorname{Id}_1(n)=n$
单位函数: $e(n)=\varepsilon(n)= \begin{cases} 1 & n = 1\\ 0 & n > 1 \end{cases} $
狄利克雷(Dirichlet)卷积 定义两个数论函数 $f$,$g$ 的 Dirichlet 卷积:
狄利克雷卷积的性质 交换律:
结合律:
分配律:
单位元:
常见的狄利克雷卷积
$d(n)=\sum_{d|n}1$,即 $d=1*1$
$\sigma(n)=\sum_{d|n}d$,即 $\sigma=d*1$
$\varphi(n)=\sum_{d|n}\mu(d)\frac{n}{d}$,即 $\varphi=\mu*\operatorname{Id}$
$\varepsilon(n)=\sum_{d|n}\mu(d)$,即 $\varepsilon=\mu*1$
一些结论和证明 $n = \sum_{d|n}\varphi(d)$。
$1$ 到 $n$ 中与 $n(n>1)$ 互质的数的和为 $\dfrac{n\times \varphi(n)}{2}$。
$\varepsilon=\mu*1$ 即为 $\sum_{d|n}\mu(d)=[n=1]$。
证明:$n=1$ 时 $\sum_{d|n}\mu(d)=1$。
$n \neq 1$ 时,设 $n$ 有 $k$ 个质因子,只有当 $n$ 的因子中所有质因子次数都为 $1$ 时,$\mu$ 不为 $0$,即
因此 $\sum_{d|n}\mu(d)=[n=1]$。
莫比乌斯反演 若两个函数 $f$,$g$ 满足:
则它们也满足
反之亦然,即
它的另一个形式:
线性筛 反演的题目经常会需要快速求积性函数,这时就要用到线性筛。
线性筛质数 设 $pr_i$ 表示 $i$ 的最小质因子。枚举所有不超过 $pr_i$ 的质数 $p$,使 $pr_(i\cdot p) = p$,相当于将每个数的质因子降序分解,每个数只会被它的最小质因子筛一次,因此复杂度是 $O(n)$ 的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void Shaker (int x) { for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = pr[i] = i; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) break ; } } }
线性筛积性函数 利用线性筛求解每个数 $n$ 的最小质因子 $p$ 的次数 $k$:令 $n = pm$,由于 $p$ 是 $n$ 最小的质因子,若 $p^2 | n$ ,则 $p | m$ ,并且 $p$ 也是 $m$ 最小的质因子,这样在筛法的同时即可算出新筛去的合数的最小质因子的次数。
这样在求解积性函数时,我们能利用 $f(n)=f(p^k)f(\frac{n}{p^k})$,在线性筛的同时快速求出 $f(n)$。
线性筛欧拉函数 $\varphi(p^k)=(p-1)p^{k-1}$,因此筛法时,若 $p | m$,$\varphi$ 就乘上 $p$,否则乘上 $p-1$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 void Shaker (int x) { phi[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = pr[i] = i, phi[i] = i - 1 ; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) { phi[k] = phi[i] * prime[j]; break ; } phi[k] = phi[i] * (prime[j] - 1 ); } } }
线性筛莫比乌斯函数 只有当 $k=1$ 时 $\mu(p^k)=-1$,否则 $\mu(p^k)=0$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 void Shaker (int x) { mu[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1 ; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) { mu[k] = 0 ; break ; } mu[k] = -mu[i]; } } }
筛法求约数个数、约数和 约数个数 $d_i$ 是积性函数,因此也可以用筛法求。类似的可以求约数和、最小质因子 $k$ 次幂的和。
求约数个数。$num_i$ 表示 $i$ 的最小质因子出现次数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 void Shaker (int x) { d[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = pr[i] = i, d[i] = 2 , num[i] = 1 ; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) { num[k] = num[i] + 1 ; d[k] = d[i] / num[k] * (num[k] + 1 ); break ; } num[k] = 1 ; d[k] = d[i] * 2 ; } } }
求约数和。$f_i$ 表示 $i$ 的约数和,$g_i$ 表示 $i$ 的最小质因子的 $p^0+p^1+p^2+\cdots +p^k$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 void Shaker (int x) { g[1 ] = f[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = pr[i] = i, g[i] = f[i] = i + 1 ; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) { g[k] = g[i] * prime[j] + 1 ; f[k] = f[i] / g[i] * g[k]; break ; } g[k] = prime[j] + 1 ; f[k] = f[i] * f[prime[j]]; } } }
题目 BZOJ 2705 求
$F$ 是积性函数,因此直接 $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 #include <bits/stdc++.h> using namespace std ;typedef long long LL;LL n, ans = 1 ; void Factor (LL x) { for (LL i = 2 ; i * i <= x; i++) { if (x % i == 0 ) { LL p = i, k = 0 , res = 1 ; while (x % i == 0 ) x /= i, k++, res *= p; ans *= res + k * (p - 1 ) * res / p; } } if (x > 1 ) ans *= x + (x - 1 ); } int main () { cin >> n; Factor(n); cout << ans << endl ; return 0 ; }
BZOJ 2226 求
令
$\sum_{d|n}d\cdot \varphi(d)$ 是积性函数,因此可以线性筛 $O(n)$ 预处理,单次询问 $O(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> using namespace std ;typedef long long LL;const int N = 1000000 + 5 ;int prime[N], pr[N], cnt;LL f[N], g[N]; void Shaker (int x) { f[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) { prime[++cnt] = pr[i] = i; g[i] = i; f[i] = (i - 1 ) * g[i] + 1 ; } for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) { g[k] = g[i] * prime[j] * prime[j] + prime[j]; f[k] = f[i] / ((prime[j] - 1 ) * g[i] + 1 ) * ((prime[j] - 1 ) * g[k] + 1 ); break ; } g[k] = prime[j]; f[k] = f[i] * ((prime[j] - 1 ) * g[k] + 1 ); } } } int main () { Shaker(1000000 ); int T; scanf ("%d" , &T); while (T--) { LL n; scanf ("%lld" , &n); printf ("%lld\n" , n * (f[n] + 1 ) / 2 ); } return 0 ; }
Luogu P1447 求
除法分块,$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 #include <bits/stdc++.h> #define fl first #define fr second #define pb push_back #define mp make_pair using namespace std ;typedef long long LL;typedef pair<int , int > pii;const int N = 100000 + 5 ;LL sum[N]; int prime[N], pr[N], phi[N], cnt;void Shaker (int x) { phi[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = pr[i] = i, phi[i] = i - 1 ; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) { phi[k] = phi[i] * prime[j]; break ; } phi[k] = phi[i] * (prime[j] - 1 ); } } for (int i = 1 ; i <= x; i++) sum[i] = sum[i - 1 ] + phi[i]; } inline LL F (LL n, LL m) { LL res = 0 ; for (register LL l = 1 , r; l <= min(n, m); l = r + 1 ) { r = min(n / (n / l), m / (m / l)); res += (sum[r] - sum[l - 1 ]) * (n / l) * (m / l); } return res; } int main () { Shaker(N - 5 ); int n, m; cin >> n >> m; cout << F(n, m) * 2 - 1L L * n * m << endl ; return 0 ; }
Luogu P1829 求
我们令
有
$G(n,m)$,$F(n,m)$ 都可以除法分块求,时间复杂度 $O(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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 #include <bits/stdc++.h> #define fl first #define fr second #define pb push_back #define mp make_pair using namespace std ;typedef long long LL;typedef pair<int , int > pii;const int N = 1e7 + 5 ;const int mod = 20101009 ;LL sum[N]; int prime[N], pr[N], mu[N], cnt;inline LL ch (LL x) { return (x % mod + mod) % mod; } void Shaker (int x) { mu[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1 ; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) { mu[k] = 0 ; break ; } mu[k] = -mu[i]; } } for (int i = 1 ; i <= x; i++) sum[i] = ch(sum[i - 1 ] + 1L L * mu[i] * i * i % mod); } inline LL Sum (LL n) { return ch(n * (n + 1 ) / 2 % mod); } inline LL G (LL n, LL m) { LL res = 0 ; for (LL l = 1 , r; l <= min(n, m); l = r + 1 ) { r = min(n / (n / l), m / (m / l)); res = ch(res + ch(sum[r] - sum[l - 1 ] + mod) * Sum(n / l) % mod * Sum(m / l) % mod); } return res; } inline LL F (LL n, LL m) { LL res = 0 ; for (LL l = 1 , r; l <= min(n, m); l = r + 1 ) { r = min(n / (n / l), m / (m / l)); res = ch(res + (r - l + 1 ) * (l + r) / 2 % mod * G(n / l, m / l) % mod); } return res; } int main () { Shaker(10000000 ); LL n, m; cin >> n >> m; cout << F(n, m) << endl ; return 0 ; }
Luogu P2257 求
方法一:这题主要难处理的是 $[\gcd(i,j)\in primes]$,如果我们有一个 $f$,使得 $\sum_{d|n}f(d)=[n\in primes]$ 就比较好了。 $f$ 容易用反演的套路 $O(n\log n)$ 递推出来。
方法二:
根据套路,我们枚举 $k=pd$,
可以线性筛求出 $\mu$,然后 $O(n\log n)$ 枚举因数求出 $\sum_{p\in primes}\mu(\frac{k}{p})$ 的前缀和。
Luogu P3327 求
其中 $d(x)$ 表示 $x$ 的约数个数。
这题只需要知道
即可,剩下的都是套路了。
另外,还有一个与这相似的式子:
原理与上面类似,都是对于每个质因子,它的幂在 $x$ 或 $y$ 上是 $0$,于是便能取到所有的幂。
杜教筛 原理 杜教筛可以处理数论函数前缀和问题。
对于数论函数 $f$,想要计算 $S(n)=\sum_{i=1}^nf(i)$。
对于任意一个数论函数 $g$,一定满足
证明:
就是交换了下求和顺序,然后把枚举 $i$ 变成了枚举 $\frac{i}{d}$。
那么就可以得到递推式
假如我们可以快速对 $\sum_{i=1}^n(f\ast g)(i)$ 求和,并用数论分块求解 $\sum_{i=2}^n g(i)S\left(\left\lfloor \frac{n}{i}\right\rfloor\right)$,就可以在较短时间内求得 $g(1)S(n)$。
莫比乌斯函数前缀和 我们知道,$\epsilon =\mu \ast 1$,即 $\epsilon(n)=\sum_{d \mid n} \mu(d)$。
因此,$S(n)=\sum_{i=1}^n \epsilon(i)-\sum_{i=2}^n S(\lfloor \frac{n}{i}\rfloor)=1-\sum_{i=2}^n S(\lfloor \frac{n}{i}\rfloor)$。
用线性筛预处理出前 $n^{\frac{2}{3}}$ 项,剩余部分用整除分块计算,总时间复杂度为 $O(n^{\frac{2}{3}})$。
欧拉函数前缀和 直接用莫比乌斯反演:
对于 $\sum_{i=1}^n \sum_{j=1}^i 1[\gcd(i,j)=1]$,排除掉 $i=1,j=1$ 的情况,再将结果除以 $2$ 即可。
当然也可以用杜教筛,$\varphi\ast 1=ID$
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 #include <bits/stdc++.h> using namespace std ;typedef long long LL;typedef pair<int , int > pii;const int N = 2000000 + 5 ;int prime[N], pr[N], mu[N], sum[N], cnt;map <LL, LL> Mu;void Shaker (int x) { mu[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1 ; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = prime[j]; if (i % prime[j] == 0 ) { mu[k] = 0 ; break ; } mu[k] = -mu[i]; } } for (int i = 1 ; i <= x; i++) sum[i] = sum[i - 1 ] + mu[i]; } LL Get_mu (LL x) { if (x <= N - 5 ) return sum[x]; if (Mu[x]) return Mu[x]; LL res = 1 ; for (LL i = 2 , j; i <= x; i = j + 1 ) { j = x / (x / i); res -= Get_mu(x / i) * (j - i + 1 ); } return Mu[x] = res; } LL Get_phi (LL x) { LL res = 0 ; for (LL i = 1 , j; i <= x; i = j + 1 ) { j = x / (x / i); res += (Get_mu(j) - Get_mu(i - 1 )) * (x / i) * (x / i); } return (res - 1 ) / 2 + 1 ; } int main () { Shaker(N - 5 ); int T; scanf ("%d" , &T); while (T--) { LL n; scanf ("%lld" , &n); printf ("%lld %lld\n" , Get_phi(n), Get_mu(n)); } return 0 ; }
P3768 简单的数学题 求
先将其化为
现在我们想求 $f(n)=n^2\varphi(n)$ 的前缀和,于是我们尝试构造 $g$,使 $f\ast g$ 和 $g$ 能够快速求和。
给 $f$ 卷上 $ID^2$,化简一下,得到
再化一下 $S(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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 #include <bits/stdc++.h> using namespace std ;typedef long long LL;typedef pair<int , int > pii;const int N = 5e6 + 5 ;int prime[N], phi[N], cnt;LL sum[N], n, p, inv2, inv6; unordered_map <LL, LL> Map;bool pr[N];void Shaker (int x) { phi[1 ] = 1 ; for (int i = 2 ; i <= x; i++) { if (!pr[i]) prime[++cnt] = i, pr[i] = 1 , phi[i] = i - 1 ; for (int j = 1 ; j <= cnt; j++) { int k = i * prime[j]; if (k > x) break ; pr[k] = 1 ; if (i % prime[j] == 0 ) { phi[k] = phi[i] * prime[j]; break ; } phi[k] = phi[i] * (prime[j] - 1 ); } } for (int i = 1 ; i <= x; i++) sum[i] = (sum[i - 1 ] + 1L L * i * i % p * phi[i]) % p; } LL qpow (LL a, LL b) { LL res = 1 ; for (; b; b >>= 1 , a = a * a % p) if (b & 1 ) res = res * a % p; return res; } LL Inv (LL x) { return qpow(x, p - 2 ); } LL Get_Sum2 (LL x) { x %= p; return x * (x + 1 ) % p * (x * 2 + 1 ) % p * inv6 % p; } LL Get_Sum3 (LL x) { x %= p; return x * (x + 1 ) % p * inv2 % p * x % p * (x + 1 ) % p * inv2 % p; } LL S (LL x) { if (x <= N - 5 ) return sum[x]; if (Map[x]) return Map[x]; LL res = Get_Sum3(x); for (LL l = 2 , r; l <= x; l = r + 1 ) { r = x / (x / l); res = (res - (Get_Sum2(r) - Get_Sum2(l - 1 )) % p * S(x / l)) % p; } return Map[x] = (res + p) % p; } LL Solve (LL x) { LL res = 0 ; for (LL l = 1 , r; l <= x; l = r + 1 ) { r = x / (x / l); res = (res + Get_Sum3(x / l) * (S(r) - S(l - 1 )) % p) % p; } return (res + p) % p; } int main () { scanf ("%lld%lld" , &p, &n); Shaker(N - 5 ); inv2 = Inv(2 ), inv6 = Inv(6 ); printf ("%lld\n" , Solve(n)); return 0 ; }