重要引理 $$ \left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\right\rfloor $$ 数论分块 洛谷P1403 题目大意： 设$f(x)$为$x$的约数个数，求$\sum_{i=1}^{n}f(i)$ 分析： 枚举约…

较简单的容斥 XMU区域赛选拔D 塔子哥数数 题目大意： 设 $g(x)$ 为莫比乌斯函数的绝对值，把 $g(1)g(2)g(3)...g(n)$ 连起来看成一个10进制数，其中 $g(1)$ 是最高位，那么这个数是多少。 解题思路： 正难则反，我们可以先考虑所有位是 $1$ ，再刨除 $g(i)=0$ 的位置。 计算所有位是 $1$ 的$n$位数…

形式与套路式 划重点！一切莫比乌斯反演题推柿子都等价于以下套路! $$ \begin{aligned} \left[gcd(i,j)=1\right]&\iff\sum_{d\mid gcd(i,j)}\mu(d)\cr \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)]&\iff\sum_{d}\sum_…

核心柿子 我们要求积性函数 $f$ 的前缀和。设： $$S(n)=\sum_{i=1}^{n}f(i)$$ 我们找到另一个积性函数 $g$，则有： $$ g(1)S(n)=\sum_{i=1}^{n}(f * g)(i)-\sum_{i=2}^{n}g(i)\cdot S\left(\left\lfloor\frac{n}{i}\right\rfl…

min25 筛分为两部分。第一部分可以求质数点值的前缀和（例如：$n$ 以内的质数之和），第二部分可以处理积性函数 $f(x)$ 前缀和，要求 $f(p)$ 是一个低阶多项式（如：$f(p)=p^2+p$），且 $f(p^c)$ 可快速求值。 以下介绍均以洛谷模版题为例：洛谷P5325 ：$f(p^k)=p^k(p^k-1)$ 第一部分-求质数点的…

hdu6607 题目大意： $$ \sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)^klcm(i, j)[gcd(i,j)\in prime]\pmod {1e9 + 7} $$ 其中 $n\le {10}^{10},\ k\le 100$ 分析： 方法一： $$ \begin{aligned} f(n,k)&=\s…