数论进阶

数论

---

数论分块

求解$\sum_{i+1}^n\lfloor\frac{n}{i}\rfloor$
据观察，$\lfloor\frac{n}{i}\rfloor$的取值只有$\sqrt{n}$个。
定理：若有一个值$i$，那么数论分块中其同值上界为$ceil=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$。
即在$[i,ceil]$这一段区间内，$\lfloor\frac{n}{i}\rfloor$的取值是一样的，于是可计算整块贡献。

int l = 1 , r , ans = 0;
while(l<=n){
    r = n/(n/l);    
    ans += (r-l+1)*(n/i);
    l = r + 1;
}

---

莫比乌斯反演

莫比乌斯反演有两种形式。。。

第一种

如果我们有函数$f(x)$,以及$g(x)$，并且有

$$g(x)=\sum_{d\mid x}f(d)$$
那么，我们就有
$$f(x)=\sum_{d\mid x}\mu (\frac{x}{d})g(d)$$

第二种

如果我们有函数$f(x)$,以及$g(x)$,并且有：

$$g(x)=\sum^n_{x\mid d}f(d)$$
其中$n$是我们限定的一个范围
那么我们可以得到：
$$f(x)=\sum_{x\mid d}^n\mu(\frac{d}{x})g(d)$$

至于$\mu$函数，叫做莫比乌斯函数。

一个数$a$，若其有质因子次数为$2$及以上,$\mu(a)=0$。
否则，若其有偶数个质因子，$\mu(a)=1$
否则，若其有奇数个质因子，$\mu(a)=-1$
至于运用？留个坑，以后写总结吧。