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

· · 题解

Solution

思路

首先枚举可能的解，然后判断是否是想要的解。为了判断，需要我们求方程左边的值，如果直接套公式的话，时间会不够QAQ。所以在求值之前，需要把方程左边通过提公因式化简：

a_0 +a_1x +a_2x^2 + … + a_nx^n = a_0+x(a_1+x(a_2+…+x(a_{n-1}+a_nx)…))

这时求值，就需要找规律，我是先把 ans 赋值成 a_n ，则 ans = ans \times x +a_{n-j} ，其中的 j 从 1 累加至 n 。当然也可以有其他观察方法。

伪代码：

long long ans=a[n],num;
for(long long j=1;j<=n;j++) ans=ans*i+a[n-j];
if(ans==0) x[++num]=i;

如果仅仅这样，那就完了，因为在求值时， ans 随时都可能超过长整型，如果用高精度只能拿50分。这时，使用取模，无需迟疑。

伪代码：

long long ans=a[n],num;
for(long long j=1;j<=n;j++) ans=(ans*i%mod+a[n-j])%mod;
if(ans==0) x[++num]=i;

还要注意 |a_i| \le 10^{10000} ，已经超过了长整型，所以读入必须手写，才可以取模。

伪代码：

long long read(){
    char c=getchar();
    long long f=1,x=0;
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' and c<='9'){
        x=(x*10+c-'0')%mod;//一定要取模QAQ
        c=getchar();
    }
    return x*f;
}
还有一点，读入 a_i 时 i 要从 0 开始。QAQ

Code

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

const int mod=1e9+9;
ll n,m,a[105],x[100005],num;

ll read(){
    char c=getchar();
    ll f=1,x=0;
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' and c<='9'){
        x=(x*10+c-'0')%mod;
        c=getchar();
    }
    return x*f;
}

int main(){
    n=read();
    m=read();
    for(ll i=0;i<=n;i++) a[i]=read();
    for(ll i=1;i<=m;i++){
        ll ans=a[n];
        for(ll j=1;j<=n;j++) ans=(x*i%mod+a[n-j])%mod;
        if(ans==0) x[++num]=i;
    }
    cout<<num<<endl;
    for(ll i=1;i<=num;i++) cout<<x[i]<<endl;
    return 0;
}

完结撒花