题解：P2312 [NOIP2014 提高组] 解方程
Bearbrother18
·
·
题解
题意
第一眼看见这串方程时是不是有点头晕。这里简单化简一下就可以得出下面的式子。
a_0+x(a_1+x(a_2+…+x(a_{n-1}+a_nx)…))
思路
通过公式我们不难发现这么长一串可以用一个循环来实现。
但是值得注意的是这个值得注意的需要注意的点。
于是就有了下面的代码。
```cpp
for(ll i=1; i<=m; i++){
ll x=a[n];
for(ll j=1; j<=n; j++) {
x=(x*i+a[n-j]);
}
if(x==0){
ans[++num]=i;
}
}
```
可是我们依然发现，还是会炸。
怎么办。
在讲下面的知识前先讲一下取模。
设一个数为 $t$。如果 $t=0$ 则有 $t\bmod p=0$。但是如果 $t\bmod p=0$，则 $t=0$ 不一定成立。
于是我们可以将 $p$ 取一个较大的质数来防炸。具体的不多阐述，不懂的点击[这里](https://oi-wiki.org/string/hash/)。给出核心代码：
```cpp
for(ll i=1; i<=m; i++){
ll x=a[n];
for(ll j=1; j<=n; j++) {
x=(x*i%p+a[n-j])%p; //p=1e9+7
}
if(x==0){
ans[++num]=i;
}
}
```
光是这样还不够。在快读中预先处理每个数让每个数先模一个 $p$ 才能算大功告成。
```cpp
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')%p;
c=getchar();
}
return x*f;
}
```
## 代码
---
这里给出完整代码，~~马蜂较稠不喜就喷~~。
```cpp
#include<bits/stdc++.h>//万能头
using namespace std;
#define ll long long//宏定义
const int p=1e9+7;//p取"较大"的质数
ll n,m,a[105],ans[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')%p;//预处理每个数
c=getchar();
}
return x*f;
}
int main(){
cin >> n >> m;
for(ll i=0; i<=n; i++){
a[i]=read();
}
for(ll i=1; i<=m; i++){
ll x=a[n];
for(ll j=1; j<=n; j++) {
x=(x*i%p+a[n-j])%p;//mod一个p防炸
}
if(x==0){
ans[++num]=i;
}
}
cout << num << endl;
for(ll i=1; i<=num; i++) {
cout << ans[i] << endl;
}
return 0;//好习惯
}
```