『算法-ACM 竞赛-数学-数论』容斥定理完全解析（转）数学–数论–容斥定理完全解析（转）对容斥原理的描述容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。 描述容斥原理可以描述如下： 要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所

『算法-ACM 竞赛-数学-数论』因子和线性筛 （模板)ACM 常用模板合集1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <bits/stdc++.h>using namespace std;typedef long long ll;#define N 50

『算法-ACM 竞赛-数学-数论』四大定理之威尔逊定理威尔逊定理当 $(p−1)!≡−1(modp)$时，$p$为素数。$p∣(p−1)!+1$即$(p−1)!≡(p−1)≡−1(mod p)$证明（静下心看）：充分性：$(p−1)!≡−1(modp)⟺p∣(p−1)!+1$假设$p$ 不是质数，且 $a$是 $p$ 的质因子。易知$a∣(p−1)!$，则$a∤(p−1)!+1$而$p∣(p−1)

『算法-ACM 竞赛-数学-数论』同余及其性质（超详细）定义：$给定一个正整数m，及两个整数a、b。\如果a-b被m整除，则称a与b模m同余，记作a≡b(mod m) \否则称a与b模m不同余，记作a≢ b(mod m)。$ 性质： $a,b模m同余\Leftrightarrow a=b+Km \quad k为任意整数$ 自反性：$a≡a（mod \quad m)$对称性：$a≡b

『算法-ACM 竞赛-数学-数论』原根(循环群生成元）突然今天，我想不起什么是原根来了，查了一下定义，哎~这货不是离散数学，循环群生成元吗？？不是$<a_+>而是<a_*>是乘法而不是加法$嘛玩意是原根：? 对于素数 p，如果存在一个正整数 1<a<p，使得 a1,a2,…,ap−1 模 p 的值取遍 1,2,…,p−1 的所有整数，称 a 是 p 的一个原根（

『算法-ACM 竞赛-数学-数论』剩余系 与 完全剩余系 与 简化剩余系剩余系：由关于模 m 同余的数的集合，每一个集合叫做关于模 mmm 同余的剩余系 比如模 5 剩余系:$<Mod_5=0>$：0，5，10，15…$<Mod_5=1>$：1，6，7，16…$……$ 完全剩余系：从模 m 的每个剩余系中各取一个数得到 m 的数，叫做模 m 的一个完全剩

『算法-ACM 竞赛-数学-数论』二次探测定理定理$若p为质数,x2≡1(modp),则x≡1(modp)或x≡p−1(modp)$证明:$移项可得:x2−1≡0(modp),也就是(x+1)(x−1)≡0(modp).$ $这个式子等价于p|(x+1)(x−1).$ $容易想到p|(x+1)或者p|(x−1)都是可行的,那么有没有p∤(x−1),p∤(x+1),而p|(x−1)(x+1)呢?$

『算法-ACM 竞赛-数学-数论』中国剩余定理模板ACM 常用模板合集12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849void exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1; y

『算法-ACM 竞赛-数学-数论』中国剩余定理+扩展中国剩余定理（孙子定理）中国剩余定理问题求解同余方程组其中$m_1,m_2,m_3…m_k$为两两互质的整数求 x 的最小非负整数解 定理令$M=\prod_{i=1}^km_i$，即 M 是所有 $m_i$的最小公倍数$t_i$为同余方程 $M_t/m_i ≡ 1(mod\ m_i )$的最小非负整数解则有一个解为

『算法-ACM 竞赛-数学-数论』中国剩余定理 拓展 HDU 1788再次进行中国余数定理 问题描述我知道部分同学最近在看中国剩余定理，就这个定理本身，还是比较简单的：假设 m1，m2，…，mk 两两互素，则下面同余方程组：x≡a1（mod m1）x≡ a2（mod m2）…x≡ak（mod mk）在 0 <= <m1m2 … mk 内有唯一解。记 Mi = M &