解方程

解方程

来源：
noip Day2 T3

输入描述：
输入共n+2行。
第一行包含2个整数n、m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a0,a1,a2,……,an。
输出描述：
第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。
样例输入：
样例输入1：
2 10
1
-2
1
样例输出1：
1
1
样例输入2：
2 10
2
-3
1
样例输出2：
2
1
2
思路：
数据范围很大，首先想到取模运算的性质：n=0 => n%p=0。
这个性质的逆推是不正确的，但如果尝试了多个p均有n%p=0，可近似认为n=0，错误率是很低的（Hash）。
因此，选取若干个（一般5个即可）质数。输入系数和多项式求值时均逐步运算，每步取模。
多项式求值使用秦九韶算法，复杂度O(n)。这里质数选取10000~20000左右，还是需要用到long long。
但此时复杂度依然很高，因此应用取模运算的另一性质：a ^ b % p = ((a % p)^b) % p
当f(x)%p!=0时，f(x+p)%p、f(x+2p)%p等均不为0。

#include<iostream>
#include<cstdio>
#include<cstring>
#define lon long long
#ifdef unix
#define ll "%lld
"
#else
#define ll "%I64d
"
#endif
using namespace std;
const int p=6;
const int maxn=110;
const int maxx=1000010;
lon n,m,tot,dont[maxx],ans[maxx],a[p][maxn];
lon prime[p]={0,10007,10009,11987,19997,19949};
char s[maxx];
lon can(lon p1,lon x)
{
    lon y=a[p1][n];
    for(int i=n-1;i>=0;i--)
    y=(y*x+a[p1][i])%prime[p1];
    return y;
}
int main()
{
    memset(a,0,sizeof(a));
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<=n;i++)
    {
        cin>>s;
        bool flag=0;
        lon len=strlen(s),now=0;
        if(s[0]=='-') flag=1,now=1;
        for(;now<len;now++)
        {
            for(int j=1;j<p;j++)
            a[j][i]=(a[j][i]*10ll+(s[now]-'0'))%prime[j];
        }
        if(flag)
        for(int j=1;j<p;j++)
        a[j][i]=-a[j][i];
    }
    for(lon i=1;i<=m;i++)
    {
        int j;
        if(dont[i]) continue;
        for(j=1;j<p;j++)
        if(can(j,i)) break;
        if(j>=p) ans[++tot]=i;
        else
        {
            lon k=i+prime[j];
            while(k<=m)
            {
                dont[k]=1;
                k+=prime[j];
            }
        }
    }
    printf(ll,tot);
    for(int i=1;i<=tot;i++)
    printf(ll,ans[i]);
    return 0;
}