洛谷P2312 [NOIP2014 提高组] 解方程 题解

题目链接：P2312 [NOIP2014 提高组] 解方程

题意：

已知多项式方程：

$$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$$

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

输入格式：

输入共 $n + 2$ 行。

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

接下来的 $n+1$ 行每行包含一个整数，依次为 $a_0,a_1,a_2\ldots a_n$ 。

输出格式：

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

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

数据范围：

$0<n\le 100,|a_i|\le 10^{10000},a_0\ne 0,m<10^6$ 。

这个题有点哈希的味道。注意到对于质数 $p$ ，

$$a_0+a_1x+a_2x^2+\cdots+a_nx^n\equiv 0 \pmod{p}$$

是原命题成立的一个必要不充分条件，不过在绝大多数情况下都是充分的。

那么我们随便取两个 $p_1,p_2$ 模一模，看看是不是都为 $0$ 就好啦，这种情况下出错的概率低到难以置信。

然后就被卡常了。

注意到 $p^k$ 的个数远小于其他的数的数量，又因为

$$f(x) \equiv 0 \pmod{p} \quad\Rightarrow\quad f(x + kp)\equiv 0\pmod {p}$$

所以我们可以取一个比较小的 $p_1$ ，比如 $10007$ ，然后预处理出哪些 $x$ 可能有解

这样就不用跑两遍大常数的 $\mathcal{O}(nm)$ 了。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(233))
#define M ((int)(2e5 + 15))

const int p1 = 10007;
const int p2 = 998244853;

char s[M], vis[M];
int n, a[N], b[N], ans[N];
bool calc(const int x, int *arr, const int p)
{
    ll sum = 0;
    for(int i = n; i; i--) sum = (sum + arr[i]) * x % p;
    return !((sum + arr[0]) % p);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m; cin >> n >> m;
    for(int i = 0; i <= n; i++)
    {
        cin >> (s + 1);
        ll x = 0, y = 0; bool f = (s[1] == '-');
        for(int j = 1 + f; s[j]; j++)
        {
            x = (x * 10 + s[j] - '0') % p1;
            y = (y * 10 + s[j] - '0') % p2;
        }
        a[i] = f ? p1 - x : x, b[i] = f ? p2 - y : y;
    }
    int tot = 0;
    for(int i = 0; i < p1; i++) if(calc(i, a, p1)) vis[i] = true;
    for(int i = 1; i <= m; i++)
        if(vis[i % p1] && calc(i, b, p2)) ans[++tot] = i;
    if(!tot) return cout << 0 << '\n', 0;
    cout << tot << '\n';
    for(int i = 1; i <= tot; i++) cout << ans[i] << '\n';
    return 0;
}

---

题外话：

最近没找什么图片。