Luogu 2312 [NOIP2014] 解方程

感觉好无聊。

秦九昭算法：一般地，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。（百度百科）

具体来说怎么做呢？

　　$f(x) = \sum_{i = 0}^{n}a_{i}*x^{i} = (((a_{n}*x + a_{n - 1}) * x + a_{n - 2})...)*x + a_{0} $

这么来说，读入优化好像也有这种思想在里面。

那么本题中数太大了，使用高精会T，怎么办呢？

搞几个大质数取取模……

Luogu上用$1e9 + 7$能AC

时间复杂度$O(mn)$

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = ;

const ll P = 1e9 + ;

int n, m, ans = , res[N];

ll a[N];

template <typename T>

inline void read(T &X) {

    X = ;

    char ch = ;

    T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = ((X << ) + (X << ) + ch - ) % P;

    X = (X * op + P) % P;

}

inline bool chk(ll k) {

    ll sum = 0LL;

    for(int i = n; i >= ; i--)

        sum = ((sum + a[i]) * k + P) % P;

    sum = (sum + a[] + P) % P;

    return sum == 0LL;

}

int main() {

    read(n), read(m);

    for(int i = ; i <= n; i++) read(a[i]);

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

        if(chk(i)) res[++ans] = i;

    printf("%d\n", ans);

    if(ans != ) {

        for(int i = ; i <= ans; i++)

            printf("%d\n", res[i]);

    }

    return ;

}