NOIP2014提高组.解方程

题目

515. 解方程

算法标签: 数论, 秦九韶算法, 素数判断, 哈希

思路

得到一些必要条件使用近似算法, 对某一个质数取模
原来的等式成立能推导出, 但是反过来不一定成立, 但是可以近似求解

$$a_0+a_{1}x+a_2{x}^2+\cdots +a_n{x}^n=0(\mathrm{mod}p)$$

因为$x$范围是$10^6$级别, 因此可以直接枚举$x$, 可以使用秦久韶算法优化多项式计算, 时间复杂度优化为$O(n)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 110, MOD = 1e9 + 7;

int n, m;
int a[N];
string s;
vector<int> ans;

//检查x是否是多项式方程的一个根
bool check(int x) {
   
    int res = 0;
    for (int i = n; i >= 0; --i) {
   
        res = ((LL) res * x + a[i]) % MOD;
    }
    return res == 0;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i <= n; ++i) {
   
        cin >> s;

        int val = 0, t = 0;
        if (s[0] == '-') t = 1;

        for (int j = t; j < s.size(); ++j) {
   
            val = ((LL) val * 10 % MOD + (s[j] - '0')) % MOD;
        }
        if (t) val = -val;
        a[i] = (val % MOD + MOD) % MOD;
    }

    //检查[1, m]中每个数是否是多项式的根
    for (int i = 1; i <= m; ++i) {
   
        if (check(i)) ans.emplace_back(i);
    }

    cout << ans.size() << "\n";
    for (int c : ans) cout << c << "\n";

    return 0;
}