Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共3篇）

P3455 [POI2007]ZAP-Queries(莫比乌斯反演)

题目 P3455 [POI2007]ZAP-Queries 解析莫比乌斯反演。给定\(n\)，\(m\)，\(d\)，求\[\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\] 那我们设\[f(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[...

莫比乌斯反演数学

2019-04-12

0 536

莫比乌斯反演

莫比乌斯函数定义对\(d\)进行质因数分解：\(d=p_1^{r1}p_2^{r2}p_3^{r3}····p_k^{rk}\) \(r=max\{r_1,r_2,r_3···r_k\}\) 莫比乌斯函数的定义为 \[\mu(d) = \begin{cases}1\qquad d=1\\ 0...

数学莫比乌斯反演

2019-04-06

0 482

P2522 [HAOI2011]Problem b (莫比乌斯反演)

题目 P2522 [HAOI2011]Problem b 解析：具体推导过程同P3455 [POI2007]ZAP-Queries 不同的是，这个题求的是\(\sum_{i=a}^b\sum_{j=c}^dgcd(i,j)=k\) 像二维前缀和一样容斥一下，输出就完了。根据luogu某大...

莫比乌斯反演数学

2019-04-13

0 551