luogu 2312 解方程 乱搞+取模

思路非常好想，但是你很难想到去用这个算法，因为这个几乎就是个乱搞~

我们发现多项式中每一个系数都很大，但是 $m$ 却很小，即最多只用 $10^6$ 个整数需要验证.

我们知道，如果一个数等于 $0$，那么这个数模任何一个数也都应该该等于 $0$

所以可以直接取 $3$ 个左右的质数当模数，分别带值，取模，然后判一下等不等于 $0$.

当然，带值的部分可以用秦九昭算法，但是我感觉这只算是常数上的优化吧~

只能在 luogu 上过，bz 上过不去~

复杂度 $O(n\times m)$

#include <bits/stdc++.h>

#define N 1000005

#define LL long long

#define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

using namespace std;

// 0 ~ 15

const LL mod[]={998244353,19,1e9+7, 1e9+9, 233,233233,23,17,19,11,613317,119,911,2332,2323,1415,1717};

int n,m;

char str[103][N];

vector<int>v;

LL a[20][N];

int check(int tmp)

{

	// 15 个模数

	int i,j;

	for(i=0;i<=0;++i)

	{

		LL temp=0ll;

		a[i][n+1]=0ll;

		for(j=n+1;j>=0;--j)

		    temp=(temp*1ll*tmp%mod[i]+a[i][j])%mod[i];

		if(temp!=0) return 0;

	}

	return 1;

}

inline void Init()

{

	int i,j;

	for(i=0;i<=0;++i)

	{

		for(j=0;j<=n;++j)

		{

			LL tmp=0,base=1ll;

			int len=strlen(str[j]);

			for(int k=len-1;k>=0;--k)

			{

				if(k==0&&str[j][k]=='-')

				{

					tmp=(mod[i]-tmp%mod[i])%mod[i];

				}

				else

				{

					tmp=(tmp+(str[j][k]-'0')*base)%mod[i], base=base*10%mod[i];

				}

			}

			a[i][j]=tmp;

			// printf("%d %lld\n",j,a[j]);

		}

	}

}

int main()

{

	// setIO("input");

	int i,j;

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

	for(i=0;i<=n;++i)  scanf("%s",str[i]);

	Init();

	for(i=1;i<=m;++i)  if(check(i))   v.push_back(i);

	printf("%d\n",v.size());

	for(i=0;i<v.size();++i)   printf("%d\n",v[i]);

	return 0;

}