luogu2312 解方程

​​http://www.elijahqi.win/archives/1353​​​

題目描述

已知多項式方程：

a0+a1x+a2x^2+..+anx^n=0

求這個方程在[1, m ] 内的整數解（n 和m 均為正整數）

輸入輸出格式

輸入格式：

輸入檔案名為equation .in。

輸入共n + 2 行。

第一行包含2 個整數n 、m ，每兩個整數之間用一個空格隔開。

接下來的n+1 行每行包含一個整數，依次為a0,a1,a2..an

輸出格式：

輸出檔案名為equation .out 。

第一行輸出方程在[1, m ] 内的整數解的個數。

接下來每行一個整數，按照從小到大的順序依次輸出方程在[1, m ] 内的一個整數解。

輸入輸出樣例

輸入樣例#1： 複制

2 10

1

-2

1

輸出樣例#1： 複制

1

1

輸入樣例#2： 複制

2 10

2

-3

1

輸出樣例#2： 複制

2

1

2

輸入樣例#3： 複制

2 10

1

3

2

輸出樣例#3： 複制

說明

對于30%的資料:0< n<=2,|ai|<=100,an!=0,m< 100

對于50%的資料:0< n<=100,|ai|<=10^100,an!=0,m< 100

對于70%的資料:0< n<=100,|ai|<=10^10000,an!=0,m< 10000

#include<cstdio>
#define ll long long
#define mod 1000000007
#define N 110
#define M 1100000
inline char gc(){
    static char now[1<<16],*S,*T;
    if(S==T){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF; }
    return *S++;
}
/*inline ll multiply(ll A,ll B,ll Mo){
    ll tmp=((ll)((double)A*B/Mo+1e-6 )*Mo);
    return A*B-tmp;
}*/
inline ll read(){
    ll x=0,f=1;char ch=gc();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
    while (ch<='9'&&ch>='0'){x=(x*10+ch-'0')%mod;ch=gc();}
    return x*f;
}
ll a[N],n,top,ans[M],m;
inline bool judge(int x){
    ll sum=0;
    for (int i=n+1;i>=1;--i){
        sum=((a[i]+sum)*x)%mod;
    }return sum==0;
} 
int main(){
    freopen("2312.in","r",stdin);
    n=read();m=read();
    for (int i=1;i<=n+1;++i) a[i]=read();
//  for (int i=1;i<=n+1;++i) printf("%d,a[i]);
    for (int i=1;i<=m;++i){
        if (judge(i)) ans[++top]=i;
    }printf("%d\n",top);
    for (int i=1;i<=top;++i) printf("%d\n",ans[i]);
    return 0;
}