记录编号	354125	评测结果	AAAAAWWWWW
题目名称	[NOIP 2014]解方程	最终得分	50
用户昵称	kilometer	是否通过	未通过
代码语言	C++	运行时间	0.302 s
提交时间	2016-11-19 21:44:54	内存使用	7.92 MiB

#include <stdio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int list[1000010]/*jie*/,a[110][10]/*hash*/;
int top,m,n;
int ok[1000010];/*panduan shibushijie*/
int hash[11]= {0,1007,10007,12347,12349,100017,111647,19720309,19750921,19981117,20150209};

int check1(int x/*gen*/,int k)/*k change hash*/
{
	int i,sum=0;
	for(i=n;i>=0;i--)
		sum=(sum*x+a[i][k])%hash[k];/*qin 9 shao*/
	if(sum!=0)
	{
		i=x;
		while(i<=m)
		{
			ok[i]=1;
			i=i+hash[k];
		}
		return 0;
	}
	else return 1;
}

int check(int x)
{
	int k;
	if(ok[x])
		return 0;
	else
		for(k=1;k<=10;k++)
		{
			if(!check1(x,k))
				return 0;
		}
		return 1;
}

int main()
{
freopen("equationa.in","r",stdin);
	freopen("equationa.out","w",stdout);
	int i,b,k,v,j;
	char c[10010];
	scanf("%d %d",&n,&m);
	memset(a,0,sizeof(a));
	memset(ok,0,sizeof(ok));
	for(i=0;i<=n;i++)
	{
		scanf("%s",&c);
		if(c[0]=='-')
		{
			b=1;/*biaoji fushu*/
		}
		else b=0;
		if(b==1)
			k=1;
		else
			k=0;
		while(c[k]>='0'&&c[k]<='9')
		{
			v=c[k]-'0';
			for(j=1;j<=10;j++)
			{
				a[i][j]=(a[i][j]*10+v)%hash[j];/*除法散列法*/
			}
			k++;
		}
		if(b)
		{
			for(j=1;j<=10;j++)
				if(a[i][j]!=0)
					a[i][j]=hash[j]-a[i][j];
		}
	}
	for(i=1;i<=m;i++)
	{
		if(check(i))
		{
			top++;
			list[top]=i;
		}
	}
	printf("%d",top);
	for(i=1;i<=top;i++)
		printf("%d",list[i]);
	return 0;
	
}