解方程

【问题描述】

已知多项式方程：

 

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

 

【输入】

输入文件名为equation.in。

输入共n+2行。

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

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

 

【输出】

输出文件名为equation.out。

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

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

 

【输入输出样例1】

equation.in	equation.out
2 10 1 -2 1	1 1

 

【输入输出样例2】

equation.in	equation.out
2 10 2 -3 1	2 1 2

 

【输入输出样例3】

equation.in	equation.out
2 10 1 3 2	0

 

【数据说明】

对于30%的数据，0<n≤2，|ai|≤100，an≠0，m≤100；

对于50%的数据，0<n≤100，|ai|≤10¹⁰⁰，an≠0，m≤100；

对于70%的数据，0<n≤100，|ai|≤10¹⁰⁰⁰⁰，an≠0，m≤10000；

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

---

思路：

有点高精度的意思，但又不全是高精度。

看数据，|ai|≤10¹⁰⁰⁰⁰ ，说实话吓到我了，但其实没什么可怕的

我们将该方程倒过来：

　　　　a_nxⁿ+……a₂x²+a₁x+a₀=0

就是我们熟悉的格式了~个鬼

意思就是这样，既然数据那么大，我们就要想办法减小数据，在一个可控范围，于是：

(a_nxⁿ+……a₂x²+a₁x+a₀)%P=0%P

不影响最终结果

要做到我们需要用快读来取模，因为我们需要把这么大的数读进来

另一个优化：秦九昭算法

可以较小的时间复杂度，算出最终答案

代码^-^

#include<stdio.h>
#include<algorithm> 
#define ll long long  
using namespace std;
const int P=1e9+7;
ll n,m,cnt,a[101],ans[1000001];

ll read()
{
    ll s=0,j=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-') j=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        s=(s*10+ch-'0')%P;
        ch=getchar(); 
    }
    return s*j;
}

bool qin(int x)
{
    ll sum=0;
    for(int i=n;i>=0;--i) {
        sum=((sum+a[i])*x)%P;
    }
    return !sum;
}

int main()
{
    n=read(),m=read();
    for(int i=0;i<=n;++i) a[i]=read();
    for(int i=1;i<=m;++i) {
        if(qin(i))
            ans[++cnt]=i;
    }
    if(!cnt) {
        printf("0");
    }
    else {
        printf("%d
",cnt);
        for(int i=1;i<=cnt;++i) printf("%d
",ans[i]);
    }
    return 0;
}