长白崎の个人博客

模运算 模运算，就是取余数，在计算机语言中%来表示。举个简单例子，3%5=3。结果的取值在0与模之间，例如res=X mod Y,那么res的取值范围应该是[0,Y-1]。结果也可以用负数来表示，3%5=-2。一般用正数的表现形式，如果出现负数，我们也该知道是怎么来的。 运算规律 模运算中同样有一些数学公式大家需要记住，基本跟四则运算比较相似。乘法大家需要注意下。 (A+B)%M=(A%M+B%M)%M(A+B)\%M =...

费马小定理 说明： 费马小定理是数论中的一个重要定理，它描述了质数的一种性质。费马小定理由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−p1​1​)×(1−p2​1​)×…×(1−pk​1​)其中，n可以分解为素数因子的乘积：n=p1a1×p2a2×…×pkakn = p_1^{a_1} \times p_2^{a_2} \times \ldots \times...

约数 试除法找约数 说明： 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...

前缀和

均值不等式 （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} >=...

常见方法有： 试除法： 朴素筛法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[] = ...

逆元 ≡符号的意思 在数学中，符号≡表示模同余的关系。当我们写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的逆元的情况下 %...

互质 什么是互质： 互质是公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。 在考虑两个区间互质的情况之前我们先考虑它的一个子问题，一个数x与一个区间[l,r]的互质问题。 处理这个问题，最简单的方法肯定是遍历区间，复杂度为O(n)，n为区间长度，显然太慢。 这时我们可以逆向思维，转换问题，我们可以考虑求不互质的个数，然后再用全部个数减去不互质的个数。 不互质也就是说，有公共的因子，如果把问题转换成求同有某个因子的数量，那就好处理， 比如如果计算都有因子2，设区间为[l,r]，那我们只要计算1~r的个数减去1~l-1的个数，也非常好算，只要r/2-(l-1)/2...

算法题型分析 DFS算法： 数据类模拟类算法题 地图模拟类算法题