题目：https://www.luogu.org/problemnew/show/P2312
https://www.lydsy.com/JudgeOnline/problem.php?id=3751
10^10000 太大了，高精度也很难做，怎么办？
注意我们要求的是方程的值 = 0 的解，不妨在取模意义下做，因为真正使方程 = 0 的解在模意义下也是 0；
然后可以用秦九韶算法，O(n) 算每个枚举的答案；
避免出错要多对几个数取模，就像哈希时有多个模数一样；
据说模数大小在 2e4 左右比较好；
模数多了会 T，少了会错，最后取了5个才勉强过去；
考试时遇到这种题怎么估计...
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const maxn=105,maxm=1e6+5; int n,m,a[10][maxn],p[10]={0,29501,18919,15671,30271,24443}; int pri[maxm],cnt,ans[maxm],c=5; bool vis[maxm],fl[10][200005]; int main() { scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) { int f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) { for(int k=1;k<=c;k++) a[k][i]=(a[k][i]*10+ch-‘0‘)%p[k]; ch=getchar(); } for(int k=1;k<=c;k++)a[k][i]=(a[k][i]*f+p[k])%p[k];//! } int cnt=0; for(int k=1;k<=c;k++) for(int x=1;x<p[k]&&x<=m;x++)// { int ret=0; for(int i=n;i>=0;i--)ret=((ll)ret*x%p[k]+a[k][i])%p[k]; if(ret)fl[k][x]=1; } for(int i=1;i<=m;i++) { bool flag=0; for(int k=1;k<=c;k++)if(fl[k][i%p[k]]){flag=1; break;}; if(!flag)ans[++cnt]=i; } printf("%d\n",cnt); for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]); return 0; }
洛谷 P2312 & bzoj 3751 解方程 —— 取模
原文：https://www.cnblogs.com/Zinn/p/9643330.html