此题不难，但我就是RE，搞不懂啊。。。郁闷。
说下基本算法吧，只要留意到要分解的因式是（x+ai）..的形式,x前是系数为1的，而且，它们的绝对值在1000以内，于是，好办了。只要枚举(x+k)中的k就可以了。然后按照除法得出余下的因式就OK了。注意结束的条件，最高次必须系数是1,结束后0次的也应当是1.
我觉得我RE这么多次很可怜。。。
)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
struct Multi{
int coef[10];
int len_pow;
void init(){
len_pow=-1;
memset(coef,0,sizeof(coef));
}
};
Multi f,g;
char str[150],ts[150];
vector<int>ans;
void deal(char s[]){
int index=0,len=strlen(s);
for(index;index<len;index++){
if(s[index]=='x')
break;
}
int cof=0,sig=1;
for(int i=0;i<index;i++){
if(s[i]=='-') sig=-1;
else{
cof=cof*10+s[i]-'0';
}
}
if(cof==0) cof=1;
cof=cof*sig;
int _pow=0;
for(int i=index+2;i<len;i++){
_pow=_pow*10+s[i]-'0';
}
if(_pow==0&&index!=len) _pow=1;
f.coef[_pow]+=cof;
}
bool Div(int k){
g.init();
for(int i=f.len_pow;i>=1;i--){
g.coef[i-1]=f.coef[i]-k*g.coef[i];
// if(k==-1) cout<<i-1<<" "<<g.coef[i-1]<<" "<<k<<endl;
}
for(g.len_pow=f.len_pow-1;g.len_pow>=0;g.len_pow--)
if(g.coef[g.len_pow]) break;
if(g.coef[0]*k!=f.coef[0]) return false;
if(g.len_pow>=0&&g.coef[g.len_pow]!=1) return false;
f=g;
if(f.len_pow==0&&f.coef[f.len_pow]==1) f.len_pow=-1;
return true;
}
bool slove(){
ans.clear();
while(f.coef[0]==0&&f.len_pow>=0){
ans.push_back(0);
for(int i=0;i<f.len_pow;i++){
f.coef[i]=f.coef[i+1];
}
f.coef[f.len_pow]=0;
f.len_pow--;
}
// if(f.len_pow<0) return false;
if(f.len_pow==0) return true;
for(int i=-1000;i<=1000;i++){
if(i==0) continue;
if(i!=0&&f.coef[0]%i!=0) continue;
if(Div(i)){
ans.push_back(i);
i--;
if(f.len_pow==-1) return true;
}
}
return false;
}
int main(){
int T,t=0;
scanf("%d",&T);
while(T--){
scanf("%s",str);
char *p;
p=strtok(str,"+");
f.init();
while(p){
strcpy(ts,p);
deal(ts);
p=strtok(NULL,"+");
}
for(int i=5;i>=0;i--)
if(f.coef[i]){
f.len_pow=i;
break;
}
printf("Case #%d: ",++t);
if(f.len_pow<0){
puts("-1");
continue;
}
if(f.coef[f.len_pow]!=1){
puts("-1");
continue;
}
// for(int i=0;i<=5;i++) cout<<i<<" "<<f.coef[i]<<endl;
bool flag=slove();
if(!flag) { puts("-1"); continue;}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
if(ans[i]==0)
printf("x");
else if(ans[i]>0)
printf("(x+%d)",ans[i]);
else printf("(x%d)",ans[i]);
puts("");
}
return 0;
}
贴个别人的。http://hi.baidu.com/chenwenwen0210/item/692b312f5ab859312b0f1cc8
#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
",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 ;
}
终于过了，我还以为是用+作分隔符呢。看了别人的才发现不是的，被题目坑了一晚。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
struct Multi{
int coef[10];
int len_pow;
void init(){
len_pow=-1;
memset(coef,0,sizeof(coef));
}
};
Multi f,g;
char str[150],ts[150];
vector<int>ans;
int c[6];
bool dig(char x){return x>='0'&&x<='9';}
void deal(char s[]){
int tmp,p,i;
memset(c,0,sizeof(c));
int 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++)//Çóʣϵij£Êý
{
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;
}
}
}
bool Div(int k){
g.init();
for(int i=f.len_pow;i>=1;i--){
g.coef[i-1]=f.coef[i]-k*g.coef[i];
// if(k==-1) cout<<i-1<<" "<<g.coef[i-1]<<" "<<k<<endl;
}
for(g.len_pow=f.len_pow-1;g.len_pow>=0;g.len_pow--)
if(g.coef[g.len_pow]) break;
if(g.coef[0]*k!=f.coef[0]) return false;
if(g.len_pow>=0&&g.coef[g.len_pow]!=1) return false;
f=g;
if(f.len_pow==0&&f.coef[f.len_pow]==1) f.len_pow=-1;
return true;
}
bool slove(){
ans.clear();
while(f.coef[0]==0&&f.len_pow>=0){
ans.push_back(0);
for(int i=0;i<f.len_pow;i++){
f.coef[i]=f.coef[i+1];
}
f.coef[f.len_pow]=0;
f.len_pow--;
}
// if(f.len_pow<0) return false;
if(f.len_pow==0) return true;
for(int i=-1000;i<=1000;i++){
if(i==0) continue;
if(i!=0&&f.coef[0]%i!=0) continue;
if(Div(i)){
ans.push_back(i);
i--;
if(f.len_pow==-1) return true;
}
}
return false;
}
int main(){
int T,t=0;
scanf("%d",&T);
while(T--){
scanf("%s",str);
/* char *p;
p=strtok(str,"+");
f.init();
/* while(p){
strcpy(ts,p);
deal(ts);
p=strtok(NULL,"+");
}*/
f.init();
deal(str);
memcpy(f.coef,c,sizeof(c));
for(int i=5;i>=0;i--)
if(f.coef[i]){
f.len_pow=i;
break;
}
printf("Case #%d: ",++t);
if(f.coef[f.len_pow]!=1){
puts("-1");
continue;
}
// for(int i=0;i<=5;i++) cout<<i<<" "<<f.coef[i]<<endl;
bool flag=slove();
if(!flag) { puts("-1"); continue;}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
if(ans[i]==0)
printf("x");
else if(ans[i]>0)
printf("(x+%d)",ans[i]);
else printf("(x%d)",ans[i]);
puts("");
}
return 0;
}