思路：
系数的范围有$10^{10000}$，但是用高精度做显然不现实，因此可以考虑一个类似于“哈希”的做法，
对方程两边同时取模，如果取的模数足够多，正确率就很高了。
中间对多项式的计算可以使用$O(n)$的秦九韶算法。
然而，我的模数试了很多种都不能A，看了题解发现只要对$1000000007$一个数取模就AC了？
1 #include<cstdio> 2 #include<cctype> 3 const long long mod=1000000007; 4 inline long long getll() { 5 bool sgn=false; 6 char ch; 7 while(!isdigit(ch=getchar())) if(ch=='-') sgn=true; 8 long long x=ch^'0'; 9 while(isdigit(ch=getchar())) x=((((x<<2)+x)<<1)+(ch^'0'))%mod; 10 return sgn?-x:x; 11 } 12 const long long N=100,M=1000001; 13 long long n; 14 long long a[N]; 15 long long ans[M]={0}; 16 inline bool check(const long long x) { 17 long long sum=0; 18 for(long long i=n;i>=0;i--) { 19 sum=(sum*x+a[i])%mod; 20 } 21 return sum==0; 22 } 23 int main() { 24 n=getll(); 25 long long m=getll(); 26 for(long long i=0;i<=n;i++) a[i]=getll(); 27 for(long long i=1;i<=m;i++) { 28 if(check(i)) ans[++ans[0]]=i; 29 } 30 for(long long i=0;i<=ans[0];i++) printf("%lld ",ans[i]); 31 return 0; 32 }
试了很多个模数都没能AC的代码：
1 #include<tuple> 2 #include<cstdio> 3 #include<cctype> 4 inline int getint() { 5 char ch; 6 while(!isdigit(ch=getchar())); 7 int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=((((x<<2)+x)<<1)+(ch^'0')); 9 return x; 10 } 11 const int mod_size=5; 12 const int mod[mod_size]={19260817,19260817,19260817,19260817,19260817}; 13 inline std::tuple<int,int,int,int,int> gettuple() { 14 bool sgn=false; 15 char ch; 16 while(!isdigit(ch=getchar())) if(ch=='-') sgn=true; 17 int x[mod_size]; 18 for(int i=0;i<mod_size;i++) x[i]=ch^'0'; 19 while(isdigit(ch=getchar())) { 20 for(int i=0;i<mod_size;i++) { 21 x[i]=((((x[i]<<2)+x[i])<<1)+(ch^'0'))%mod[i]; 22 } 23 } 24 return sgn?std::make_tuple(mod[0]-x[0],mod[1]-x[1],mod[2]-x[2],mod[3]-x[3],mod[4]-x[4]):std::make_tuple(x[0],x[1],x[2],x[3],x[4]); 25 } 26 const int N=100,M=1000001; 27 int n; 28 int a[mod_size][N]; 29 int ans[M]={0}; 30 inline bool check(const int x) { 31 int sum[mod_size]; 32 for(int i=n;i>=0;i--) { 33 for(int j=0;j<mod_size;j++) { 34 sum[j]=(sum[j]*x%mod[j]+a[j][i])%mod[j]; 35 } 36 } 37 bool ret=true; 38 for(int i=0;i<mod_size;i++) ret=ret&&!sum[i]; 39 return ret; 40 } 41 int main() { 42 n=getint(); 43 int m=getint(); 44 for(int i=0;i<=n;i++) { 45 std::tuple<int,int,int,int,int> p=gettuple(); 46 a[0][i]=std::get<0>(p); 47 a[1][i]=std::get<1>(p); 48 a[2][i]=std::get<2>(p); 49 a[3][i]=std::get<3>(p); 50 a[4][i]=std::get<4>(p); 51 } 52 for(int i=1;i<=m;i++) if(check(i)) ans[++ans[0]]=i; 53 for(int i=0;i<=ans[0];i++) printf("%d ",ans[i]); 54 return 0; 55 }