程序模板

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
#include<cstring>
using namespace std;



int main()
{
    
    return 0;
}

数学模板

公约数、公倍数

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

素数

1
2
3
4
5
6
7
int prime(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];
		}
	}
}

快速幂

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;
}

快速幂取模

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;
}

十进制转换其他进制

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;
}

常用数学公式

1
2
3
4
5
6
7
8
等差数列求和公式：

Sn=n*a1+n(n-1)d/2
Sn=n(a1+an)/2

等比数列求和公式：

Sn=a1(1-q^n)/(1-q)

常用函数

1
2
sort（起始地址，终点地址，比较方法）；
lower_bound（起始地址，终点地址，查找元素）；