2013腾讯马拉松初赛 ACM 威威猫系列故事——因式分解

[c]代码库

/*

2013腾讯马拉松初赛第3场

1002 威威猫系列故事——因式分解
 
Time Limit: 0.2 Seconds   Memory Limit: 65536K
 
“春天来了，万物复苏，大地一片生机盎然，又到了动物们求偶的季节...”
周末的威威猫虽然眼睛盯着电视屏幕，但是思绪却停留在自己喜欢的数学问题上。
有人说孤独是可耻的，但是单身一人的威威猫并不孤独，随着对数学的深入学习，威威猫甚至很庆幸自己没有陷入儿女情长，因为他有喜爱的数学相伴，最近，他就在潜心研究因式分解问题。
在我们学习数学的过程中，经常需要把一个多项式进行因式分解，也就是把它写成乘积的形式，比如多项式x^2+3x+2分解因式的结果就是(x+1)(x+2)。这个因式一眼就能看出来，但是当x的指数更高时，就不太容易分解了。
现在，威威猫就是在研究如何编写程序来实现对多项式的因式分解。
Input
输入第一行是一个整数T(T<=50)，表示测试数据的组数；
接下来是T行字符串表示T个测试用例，每行1个数学多项式，多项式长度不会超过100个字符，每个多项式表示形式如下：	A[1]x^P[1]+A[2]x^P[2]+...+A[m]x^P[m]
其中0<=P[i]<=5，A[i]表示x^P[i]的系数，A[i]=0时直接简写为0,A[i]=1和-1时分别简写为x^P[i]与-x^P[i]，P[i]=0和1时分别简写为A[i]与A[i]x，且同一指数r的对应项系数之和的绝对值不超过1000, 每行中没有多余空格，具体格式可参考Sample Input。
Output
对于每组测试数据，首先输出Case #X: ，X代表多项式编号，从1开始计数，然后输出因式分解的结果，分解结果的表示形式规定如下：
(x+B[1])(x+B[2])...(x+B[m])
其中，B[1]<=B[2]<=...<=B[m],若B[i]=0则不加括号直接简写为x，如果无法表现成上述格式，则输出"-1"。
具体可参考Sample Output。
Sample Input
4
x
x+1
-2x^2+x^2+x^3
2x+2

Sample Output
Case #1: x
Case #2: (x+1)
Case #3: (x-1)xx
Case #4: -1
 
*/

/*
解题报告：

这题的话初看很难，一些头续也没有。
仔细研究会发现，p[i]比较小，最多是5，也就是说，分解出来的因式最多5个。
每一个因子是形如(x+b[i])也就是说确定b[i]就可以了。
题目中说了每一项系数绝对值不超过1000，我们考虑最后一项常数项
常数项是由b[1]*b[2]*b[3]*b[4]*...*b[5]

也就是说这些b[i]是常数项的因子，而且乘起来要等于常数项。

常数项不大，我们可以枚举常数项的因子。

然后去验证。

之儿有一个小问题就是，如果常数项为0怎么办，这种情况下的话，也就是说大家可以提出一个x来，如果还是0，就再提x。
对最后常数项不为0的进行分解就行了。
*/


#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std ;
const int MAX = 110;
const int INF = 100000000;
char s[MAX];
int c[6];
struct BigNum {
    int dig[6];
    int len;
    void clr() {
        len = 1;
        memset(dig, 0, sizeof(dig));
    }
};

bool dig(char x) {
    return x >= '0' && x <= '9';
}
BigNum f;
BigNum Div(BigNum a, int b) {
    int i;
    int t;
    BigNum ret;
    ret.clr();
    for(i = a.len - 1; i >= 1; i--) {
        t = a.dig[i];
        ret.dig[i - 1] += t;
        a.dig[i] = 0;
        a.dig[i - 1] -= b * t;
    }
    ret.len = -1;
    if(a.dig[0] != 0)return ret;

    for(i = 5; i >= 0 && ret.dig[i] == 0; i--);

    ret.len = i + 1;
    return ret;
}
int calc() {
    int i;
    if(f.dig[0] == 0) {
        for(i = 0; i + 1 < f.len; i++) {
            f.dig[i] = f.dig[i + 1];
        }
        f.len--;
        return 0;
    }
    for(i = -1000; i <= 1000; i++) {
        if(i == 0 && f.dig[0] != 0)continue;
        else if(i != 0 && f.dig[0] % i != 0)continue;

        BigNum tmp = Div(f, i);
        if(tmp.len == -1)continue;
        f = tmp;
        return i;
    }
    return INF;
}
int main () {
    int T, CS = 1;
    int len;
    int tmp, p;
    int i;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s);
        memset(c, 0, sizeof(c));
        len = strlen(s);
        int left, right;
        for(i = 0; i < len; i++) {
            if(s[i] == 'x') {
                //计算有边
                if(s[i + 1] == '^') {
                    right = i + 2;
                    p = s[right] - '0'; //最多是5，取1为就行了
                } else {
                    right = i;
                    p = 1;
                }

                int ten = 1;

                left = i - 1;
                tmp = 0;
                while(left >= 0 && dig(s[left])) {
                    tmp += (s[left] - '0') * ten;
                    ten *= 10;
                    left--;
                }

                if(tmp == 0)tmp++;

                if(left >= 0 && s[left] == '-') {
                    tmp = -tmp;
                    left--;
                }

                c[p] += tmp;

                for(left++; left <= right; left++) {
                    s[left] = 1;
                }
            }
        }
        //puts("zz");
        for(i = 0; i < len; i++) { //求剩下的常数
            if(s[i] == '-' || dig(s[i])) {
                int sign = 1;
                tmp = 0;
                if(s[i] == '-') {
                    sign = -1;
                    i++;
                }
                while(i < len && dig(s[i])) {
                    tmp = tmp * 10 + s[i] - '0';
                    i++;
                }
                i--;
                c[0] += tmp * sign;
            }
        }
        int maxc = 5;
        while(maxc >= 0 && c[maxc] == 0) {
            maxc--;
        }
        printf("Case #%d: ", CS++);
        if(maxc <= 0) {
            puts("-1");
            continue;
        } else if(c[maxc] != 1) {
            puts("-1");
            continue;
        }
        //puts("");for(i=0;i<=maxc;i++)printf("x[%d]=%d\n",i,c[i]);
        int ans[6];

        f.clr();
        memcpy(f.dig, c, sizeof(c));
        f.len = maxc + 1;
        for(i = 0; i < maxc; i++) {
            ans[i] = calc();
            if(ans[i] == INF)break;
        }
        if(i < maxc) {
            puts("-1");
        } else {
            sort(ans, ans + maxc);
            for(i = 0; i < maxc; i++) {
                if(ans[i] == 0)putchar('x');
                else if(ans[i] < 0)printf("(x%d)", ans[i]);
                else printf("(x+%d)", ans[i]);
            }
            puts("");
        }
    }
    return 0 ;
}