Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SDOI2016」数字配对 - 费用流

    n n 种数字,第 i i 种数字是 ai a_i 、有 bi b_i 个,权值是 ci c_i

    若两个数字 ai a_i aj a_j 满足,ai a_i aj a_j 的倍数,且 aiaj \frac{a_i}{a_j} 是一个质数,那么这两个数字可以配对,并获得 ci×cj c_i \times c_j 的价值。

    一个数字只能参与一次配对,可以不参与配对。
    在获得的价值总和不小于 0 0 的前提下,求最多进行多少次配对。

    于  BZOJ, COGS, Edmonds-Karp, SDOI, 二分答案, 数论, 素数判定, 线性筛, 网络流, 费用流 继续阅读

  2. 线性筛法筛素数、莫比乌斯函数、欧拉函数

    线性筛法(欧拉筛法)可以在 O(n) O(n) 的时间内获得 [1,n] [1, n] 的所有素数。算法保证每个合数都会被它的最小质因子筛掉,所以复杂度是线性的。同时,我们可以利用这一特性,结合积性函数的性质,在 O(n) O(n) 的时间内筛出一些积性函数的值。

    于  学习笔记, 数学, 数论, 算法模板, 线性筛 继续阅读

  3. 「HAOI2011」Problem b - 莫比乌斯反演

    对于给出的 n n 个询问,每次求有多少个数对 (x,y) (x, y) ,满足 axb a \leq x \leq b cyd c \leq y \leq d ,且 gcd(x,y)=k \gcd(x, y) = k gcd(x,y) \gcd(x, y) 函数为 x x y y 的最大公约数。

    于  BZOJ, COGS, HAOI, 数学, 数论, 线性筛, 莫比乌斯反演 继续阅读

  4. 「BZOJ 2820」YY的GCD - 莫比乌斯反演

    1xN 1 \leq x \leq N 1yM 1 \leq y \leq M gcd(x,y) \gcd(x, y) 为质数的 (x,y) (x, y) 数量。

    于  BZOJ, 数学, 数论, 线性筛, 莫比乌斯反演 继续阅读