P2312 解方程
题目描述
已知多项式方程：
a0+a1x+a2x^2+..+anx^n=0
求这个方程在[1, m ] 内的整数解（n 和m 均为正整数）
输入输出格式
输入格式：
输入文件名为equation .in。
输入共n + 2 行。
第一行包含2 个整数n 、m ，每两个整数之间用一个空格隔开。
接下来的n+1 行每行包含一个整数，依次为a0,a1,a2..an
输出格式：
输出文件名为equation .out 。
第一行输出方程在[1, m ] 内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m ] 内的一个整数解。
输入输出样例
输入样例#1：
2 10
1
-2
1
输出样例#1：
1
1
输入样例#2：
2 10
2
-3
1
输出样例#2：
2
1
2
输入样例#3：
2 10
1
3
2
输出样例#3：
0
说明
30%:0<n<=2,|ai|<=100,an!=0,m<100
50%:0<n<=100,|ai|<=10^100,an!=0,m<100
70%:0<n<=100,|ai|<=10^10000,an!=0,m<10000
100%:0<n<=100,|ai|<=10^10000,an!=0,m<1000000
AC代码：
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define M 110
#define N 1000100
int n,m,ans;
bool sum[N];
ll a[][M];
char s[N];
int prime[]={,,};
void pre(char *s,int k){
int len=strlen(s);bool flag=;
for(int i=,start;i<=;i++){
start=;
if(s[]=='-'){
flag=;
start=;
}
for(;start<len;start++){
a[i][k]=(a[i][k]*10LL%prime[i]+s[start]-'')%prime[i];
}
if(flag) a[i][k]=prime[i]-a[i][k];
}
}
bool judge(int x,int k){
ll ans=,b=;
for(int i=;i<=n;i++){
ans=(ans+1LL*a[k][i]*b)%prime[k];
b=1LL*b*x%prime[k];
}
return ans%prime[k];
}
int main(){
scanf("%d%d",&n,&m);
memset(sum,,sizeof sum);
for(int i=;i<=n;i++){
scanf("%s",s);
pre(s,i);
}
for(int i=;i<=prime[];i++){
if(judge(i,)) continue;
for(int j=i;j<=m;j+=prime[]) if(!judge(j,)) sum[j]=;
//break;//交了5次才发现，QAQ
}
for(int i=;i<=m;i++) if(sum[i]) ans++;
printf("%d\n",ans);
for(int i=;i<=m;i++) if(sum[i]) printf("%d\n",i);
return ;
}