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

题意

第一眼看见这串方程时是不是有点头晕。这里简单化简一下就可以得出下面的式子。

a_0+x(a_1+x(a_2+…+x(a_{n-1}+a_nx)…))

思路

通过公式我们不难发现这么长一串可以用一个循环来实现。

但是值得注意的是这个值得注意的需要注意的点。

10^{10000}

。这下直接让爆搜的梦想破灭了。有人会说用高精度不就行了。这就说的很对，恭喜你成功拿到了五十分。如果想要剩下的五十分，就要用哈希来解决了。

于是就有了下面的代码。

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

取一个较大的质数来防炸。具体的不多阐述，不懂的点击这里。给出核心代码：

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;//好习惯
}

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

文章操作

题意

思路

代码

相关推荐

评论

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