调了一下午的一点心得……

· · 题解

题外话

@DX3906_ourstar （下文简称 DX）被本题卡了一下午，所以决定发篇题解纪念一下。

DX 的专栏被禁了，所以用的小号。

题意

求下面这个 1 元 n 次方程的不大于 m 正整数解：

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

思考

可能很多同学看到这里就跃跃欲试了：直接套求根公式！

很遗憾，高次方程没有求根公式。

看来要另辟蹊径了。我们可以先对等号左边的式子进行化简、变形，看看能否有所帮助。为表述方便，我们将它简写为 f(x)，而我们的任务就是确保它为零。

不妨尝试提公因式，一次提出一个 x。则有：

{} & f(x)\\ = & a_0+a_1x+a_2x^2+\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+a_4x^2\cdots+a_nx^{n-2}))\\ = & a_0+x(a_1+x(a_2+x(a_3+a_4x+a_5x^2+\cdots+a_nx^{n-3})))\\ = & \cdots\\ = & a_0+x(a_1+x(a_2+\cdots+x(a_{n-1}+a_nx)))\\ = & 0 \end{aligned}

而这，就是我们解决本题的关键所在。

既然 f(x)=0，那么就有下面的等式：

f(x) \bmod p=0

其中，p 为一个很大的质数。显然，这个式子成立时，f(x) 不一定为 0。它可以为 2p,3p,4p\cdots但感性认知一下，只要 p 的取值恰当，那 f(x) 就有极大的可能是 0，足够我们通过此题。

代码

接下来，我们就需要结合上面推出的等式，用代码来表示 f(x) \bmod p 了。试看下面这段代码：

ll sum=0;//十年 OI 一场空，______见祖宗。 
for(int i=n;i>=1;--i){
    sum=((a[i]+sum)*x)%p;//也就是我们推出的式子。
} 
sum=(a[0]+sum)%p;

其中，ll 即为 long long，sum 即为等号左边的运算结果。把这段代码封装到一个 bool 型的函数里，便可用于判断某个 x 的值是否可令 f(x) \bmod p 为 0，也就是像下面这样：

inline bool check(int x){
    /*这部分代码略*/
    return sum==0;
}

那么剩下的工作就非常简单了。m 并不是一个非常大的数，其取值范围允许我们一一枚举 x \in [1,m]。我们只需要挨个判断，最后进行输出即可。

多说无益，直接上完整代码！

#include<iostream>
#include<queue>
#define ll long long
#define p 998244353377//学长说这是一个很棒的模数，不知道为甚，有巨佬能解答一下吗。 
using namespace std;

namespace OIfast{//一个快读快写的板子，曾被 @jerry1717 吐槽慢的一批 

    inline ll read(){
        int n=0,f=1;
        char c=getchar();
        while(c<'0'||c>'9'){
            if(c=='-')f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
        return n*f;
    }

    inline void print(ll n){
        if(n<0)putchar('-'),n=-n;
        if(n>=10)print(n/10);
        putchar(n%10+'0');
        return ;
    }

    inline void write(ll n,char c){
        print(n),putchar(c);
        return ;
    }

}using namespace OIfast;

const int N=1e6+5;

int n,m;
ll a[N];
queue<ll> q;

inline bool check(int x){
    ll sum=0;
    for(int i=n;i>=1;--i)sum=((a[i]+sum)*x)%p;
    sum=(a[0]+sum)%p;
    return sum==0;
}

signed main(){
    n=read(),m=read();
    for(int i=0;i<=n;++i)a[i]=read();
    for(int x=1;x<=m;++x){//枚举解。 
        if(check(x))q.push(x);//成立，则入队。 
    }
    write(q.size(),'\n');//使用队列就无需单独记录解的数量。 
    while(!q.empty())write(q.front(),'\n'),q.pop();//最喜欢用队列了。 
    return 0;
}

然后就可以愉快地 AC 了——吗？

敲黑板——几个坑点

下面的抽象错误卡了 DX 一整个下午，真心希望同学们不要重蹈覆辙。

坑点一：long long 开了，但没完全开

注意 Ln10：int n=0,f=1;，这是 DX 快读打魔怔了，不看数据规模的结果。可以发现，这里的 n 开的是 int，稳炸。

修改措施：把 int 改成 ll 即可。

坑点二：开了 long long 也并非不会炸

注意数据规模：|a_i|\le10^{10000}，再来看看快读里，开的不过是普通的 long long，稳炸。

我们又不可能再写一个高精吧……

但我们可以更充分地利用模数。我们可以把 Ln16 后面加上这句话：n%=p。这就确保了 |n|\le998244353377，不会再爆炸。

总结

本题恶狠狠地给 DX 上了一课。这同时也告诫大家注意细节，不要忽略任何一个可能出错的地方！