解方程（NOIP2014）Warning!（前方高能！！）

原题传送门

一看这不是水题嘛。

枚举+乱搞。。特别容易、。。、

然后a[i]取值范围出现了

当当当当~：|a[i]|<=10^10000!!!!!

我去，这是什么鬼。。

高精度？

然后默默算了算。。

O(10000*n*m)BOOM!TLE..

好吧，高精度没用了。。

那么我们再来看一看。。

根据某位大牛的说法x mod p=0那么(x+p)mod p=0；

我们反过来

假设一个数a=k*x+q

那么a mod x=q;

所以我们可以直接%，不用怕结果会改变，，边读边膜。

首先我们要多找几个质数。。（10000左右）

5个就差不多了。

然后我们要把1~质数最大值的数都代入方程里check一下，看那些是方程的解（注意！要5个都代！不然有可能出现膜数的倍数！）

然后就是寻找解*k的答案啦（在1~m中找）

下面贴代码：

注意！对于这道鬼畜的题目，在跑的慢的评测机上strlen()极容易TLE（我也不知道为什么。。也许常数太大了。。）

所以对于字符串的判断我们要用(for int j=0;num[j];++j)来进行。。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char num[10005];
int a[5][105];
int b[5][13500];
int ans[1000005];
int ans1,n,m;
const int mod[5]={10007,10009,10037,10039,10061};
void check(int x)
{
    for(int i=0;i<5;i++)
    for(int j=n;j>=0;j--)
    b[i][x%mod[i]]=(b[i][x%mod[i]]*(x%mod[i])+a[i][j])%mod[i];
}
bool judge(int x)
{
    for(int i=0;i<5;i++)
    if(b[i][x%mod[i]])return 0;
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
    {
        scanf("%s",num);
        for(int j=0;num[j];++j)
        {
            if(num[j]>='0'&&num[j]<='9')
            {        
                for(int k=0;k<5;k++)
                a[k][i]=(a[k][i]*10+num[j]-'0')%mod[k];
            }
        }
        if(num[0]=='-')
        {
            for(int k=0;k<5;k++)
            a[k][i]*=-1;
        }
    }
    for(int i=0;i<10061;i++)check(i);
    for(int i=1;i<=m;i++)
    if(judge(i))ans[++ans1]=i;
    printf("%d
",ans1);
    for(int i=1;i<=ans1;i++)
    printf("%d
",ans[i]);
}