专栏文章

P2312 [NOIP2014 提高组] 解方程

xxfrvq
P2312题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miqm7ry9
此快照首次捕获于
2025/12/04 07:05
3 个月前
此快照最后确认于
2025/12/04 07:05
3 个月前
查看原文
摘要：本文介绍了 O(nm)O(nm) 正解，秦九韶公式，O(n2mC+nC)O\left(\dfrac{n^2m}C+nC\right) 更优做法。
题目看起来无处下手。但注意到高次方程没有求根公式，且题目只求整数解。我们不妨考虑将 x=1,⋯ ,mx=1,\cdots,m 一一代入方程验证是否是解。
此时又有一个问题：ai≤1010000,mn≤10600a_i\le10^{10000},m^n\le10^{600}。都是天文数字，高精度计算会超时。于是考虑哈希，设一个大数 PP，求出原式模 PP 的值。原式为 00 的必要条件是原式模 PP 余数为 00。
于是我们只需要用到 a0 mod P,⋯ ,an mod Pa_0\bmod P,\cdots,a_n\bmod P 和 x mod P,⋯ ,xn mod Px\bmod P,\cdots,x^n\bmod P 的值就可以计算了。前者直接在读入时处理，后者可以对每个 xx 递推一遍。
CPP
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e2 + 5,M = 1e6 + 5;
const ll P = 1e9 + 9; // 一个大质数（这里不能取 1e9 + 7 会被卡）

int n,m,tot;
ll a[N],b[N];
bool ans[M];

int main(){
	scanf("%d%d",&n,&m);
	for(int i = 0;i <= n;++i){
		char c = getchar();
		bool flg = 0;
		for(;!isdigit(c);c = getchar()) flg |= c == '-';
		for(;isdigit(c);c = getchar()) a[i] = (a[i] * 10 + (c - '0')) % P; // 读入时预处理取模后结果
		if(flg) a[i] = P - a[i];
	}
	for(int i = 0;i <= m;++i){
		b[0] = 1;
		for(int j = 1;j <= n;++j) b[j] = b[j - 1] * i % P; // 计算 b[j] = i 的 j 次方结果
		ll f = 0;
		for(int j = 0;j <= n;++j) (f += a[j] * b[j] % P) %= P; // 计算原多项式取模结果
		if(f == 0) ans[i] = 1,++tot; // 存入答案
	}
	printf("%d\n",tot);
	for(int i = 1;i <= m;++i) if(ans[i]) printf("%d\n",i);
	return 0;
}

Bonus：秦九韶公式

我们发现预处理 x,x2,⋯ ,xnx,x^2,\cdots,x^n 的值有点鸡肋，考虑优化多项式求值的方法。
a0+a1x+a2x2+a3x3+⋯+anxn=a0+x(a1+a2x+a3x2+⋯+anxn−1)=a0+x(a1+x(a2+a3x+⋯+anxn−2))⋯=a0+x(a1+x(a2+x(a3+⋯+anx)))\begin{aligned} &a_0+a_1x+a_2x^2+a_3x^3+\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+\cdots+a_nx^{n-2}))\\ &\cdots\\ =&a_0+x(a_1+x(a_2+x(a_3+\cdots+a_nx))) \end{aligned}
于是我们从括号内往外求和：倒序枚举 i=n,⋯ ,0i=n,\cdots,0，维护当前和 ss。初始 s=0s=0，之后不断 s←s×x+ais\gets s\times x+a_i 即可。
更改后的求和部分代码：
CPP
for(int i = 0;i <= m;++i){
	ll f = 0;
	for(int j = n;j >= 0;--j) f = (f * i + a[j]) % P;
	if(f == 0) ans[i] = 1,++tot;
}

Bonus：更优复杂度做法

我们不再枚举 1,⋯ ,m1,\cdots,m 代入，而是另设一个数 CC，代入 0,⋯ ,C−10,\cdots,C-1 计算多项式模 CC 的结果，设其为 f0,⋯ ,fC−1f_0,\cdots,f_{C-1}。
注意到一件事：代入 x=1,C+1x=1,C+1 时，在模 CC 意义下多项式值相同。原因很简单：1≡C+1(modC)1\equiv C+1\pmod C。由于 1∼C1\sim C 都已处理，[1,m][1,m] 每个数在模 CC 意义下多项式值 gig_i 都已解出来了：gi=fi mod Cg_i=f_{i\bmod C}。
这时我们再枚举 i=1,⋯ ,mi=1,\cdots,m，如果 gi≠0g_i\ne 0，那么 ii 作为根的可能就已经被排除了，我们再验证那些未被排除的。
这样做的复杂度是多少呢？
注意到方程根至多有 nn 个。故 f0,⋯ ,fCf_0,\cdots,f_C 中至多有 nn 个 fi=0f_i=0。我们最后只验证了 O(nmC)O\left(\dfrac{nm}C\right) 个数，总复杂度 O(n2mC+Cn)O\left(\dfrac{n^2m}C+Cn\right)。
将 CC 取到 O(n2)O(n^2) 级别，该算法优于 O(nm)O(nm)。
CPP
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e2 + 5,M = 1e6 + 5;
const ll m1 = 1e9 + 9,m2 = 99929; // m1 是刚刚的 P, m2 是 C 

int n,m,tot;
ll a1[N],a2[N]; // a1: a 数组模 m1 意义下结果，a2：模 m2 意义下结果 
bool vis[m2],ans[M];

int main(){
	scanf("%d%d",&n,&m);
	for(int i = 0;i <= n;++i){
		char c = getchar(); bool f = 0;
		for(;!isdigit(c);c = getchar()) f |= c == '-';
		for(;isdigit(c);c = getchar())
			a1[i] = (a1[i] * 10 + (c - '0')) % m1,
			a2[i] = (a2[i] * 10 + (c - '0')) % m2;
		if(f) a1[i] = -a1[i],a2[i] = -a2[i];
	}
	for(int i = 0;i < m2;++i){ // 枚举 0 ~ C-1 
		ll k = 0;
		for(int j = n;j >= 0;--j) k = (k * i + a2[j]) % m2;
		vis[i] = k; // vis[i]: 模 C 余 i 的数是否被排除 
	}
	for(int i = 0;i <= m;++i) if(!vis[i % m2]){ // 没排除的数再暴力验证 
		ll f = 0;
		for(int j = n;j >= 0;--j) f = (f * i + a1[j]) % m1;
		if(f == 0) ans[i] = 1,++tot;
	}
	printf("%d\n",tot);
	for(int i = 1;i <= m;++i) if(ans[i]) printf("%d\n",i);
	return 0;
}

评论

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

正在加载评论...