设计模式
设计模式
一、设计模式简介
设计模式（Design pattern）代表了最佳的实践，通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。
设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了重用代码、让代码更容易被他人理解、保证代码可靠性。 毫无疑问，设计模式于己于他人于系统都是多赢的，设计模式使代码编制真正工程化，设计模式是软件工程的基石，如同大厦的一块块砖石一样。项目中合理地运用设计模式可以完美地解决很多问题，每种模式在现实中都有相应的原理来与之对应，每种模式都描述了一个在我们周围不断重复发生的问题，以及该问题的核心解决方案，这也是设计模式能被广泛应用的原因。
二、什么是 GOF（四人帮，全拼 Gang of Four）？
在 1994 年，由 Erich Gamma、Richard Helm、Ralph Johnson 和 John Vlissides 四人合著出版了一本名为 Design Patte ...
费马小定理
费马小定理
说明：
费马小定理是数论中的一个重要定理，它描述了质数的一种性质。费马小定理由17世纪法国数学家皮埃尔·德·费马提出，是他在给予数论的贡献之一。
费马小定理陈述如下：
如果p是一个质数，而a是一个不是p的倍数的整数，则ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp)
其中，a是任意整数，p是一个质数。
简单来说，费马小定理表明，如果我们有一个质数p，那么对于任意不是p的倍数的整数a，a的p-1次幂除以p的余数等于1。这意味着在模p下，a的p-1次幂与1同余。
费马小定理的推论包括：
在模p下，如果a不是p的倍数，则ap≡a(modp)a^p \equiv a \pmod{p}ap≡a(modp)。
在模p下，如果a不是p的倍数，则ap−2≡1a(modp)a^{p-2} \equiv \frac{1}{a} \pmod{p}ap−2≡a1(modp)，这说明了求模质数的逆元的一种方法。
费马小定理在密码学、计算机科学和数学中有广泛的应用，特别是在素数测试和建立加密算法的安全性证明方面。
欧拉函数
欧拉函数
1 欧拉函数的定义
欧拉函数（Euler’s totient function），通常记为φ(n)，是一个与正整数n相关的数论函数。它表示小于或等于n的正整数中与n互质的数的个数。互质的意思是这些数的最大公约数（最大公因数）为1。
欧拉函数的计算公式是φ(n)=n×(1−1p1)×(1−1p2)×…×(1−1pk)φ(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \ldots \times \left(1 - \frac{1}{p_k}\right)φ(n)=n×(1−p11)×(1−p21)×…×(1−pk1)其中，n可以分解为素数因子的乘积：n=p1a1×p2a2×…×pkakn = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}n=p1a1×p2a2×…×pkak其中，p1、p2、…、pk是不同的素数，a1、a2、…、ak是它们的幂次。
举个例 ...
约数
约数
试除法找约数
说明：
Java代码模板（统计有多少个约数）：
12345678910static long solve(int a) { long ans = 0; for(int i = 1;i<=Math.sqrt(a);++i) { if(a%i==0) { ++ans; if(a/i!=i) ++ans; } } return ans;}
Java代码模板（统计质约数的个数）：
12345678910111213141516171819202122232425262728293031323334import java.util.Scanner;/** * https://www.acwing.com/problem/content/4661/ * @author 长白崎 * @class["质因数", "数论"] * */public class Main { public static void main(String[] args) { // TODO Auto-generated method stub ...
前缀和
前缀和
均值不等式
均值不等式
（1）对实数a,b有a2+b2>=2ab(当且仅当a=b时取“=”号)，a2+b2>=−2ab(当且仅当a=−b时取“=”号)a^2+b^2>=2ab(当且仅当a=b时取“=”号)，a^2+b^2>=-2ab(当且仅当a=-b时取“=”号)a2+b2>=2ab(当且仅当a=b时取“=”号)，a2+b2>=−2ab(当且仅当a=−b时取“=”号)
（2）对于非负实数a,b,有$a+b>=2\sqrt{ab},即{a+b \over 2}>=\sqrt{ab} $
（3）对非负实数a,b有a(a−b)>=2ab>=0a(a-b)>=2 \sqrt{ab} >= 0a(a−b)>=2ab>=0
（4）对实数a,b有a(a−b)>=b(a−b)a(a-b)>=b(a-b)a(a−b)>=b(a−b)
（5）对非负实数a,b,有a2+b2>=2ab>=0a^2+b^2>=2ab>=0a2+b2>=2ab>=0
（6）对非负实数a,b,有a2+b2 ...
质数筛选
常见方法有：
试除法：
朴素筛法O(nlogn)O(nlogn)O(nlogn)：
埃氏筛法O(nloglogn)O(nloglogn)O(nloglogn)：
线性筛法O(n)O(n)O(n)：
Java代码模板(朴素筛时间复杂度O(nlogn)O(nlogn)O(nlogn)
12345678910111213141516171819202122232425262728293031323334import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(primes(n)); } /** * 朴素筛法 */ static int primes(int n) { boolean st[] = new bo ...
逆元
逆元
≡符号的意思
在数学中，符号≡表示模同余的关系。当我们写a≡b(modm)a \equiv b \pmod{m}a≡b(modm)时，意思是a与b在模m下同余，也就是说它们除以m后得到相同的余数。换句话说，a和b的差是m的倍数。例如，17≡3(mod7)17 \equiv 3 \pmod{7}17≡3(mod7)表示17和3在模7下同余，因为它们相减得到的结果是7的倍数，即17−3=14=2×717 - 3 = 14 = 2 \times 717−3=14=2×7。
逆元的本质：
逆元的定义： 假设 a 除
b，且a和b都是整数，非浮点数，那么我们希望不做除法，因为取余数的话除法很麻烦，所以我们希望把除法变成乘法，希望找到一个数，使得a/b的余数 == ax%m。 即对于某一个b，我们能够找到一个数x，使得a/b和ax模m的余数相同的话， 则把x记作b的模m的逆元，记作b的-1次方； 即b的逆元， b的-1次方，是一个整数，是一个标记。即我们可以把所有a/b的情况转化为a*b的逆元的情况下 % M；即把除法变成了整数。
C++模板：
12345678910111213 ...
互质
互质
什么是互质：
互质是公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。
在考虑两个区间互质的情况之前我们先考虑它的一个子问题，一个数x与一个区间[l,r]的互质问题。
处理这个问题，最简单的方法肯定是遍历区间，复杂度为O(n)，n为区间长度，显然太慢。
这时我们可以逆向思维，转换问题，我们可以考虑求不互质的个数，然后再用全部个数减去不互质的个数。
不互质也就是说，有公共的因子，如果把问题转换成求同有某个因子的数量，那就好处理， 比如如果计算都有因子2，设区间为[l,r]，那我们只要计算1~r的个数减去1~l-1的个数，也非常好算，只要r/2-(l-1)/2 就可以计算出区间[l,r]中有因子2的数字的数量(这里的除法若无特殊说明都为整数除法，即向下取整)。
这样我们就可以把数x进行因数分解，然后对每一个因数去计算区间中有几个数同时有这个因数，累加到sum[i](i为当前这个因数中有几个质因子)，这样我们就把区间中的数分类到了，几个集合中，数sun[i]，就表示区间中与x共有i个质因子的数的数量，当然这些集合并不是区间的一个 ...
算法题型分析
算法题型分析
DFS算法：
数据类模拟类算法题
地图模拟类算法题
