1.求质数

(1)埃氏筛

时间复杂度：O(n*loglogn)

大致思路：用标记数组标记它平方以上的倍数，若最后还没有标记的那就是质数

模板代码

CPP

void e_prime()
{
	vis[1]=1;
	for(int i=2;i*i<=n;i++)
	{
		if(vis[i]==0)
		{
			for(int j=i*i;j<=n;j+=i)vis[j]=1;
		}
	}
}

例题

1.P3912 素数个数

模板题，但是要注意数组大小和vis要是bool

CPP

#include <bits/stdc++.h>
using namespace std;
const int N=1e8+5;
int n,ans;
bool vis[N];
void e_prime()
{
	vis[1]=1;
	for(int i=2;i*i<=n;i++)
	{
		if(vis[i]==0)
		{
			for(int j=i*i;j<=n;j+=i)
            {
                vis[j]=1;
            }
		}
	}
}
int main()
{
	cin>>n;
	e_prime();
    for(int i=2;i<=n;i++)
    {
        if(vis[i]==0)ans++;
    }
    cout<<ans;
	return 0;
}

2.P1621 集合

模板+并查集，主要是考的对埃氏筛的理解

主要思路

在求质数的同时判断p,并且合并，最后判断集合即可

代码

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a,b,p,fa[N],cnt;
bool vis[N];
int find(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y)return ;
	fa[x]=y;
}
void e_prime()
{
	vis[1]=1;
	for(int i=2;i<=b;i++)
	{
		if(vis[i]==0)
		{
			for(int j=i*2;j<=b;j+=i)
            {
                vis[j]=1;
                if(i>=p)unionn(i,j);
            }
		}
	}
}
void solve()
{
	for(int i=1;i<=b;i++)fa[i]=i;
	e_prime();
	int res=0;
	for(int i=a;i<=b;i++)
	{
		if(fa[i]==i)res++; 
	}
	cout<<res;
	return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>a>>b>>p;
	solve();
	return 0;
}

(2)空间时间都高的质数题目

当一个题目空间时间都高的时候，该怎么办呢？不妨将他砍半，比如2^32变为2^16,也就是65536

例题

1.UVA10140/P1835 素数密度

主要思路

1.无法筛出1~R的所有质数,时间TLE,标记数组空间MLE

2.因为R-L不超过1e6,那么L~R是可以枚举的

3.任意一个荷属x只要被他最小的质因数p标记即可 -> 这时p<=sqrt(x)

4.只要将2^16以内(65536)的质数筛出来，就足以标记2^32以内的所有合数

5.空间问题可以用平移即可解决->vis[i-L]=1而不是vis[i]=1

6.当标记L~R的所有合数后再枚举L~R维护ans表示上一个找到的质数即可

实现代码

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int l,r,x,y,tot;
bool vis[N];
int prime[N];
void e_prime(int n)
{
	vis[1]=1;
	for(int i=2;i*i<=n;i++)
	{
		if(vis[i]==0)
		{
			for(int j=i*i;j<=n;j+=i)
            {
                vis[j]=1;
            }
		}
	}
	for(int i=2;i<=65536;i++)
	{
		if(!vis[i])prime[++tot]=i;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	e_prime(65536);
	memset(vis,0,sizeof(vis));
	cin>>l>>r;
	for(int i=1;i<=tot;i++)
	{
		int p=prime[i],x=ceil(l*1.0/p);
		for(int j=max(2ll,x)*p;j<=r;j+=p)vis[j-l]=1;
	}
	int cnt=0;
	int maxx=-1e18,minn=1e18,ans=0,mxa=0,mxb=0,mia=0,mib=0;
	for(int i=l;i<=r;i++)
	{
		if(!vis[i-l])cnt++;
	}
	if(l==1)cnt--;
	cout<<cnt<<"\n";
	return 0;
}

因数分解

简单的质因数分解

(1)不需要思考直接按题意模拟

例题

1.B3871 [GESP202309 五级] 因数分解

模板题

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
bool is_prime(int n)
{
	if(n<2)return 0;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)return 0;
	}
	return 1;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	if(is_prime(n))
	{
		cout<<n;
		return 0;
	}
	for(int i=2;i*i<=n;i++)
	{
		int cnt=0;//统计次数 
		while(n%i==0)n/=i,cnt++;
		if(cnt==0)continue;
		else if(cnt>1)
		{
			cout<<i<<"^"<<cnt;
			if(n==0)break; 
			else cout<<" * ";
		}
		else
		{
			cout<<i;
			if(n==0)break;
			else cout<<" * ";
		}
	}
	if(n)cout<<n;
	return 0;
}

(2)技巧性题目

例题

1.P1469 找筷子

实现思路

直接异或

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		ans^=x;
	}
	cout<<ans;
	return 0;
}

国庆day3总结--上午

文章操作