题目描述
已知多项式方程：
a0+a1x+a2x2+⋯+anxn=0
求这个方程在 [1,m]内的整数解（n 和 m 均为正整数）。
输入输出格式
输入格式：
共 n+2 行。
第一行包含 2个整数 n,m，每两个整数之间用一个空格隔开。
接下来的 n+1n+1n+1 行每行包含一个整数，依次为 a0,a1,a2…an
输出格式：
第一行输出方程在 [1,m] 内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在 [1,m]内的一个整数解。
思路：
有一个奇妙的东西叫秦九韶算法
（不知道的请左转百度）
然后我们看到a都很大
于是我们想到了hash
将 a hash掉
之后验证时取膜即可
代码：
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
#define p1 19260817
#define p2 23333
using namespace std;
char ai[];
long long a1[],a2[];
int ans[],n,m,cnt;
inline void c1(int wz,int len)
{
int pd=;
int fi=;
if(ai[]=='-')
{
pd=-;
fi=;
}
long long ans=ai[fi]-'';
for(rii=fi+;i<=len-;i++)
{
ans*=;
ans+=ai[i]-'';
ans%=p1;
}
a1[wz]=ans*pd;
}
inline void c2(int wz,int len)
{
int pd=;
int fi=;
if(ai[]=='-')
{
pd=-;
fi=;
}
long long ans=ai[fi]-'';
for(rii=fi+;i<=len-;i++)
{
ans*=;
ans+=ai[i]-'';
ans%=p2;
}
a2[wz]=ans*pd;;
}
inline bool check(int v)
{
long long ans=a1[n];
for(rii=n;i>=;i--)
{
ans*=v;
ans%=p1;
ans+=a1[i-];
ans%=p1;
}
if(ans!=)
{
return ;
}
ans=a2[n];
for(rii=n;i>=;i--)
{
ans*=v;
ans%=p2;
ans+=a2[i-];
ans%=p2;
}
if(ans!=)
{
return ;
}
return ;
}
inline void sr()
{
int wz=;
char l=getchar();
while(l!=)
{
ai[wz]=l;
l=getchar();
wz++;
}
}
int main()
{
scanf("%d%d\n",&n,&m);
for(rii=;i<=n;i++)
{
memset(ai,,sizeof(ai));
// scanf("%s",ai);
sr();
int ltt=strlen(ai);
c1(i,ltt);
c2(i,ltt);
}
// for(rii=0;i<=n;i++)
// {
// cout<<a2[i]<<" ";
// }
for(rii=;i<=m;i++)
{
if(check(i)==)
{
cnt++;
ans[cnt]=i;
}
}
cout<<cnt<<endl;
for(rii=;i<=cnt;i++)
{
printf("%d\n",ans[i]);
}
}