莫比乌斯反演习题:bzoj 1101 [POI2007]Zap

题目描述

有$T$组询问,每次给定整数$a,b,d$,求有多少对正整数$x,y$,满足$x \le a \wedge y \le b \wedge (x,y)=d$

阅读全文

莫比乌斯反演习题:bzoj 3529 [Sdoi2014]数表

题目描述

有一张$n \times m$的数表,其第$i$行第$j$列$(1 \le i \le n, 1 \le j \le m)$的数值为能同时整除$i$和$j$的所有自然数之和

阅读全文

莫比乌斯反演习题:bzoj 2956 模积和

题目描述

求$\sum_{i=1}^{n}\sum_{j=1}^{m}(n \text{ mod } i) \times (m \text{ mod } j)$

阅读全文

莫比乌斯反演习题:bzoj 2820 YY的GCD

题目描述

有$T$组询问,每次给定$n,m$求$1 \le x \le n \wedge 1 \le y \le m \wedge (x,y) \in P$的$(x,y)$的个数,其中$P$是素数集合

阅读全文

莫比乌斯反演习题:bzoj 2301 [HAOI2011]Problem b

题目描述

有$T$组询问,每次给定整数$a,b,c,d,k$,求有多少对正整数$x,y$,满足$a \le x \le b \wedge c \le y \le d \wedge (x,y)=k$

阅读全文

莫比乌斯反演习题:bzoj 2154 Crash的数字表格

题目描述

给定$n,m$,求$\sum_{i=1}^{n}\sum_{j=1}^{m}\text{lcm}(i,j)$

$n,m \le 10^7$

阅读全文

莫比乌斯反演习题:bzoj 1257 [CQOI2007]余数之和

题目描述

给出正整数$n$和$k$,计算$f(n, k)=k \text{ mod } 1 + k \text{ mod } 2 + k \text{ mod } 3 + \cdots + k \text{ mod } n$的值

阅读全文

莫比乌斯反演

阅读全文

01trie

简介

trie(retrieval)树,一种存储多个有序序列的树,在存储前缀相等次数多的数据时有很大的优势

一般来说,trie树是用于字典树,但这篇文章不谈字典树,而谈一谈它的近亲——binary trie

阅读全文

斜率优化

何为斜率优化

对于一类动态规划问题,方程式诸如

$$
f_i=\max\{c_i + k_i \cdot x_j + y_j | j \lt i\}
$$

阅读全文