何事秋。

数论基本算法

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / 数论基本算法（共64篇）

质数（素数）、约数

一、质数：若一个正整数无法被除了1和它自身之外的任何自然数整除，则称该数为质数（或素数），否则称该正整数为合数。 1不是素数，2是最小的素数。在整个自然数集合中，质数的数量不多，分布比较稀疏，对于一个最够大的整数 N，不超过 N 的质数大约有 ...

2020-09-04

0 928

欧拉函数

一、互质：若gcd(a,b)=1,则称a,b互质。若gcd(a,b,c)=1,则称a,b,c互质。若gcd(a,b)=gcd(a,c)=gcd(b,c)=1,则称a,b,c两两互质。二、欧拉函数： 1。1–N中与N互质的数的个数被成为欧拉函数。记为 ...

2020-09-04

0 390

欧几里得、扩展欧几里得、同余

一、同余： 1。若整数a和整数b除以正整数m的余数相等，则称a，b模m同余，记作a≡b（mod m）。 2。费马小定理：若p是质数，则对于任意整数a，有ap ≡a（mod p）。 3。欧拉定理：若正整数a，n互质，则 aφ(n)≡1(mod n) ,其中φ(n)是欧拉函数。 4。若正整数a，n...

2020-09-04

0 565

快速幂、矩阵快速幂

一、快速幂： ll mypow(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } re...

2020-09-04

0 426

Miller-Rabin测试

一、贴代码： #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cstdlib&...

2020-09-04

0 468

求组合数

一、不取模直接运算。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #define ll long l...

2020-09-04

0 431

莫比乌斯函数：

一、线性筛 const int maxn=1000006; int prime[maxn]; bool ha[maxn]; int mu[maxn]; int cnt=0; void Mu(void) { mu[1]=1; ha[1]=true; for(int i=2;...

2020-09-04

0 452

中国剩余定理：

一、标版：题目描述现有两组数字，每组k个，第一组中的数字分别为：a1，a2，…，ak表示，第二组中的数字分别用b1，b2，…，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n - ai能被bi整除。输入输出格式输入格式：输入数据的第一行是一个整数k，（1...

2020-09-04

0 343

高次同余方程：

一、算法进阶给的板子： int bsgs(int a,int b,int p) { map<int,int>_hash; _hash.clear(); b%=p; int t=(int) sqrt(p)+1; for(int j=0;j...

2020-09-04

0 528

容斥原理：

一、多重集的组合数： #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<cmath> #include<string...

2020-09-04

0 600