长白崎の个人博客

线段树 说明： 线段树模板 推荐视屏： 【喵的算法课】线段树 数据结构【6期】_哔哩哔哩_bilibili 推荐文章： 《算法竞赛》上册 罗勇军...

...

分解质因数 定义： 若一个正整数无法被除了 1 和它自身之外的任何自然数整除，则称该数为质数（或者素数），否则称该自然数为合数。 说明： 分解质因数的主要作用就是将数字分解成多个质数因数，这些因数相乘等于这个数。 推荐文章： (158条消息) 分解质因数_质因数分解_晴空๓的博客-CSDN博客 ACM——常见的几种分解质因子的方法 - 知乎 (zhihu.com) 题目推荐 4658. 质因数个数 - AcWing题库 Java代码模板： 123456789101112131415161718192021222324252627282930313233343536/** * @description: 分解质因数 * @author 长白崎 * @date 2023/5/6 10:33 * @version 1.0 */public class 分解质因数 { public static void main(String[] args) { //测试条例，可以忽略 System.out.println(slove(10)); ...

判断是否为素数（质数） 说明： 质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。(0，1不是素数) Java代码模板(试除法，时间复杂度为O(n)O(\sqrt{n})O(n​)) 1234567891011121314151617181920212223242526272829/** * @description: 质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 * @author 长白崎 * @date 2023/3/30 12:29 * @version 1.0 */public class PrimeNumber { public static void main(String[] args) { //测试集，这里是判断100是否为素数 System.out.println( primeNumber(100) ); } /** * 判断素数模板 * @param num 需要判断的数字 * @return...

并查集 介绍： 此算法主要是用于查找树中的一结点的根结点，通常会用作查找匹配两个节点的根节点是否是同一个。 Java代码模板： 1234567891011121314151617181920212223242526272829303132333435363738/** * @description: TODO * @author 长白崎 * @date 2023/3/25 16:34 * @version 1.0 *//** * 并查集主要作用就是搜索两棵树的父节点是否是同一个节点。 */public class Main { public static void main(String[] args) { //并查集中用于记录每个结点的父节点的数组，数组下标代表的就是对应节点，对应下标数组元素的内容代表的是其父结点。 int parent[] = new int[100]; //这一步是必不可少的，这一步是为了初始化并查集的数组，初始状态下每个结点的父结点就是他本身。 for(int i =0 ;...

日期合格及平年闰年判断 说明： 主要用于判断日期是否合格以及判断日期是否为平年或闰年 Java代码模板： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182import java.time.LocalDate;import java.time.LocalDateTime;public class DateJudge { public static void main(String[] args) { } /** * 常规判断输入的日期是否合格 * @param year * @param month * @param day * @param hour * @param minute * @param seconds * @return...

最大公约数 说明： 计算最大公约数,这里只展示通过递归实现。 其方法使用的是数学上的==辗转相除法== gcd相关的概念还有裴蜀定理 ，即任意两个数的组合必定是他们gcd的倍数。同样可以推广到更多数：如果这些数的gcd是d，那么他们的组合是d的倍数，如果d不是1，那么必然有无限个数无法被组合出来。 Java代码模板： 1234567891011121314151617181920212223242526272829303132333435363738import java.math.BigInteger;/** * @description: 求最大公约数 * @author 长白崎 * @date 2023/3/30 12:33 * @version 1.0 */public class GCD { public static void main(String[] args) { //测试集 System.out.println(gcd(24,60)); ...

树状数组 说明： 核心点：lowbit()函数 该函数是用来求二进制数（从右往左数）第一个1以及后面的0组成的值。 例如：lowbit(10100)=100。（都是二进制数） lowbit(x)=x&(-x),x为二进制数。 （对于一个二进制数x，-x相当于按位取反再加1，即求其补码。&就是将其补码的x按位做与运算。） 讲解视屏： 五分钟丝滑动画讲解 | 树状数组_哔哩哔哩_bilibili 相应文章： 树状数组详解 - Xenny - 博客园 (cnblogs.com) 《算法竞赛》上册 罗勇军 第160页 题目推荐： 敌兵布阵 - HDU 1166 - Virtual Judge (vjudge.net) Java代码模板： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081import...

求最小公倍数 说明： 求最小公倍数可以在求最大公因数的基础上进行，这样就可以极大提高效率,这里需要明白一个点： a×bgcd(a,b)\frac{a\times b}{gcd(a,b)} gcd(a,b)a×b​ 上面公式中gcd指的是求最大公因数，意思就是说a与b的最小公倍数就是a和b相乘再除以他们两的最大公因数。 Java模板： 1234567891011121314151617181920212223242526272829303132333435/** * @description: 求最小公倍数 * 这里的最小公倍数做了比较大优化(时间复杂度大大降低)，是通过最小公因数来求最小公倍数 * @author 长白崎 * @date 2023/4/5 21:00 * @version 1.0 */public class LCD { public static void main(String[] args) { //测试实例 System.out.println(lcd(3,4)); } /** *...