3751: [NOIP2014]解方程
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 3499 Solved: 733
[Submit][Status][Discuss]
Description
已知多项式方程：
a0+a1*x+a2*x^2+...+an*x^n=0
求这个方程在[1,m]内的整数解（n和m均为正整数）。
Input
第一行包含2个整数n、m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a0,a1,a2,...,an。
Output
第一行输出方程在[1,m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。
Sample Input
2 10
2
-3
1
2
-3
1
Sample Output
2
1
2
1
2
HINT
对于100%的数据，0<n≤100，|ai|≤1010000，an≠0，m≤1000000。
一道看起来很高端的题
由于我们无法直接算出f(x)的值
所以我们将f(x)取模
当f(x)==0时，易知f(x) mod p==0
但反命题不一定成立
所以我们要多取几个p，才能保证当f(x) mod p==0时 f(x)==0
至于为什么要取素数
易知当x mod p==0时，f(x) mod p ==0
所以我们取几个素数时，它们是互质的，所以它们的最小公倍数很大，已经超过了m的范围
所以就不用担心因为x mod p ==0而导致f(x) mod p ==
然后如果我们直接枚举1~m的数，每一个进行计算的话，仍无法通过100%的数据
而我们会发现f(x) mod p==f(x+p) mod p
所以就可以只算到1~mod-1，之后的数mod一下就好了
恩，就这样
#include<cstdio>
#include<cstring>
char ch[10005];
int mod[5]={11261,19997,22877,21893,14843};
int a[5][115];
int pre[5][115];
int res[5][30000];
int ans[1000005];
int n,m;
int cal(int t)
{
int sum=0;
for(int i=0;i<=n;i++)
sum=(sum+a[t][i]*pre[t][i])%mod[t];
if(sum<0) sum+=mod[t];
return sum;
}
bool judge(int x)
{
for(int t=0;t<5;t++)
if(res[t][x%mod[t]]!=0) return 0;
return 1;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<=n;i++)
{
scanf("%s",ch+1);
int l=strlen(ch+1);
bool flag=0;
if(ch[1]!='-') for(int t=0;t<5;t++) a[t][i]=ch[1]-'0';
else for(int t=0;t<5;t++) a[t][i]=0,flag=1;
for(int t=0;t<5;t++)
{
for(int k=2;k<=l;k++)
a[t][i]=(a[t][i]*10+ch[k]-'0')%mod[t];
if(flag) a[t][i]=-a[t][i];
}
}
for(int t=0;t<5;t++)
for(int x=1;x<mod[t];x++)
{
pre[t][0]=1;
for(int i=1;i<=n;i++) pre[t][i]=(pre[t][i-1]*x)%mod[t];
res[t][x]=cal(t);
}
for(int j=1;j<=m;j++)
if(judge(j)) ans[++ans[0]]=j;
printf("%d
",ans[0]);
for(int j=1;j<=ans[0];j++)
printf("%d
",ans[j]);
return 0;
}