cf1147

C——筛法

#include<bits/stdc++.h>
using namespace std;
int n,a[200005];
int main(){
    cin>>n;
    int cnt=0;
    for(int i=2;i<=n;i++)
        if(a[i]==0){
            cnt++;
            for(int j=i;j<=n;j+=i)
                a[j]=cnt;
        }
    for(int i=2;i<=n;i++)
        cout<<a[i]<<" ";
} 

D——异或前缀和+bitmask，好题

/*
每个前缀和不同。。。 
枚举每个前缀和，然后vis数组用来判断i^x是否存在了 
*/
#include <iostream>
#include <vector>
using namespace std;
bool ex[(1<<18)];
int main()
{
    int n,x;
    scanf("%d%d",&n,&x);
    ex[0]=1;
    vector<int> v({0});
    for (int i=1;i<(1<<n);i++)
    {
        if (ex[i^x])
        continue;
        v.push_back(i);
        ex[i]=1;
    }
    printf("%d
",v.size()-1);
    for (int i=1;i<v.size();i++)
    printf("%d ",(v[i]^v[i-1]));
}

E——待补