题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/11/20161108.pdf
还好之前做过类似的题目,要不然肯定做不起了 QAQ
原题在这里:http://oi.cyo.ng/?p=339
1k以内右168个素数,但第12个素数就大于33了
换一句话来说,第12~168个素数不会不会互相干扰
于是前11个素数拿来暴力,后面的素数直接贪心即可
#include<bits/stdc++.h> #define LL long long #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; const int N = 1001; const int M = 200; const int MX = 2100; bitset<N> vec[M],vis,ans; int n,m,BAS[N],vout,sign,f[2][MX],w,p; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void DFS(int t) { if (!sign && t == m+1) { vout = max(vout, (int)vis.count()); } else if (sign && t == 12) { int ret = 0; for (int i=1;i<=11;i++) { if (ans[i]) { ret += (1<<(i-1)); } } f[p][ret] = max(f[p][ret],(int)vis.count()); } else { DFS(t + 1); for (int i=1;i*BAS[t]<=n;i++) vis[i*BAS[t]] = vis[i*BAS[t]] ^ 1; ans[t] = 1; DFS(t + 1); for (int i=1;i*BAS[t]<=n;i++) vis[i*BAS[t]] = vis[i*BAS[t]] ^ 1; ans[t] = 0; } } int main() { freopen("prime.in","r",stdin); freopen("prime.out","w",stdout); for (int T=read(),cnt;T;T--,vout=0,sign=0) { n = read(); m = read(); if (m > 12) { w = 1; p = 0; memset(f,0,sizeof(f)); vis.reset(); ans.reset(); for (int i=1;i<=m;i++) BAS[i] = read(); sort(BAS+1,BAS+1+m); sign = 1; DFS(1); for (int i=12;i<=m;i++,w^=1,p^=1) { memset(f[w],0,sizeof(f[w])); for (int j=0,sta,tmp;j<=2047;j++) { tmp = 0; for (int k=1,lim=n/BAS[i];k<=lim;k++) { sta = 0; for (int x=1,cur=1;x<=11;x++,cur<<=1) { if ((j&cur) && k % BAS[x] == 0) sta ^= 1; } if (sta) tmp--; else tmp++; } f[w][j] = f[p][j] + max(0, tmp); } } for (int i=0;i<=2047;i++) vout = max(f[p][i], vout); printf("%d\n",vout); } else { vis.reset(); for (int i=1;i<=m;i++) BAS[i] = read(); sign = 0; DFS(1); printf("%d\n",vout); } } return 0; }