题意：给定一个多项式，对其进行因式分解。
解法：由于多项式每一项系数绝对值不超过1000，由于最后解的形式为(x-a)(x-b)(x-c)(x-d)(x-e)其中a*b*c*d*e一定是最后的常数项系数，因此a, b, c, d, e的取值范围都在[-1000, 1000]内，因此枚举所有的根，剩下的就是重根的时候该怎么办？一个解决办法就是对原多项式进行求导，如果一个根t是f(x)的K重根的话，那么t一定是f(x)'的K-1重根。该题的字符串处理我没写好，后面调了很久。还有就是由于有5次方存在，因此代入时使用long long计算。
代码如下：
#include#include #include #include #include #include using namespace std;char str[500];int seq[10];long long _pow(int a, int b) { long long ret = 1; for (int i = 0; i < b; ++i) { ret *= a; } return ret;}int jiechen[10] = { 1, 1, 2, 6, 24, 120};void qiudao(int *rec, int k) { for (int i = k; i <= 5; ++i) { rec[i-k] = jiechen[i] / jiechen[i-k] * seq[i]; }}bool judge(int rec[], int x) { long long sum = 0; for (int i = 0; i <= 5; ++i) { sum += 1LL * rec[i] * _pow(x, i); } return sum == 0;}void gao(char ts[]) { int len = strlen(ts); int p = -1, a, b; for (int i = 0; i < len; ++i) { if (ts[i] == 'x') { if (isdigit(ts[i-1])) { ts[i] = '\0'; } else { ts[i] = '1'; } p = -2; } else if (ts[i] == '^') { ts[i] = '\0'; p = i+1; } } a = atoi(ts); if (!a && p != -1) a = 1; if (p == -1) { b = 0; } else if (p == -2) { b = 1; }else { b = atoi(ts+p); } seq[b] += a;}void solve() { vector v; int cnt = 0; memset(seq, 0, sizeof (seq)); char ts[50], *p; p = strtok(str, "+"); while (p) { strcpy(ts, p); gao(ts); p = strtok(NULL, "+"); } for (int i = 5; i >= 0; --i) { if (seq[i] != 0) { cnt = i; break; } } for (int i = -1000; i <= 1000; ++i) { for (int j = 0; j < cnt; ++j) { int rec[10] = { 0}; qiudao(rec, j); if (judge(rec, i)) { v.push_back(i); } else { break; } } } //x^4-x^2 //x^4-7x^3+18x^2-20x+8 //x^3-13x^2+55x-75 //x^2+5x^2-6x^2+x^2+2x-20x+30x-10x+8-7 //x^5-10x^4+39x^3-74x^2+68x-24 //以上都是能够分解的式子 if (v.size() != cnt || seq[cnt] != 1 || cnt == 0) { printf("-1\n"); } else { sort(v.begin(), v.end()); for (int i = v.size()-1; i >= 0; --i) { if (v[i] < 0) { printf("(x+%d)", -v[i]); } else if (v[i] == 0) { printf("x"); } else { printf("(x-%d)", v[i]); } } puts(""); }}int main() { int T, ca = 0; scanf("%d", &T); while (T--) { scanf("%s", str); int len = strlen(str); for (int i = 0; i < len; ++i) { if (str[i] == '-') { for (int j = len-1; j >= i; --j) { str[j+1] = str[j]; } str[i] = '+'; len += 1; ++i; str[len] = '\0'; } } printf("Case #%d: ", ++ca); solve(); } return 0;}