【BZOJ 3751】 [NOIP2014]解方程

3751: [NOIP2014]解方程Time Limit:10 SecMemory Limit:128 MBSubmit:914Solved:173[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 102-31

Sample Output

212

哈希+拉格朗日定理

取一个质数p，求出方程在模p意义下的解，根据拉格朗日定理，有不超过n个解。

然后用在模p意义下的解每次加上p(在模p意义下仍是解)，，在模另一个大质数下判断是否是解，如果是的话，那么基本可以断定这个值就是解了。

此时复杂度为O(n^2*m/p)，当p取到sqrt(m*n)附近时，时间复杂度为O(n*sqrt(m*n))

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#define LL long longusing namespace std;int tot=0,p[4],v[1000005],n,m;char s[10005];LL a[4][105];void Change(char *s,int k){int fu=1,i=0;int l=strlen(s);for (int j=1;j<=2;j++){i=0;if (s[0]=='-') fu=-1,i=1;for (;i<l;i++)a[j][k]=a[j][k]*10LL%p[j]+s[i]-'0';if (fu==-1)a[j][k]=p[j]-a[j][k];}}int Calc(int x,int k){LL ans=0,b=1;for (int i=0;i<=n;i++)ans=(ans+1LL*a[k][i]*b)%p[k],b=1LL*b*x%p[k];return ans%p[k];}int main(){p[1]=67891,p[2]=1000000207;scanf("%d%d",&n,&m);for (int i=1;i<=m;i++)v[i]=0;for (int i=0;i<=n;i++)scanf("%s",s),Change(s,i);for (int i=1;i<=p[1];i++){if (Calc(i,1)!=0) continue;for (int j=i;j<=m;j+=p[1])if (Calc(j,2)==0)v[j]=1;}int tot=0;for (int i=1;i<=m;i++)if (v[i])tot++;printf("%d\n",tot);for (int i=1;i<=m;i++)if (v[i])printf("%d\n",i);return 0;}

TLE都是因为p取得太小。

没有了爱的语言，所有的文字都是乏味的