常用算法模板总结（1）----快速，最大公约数，最小公倍数，求一个数的所有因数之和，素数判断
1.快速幂模板。
快速幂的模板大家应该是不陌生的，之前我一直是直接记模板的，今天来具体解释一下快速幂模板的意义。
不取模的模板如下：（取模自己修改一下）
ll fp(ll a,ll b){
ll ans=1;
ll base=a;
while(b!=0){
if(b&1!=0)
ans=ans*base;
base*=base;
b>>=1;
}
return ans;
} 如何理解该模板：
首先快速幂的基本思想是分治和二进制，我们直接带入一个例子更好理解，如计算2的11次方。
首先ans=1,base=2,b=11;我们知道11的二进制是1011；if(b&1!=0) ans=ans*base;这一个语句的作用是，根据幂的二进制来决定是否要乘入答案，base*=base;的作用是让基数翻倍；
拿2的11次方来说，①b=1011,ans=1,base=2 ②ans=1*2,base=2*2,b=101, ③ans=2*2*2，base=2*2*2*2，b=10 ④ans=2*2*2，base=2*2*2*2*2*2*2*2,b=1 ⑤ ans=2*2*2*2*2*2*2*2*2*2*2,b=0 ⑥跳出for循环，结束。
这么理解一下，快速幂的模板再也不用四级硬背了，信手拈来。
由上可见，达到了计算2的11次方的目的，最坏的复杂度也只为O(logn)，而暴力的复杂度是O(n),快速幂简直是完美情人！
2.求两个数的最大公约数模板
（1）经典欧几里得算法（辗转相除法）一般用这个就够了
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b,a%b);
}如何理解记忆：
写题最讨厌的就是找代码模板了，所以我们要做到让这些常用代码印在心中！
其实就是两个数反复换位相互求余，当b为0时，a即为最大公因数。
如计算8和12的最大公因数，gcd(8,12),gcd(12，8)，gcd(8,4),gcd(4,0)。
推导一遍就很容易记下。欧几里得算法依旧是复杂度为O（logn）的优秀算法。
（2）stein算法（如果不能A题，用这个改进一下）
针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。
ll gcd(ll u,ll v)
{
if (u == 0) return v;
if (v == 0) return u;
if (~u & 1)
{
if (v & 1)
return gcd(u >> 1, v);
else
return gcd(u >> 1, v >> 1) << 1;
}
if (~v & 1)
return gcd(u, v >> 1);
if (u > v)
return gcd((u - v) >> 1, v);
return gcd((v - u) >> 1, u);
}
直接贴代码，因为也不常用，没有去理解，用得上的机会比较少。
3.最小公倍数。
求两个数的最小公倍数算法是基于gcd算法的基础上的。
int lcm(int a,int b){
return a/gcd(a,b)*b;
}如何理解记忆：
这个还是比较简单的，就是用一个数去除以最大公因数得到的结果，再乘以另一个数，就可以得到这两个数的最小公倍数。
4.求一个数的所有因数之和。
（包括一，不包括本身）算法的解释都在代码里面了，比较好理解。
int factorSum(int n){
int sum=0;
for (int i=1;i*i<=n;i++){//折半除，降低复杂度
if (n%i==0){
if (i==1||i*i==n) sum+=i;//如果这个因数为1或者刚好是该数的平方根，只加一个就可以了。
else sum+=i+n/i;//加上该因数和该因数的关联因数。
}
}
return sum;
}
5.素数判断
（1）一般情况下，简单的判断素数代码。
bool is_prime(int n){
if(n<=1) return false;
for(int i=2;i*i<=n;i++)
if(n%i==0) return false;
return true;
}这个比较好理解，只要有除1以外的因数直接返回false，否则返回true
复杂度O(根号n)，这个模板的时间复杂度对于10的12次方以内的数的判断是没有问题的
（2）更快速的方法
这两个方法在数据不是很大时对比不明显，数据很大时可以体现出方法2的优越性。代码如下：
bool isPrime(int a) {
if(a == 1) return 0;
if(a == 2 || a == 3) return 1;
if(a%6 != 1 && a%6 != 5) return 0;
int sqrtA = sqrt(a);
for(int i = 5; i <= sqrtA; i += 6) {
if(!(a%i)|| !(a%(i+2))) return 0;
}
return 1;
}如何理解记忆：
这个的理解过程就比较长了。【素数的判定-从暴力到高效】-C++ - 摸鱼酱 - 博客园 (cnblogs.com)
可以去博客园看一下这篇比较详细的博客，搬运一下。
