Luogu P2312

题目：

求$a_0+a_{1}x+a_2{x}^2+...+a_n{x}^n=0$ 在$[1,m]$中的整数解 数据范围：$n\le 100,|a_i|\le 10^{10000},m<10^6$

题解：

先看题，额，暴力枚举每个x判断符合与否 再看范围。。。。 高精？真的超级不想打 细想一下，$O(nm)$就已经$10^8$高精常数这么大随便就死翘翘啊。。。

---

神仙解法：对于每个$a_i$用大质数取模，想一下有点道理，就跟哈希差不多，要是怕的话多来几个大质数

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=103,mod=19260817; inline int read() { int ans=0,f=1;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)) { ans=(ans*10%mod+(s&15))%mod; s=getchar(); }return ans*f; } int n,m; int a[N]; bool f(int x) { ll ans=0; for(int i=n+1;i>=1;i--) { ans=(ans*x%mod+a[i])%mod; } if(ans==0)return 1; return 0; } int z[N],p; int main() { n=read();m=read(); for(int i=1;i<=n+1;i++) a[i]=read(); for(int i=1;i<=m;i++) { if(f(i))z[++p]=i; } printf("%d\n",p); for(int i=1;i<=p;i++) printf("%d\n",z[i]); }