又是数论题
Q&A
Q：你TM做数论上瘾了吗
A：没办法我数论太差了，得多练（shui）啊
题意
题目描述
已知多项式方程：
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 ] 内的一个整数解。
我们来看看这鬼畜的NOIP题目怎么做（shui）
讲道理，这道题最难的地方在于：不知谁在洛谷上给它贴上了高精度的标签（管理给我滚粗来）我想知道有多少人在这狗血标签的引导下怒写高精+压位+秦九昭+各种奇技淫巧优化，最后拿个T回去哭
正解并没有用到高精度（虽然我写的输入是仿照高精度的，但是hzw大的代码是直接字符串处理的Orz）
但是hzw用了一个神奇的pre来存x的i次方，我懒得打就打了一个秦九昭（讲道理，秦九昭不会比暴力难打，而且可以少开一个数组）
顺便一提，据说大神用过的质数会有灵气，我直接用了hzw用的5个质数当mod
对于5个（其实无所谓选几个，多一点可以保险一些我这种rp不佳的必备）选出的质数p，每个都处理出1~p-1代入原式modp算出的结果
这个结果就可以代表所有modp同余的数的结果（因为显然每次增加p的话，结果变化量是p的倍数，modp以后不会变），若modp以后不为0则一定不是方程解
尽管我们不能保证为0的话实际结果就一定是0，但是用5个数都验证一遍以后基本就能保证这个结果为0
===没了===
上代码
#include<cstdio>
int mod[]={,,,,};
int n,m;
int ans[];
int a[][],res[][],aa[][],num[];
bool flag[];
int main()
{
scanf("%d%d",&n,&m);
char ch=getchar();
for(int i=;i<=n;i++)
for(num[i]=,flag[i]=false,ch=getchar();(ch>='' && ch<='')||(ch=='-');ch=getchar())
if(ch=='-')
flag[i]=true;
else
aa[i][++num[i]]=ch-'';
for(int i=;i<;i++)
for(int j=;j<=n;j++)
{
a[i][j]=;
for(int k=;k<=num[j];k++)
a[i][j]=(a[i][j]*+aa[j][k])%mod[i];
if(flag[j])
a[i][j]=-a[i][j];
}
for(int t=;t<;t++)
for(int x=;x<mod[t];x++)
{
int sum=;
for(int i=n;i>=;i--)
sum=(sum*x+a[t][i])%mod[t];
res[t][x]=sum;
}
int sum=;
bool flag;
for(int i=;i<=m;i++)
{
flag=true;
for(int t=;t<;t++)
if(res[t][i%mod[t]]!=)
{
flag=false;
break;
}
if(flag)
ans[++sum]=i;
}
printf("%d\n",sum);
for(int i=;i<=sum;i++)
printf("%d\n",ans[i]);
return ;
}