【日常小测】素数

题目传送门: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;
}

22 thoughts to “【日常小测】素数”

  1. Hello! I know this is somewhat off topic but I was
    wondering which blog platform are you using for this website?
    I’m getting tired of WordPress because I’ve had issues
    with hackers and I’m looking at options for another platform.
    I would be awesome if you could point me in the direction of a good platform.

  2. I loved as much as you will receive carried out right here.
    The sketch is attractive, your authored material stylish.
    nonetheless, you command get bought an nervousness over that you wish be delivering the following.
    unwell unquestionably come further formerly again since
    exactly the same nearly a lot often inside case you shield this increase.

  3. I am not sure where you are getting your information, but great topic.
    I needs to spend some time learning much more or understanding more.
    Thanks for great information I was looking for this information for my mission.

  4. Simply want to say your article is as astonishing.
    The clearness for your post is just great and that i could suppose you are
    an expert on this subject. Well with your permission let me to take hold of your feed
    to stay updated with impending post. Thank you 1,000,000 and please carry on the rewarding work.

  5. Woah! I’m really enjoying the template/theme of this website.
    It’s simple, yet effective. A lot of times it’s difficult to get that “perfect balance” between usability and visual appeal.
    I must say you’ve done a great job with this.
    In addition, the blog loads very quick for me on Internet explorer.
    Exceptional Blog!

  6. Have you ever thought about including a little bit more
    than just your articles? I mean, what you say is important and everything.
    But think about if you added some great pictures or videos
    to give your posts more, “pop”! Your content is excellent but with images and clips, this site could certainly be one of the best in its
    niche. Wonderful blog!

  7. Hmm is anyone else experiencing problems with
    the images on this blog loading? I’m trying to find out if its a problem on my end or if it’s
    the blog. Any feedback would be greatly appreciated.

  8. Nice weblog right here! Additionally your website so much up very fast!
    What web host are you the use of? Can I am getting your
    affiliate hyperlink to your host? I want my site loaded up as fast as yours lol

  9. Hey there I am so delighted I found your blog page, I really found you by accident, while I was looking
    on Digg for something else, Anyways I am here now and would just
    like to say many thanks for a tremendous post and a
    all round entertaining blog (I also love the theme/design), I don’t have time to read
    it all at the minute but I have book-marked it and also added in your RSS feeds,
    so when I have time I will be back to read more, Please
    do keep up the fantastic job.

  10. hey there and thank you for your information – I have certainly picked up anything new
    from right here. I did however expertise several technical
    points using this web site, as I experienced to reload the site a lot of times previous to
    I could get it to load correctly. I had been wondering if your
    web hosting is OK? Not that I’m complaining, but sluggish loading instances times will often affect
    your placement in google and could damage your quality score if ads and marketing with Adwords.
    Anyway I am adding this RSS to my e-mail and can look out for much more
    of your respective interesting content. Make sure you update this again soon.

  11. I’m really enjoying the design and layout of your site. It’s a
    very easy on the eyes which makes it much more enjoyable for me
    to come here and visit more often. Did you hire out
    a developer to create your theme? Superb work!

  12. Hey there, I think your website might be having browser compatibility issues.

    When I look at your blog site in Firefox, it looks fine
    but when opening in Internet Explorer, it has some overlapping.

    I just wanted to give you a quick heads up! Other then that,
    very good blog!

  13. Whats up very cool website!! Guy .. Beautiful .. Wonderful ..
    I will bookmark your blog and take the feeds additionally?

    I am satisfied to seek out numerous useful info here within the publish,
    we want develop more techniques in this regard, thank you for sharing.
    . . . . .

Leave a Reply to tinyurl.com Cancel reply

Your email address will not be published. Required fields are marked *