崎径 其镜赵安琪的博客
·
力扣笔记
内容提要
本文介绍了多种常用的数学和编程模板，包括最大公约数、最小公倍数、素数判断、排列组合、快速幂运算和进制转换等算法和公式。
关键要点
-
最大公约数算法：使用递归方法计算两个数的最大公约数。
-
最小公倍数算法：通过最大公约数计算两个数的最小公倍数。
-
素数判断算法：通过循环判断一个数是否为素数。
-
排列组合算法：使用动态规划方法预计算组合数。
-
快速幂运算：通过位运算实现快速计算幂。
-
快速幂取模：在计算幂的同时进行取模操作。
-
进制转换算法：将十进制数转换为其他进制。
-
等差数列求和公式：Sn=n*a1+n(n-1)d/2 或 Sn=n(a1+an)/2。
-
等比数列求和公式：Sn=a1(1-q^n)/(1-q)。
延伸解读
算法应用场景
本文介绍的算法和公式在编程竞赛、数据分析和科学计算中具有广泛应用。例如，最大公约数和最小公倍数的计算在处理分数和比例问题时尤为重要，而素数判断则在密码学中扮演关键角色。了解这些算法的应用场景可以帮助读者在实际问题中选择合适的工具。
动态规划与组合数学
排列组合算法使用动态规划方法预计算组合数，这种方法在解决复杂问题时效率更高。动态规划的思想可以应用于许多其他问题，如最短路径和背包问题，掌握这一技巧将提升解决问题的能力。
快速幂运算的优势
快速幂运算通过位运算实现高效计算，尤其在处理大数时，能够显著减少计算时间。这在算法设计中非常重要，尤其是在需要频繁进行幂运算的场景，如图形处理和加密算法中。
延伸问答
如何计算两个数的最大公约数？
可以使用递归方法，通过函数gcd(int a, int b)来计算最大公约数。
最小公倍数是如何计算的？
最小公倍数可以通过最大公约数计算，使用公式lcm(int a, int b) = a/gcd(a,b)*b。
如何判断一个数是否为素数？
可以通过循环判断，使用函数prime(int b)来检查一个数是否为素数。
排列组合的动态规划方法是怎样的？
使用动态规划预计算组合数，具体实现可以参考com()函数。
快速幂运算的实现方式是什么？
快速幂运算可以通过位运算实现，使用函数Fast(int x, int n)进行计算。
如何将十进制数转换为其他进制？
可以使用trans(int num, int base)函数将十进制数转换为指定进制。
