2890: [NOIP2014]解方程 D2 T3

Description

啊啊啊，难死啦。

首先想到a都是高精度，肯定不能是什么高级化简。所以，考虑取模。假设，左面那一大坨式子的值和很多质数取模都等于0；那么很有可能这个数就是解。然后，对于每一个x是解，x+mod也是解，所以只需要枚举1~p,O(p*n+m/p*解的个数)能弄出所有解。

所以，我们找到几个质数，将a分别取模，然后计算1~prime的可行解，对于所有质数都成立的解就是答案。

经验：

1.如果找方程=0的解，可以考虑将方程和很多质数取模，然后都等于0的数就很有可能为方程的解。

2.注意方程的解与解之间的关系。看可不可以用已有的解推出下一个解。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int prime[6]={26947,27031,27011,26993,26681,26641};
int a[1100][6],n,m,ans;
int v[1001000];
char st[11000];
bool cal(int id,int x,int mod)
{
	int re=0;
	for(int i=n;i>=0;i--)
		re=(re*x+a[i][id])%mod;
	return re==0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)
	{
		scanf("%s",st+1);
		int len=strlen(st+1),f=1,fro=1;
		if(st[1]=='-') f=-1,fro=2;
		for(int j=0;j<6;j++)
		{
			int tmp=0,mod=prime[j];
			for(int k=fro;k<=len;k++)
				tmp=((tmp<<1)+(tmp<<3)+st[k]-'0')%mod;
			a[i][j]=tmp*f;
		}
	}
	for(int i=0;i<6;i++)
	{
		int tmp=prime[i];
		for(int j=1;j<=tmp;j++)
			if(cal(i,j,tmp))
				for(int k=j;k<=m;k+=tmp) v[k]++,ans+=(v[k]==6);
	}
	printf("%d\n",ans);
	for(int i=1;i<=m;i++)
		if(v[i]==6) printf("%d\n",i);
	return 0;
}