神奇的，这次 test 8 TLE，但是其它 AC，，，
思路是因式定理，枚举常数项的全部因子，然后用类大除法的去降次。
#include <bits/stdc++.h>
using lint = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
const int N = 20;
const int MOD[2] = {998244353, (int)1e9 + 7};
int n;
std::map<int, int> mp;
pii a[N]; // first：系数 second：指数
std::string str;
inline void split() {
size_t lst = 0;
size_t pos = std::min(str.find('+'), str.find('-'));
while (pos != std::string::npos) {
++n;
std::string s = str.substr(lst, pos - lst);
size_t zhi = s.find('^');
if (zhi != std::string::npos) {
// ax^b
if (s[0] == 'x') a[n].first = 1;
else a[n].first = stoi(s.substr(0, zhi - 1));
a[n].second = stoi(s.substr(zhi + 1));
} else { // 指数为 1
if (s[0] == 'x') a[n].first = 1;
else a[n].first = stoi(s.substr(0, s.size() - 1));
a[n].second = 1;
}
lst = pos;
pos = std::min(str.find('+', lst + 1), str.find('-', lst + 1));
}
// 处理常数项
a[++n].first = stoi(str.substr(lst));
a[n].second = 0;
// std::reverse(a + 1, a + n + 1);
}
inline lint qpow(lint a, lint b, int id) {
lint res = 1;
for (; b; b >>= 1) {
if (b & 1) (res *= a) %= MOD[id];
(a *= a) %= MOD[id];
}
return res;
}
inline lint calc(lint x, int id) {
lint res = 0;
for (int i = 1; i <= n; ++i) {
(res += a[i].first * qpow(x, a[i].second, id) % MOD[id]) %= MOD[id];
}
return res;
}
inline ull qpow(ull a, lint b) {
ull res = 1;
for (; b; b >>= 1) {
if (b & 1) res *= a;
a *= a;
}
return res;
}
inline ull calc2(lint x) {
ull res = 0;
for (int i = 1; i <= n; ++i) {
res += a[i].first * qpow(x, a[i].second);
}
return res;
}
inline bool check(lint x) { // 检查这个选项带入后是否可行
return (calc(x, 0) == 0) && (calc(x, 1) == 0) && (calc2(x) == 0);
}
inline void work(lint t) { // 除法
t = -t;
// 全部除以 x + t
for (int i = 1; i < n; ++i) {
// 取出 x^{a[i].second - 1}
a[i + 1].first -= a[i].first * t;
}
--n;
}
int main() {
freopen("decompose.in", "r", stdin);
freopen("decompose.out", "w", stdout);
std::cin >> str;
split(); // 将每一项分离
auto t = abs(a[n].first);
while (n > 1) {
for (lint i = 1; i <= t / i; ++i) {
if (t % i) continue;
// 存在 i, -i, a[1] / i, -a[1] / i
if (check(i)) {
work(i);
++mp[-i];
break;
}
if (check(-i)) {
work(-i);
++mp[i];
break;
}
if (check(t / i)) {
work(t / i);
++mp[-t / i];
break;
}
if (check(-t / i)) {
work(-t / i);
++mp[t / i];
break;
}
}
}
for (auto p : mp) {
std::cout << "(x";
if (p.first >= 0) std::cout << "+" << p.first << ")";
else std::cout << p.first << ")";
if (p.second > 1) std::cout << "^" << p.second;
}
std::cout << std::endl;
return 0;
}
