整除分块
通常,要求
需要的时间为\(O(n)\)。
但是实际上,对于几块连续的\(i\),\(\lfloor\frac{n}{i}\rfloor\)的值是相同的。
于是,我们可以计算出每块的长度,然后用乘法求和。
对于每块以\(i\)开始的区间,它的右端点都是\(n/(n/i)\)。
for (int l = 1, r; i <= n; i = r+1) {
r = n/(n/i);
ans += (r-i+1) * (n/i);
}
莫比乌斯函数 \(\mu\)
定义
\(d = 1\)时,\(\mu(d) = 1\)。
设\(d\)有\(k\)个质因子。如果质因子的幂都等于\(1\),那么\(\mu(d)=(-1)^k\)。
如果存在\(d\)的质因子的幂大于等于\(2\),那么\(\mu(d)=0\)。
几个性质
-
对于任意正整数\(n\),\(\sum_{d|n}{\mu(d)} = [n=1]\)。(\([a] = a ? 1 : 0\))
证明:-
\(n = 1\)时,正确性显然。
-
\(n ≠ 1\)时,设\(n = p_1^{m_1}p_2^{m_2}...p_k^{m_k}\)。要从这\(k\)个质因子中每个至多选\(1\)个构成\(d\),才对和式的答案有影响。答案即是\(\sum_{i=0}^k{(-1)^i}\),通过二项式定理,即\((1-1)^k\)。
-
-
对于任意正整数\(n\),\(\sum_{d|n}\frac{\mu(d)}{d} =\frac{\phi(n)}{n}\)。
莫比乌斯反演
莫比乌斯反演定理
对于
有
即
证明
根据狄利克雷卷积
和\(I(n) = n\)
因为\(F(n) = (f * I)(n)\)
所以\((\mu*F)(n) = (\mu*f*I)(n) = (f*\varepsilon)(n) = f(n)\)
其中,\(I(n)=n\),\(\varepsilon(n) = [n = 1]\),叫做狄利克雷单位元。
为什么\(\mu*I = \varepsilon\)?
因为\((\mu*I)(n) = \sum_{d|n}\mu(d)=[n=1]\)(上面莫比乌斯函数的性质)