CSP集训笔记-Day 1
2026-08-11 13:49:35
发布于：天津
15阅读
0回复
0点赞
数论
#include<bits/stdc++.h>
using namespace std;
//最大公因数
//------------------------------
int x,y;
//枚举法，复杂度O(n)
/*
if(a%i==0&&b%x==0){
return i;
}
*/
//更相减损法
/*
a-=b;
if(a<b){
int t=a;
a=b;
b=t;
}
*/
//辗转短除法，复杂度o(log max(a,b))
int zzdc(int a,int b){
while(b!=0){
int t=a;
a=b;
b=t%b;
}
return a;
}
//辗转短除法2
int zzdc2(int a,int b){
if(b==0){
return a;
}
return zzdc2(b,a%b);
}
//最小公倍数
int zxgbs(int a,int b){
return a/zzdc2(a,b)*b;
}
//质因子分解
//------------------------------
int z;
//慢版||平均复杂度较快，但n为素数时复杂度O(n)
void zyz1(int c){
int x=2;
while(c!=1){
if(c%x==0){
c/=x;
cout<<x<<" ";
}
else{
x++;
}
}
}
//快版
void zyz2(int c){
for(int i=2;i*i<=c;i++){
while(c%i==0){
cout<<i<<" ";
c/=i;
}
}
if(c!=1){
cout<<c;
}
}
//埃氏筛，复杂度O(nlogn)，百万级数据以下最优解法
/*注意事项：
1.0和1要手动筛
2.数组长度必须>n
3.看i*i是否会爆int(i<=10^5)
*/
int n,a[100];
void aish(int n){
for(int i=2;i<=sqrt(n);i++){
if(a[i]==1)continue;
for(int j=i*i;j<=n;j+=i){
a[j]=1;
}
}
for(int i=1;i<=n;i++){
if(a[i]==1)continue;
cout<<i<<" ";
}
}
//线性筛，适用大数据（亿万级）
//特点：每一个合数只会被最小质因子筛一次
int b[100],p[100],idx=0;
void xianx(int n){
for(int i=2;i<=n;i++){//不是到根号n
if(b[i]==0)p[++idx]=i;
for(int j=1;j<=idx;j++){
if(i*p[j]>n)break;
b[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
for(int i=1;i<=idx;i++){
cout<<p[i];
}
}
int main(){
cin>>x>>y;
cout<<zzdc(x,y)<<endl;
cout<<zzdc2(x,y)<<endl;
cout<<zxgbs(x,y)<<endl;
//------------------------------
cin>>z;
zyz1(z);
cout<<endl;
zyz2(z);
//------------------------------
cin>>n;
cout<<endl;
aish(n);
xianx(n);
return 0;
}
排序
#include<bits/stdc++.h>
using namespace std;
int n,a[100009];
//冒泡OoO
void Oo(){
for(int i=1;i<=n-1;i++){
for(int j=1;j<=n-i;j++){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
}
}
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
}
//选择口↖
void choose(){
for(int i=1;i<=n;i++){
int min_id=i;
for(int j=i+1;j<=n;j++){
if(a[j]<a[min_id]){
min_id=j;
}
}
swap(a[min_id],a[i]);
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
}
//插入||\||
void get_in(){
for(int i=2;i<=n;i++){
int t=a[i],j=i-1;
while(j>=1&&a[j]>t){
a[j+1]=a[j];
j--;
}
a[j+1]=t;
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
return 0;
}
桶（因为其特殊性需要单独写代码）
#include<bits/stdc++.h>
using namespace std;
//桶|_||_||_|
//适用于数多但数不大的情况
int n,a[10000009];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[x]++;
}
for(int i=1;i<=n;i++){
while(a[i]!=0){
cout<<i<<" ";
a[i]--;
}
}
return 0;
}
归并
#include<bits/stdc++.h>
using namespace std;
int n,a[100009],b[100009];
void gb(int l,int r){
if(l<r){
int m=(l+r)/2;
gb(l,m);
gb(m+1,r);
int i=l,j=m+1,t=l;
while(i<=m&&m+1<=r){
if(a[i]<a[j]){
b[t++]=a[i++];
}
else{
b[t++]=a[j++];
}
}
while(i<=m){
b[t++]=a[i++];
}
while(m+1<=r){
b[t++]=a[j++];
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
gb(1,n);
return 0;
}
叠甲：本文是作者上课笔记，不是题解，发在这里一是存档二是给大家分享知识，如有问题欢迎提出。
有帮助，赞一个