记录编号	139580	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]解方程	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.332 s
提交时间	2014-11-12 21:11:11	内存使用	11.89 MiB

/*======================================================*/
/*========================ASM.DEF=======================*/
/*======================================================*/
#include <cstdio>
#include <cctype>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <ctime>
using namespace std;
#if defined WJX_Asm_Def_DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("equationa.in", "r");
FILE *out = fopen("equationa.out", "w");
#endif
inline bool getd(int &x){
	int c = fgetc(in);
	bool minus = 0;
	while(c != '-' && c != EOF && !isdigit(c))c = fgetc(in);
	if(c == EOF)return 0;
	if(c == '-'){
		x = 0;
		minus = 1;
	}
	else x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
	return 1;
}
#define iter(v) v::iterator
#define pb push_back
#define pf push_front
#define ppf pop_front
/*===========================================================*/
const int maxn = 100 + 3, maxm = 1000000 + 10, maxl = 10000 + 10;
int n, m, len[maxm] = {0}, a[maxn][maxl], amod[maxn] = {0};
bool neg[maxn] = {0};
int P[maxm], Pcnt = 0, basep;
bool not_ans[maxl] = {0};

inline void euler(){
	bool not_p[maxl] = {0};
	int i, j;
	for(i = 2;i < maxl;++i){
		if(!not_p[i])P[Pcnt++] = i;
		for(j = 0;j < Pcnt;++j){
			if(i * P[j] > maxl)break;
			not_p[i * P[j]] = 1;
			if(i % P[j] == 0)break;
		}
	}
}

inline void init(){
	srand(time(NULL));
	euler();
	getd(n), getd(m);
	int i, c;
	for(i = 0;i <= n;++i){
		c = fgetc(in);
		while(!isdigit(c) && c != '-')c = fgetc(in);
		if(c == '-'){
			neg[i] = 1;
			c = fgetc(in);
		}
		a[i][len[i]++] = c - '0';
		while(isdigit(c = fgetc(in)))
			a[i][len[i]++] = c - '0';
	}
}

inline bool getamod(int p){
	int i, j;
	bool ans = 0;
	for(i = 0;i <= n;++i){
		amod[i] = a[i][0] % p;
		for(j = 1;j < len[i];++j)
			amod[i] = (amod[i] * 10 + a[i][j]) % p;
		if(amod[i])ans = 1;
	}
	return ans;
}

inline int f(int x, int p){
	int i, k = 1, ans = 0, t;
	x %= p;
	for(i = 0;i <= n;++i){
		t = neg[i] ? p - amod[i] : amod[i];
		ans = (ans + k * t) % p;
		k = (k * x) % p;
	}
	return ans;
}

inline void work(){
	int i, k, p, cnt = m;
	bool not_A[maxm] = {0};
	i = lower_bound(P, P + Pcnt, (int)sqrt((double)m * n)) - P;
	basep = P[i];
	while(!getamod(basep))basep = P[--i];
	for(i = 0;i < basep;++i)
		if(f(i, basep))not_ans[i] = 1;
	k = 5;
	while(k || cnt > n){
		--k;
		p = P[rand() % Pcnt];
		while(!getamod(p))p = P[rand() % Pcnt];
		for(i = 1;i <= m;++i){
			if(not_A[i])continue;
			if(not_ans[i % basep]){
				not_A[i] = 1;
				--cnt;
				continue;
			}
			if(f(i, p))not_A[i] = 1, --cnt;
		}
	}
	fprintf(out, "%d\n", cnt);
	for(i = 1;i <= m;++i)
		if(!not_A[i])
			fprintf(out, "%d\n", i);
}

int main(){
	init();
	
	work();
	
	return 0;
}