luogu 2312 解方程 乱搞+取模

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

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

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

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

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

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

复杂度 $O(n imes 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
",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
",v.size()); 
	for(i=0;i<v.size();++i)   printf("%d
",v[i]);     
	return 0;
}