3751: [NOIP2014]解方程

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=3751

Description

已知多项式方程：

a0+a1*x+a2*x^2+...+an*x^n=0

求这个方程在[1,m]内的整数解（n和m均为正整数）。

Input

第一行包含2个整数n、m，每两个整数之间用一个空格隔开。

接下来的n+1行每行包含一个整数，依次为a0,a1,a2,...,an。

Output

第一行输出方程在[1,m]内的整数解的个数。

接下来每行一个整数，按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。

Sample Input

2 10

2

-3

1

Sample Output

2

1

2

Hint

对于100%的数据，0<n≤100，|ai|≤1010000，an≠0，m≤1000000。

题意

题解：

找6个10000左右的素数，然后把这个素数范围内的数拿去测试就好了

因为 (a % p) = (a+p % p)，所以a不合适，那么a+p肯定也是不合适的。

于是用这个方法去xjb筛一波就好了。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 105;

const int N = 1e6+6;

int p[10]={19997,22877,14843,10007,11261,21893};

char s[105][10005];

int flag[N];

int a[maxn],n,m,len[maxn];

int main(){

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

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

        scanf("%s",s[i]);

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

        len[i]=strlen(s[i]);

    for(int o=0;o<6;o++){

        for(int i=0;i<=n;i++){

            int flag = (s[i][0]=='-')?1:0;

            a[i]=0;

            for(int j=flag;j<len[i];j++){

                a[i]=(a[i]*10+(s[i][j]-'0'))%p[o];

            }

            if(flag)a[i]=-a[i];

        }

        for(int i=1;i<=p[o];i++){

            int tmp=0;

            for(int j=n;j>=0;j--)

                tmp=(tmp*i+a[j])%p[o];

            if(tmp)for(int j=0;i+j*p[o]<=m;j++)

                flag[i+j*p[o]]=1;

        }

    }

    int ans = 0;

    for(int i=1;i<=m;i++)if(!flag[i])ans++;

    cout<<ans<<endl;

    for(int i=1;i<=m;i++)

        if(!flag[i])

            cout<<i<<endl;

}