洛谷 P2312 & bzoj 3751 解方程 —— 取模

题目：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=,maxm=1e6+;

int n,m,a[][maxn],p[]={,,,,,};

int pri[maxm],cnt,ans[maxm],c=;

bool vis[maxm],fl[][];

int main()

{

  scanf("%d%d",&n,&m);

  for(int i=;i<=n;i++)

    {

      int f=; char ch=getchar();

      while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

      while(ch>=''&&ch<='')

    {

      for(int k=;k<=c;k++)

        a[k][i]=(a[k][i]*+ch-'')%p[k];

      ch=getchar();

    }

      for(int k=;k<=c;k++)a[k][i]=(a[k][i]*f+p[k])%p[k];//!

    }

  int cnt=;

  for(int k=;k<=c;k++)

    for(int x=;x<p[k]&&x<=m;x++)//

    {

      int ret=;

      for(int i=n;i>=;i--)ret=((ll)ret*x%p[k]+a[k][i])%p[k];

      if(ret)fl[k][x]=;

    }

  for(int i=;i<=m;i++)

    {

      bool flag=;

      for(int k=;k<=c;k++)if(fl[k][i%p[k]]){flag=; break;};

      if(!flag)ans[++cnt]=i;

    }

  printf("%d\n",cnt);

  for(int i=;i<=cnt;i++)printf("%d\n",ans[i]);

  return ;

}