初等数论及其应用——Lucas定理

笔者经多番周折终于看懂了\(\text{Burnside}\)定理和\(\text{Polya}\)定理，特来写一篇学习笔记来记录一下。 群定义 定义：群\((G,·)\)是一个集合与一个运算·所定义的群。它所需要满足的性质是： 结合律：对于任...

注：转载本文须标明出处。 原文链接https://www.cnblogs.com/zhouzhendong/p/Number-theory.html 数论算法 剩余系相关 学习笔记 (基础回顾,(ex)CRT,(ex)lucas,(ex)BSGS,原根与指标入门,高次剩余,Miller_Robin+Pol...

题面 一根长为 n 的无色纸条，每个位置依次编号为 1,2,3,…,n ，m 次操作，第 i 次操作把纸条的一段区间 [l,r] （l <= r , l,r ∈ {1,2,3,…,n}）涂成颜色 i ，最后一定要把纸条涂满颜色，问最终的纸条有多少种可...

今天跟 hym 打球时讲到了这个东西，突然发现证明拉格朗日定理的思想有许多跟轨道-稳定集定理很像，所以这里又记录一下。 为了证明 Lagrange 定理，我们需要了解一些关于子群和陪集的性质。 首先给定一个群 \(G\)...

预备 0.1 渐进符号 其实不少高等数学 / 数学分析教材在讲解无穷小的比较时已经相当严谨地介绍过大 O、小 O 记号，然而各种历史习惯记法的符号滥用（abuse of notation）[1] 直到现在都让笔者头疼. These notati...

目录 什么是Lucas定理 证明Lucas定理 Lucas定理求解组合数的C++实现 什么是Lucas定理 这是一个有助于分解组合数来求解的定理，适合模数小，数字大的问题。 有质数 \(p\)，对于\(n,m\)，如果\(n=k_1p+b_1,m=k_2p+b...

约定 \(A\perp B\) 表示 \(\gcd(A,B)=1\)。 \(A\mid B\) 表示 \(B\equiv 0\pmod{A}(A\neq0)\)。 引入 考虑以下这道题： 有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。 問物幾何？—— 《孫子算經》 ...

初等数论 素数定义 设整数 \(p\ne 0,\pm 1\) 。如果 \(p\) 除了平凡约数以外没有其他约数，那么称 \(p\) 为素数（不可约数）。 若整数 \(a\ne 0,\pm 1\) 且 \(a\) 不是素数，则称 \(a\) 为合数。 ——————OI Wiki ...