2021安徽大学新生赛 F.金属制品

题目链接：金属制品

标签 ： 数学

---

问题描述

链接：https://ac.nowcoder.com/acm/contest/23846/F
来源：牛客网

形式化的问题是，给出 \(n,p\) 和 \(a_0,a_1,\dots,a_n\)，希望你求出序列 \(k\) 是的模素数 \(p\) 意义下 \(\prod_{i = 1}^{n}(x + k_i) = \sum_{i = 0}^{n}a_ix^i\)

\(n,p \le 5000\)，保证 \(0 \le a_i < p\)

（所以这题和金属制品有什么关系）

---

解题思路

由于并没有官方题解，思路参考了大佬[代码](代码查看 (nowcoder.com))

考虑到 \(n,p\) 的数据范围并不是很大，本题可以接受\(O(n^2)\)的时间复杂度，所以我们可以使用较为暴力的算法。

对于给出的\(n\)次多项式，题目中所求的序列 \(k\) 可以转化为求它的\(n\)个解。

我们可以枚举 \(0\) 到 \(p-1\) 中的每一个数，以这个数为解尝试将原多项式分解为 \((x - k) * (a_1'x + a_2'x^2 + \dots+a_{n-1}'x^{n-1})\) 两部分。

如果成功分解，就将该数计入答案序列，并将分解出来的右侧的多项式作为新的多项式进行计算，最终得到所有答案

---

代码

#include<bits/stdc++.h>
using namespace std;
void solve() {
	int n, p;
	cin >> n >> p;
	vector<int> a(n + 1);
	for (int i = 0; i <= n; i++)
		cin >> a[i];
	vector<int> ans;
	for(int i = 0; i < p; i++) {
		int f = 1;
		while (f) {
			f = 0;
			int cur = a.back();
			vector<int> b;
			for (int j = a.size() - 1; j >= 1; j--) {	
				b.emplace_back(cur);
				cur = ((a[j - 1] - cur * i) % p + p) % p;//具体分解方法，不是很难可以自行推导
			}
			if (cur == 0) {
				reverse(b.begin(), b.end());
				f = 1;
				a = b;
				ans.emplace_back(i);
			}
		}
	}
	for (auto i : ans) {
		cout << i << " ";
	}
	cout << "\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}