首页 > 其他 > 详细

BZOJ 3751 [NOIP2014]解方程

时间:2018-02-20 11:43:09      阅读:98      评论:0      收藏:0      [点我收藏+]

标签:ios   筛法   ace   sizeof   clu   char s   pan   true   oid   

题解:运用筛法的思想,%p意义下,F(x)!=0则F(x+p)!=0

多选几个质数把F(x)!=0的筛去就可以了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m;
int ans;
int vis[1000009];

int p[51]={0,30011,11261,14843,19997,21893};
int a[200][51];

void Minit(){
	memset(a,0,sizeof(a));
	memset(vis,0,sizeof(vis));
	ans=0;
}

char s[100009];
int main(){
	scanf("%d%d",&n,&m);
//	for(int i=1;i<=50;++i)p[i]=10000+i;
	Minit();
	for(int i=0;i<=n;++i){
		scanf("%s",s);
		int len=strlen(s);
		for(int k=1;k<=5;++k){
			if(s[0]!=‘-‘){
				a[i][k]=s[0]-‘0‘;
			}else{
				a[i][k]=0;
			}
			for(int j=1;j<len;++j){
				a[i][k]=(a[i][k]*10+(s[j]-‘0‘))%p[k];
			}
			if(s[0]==‘-‘){
				a[i][k]=(-a[i][k]+p[k])%p[k];
			}
		}
	}
//	for(int i=0;i<=n;++i)cout<<a[i][1]<<‘ ‘;
//	cout<<endl;
	for(int k=1;k<=5;++k){
		for(int j=1;j<=min(p[k],m);++j){
			long long fx=0;
			for(int i=n;i>=0;--i)fx=(fx*j+a[i][k]+p[k])%p[k];
//			cout<<fx<<endl;
			if(fx){
				for(int d=0;j+p[k]*d<=m;++d)vis[j+p[k]*d]=1;
			}
		}
	}
	
	for(int i=1;i<=m;++i)if(!vis[i])++ans;
	printf("%d\n",ans);
	for(int i=1;i<=m;++i)if(!vis[i])printf("%d\n",i);
	return 0;
}

  

BZOJ 3751 [NOIP2014]解方程

标签:ios   筛法   ace   sizeof   clu   char s   pan   true   oid   

原文:https://www.cnblogs.com/zzyer/p/8454915.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号