可解的算法太多了，采用的算法是试x的值。注意题目的输入x^3-2x^2不会写成x^3+-2x^2。一直RE在这儿。
/* 4516 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define LL long long const int maxl = ;
const int maxn = ;
char s[maxl], ss[maxl];
int A[][maxn], B[maxn], B_[maxn];
int c[maxn], cn; bool check() {
memset(B, , sizeof(B));
B[] = ;
B[] = c[]; rep(i, , cn) {
memset(B_, , sizeof(B_));
rep(j, , maxn)
B_[j] += B[j-];
rep(j, , maxn)
B_[j] += B[j] * c[i];
memcpy(B, B_, sizeof(B));
} rep(i, , maxn) {
if (A[][i] != B[i])
return false;
} return true;
} bool judge(int p, int i, int x) {
LL ret = , base = ; for (int j=; j<=i; ++j) {
ret += A[p][j] * base;
base *= x;
} return ret == ;
} void reduce(int p, int i, int x) {
int q = p + ; memcpy(B, A[p], sizeof(B));
for (int j=i; j>; --j) {
A[q][j-] = B[j];
B[j-] -= B[j] * x;
}
} bool solve() {
// init parameter
int i = , a = , p = , q;
int cnt = ;
bool neg = false, flag = false; memset(A, , sizeof(A));
cn = ; while () {
if (s[i]=='+' || s[i]=='\0') {
if (neg)
a = -a;
if (flag && p==)
p = ;
A[][p] += a;
neg = false;
flag = false;
p = ;
a = ;
cnt = ;
} else if (s[i] == '-') {
neg = true;
} else if (s[i] == 'x') {
if (cnt == )
a = ;
flag = true;
} else if (s[i] == '^') {
;
} else {
if (flag)
p = p*+s[i]-'';
else
a = a*+s[i]-'';
++cnt;
}
if (s[i] == '\0')
break;
++i;
} p = , q = ;
int x, xx; while () {
for (i=; i>=; --i) {
if (A[p][i] != )
break;
}
if (i < )
break;
if (A[p][i] != )
return false;
if (i == )
break; a = A[p][];
if (a == ) {
c[cn] = ;
while (i > ) {
A[q][i-] = A[p][i];
--i;
}
flag = true;
} else if (a > ) {
flag = false;
for (x=; x*x<=a; ++x) {
if (a%x == ) {
if (judge(p, i, -x)) {
reduce(p, i, x);
flag = true;
c[cn] = x;
break;
} else if (judge(p, i, x)) {
reduce(p, i, -x);
flag = true;
c[cn] = -x;
break;
}
xx = a/x;
if (xx != x) {
if (judge(p, i, -xx)) {
reduce(p, i, xx);
flag = true;
c[cn] = xx;
break;
} else if (judge(p, i, xx)) {
reduce(p, i, -xx);
flag = true;
c[cn] = -xx;
break;
}
}
}
}
} else {
flag = false;
a = -a;
for (x=; x*x<=a; ++x) {
if (a%x == ) {
if (judge(p, i, x)) {
reduce(p, i, -x);
c[cn] = -x;
flag = true;
break;
} else if (judge(p, i, -x)) {
reduce(p, i, x);
c[cn] = x;
flag = true;
break;
}
xx = a/x;
if (xx != x) {
if (judge(p, i, xx)) {
reduce(p, i, -xx);
flag = true;
c[cn] = -xx;
break;
} else if (judge(p, i, -xx)) {
reduce(p, i, xx);
flag = true;
c[cn] = xx;
break;
}
}
}
}
} if (!flag)
return false; ++cn;
++p;
++q;
} return cn>;
} void change() {
int l = ;
int i = ;
int len = strlen(s); while (i < len) {
if (s[i] == '-') {
if (i && s[i-]!='+')
ss[l++] = '+';
}
ss[l++] = s[i++];
} ss[l] = '\0';
strcpy(s, ss);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t;
bool flag; scanf("%d", &t);
rep(tt, , t+) {
scanf("%s", s);
change();
flag = solve();
printf("Case #%d: ", tt);
if (flag) {
sort(c, c+cn);
rep(i, , cn) {
if (c[i] == )
printf("x");
else if (c[i] > )
printf("(x+%d)", c[i]);
else
printf("(x-%d)", -c[i]);
}
putchar('\n');
#ifndef ONLINE_JUDGE
if (!check())
puts("wrong");
#endif
} else {
puts("-1");
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
测试数据和答案。
from random import randint
import shutil def GenEle(k):
if k == 0:
return "x"
elif k>0:
return "(x+%d)" % (k)
else:
return "(x-%d)" % (-k) def GenLine():
src, ans = "", ""
k = randint(1, 5)
L = []
for i in xrange(k):
x = randint(-10, 10)
L.append(x)
L = sorted(L)
ans = "".join(map(GenEle, L))
a = [0 for i in xrange(6)]
a[1] = 1
a[0] = L[0]
for i in xrange(1, k):
b = [0 for j in xrange(6)]
for j in xrange(1, 6):
b[j] += a[j-1]
for j in xrange(0, 6):
b[j] += a[j] * L[i]
a = b
i = 5
while i>=0:
if a[i]>0:
break
i -= 1
srcList = []
while i>=0:
line = ""
if a[i] < 0:
line += "-"
a[i] = -a[i]
if i==0 or a[i]!=1:
line += str(a[i])
if i==1:
line += "x"
elif i>1:
line += "x^%d" % i
i -= 1
srcList.append(line)
src = "+".join(srcList)
return src, ans def GenDataIn():
bound = 10**2
ansList = []
with open("data.in", "w") as fout:
t = 50
fout.write("%d\n" % (t))
for tt in xrange(t):
line, ans = GenLine()
fout.write(line + "\n")
ansList.append(ans)
with open("F:\code_today\data.in", "w") as fout:
for i,ans in enumerate(ansList):
line = "Case #%d: %s\n" % (i+1, ans)
fout.write(line) def MovDataIn():
desFileName = "F:\workspace\cpp_hdoj\data.in"
shutil.copyfile("data.in", desFileName) if __name__ == "__main__":
GenDataIn()
MovDataIn()