Deep_Dark_FAntasy♂

基本数论、组合...

Codeforces(3) 博弈论(3) 并查集(2) 数据结构(2) 未归档(176) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 基本数论、组合数学（排列组合，容斥等）（共14篇）

(大数判断素性)Miller-Rabin素数测试算法

作用：有时候我们想快速的知道一个数是不是素数，而这个数又特别的大导致 O( √n) 的算法不能通过，这时候我们可以对其进行 Miller-Rabin 素数测试，可以大概率测出其是否为素数。两个定理：费马小定理：如果p是素数，a是小于p的正整数，那么a^(p-1) mod p = 1。证明：首先我们...

Miller_Rabin素性测试大数素性判断

2020-06-29

0 4697

最大公约数(lcm)

先看题目：https://ac.nowcoder.com/acm/problem/16710解题思路：公式lcm(a,b) = ab / gcd(a,b)记得要先a/gcd(a,b)然后再乘b以防止越界*代码：** #include<bits/stdc++.h> using namesp...

lcm

2020-06-26

0 438

同余方程

先看题目：https://ac.nowcoder.com/acm/problem/16563解题思路：exgcd模板题，求ax≡1(mod b)，可以写为方程的形式 ax = yb + 1, 即 ax - by = 1，这个符号可以塞到y里，令k=-y，就还是二元线性方程的形式了 —— ax + b...

exgcd 同余方程二元线性方程

2020-06-26

1 625

大水题

先看题目：https://ac.nowcoder.com/acm/problem/15079解题思路：题目要求的是不是2，5，11，13的倍数，我们可以考虑是2，5，11，13的倍数有多少个，即求|2的倍数 U 5的倍数 U 11的倍数 U 13的倍数|，如果把它们直接加起来，发现会有一些元素重复统...

容斥原理

2020-06-25

0 520