ACM C++基础算法模板

打表:质数

typedef unsigned long long ull;
void prime(long long max,long long min=2){
	if (max<2 || min>max) return;
	//cout<<"2	3	5	7	11";
	for (ull i=min; i<=max; i+=2){
	//只有奇数才可能是质数
		ull ii=(ull)sqrt(i);
		//注意sqrt()返回值为浮点型,必须强制转换
		for (ull j=3; j<=ii; j+=2){
		//遍历所有的奇数(此处可以开一个存之前所有质数的数组,来优化次数)
			if (i%j==0) goto next;
			//goto有时很好用
		}
		cout<<i<<'	';
		next:;
	}
}

打表:所有排列

https://blog.csdn.net/Cow_cz/article/details/84305205

void arrange(int a[],int s,int e){
	if (s==e) {
		for (int i=1; i<=e; i++) cout<<a[i]<<" ";
		cout<<"\n";
	}
	for (int i=s; i<=e; i++){
		swap(a[s],a[i]);
		arrange(s+1,e);//for循环配合递归以实现排列,建议使用<vector>更加高效
		swap(a[s],a[i]);//回溯,即复原
	}
}

数学:求最大公因数

ull GCD(ull a,ull b){
	if (a>b) swap(a,b);
	b=b%a;
	if (b==0) return a;//能整除,被除数就是最大公因数
	else return b;//否则余数是最大公因数
	//这种写法节省中间临时变量
}
void t1(){
	ull a,b=0;
	cout<<"1.求最大公因数,请直接输入所有数据,要结束请按Ctrl+Z输入EOF特殊符号并回车!\n";
	cin>>a;
	while (cin>>b) a=GCD(a,b);//while(cin>>...)
	//快速幂的数学原理:a%b=(a%b)%b
	cout<<"最大公因数:"<<a<<"\n";
}
上一篇:[Python学习笔记-012]古巴比伦人的乘法表


下一篇:使用redis对 ip实现限流