【BZOJ】3751: [NOIP2014]解方程【秦九韶公式】【大整数取模技巧】

2022-09-25 21:44:03

3751: [NOIP2014]解方程

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4856 Solved: 983
[Submit][Status][Discuss]

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。

Solution

暴力枚举即可，难点主要是读入和快速计算。

大整数读入解决方法是mod大~质数，题解大佬说mod一个可能会出问题所以有时候要mod几个~

快速计算的话就是秦九韶公式了QAQ，很好理解的，不过这道题要控制mod的次数！不然多100次都t了QAQ！

Code

#include<bits/stdc++.h>

#define LL long long

#define mod 1000000007

using namespace std;

inline LL read() {

    LL x = ; int t = ; char ch = getchar();

    while(ch > '' || ch < '')    { if(ch == '-') t = -; ch = getchar(); }

    while(ch >= '' && ch <= '') { x = ((x << ) % mod + (x << ) % mod + ch - '') % mod;    ch = getchar(); }

    return x * t;

}

LL a[];

int n, m, ans[], tot;

inline bool cal(int x) {

    LL res = a[n];

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

        res = (res * x % mod + a[i]);

    return res == ;

}

int main() {

    n = read(); m = read();

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

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

        if(cal(i))    ans[++tot] = i;

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

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

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

    return ;

}

码农公寓