数学是编程中永远绕不开的一个点,而在一些算法竞赛(蓝桥杯、NOIP等)中,数学问题还出现的蛮多的,这篇文章谈一谈如下几个点:

  • 整除及取余
  • 最大公约数与最小公倍数
  • 质数与筛法

整除:

整除性:如果a能把b整除,没有余数,称a整除b,亦称b被a整除,记为a|b。
性质:对于任意的n,有n|n
如果a|b、b|c 可推出 a|c
a|b、b|a 可推出 a==b

约数与倍数:a|b,a为b的约数,b是a的倍数,称a为b的因子,有个小结论:任何数n至少有两个因子,1和n本身,将他们称为n的平凡因子(平凡意味着很普遍嘛)

有个小问题可以思考一下:

求[1,n]中每个数的约数个数,n的每个约数d(n),给出一个O(nlogn)的算法:

(思考一下再往下看?)

这个地方我们可以转换成倍数来搞,暴力枚举:将1到n中1的倍数全部标记一遍、再将1到n中2的倍数全部标记一遍,最后看每个数标记了多少次就知道有多少个约数啦。

复杂度分析:用1标记时,每个数都要标记,O(n)的复杂度;用2标记时,一半的数要标记,O(n/2)的复杂度......
最终的复杂度就是n+n/2+n/3+...=n(1+1/2+1/3...) 后面的括号里面的内容称为调和级数,求和为logn,所以时间复杂度就是O(nlogn)了。

想一想代码怎么写?

#include<iostream>
using namespace std;

int main()
{
	int a[105] = {0};
	int n = 100;
	for(int i = 1 ; i <= n ; ++i)   //打标记
	{
		for(int j = 1 ; j * i <= n ; ++j)
			a[i*j]++;
	}
	
	for(int i = 1 ; i <= 10 ; ++i)   //输出每个数被标记了多少次
	{
		cout<<"a["<<i<<"]"<<" = "<<a[i]<<endl;
	}
	return 0;
 } 

质数:

质数:质数是不存在非平凡因子的个数,如果一个数的因子要出现,肯定是成对吹出现的,这个应该不需要证明,例如,n = a * b,一个肯定小于等于sqrt(n),一个大于等于sqrt(n),所有如果要枚举判断质数,只需要O(sqrt(n))的算就可以判断质数。

1既不是质数也不是合数,这个关系到整个数论这个体系成不成立,是公认的,不做证明。。。

质数有无限个,如何证明?(可以先别往下滑,思考一下,这个证明太厉害了)

我开始了...

首先要用到反证法:假设质数有限

假设有一个M,M=p1*p2*...*pn + 1 (p在这里是质数,且有限,最多是pn),那么M%p1 == 1 , M%p2 == 1,继续往下M%pn == 1,这个就可以直接推出M是质数了,M比p中所有的数都要大(显然),与假设矛盾,所以质数无限

求质数:朴素办法是用循环枚举,复杂度为O(n*sqrt(n))
筛法:先筛掉2的倍数,再筛掉3的倍数,直到n的倍数,最后留下来的数就是质数了,像想一想代码怎么写:

#include<iostream>
using namespace std;

int main()
{
	int a[105] = {0} , n = 100;
	for(int i = 2 ; i <= n ; ++i)
	{
		if(a[i] == 0)
		{

		    cout<<i<<" ";
		    for(int j = 2 ; i*j <= n ; ++j)  //筛选
			a[i*j] = 1;
		}
	}
	return 0;
 } 

质因数分解:

质因数分解:每个数都可以拆成质数乘积的方式,这个过程叫做质因数分解
eg. 5 = 5 = pow(5,1) //表示5的一次方
15 = 3 * 5 = pow(3,1) * pow(5,1)
36 = 2*2*3*3 = pow(2,2) * pow(3,2)

有一个思考题:给定一个质因数的分解形式,如何求d(n) (不记得d(n)是啥的往上翻)。这个题可以在评论区留言讨论,,好吧,估计也没人看。

模:

除法表示:a = 1/p * p + a%p (1/p是C语言中的表示,因为下取整的那个符号我不会打..)

模的性质:a%p一定落在[0,p-1]之间 (显然)
随时取模性质:在只含加法和乘法的式子中,如果左后的运算结果需要对p取模, 则可以在运算过程中随便取模,只需最后把结果再对p取模,答案就是正确的

随时取模性质可以防止在计算过程中爆int,爆long int。

大名鼎鼎的GCD与LCM

gcd(a,b)=d , a,b的最大公因数 条件:d|a , d|b && d要最大
lcm(a,b) = d , a,b的最小公倍数

eg. gcd(40,60) = 20 gcd(30,80) = 10
gcd(33,7) = 1 if(gcd(a,p) = 1) , 则a和p互质

有个思考问题:把A分解成了pow(2,a1)*pow(3,a2)*pow(5,a3)
把B分解成了pow(2,b1)*pow(3,b2)*pow(5,b3)
快速求d = gcd(A,B),仅作思考,不要求,因为求gcd一般都用辗转相除

GCD递归定理,gcd(a,b) = gcd(b,a%b),在求gcd时,用递归比用循环迭代好看很多

#include<iostream>
using namespace std;

int gcd(int a , int b)
{
	if(b == 0)
		return a;
	return gcd(b , a%b);
}

int main()
{
	int a = 7 , b = 28;
	cout<<gcd(a,b)<<endl;
	return 0;
 } 

最后一点,再计算lcm时,lcm=a*b/gcd(a,b),易爆int,可以改成lcm = a/gcd(a,b) * b


立志做一名攻城狮