力扣笔记
内容提要
本文总结了C++编程中常用的数学算法模板，包括最大公约数、最小公倍数、素数判断、排列组合打表、快速幂及取模、进制转换，并列出等差数列和等比数列求和公式及sort、lower_bound等常用函数，为编程竞赛提供基础工具。
延伸解读
模板的适用场景
这些模板主要面向编程竞赛和算法练习，覆盖了数论和组合数学中的基础操作。gcd、lcm、素数判断、快速幂等是解决许多问题的基石，而排列组合打表则适用于需要频繁查询组合数的场景。掌握这些模板能提高编码效率，但需注意它们通常针对整数运算，且未处理大数溢出等问题。
实现细节与潜在风险
素数判断函数使用sqrt(b)作为循环上限，但未包含头文件<cmath>，实际使用时需补充。快速幂取模中的p未定义，需在全局或调用前声明。排列组合打表使用二维数组c[N][N]，N需预先定义且注意内存占用。这些细节若不注意，可能导致编译错误或运行时问题。
常用函数的注意事项
sort和lower_bound是C++标准库中的常用函数，但使用时需包含<algorithm>头文件。sort默认升序，可通过自定义比较函数实现降序等；lower_bound要求序列有序，返回第一个不小于目标值的迭代器。理解这些函数的参数和返回值，能避免边界错误。
Q&A
C++中如何实现最大公约数（GCD）的计算？
可以使用递归函数：int gcd(int a, int b) { if(b==0) return a; else return gcd(b, a%b); }
最小公倍数（LCM）的公式是什么？
最小公倍数 = a / gcd(a,b) * b，即先除以最大公约数再乘以另一个数。
如何判断一个数是否为素数？
从2到sqrt(b)遍历，若存在能整除b的数则不是素数，否则是素数。代码：int prime(int b) { for(int i=2; i<=(int)sqrt(b); i++) if(b%i==0) return 0; return 1; }
排列组合打表的递推公式是什么？
使用杨辉三角递推：c[i][j] = c[i-1][j] + c[i-1][j-1]，边界为c[i][0]=c[i][i]=1。
快速幂算法的原理和实现是什么？
快速幂利用二进制分解指数，将幂运算复杂度降为O(log 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; }
十进制数如何转换为其他进制？
使用短除法，将余数转换为对应字符（0-9，A-Z），最后反转字符串。代码：string trans(int num, int base) { string str; while(num>0) { if(num%base<10) str+=num%base+'0'; else str+=num%base-10+'A'; num/=base; } reverse(str.begin(), str.end()); return str; }
等差数列和等比数列的求和公式是什么？
等差数列：Sn = n*a1 + n(n-1)d/2 或 Sn = n(a1+an)/2；等比数列：Sn = a1(1-q^n)/(1-q)。
C++中sort和lower_bound函数的基本用法是什么？
sort(起始地址, 终点地址, 比较方法)；lower_bound(起始地址, 终点地址, 查找元素)。
