常用算法模板总结(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)

可以去博客园看一下这篇比较详细的博客,搬运一下。

看到这里,感谢观看,写了这么久,点个赞吧,嘿嘿嘿,下次见。

上一篇:蓝桥杯 既约分数


下一篇:G. GCD Festival(莫比乌斯反演)