第五节 数学简单问题

  竞赛中的很多题目会考到数学相关的知识，在这一节，我们会挑出一些简单的问题集中讲解。

最大公约数/最小公倍数

  首先我们要介绍一个算法，欧几里德算法。欧几里得是著名的古希腊数学家，被称为“几何学之父”，代表作为《几何原本》。

  欧几里得算法又称辗转相除算法，定理如下：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。（最大公约数缩写为gcd）在这里就不作证明了，直接给出代码：

1
2
3
4
5
6
7
8
9
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;
}

判断素数

  什么是素数呢？素数是大于等于2的，只有1和他本身能够整除他的数。要去判断一个数n是否是素数，只要从2到sqrt(n)依次判断即可，代码如下：

1
2
3
4
5
6
7
int su(int b)
{
    for(int i=2;i<=(int)sqrt(b);i++) {
        if(b%i==0) return 0;
    }
    return 1;
}

排列组合打表

1
2
3
4
5
6
7
8
9
10
int c[N][N];
void com() {
	memset(c,0,sizeof(c));
	for(int i=1;i<N;i++) {
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;j++) {
			c[i][j]=c[i-1][j]+c[i-1][j-1];
		}
	}
}

快速幂

  求a的b次幂，我们可以直接使用for循环去做。但是当b很大的时候，就会花费很多时间，这时候需要使用快速幂算法。

  下面我们就以求a^11为例，介绍一下快速幂算法。

  1. 将11转化为二进制——1011
  2. 分解：11=1*2^3+0*2^2+1*2^1+1*2^0
  3. 将a^11转化为a^(2^3)*a^(2^1)*a^(2^0)

  代码如下：

1
2
3
4
5
6
7
8
9
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;
}

快速幂取模

  公式：a*b%c=((a%c)*b)%c  (a+b)%c=(a%c+b%c)%c

1
2
3
4
5
6
7
8
9
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;
}

十进制转换为x进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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=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)