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

题外话

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 了——[吗？](https://www.luogu.com.cn/record/list?pid=P2312&user=1268524&status=14&page=1) ## 敲黑板——几个坑点 ~~下面的抽象错误卡了 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 上了一课。这同时也告诫大家注意细节，不要忽略任何一个可能出错的地方！

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

文章操作

题外话

题意

思考

相关推荐

评论

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