Menci

眉眼如初,岁月如故

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


  1. 「SDOI2013」随机数生成器 - 数学 + BSGS

    给定 p p a a b b x1 x_1 ,现有一数列

    求最小的 i i 满足 xi=t x_i = t

    于  BSGS, BZOJ, SDOI, 数学, 数论 继续阅读

  2. 「Codeforces 716E」Digit Tree - 点分治

    给一棵树,每一条边上有一个 [1,9] [1, 9] 内的数字,求有多少有序点对 (u,v) (u, v) 满足,将 u u v v 的最短路上所有边上的数字连接成一个数,这个数是 m m 的倍数。其中 gcd(m,10)=1 \gcd(m, 10) = 1

    于  Codeforces, 乘法逆元, 数学, 数据结构, 数论, 点分治 继续阅读

  3. 从傅里叶变换到数论变换

    FFT 可以用来计算多项式乘法,但复数的运算会产生浮点误差。对于只有整数参与的多项式运算,有时,使用数论变换(Number-Theoretic Transform)会是更好的选择。

    于  原根, 多项式, 学习笔记, 数学, 数论, 算法模板 继续阅读

  4. 乘法逆元的几种计算方法

    乘法逆元是数论中重要的内容,也是 OI 中常用到的数论算法之一。所以,如何高效的求出乘法逆元是一个值得研究的问题。

    这里我们只讨论当模数为素数的情况,因为如果模数不为素数,则不一定每个数都有逆元。

    于  乘法逆元, 学习笔记, 数学, 数论, 算法模板 继续阅读

  5. 「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, 二分答案, 数论, 素数判定, 线性筛, 网络流, 费用流 继续阅读

  6. 「BZOJ 4403」序列统计 - 组合数

    给定三个正整数 N N L L R R ,统计长度在 1 1 N N 之间,元素大小都在 L L R R 之间的单调不降序列的数量。输出答案对 106+3 10 ^ 6 + 3 取模的结果。

    于  BZOJ, Lucas 定理, 乘法逆元, 数学, 数论, 组合数, 组合数学 继续阅读

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

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

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

  8. 「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, 数学, 数论, 线性筛, 莫比乌斯反演 继续阅读

  9. 「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, 数学, 数论, 线性筛, 莫比乌斯反演 继续阅读

  10. 「BZOJ 2296」随机种子 - 数论基础

    给定一个数 x x 0x106 0 \leq x \leq 10 ^ 6 ),求一个数 n n 满足:

    1. n n 的十进制表示中包含 0 ~ 9 的所有数;
    2. 0n1016 0 \leq n \leq 10 ^ {16}

    于  BZOJ, 安徽集训, 数论 继续阅读