记录编号	463686	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]解方程	最终得分	100
用户昵称	HZOI_蒟蒻一只	是否通过	通过
代码语言	C++	运行时间	2.052 s
提交时间	2017-10-24 17:07:54	内存使用	3.12 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxm=(int)1e6+5,maxl=10005,maxn=105;
const int mod[]={2147483647,999946333};
int n,m,a[maxn][maxl],anssum,isfu[maxn];unsigned long long amod[maxn];bool notans[maxm];
char s[maxm];
unsigned long long check(unsigned long long val)
{
	unsigned long long y=0;
	for(int i=n;~i;i--)
	{
		y=y*val+amod[i];
		y=(y&0x7fffffff)+(y>>31);
	}
	y%=0x7fffffff;
	return y;
}
bool check(int val,int module)
{
	val%=module;unsigned long long y=0;
	for(int i=n;~i;i--)
	{
		y=y*val+amod[i];
		y%=module;
	}
	y%=module;return y;
}
int haha()
{
	freopen("equationa.in","r",stdin);
	freopen("equationa.out","w",stdout);
	scanf("%d%d",&n,&m);anssum=m;
	for(int i=0;i<=n;i++)
	{
		scanf("%s",s+1);int len=strlen(s+1);
		for(int j=1;j<=len;j++)
		{
			if(s[j]=='-'){isfu[i]=1;continue;}
			if(s[j]>='0'&&s[j]<='9')a[i][++a[i][0]]=s[j]-'0';
		}
	}
	for(int i=0;i<=n;i++)
	{
		amod[i]=0;
		for(int j=1;j<=a[i][0];j++)
		{
			amod[i]=amod[i]*10+a[i][j];
			amod[i]%=0x7fffffff;
		}
		amod[i]=amod[i]%0x7fffffff;
		if(isfu[i]&&amod[i])amod[i]=0x7fffffff-amod[i];
	}
	for(int i=1;i<=m;i++)
		if(check(i))anssum--,notans[i]=1;
	for(int t=1;t<2;t++)
	{
		for(int i=0;i<=n;i++)
		{
			amod[i]=0;
			for(int j=1;j<=a[i][0];j++)
			{
				amod[i]=amod[i]*10+a[i][j];
				amod[i]%=mod[t];
			}
			amod[i]%=mod[t];
			if(isfu[i]&&amod[i])amod[i]=mod[t]-amod[i];
		}
		for(int i=1;i<=m;i++)
		{
			if(notans[i])continue;
			if(notans[i%mod[t]]){anssum--,notans[i]=1;continue;}
			if(check(i,mod[t]))anssum--,notans[i]=1;
		}
	}
	printf("%d\n",anssum);
	for(int i=1;i<=m;i++)
		if(!notans[i])printf("%d\n",i);
}
int sb=haha();
int main(){;}