国庆day3总结--上午

· · 个人记录

1.求质数

(1)埃氏筛

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

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

模板代码

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

#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,并且合并，最后判断集合即可

代码

#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表示上一个找到的质数即可

实现代码

#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 五级] 因数分解

模板题

#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 找筷子

实现思路

直接异或


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