专栏文章

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

__Calmly_
P2312题解参与者 8已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@miqgeeo2
此快照首次捕获于
2025/12/04 04:22
3 个月前
此快照最后确认于
2025/12/04 04:22
3 个月前
查看原文

Solution

思路

首先枚举可能的解，然后判断是否是想要的解。为了判断，需要我们求方程左边的值，如果直接套公式的话，时间会不够QAQ。所以在求值之前，需要把方程左边通过提公因式化简：
a0+a1x+a2x2+…+anxn=a0+x(a1+x(a2+…+x(an−1+anx)…))a_0 +a_1x +a_2x^2 + … + a_nx^n = a_0+x(a_1+x(a_2+…+x(a_{n-1}+a_nx)…))
这时求值，就需要找规律，我是先把 ansans 赋值成 ana_n ，则 ans=ans×x+an−jans = ans \times x +a_{n-j} ，其中的 jj 从 11 累加至 nn 。当然也可以有其他观察方法。
伪代码：
CPP
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;
如果仅仅这样，那就完了，因为在求值时， ansans 随时都可能超过长整型，如果用高精度只能拿50分。这时，使用取模，无需迟疑。
伪代码：
CPP
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;
还要注意 ∣ai∣≤1010000|a_i| \le 10^{10000} ，已经超过了长整型，所以读入必须手写，才可以取模。
伪代码：
CPP
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;
}
还有一点，读入 aia_i 时 ii 要从 00 开始。QAQ

Code

CPP
#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;
}

完结撒花

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...