崎径其镜赵安琪的博客 ·

力扣笔记

Q: 排列组合的打表方法是怎样的？

使用二维数组 c[N][N]，通过动态规划计算组合数，具体实现见函数 com()。

Q: 快速幂算法的实现是什么？

快速幂算法可以用 int Fast(int x,int n) { int tem=x,ans=1; while(n) { if(n%2==1) ans*=tem; tem*=tem; n>>=1; } return ans; } 来实现。

💡 原文中文，约1300字，阅读约需4分钟。

📝

内容提要

本文介绍了常用的数学和编程模板，包括最大公约数和最小公倍数的计算、素数判断、排列组合的打表方法、快速幂算法及其取模实现，以及十进制转换为其他进制的函数。同时列出了等差数列和等比数列的求和公式。

🎯

关键要点

最大公约数的计算函数：int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); }
最小公倍数的计算函数：int lcm(int a,int b) { return a/gcd(a,b)*b; }
素数判断函数：int prime(int b) { for(int i=2;i<=(int)sqrt(b);i++) { if(b%i==0) return 0; } return 1; }
排列组合的打表方法：使用二维数组c[N][N]，通过动态规划计算组合数。
快速幂算法：int Fast(int x,int n) { int tem=x,ans=1; while(n) { if(n%2==1) ans*=tem; tem*=tem; n>>=1; } return ans; }
快速幂取模实现：int pow(int a,int x) { int ans=1,temp=a%p; while(x) { if(x&1) ans=((long long)ans*temp)%p; temp=((long long)temp*temp)%p; x>>=1; } return ans; }
十进制转换为其他进制的函数：string trans(int num,int base) { ... }
等差数列求和公式：Sn=n*a1+n(n-1)d/2 或 Sn=n(a1+an)/2
等比数列求和公式：Sn=a1(1-q^n)/(1-q)

🔎

延伸解读

数学模板的实用性

本文提供的数学和编程模板对于解决常见算法问题非常实用。最大公约数和最小公倍数的计算函数可以帮助开发者在处理数论问题时提高效率，尤其是在竞赛编程中。

快速幂算法的优势

快速幂算法在计算大数的幂时表现出色，尤其是在需要取模的情况下。它的时间复杂度为O(log n)，相比于传统的乘法方法，能够显著减少计算时间，适用于大规模数据处理。

排列组合的动态规划

使用动态规划计算排列组合的打表方法，可以有效减少重复计算，提高效率。这种方法在处理组合问题时尤为重要，尤其是在数据量较大时，能够显著提升程序的运行速度。

❓

延伸问答

如何计算两个数的最大公约数？

可以使用函数 int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } 来计算。

最小公倍数的计算公式是什么？

最小公倍数可以通过函数 int lcm(int a,int b) { return a/gcd(a,b)*b; } 计算。

如何判断一个数是否为素数？

可以使用函数 int prime(int b) { for(int i=2;i<=(int)sqrt(b);i++) { if(b%i==0) return 0; } return 1; } 来判断。

排列组合的打表方法是怎样的？