崎径 其镜赵安琪的博客
·
力扣笔记
💡
原文中文，约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)
❓
延伸问答
如何计算两个数的最大公约数？
可以使用函数 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]，通过动态规划计算组合数，具体实现见函数 com()。
快速幂算法的实现是什么？
快速幂算法可以用 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; } 来实现。
如何将十进制数转换为其他进制？
可以使用函数 string trans(int num,int base) 来实现十进制到其他进制的转换。
➡️
