描述
已知多项式方程:
a0+a1x+a2x2+...+anxn=0a0+a1x+a2x2+...+anxn=0
求这个方程在[1, m]内的整数解(n 和 m 均为正整数)。
格式
输入格式
输入共 n+2 行。
第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。
接下来的 n+1 行每行包含一个整数,依次为a0,a1,a2,...,ana0,a1,a2,...,an
。
输出格式
第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。
限制
对于 30%的数据,0 < n ≤ 2, |ai||ai|
≤ 100,anan
≠ 0, m ≤ 100;
对于 50%的数据,0 < n ≤ 100, |ai||ai|
≤ 1010010100
,anan
≠ 0,m ≤ 100;
对于 70%的数据,0 < n ≤ 100, |ai||ai|
≤ 10100001010000
,anan
≠ 0,m ≤ 10000;
对于 100%的数据,0 < n ≤ 100, |ai||ai|
≤ 10100001010000
,anan
≠ 0,m ≤ 1000000。
来源
NOIP2014 提高组 Day2
初看本题,知道要取模一个素数但是有两个地方没考虑
1一个素数不够用,可能要出错,用5个素数就差不多了,这五个素数可以比较小10^4级就可以了
2根据题意如果f(x)=0,那么f(x+p)=0,后面的就不用算了
AC代码
#include<cstdio>
#include<iostream>
#define M 1000002
#define N 102
using namespace std;
int n,m;
int ans[M];
int a[N][];
int t[][];
int c[][];
int p[]={,,,,};
int cal(int y)
{
int tmp=;
for(int i=;i<=n;i++)
tmp=(tmp+a[i][y]*t[i][y])%p[y];
if(tmp<)//减法取余要注意可能减到负数
tmp+=p[y];
return tmp;
}
bool check(int mm)
{
for(int i=;i<;i++)
if(c[mm%p[i]][i]!=)
return false;
return true;
}
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)//读大系数
{
char ai[];
scanf("%s",ai);
for(int k=;k<;k++)
{
int factor=;
int j=;
if(ai[]=='-')j++;
for(;;j++)
{
if(ai[j]<=''&&ai[j]>='')
factor=(factor*+ai[j]-'')%p[k];
else break;
}
if(ai[]=='-')
factor*=-;
a[i][k]=factor;
}
}
for(int i=;i<;i++)
for(int j=;j<=p[i];j++)
{
t[][i]=;//第一个系数为a0*x^0
for(int k=;k<=n;k++)t[k][i]=(t[k-][i]*j)%p[i];
c[j][i]=cal(i);
}
for(int i=;i<=m;i++)
if(check(i))
ans[++ans[]]=i;
cout<<ans[]<<endl;
for(int i=;i<=ans[];i++)
printf("%d\n",ans[i]);
return ;
}