P2312 [NOIP2014 提高组] 解方程

· · 题解

摘要：本文介绍了 O(nm) 正解，秦九韶公式，O\left(\dfrac{n^2m}C+nC\right) 更优做法。

题目看起来无处下手。但注意到高次方程没有求根公式，且题目只求整数解。我们不妨考虑将 x=1,\cdots,m 一一代入方程验证是否是解。

此时又有一个问题：a_i\le10^{10000},m^n\le10^{600}。都是天文数字，高精度计算会超时。于是考虑哈希，设一个大数 P，求出原式模 P 的值。原式为 0 的必要条件是原式模 P 余数为 0。

于是我们只需要用到 a_0\bmod P,\cdots,a_n\bmod P 和 x\bmod P,\cdots,x^n\bmod P 的值就可以计算了。前者直接在读入时处理，后者可以对每个 x 递推一遍。

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e2 + 5,M = 1e6 + 5;
const ll P = 1e9 + 9; // 一个大质数（这里不能取 1e9 + 7 会被卡）

int n,m,tot;
ll a[N],b[N];
bool ans[M];

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i <= n;++i){
        char c = getchar();
        bool flg = 0;
        for(;!isdigit(c);c = getchar()) flg |= c == '-';
        for(;isdigit(c);c = getchar()) a[i] = (a[i] * 10 + (c - '0')) % P; // 读入时预处理取模后结果
        if(flg) a[i] = P - a[i];
    }
    for(int i = 0;i <= m;++i){
        b[0] = 1;
        for(int j = 1;j <= n;++j) b[j] = b[j - 1] * i % P; // 计算 b[j] = i 的 j 次方结果
        ll f = 0;
        for(int j = 0;j <= n;++j) (f += a[j] * b[j] % P) %= P; // 计算原多项式取模结果
        if(f == 0) ans[i] = 1,++tot; // 存入答案
    }
    printf("%d\n",tot);
    for(int i = 1;i <= m;++i) if(ans[i]) printf("%d\n",i);
    return 0;
}

Bonus：秦九韶公式

我们发现预处理 x,x^2,\cdots,x^n 的值有点鸡肋，考虑优化多项式求值的方法。

\begin{aligned} &a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n\\ =&a_0+x(a_1+a_2x+a_3x^2+\cdots+a_nx^{n-1})\\ =&a_0+x(a_1+x(a_2+a_3x+\cdots+a_nx^{n-2}))\\ &\cdots\\ =&a_0+x(a_1+x(a_2+x(a_3+\cdots+a_nx))) \end{aligned}

于是我们从括号内往外求和：倒序枚举 i=n,\cdots,0，维护当前和 s。初始 s=0，之后不断 s\gets s\times x+a_i 即可。

更改后的求和部分代码：

for(int i = 0;i <= m;++i){
    ll f = 0;
    for(int j = n;j >= 0;--j) f = (f * i + a[j]) % P;
    if(f == 0) ans[i] = 1,++tot;
}

Bonus：更优复杂度做法

我们不再枚举 1,\cdots,m 代入，而是另设一个数 C，代入 0,\cdots,C-1 计算多项式模 C 的结果，设其为 f_0,\cdots,f_{C-1}。

注意到一件事：代入 x=1,C+1 时，在模 C 意义下多项式值相同。原因很简单：1\equiv C+1\pmod C。由于 1\sim C 都已处理，[1,m] 每个数在模 C 意义下多项式值 g_i 都已解出来了：g_i=f_{i\bmod C}。

这时我们再枚举 i=1,\cdots,m，如果 g_i\ne 0，那么 i 作为根的可能就已经被排除了，我们再验证那些未被排除的。

这样做的复杂度是多少呢？

注意到方程根至多有 n 个。故 f_0,\cdots,f_C 中至多有 n 个 f_i=0。我们最后只验证了 O\left(\dfrac{nm}C\right) 个数，总复杂度 O\left(\dfrac{n^2m}C+Cn\right)。

将 C 取到 O(n^2) 级别，该算法优于 O(nm)。

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e2 + 5,M = 1e6 + 5;
const ll m1 = 1e9 + 9,m2 = 99929; // m1 是刚刚的 P, m2 是 C 

int n,m,tot;
ll a1[N],a2[N]; // a1: a 数组模 m1 意义下结果，a2：模 m2 意义下结果 
bool vis[m2],ans[M];

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i <= n;++i){
        char c = getchar(); bool f = 0;
        for(;!isdigit(c);c = getchar()) f |= c == '-';
        for(;isdigit(c);c = getchar())
            a1[i] = (a1[i] * 10 + (c - '0')) % m1,
            a2[i] = (a2[i] * 10 + (c - '0')) % m2;
        if(f) a1[i] = -a1[i],a2[i] = -a2[i];
    }
    for(int i = 0;i < m2;++i){ // 枚举 0 ~ C-1 
        ll k = 0;
        for(int j = n;j >= 0;--j) k = (k * i + a2[j]) % m2;
        vis[i] = k; // vis[i]: 模 C 余 i 的数是否被排除 
    }
    for(int i = 0;i <= m;++i) if(!vis[i % m2]){ // 没排除的数再暴力验证 
        ll f = 0;
        for(int j = n;j >= 0;--j) f = (f * i + a1[j]) % m1;
        if(f == 0) ans[i] = 1,++tot;
    }
    printf("%d\n",tot);
    for(int i = 1;i <= m;++i) if(ans[i]) printf("%d\n",i);
    return 0;
}