lrxQwQ - 博客园_a56爆大奖在线娱乐

2023年5月10日

摘要：一、问题给定 $n,m,p$，求 $C_n^m\bmod p$，$n,m\le 10^{18},p\le 10^6$。 $p$ 现在不一定是质数了，该怎么办？二、解法首先，数论题一个常见的做法：如果模数不一定是质数，那就把模数拆成若干个质数的积，然后分别求解，最后用中国剩余定理求解。 1. 拆阅读全文

posted @ 2023-05-10 23:42 lrxQwQ 阅读(16) 评论(0) 推荐(1) 编辑

Lucas 定理学习笔记

摘要：一、定理给定 $n,m,p$，$p$ 是质数，求 $C_{m+n}^n\bmod p$，$n,m\le 10^{18},p\le 10^6$。这题可以用 Lucas 定理求解。 Lucas 定理：当 $p$ 是个质数时，$\forall m,n\in N,C_n^m\equiv C_{\lfl 阅读全文

posted @ 2023-05-10 13:28 lrxQwQ 阅读(16) 评论(0) 推荐(1) 编辑

2023年5月9日

中国剩余定理学习笔记

摘要：给定 $n$ 组非负整数 $a_i, b_i$，其中 $b_i$ 两两互质，求解关于 $x$ 的方程组的最小非负整数解。 $\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \ x\equiv b_2\ ({\rm mod}\ a_2) \ ... \ x \ 阅读全文

posted @ 2023-05-09 20:36 lrxQwQ 阅读(20) 评论(0) 推荐(1) 编辑

数学汇总

摘要： ### $\mathrm{I}$ 数论 #### 一、整除理论 ##### 1. 自然数与整数 ##### 2. 整除的基本知识 ##### 3. 带余除法 ##### 4. 最大公约数理论 1. [计算两个数的最大公约数](/qwq-qaq-tat/p 阅读全文

posted @ 2023-05-09 18:00 lrxQwQ 阅读(22) 评论(0) 推荐(1) 编辑

扩展中国剩余定理学习笔记

摘要：给定 $n$ 组非负整数 $a_i, b_i$ ，求解关于 $x$ 的方程组的最小非负整数解。 $\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \ x\equiv b_2\ ({\rm mod}\ a_2) \ ... \ x \equiv b_n\ ({ 阅读全文

posted @ 2023-05-09 17:56 lrxQwQ 阅读(13) 评论(0) 推荐(1) 编辑

大步小步算法学习笔记

摘要：一、BSGS 算法系统来说，它适用于求离散对数，也就是高次同余方程的解。给定一个整数 $p$，以及一个整数 $b$，一个整数 $n$，现在要求你计算一个最小的非负整数 $l$，满足 $b^l \equiv n \pmod p$，$2\le b,n < p<2^{31},\gcd(p,b)=1$。阅读全文

posted @ 2023-05-09 17:04 lrxQwQ 阅读(21) 评论(0) 推荐(1) 编辑

同余方程学习笔记

摘要：一、裴蜀定理裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 $a,b$ 和它们的最大公约数 $d$，关于未知数 $x$ 和 $y$ 的线性不定方程（称为裴蜀等式）：若 $a,b$ 是整数,且 $\gcd(a,b)=d$，那么对于�a56爆大奖在线娱乐獾恼� $x,y,ax+by$ 都一定是 $ 阅读全文

posted @ 2023-05-09 11:01 lrxQwQ 阅读(32) 评论(0) 推荐(1) 编辑

2023年5月2日

Treap 学习笔记

摘要：一、Treap Treap 是a56爆大奖在线娱乐通过旋转操作维护性质的二叉搜索树。定义详见要维护的东西还是一样，对于a56爆大奖在线娱乐节点，要维护它的左右儿子，子树大小，还有权值和随机的优先级（这样才能保证树的高度是 $O(\log n)$ 级别的）。注意：旋转、分裂、伸展什么的都是手段，维持平衡树的 2 个性质才是目的阅读全文

posted @ 2023-05-02 07:45 lrxQwQ 阅读(11) 评论(0) 推荐(1) 编辑

2023年4月30日

堆与二叉搜索树学习笔记

摘要：部分内容来自 OI-WIKI。 1. 堆 0. 堆的定义堆是一棵二叉树，满足a56爆大奖在线娱乐节点的键值都大于等于它的父亲节点或者小于等于它的父亲节点。a56爆大奖在线娱乐节点的键值都大于等于它的父亲节点的叫小根堆，a56爆大奖在线娱乐节点的键值都小于等于它的父亲节点的叫大根堆。优先队列是a56爆大奖在线娱乐抽象数据类型，它是a56爆大奖在线娱乐容器，里面有一些元素，这些阅读全文

posted @ 2023-04-30 19:08 lrxQwQ 阅读(36) 评论(0) 推荐(1) 编辑

左偏树学习笔记

摘要：一、前言左偏树是a56爆大奖在线娱乐可以在 $O(\log n)$ 内快速合并的堆式数据结构。具体来说，插入一个元素：$O(\log n)$。查询最值：$O(1)$。删除最值：$O(\log n)$。合并：$O(\log n)$。减少一个元素的值：$O(\log n)$。同时它可以持久化。二、定义阅读全文

posted @ 2023-04-30 19:05 lrxQwQ 阅读(16) 评论(0) 推荐(1) 编辑

qwq-qaq-tat

公告