信友队-因式分解

wflengxuenong · 2024-10-24 11:31:54 · 个人记录

/*
信友队：2024csp-j考前模拟赛 
x^6+2x^5-8x^4-10x^3+19x^2+8x-12
(x-2)(x-1)^2(x+1)(x+2)(x+3)

   anxn+a[n-1]x^(n-1)+....+a1x^1+a0
=(b[n-1]x^(n-1)+b[n-2]x^[n-2]...b1x+b0)*(x+c)   c是a0的因子
正向推导 
an=b[n-1]=1;                     b[n-1]=1
a[n-1]=c*b[n-1]+b[n-2]           b[n-2]=a[n-1]-c*b[n-1]
....

逆向推到
b0=a0/c
a1=b0*c+b1   b1=a1-b0*c 

*/ 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 25;
ll n,cnt[N+5],a[N],na[N],nb[N],b[N];
string s;
bool check(int cp){

    b[n]=0;b[n-1]=1;
    for(int i=n-1;i>=1;i--){
        b[i-1]=a[i]-cp*b[i];
    }

    if(b[0]*cp!=a[0])return 0;
    return 1;
}
int main(){

    cin>>s;
    if(isdigit(s[0])){
        cout<<s;
        return 0;
    }
    int lstB=-1,len=s.length();
    for(int i=0,tmp;i<len;i++){
        if(s[i]=='x'){//处理x的系数和指数 
            if(!i){//i==0,直接向后找指数 
                if(s[i+1]!='^'){
                    tmp=1;
                }else{
                    i+=2;
                    tmp=0;
                    while(isdigit(s[i])){
                        tmp=tmp*10+s[i]-'0';
                        i++;
                    }
                    if(!tmp)tmp=1;
                }
                a[tmp]=1;
                n=tmp;
            }else{//向前找对应的系数 tp
                int tp=0,tmpi=i;
                i--;
                while(isdigit(s[i])){
                    i--;    
                }
                int flg=(s[i]=='-');
                i++;
                while(isdigit(s[i])){
                    tp=tp*10+s[i]-'0';
                    i++;
                }
                if(flg)tp*=-1;
                if(s[i+1]!='^'){//向后找对应的指数 
                    tmp=1;
                }else{
                    i+=2;
                    tmp=0;
                    while(isdigit(s[i])){
                        tmp=tmp*10+s[i]-'0';
                        i++;
                    }
                }

                a[tmp]=tp;
            }
        }
    }
    int ii=len-1;//处理常数项 
    while(isdigit(s[ii]))ii--;
    bool flg=(s[ii]=='-');
    int tmp=0;
    ii++;
    while(isdigit(s[ii])){
        tmp=tmp*10+s[ii]-'0';
        ii++;
    }
    if(flg)tmp*=-1;
    a[0]=tmp;
    vector<int>vec;
    for(int i=1;i*i<=abs(a[0]);i++){//处理常数项的因子 
        if(abs(a[0])%i==0){
            vec.push_back(i);
            if(i*i!=abs(a[0]))vec.push_back(abs(a[0])/i);
        }
    }
    sort(vec.begin(),vec.end());

    vector<pair<int,int> >ans;
    int siz=vec.size();
    for(int i=0;i<siz;i++){
        int pos=vec[i]*-1;
        int cnt=0;
        while(check(pos)){//找因子 
            for(int i=n;i>=0;i--)a[i]=b[i];
            cnt++;
            while(!a[n]&&n>=1)n--;
        }
        if(cnt)ans.push_back({pos,cnt});
        pos=vec[i];
        cnt=0;
        while(check(pos)){//找到对应的的指数 
            for(int i=n;i>=0;i--)a[i]=b[i];
            cnt++;
            while(!a[n]&&n>=1)n--;
        }
        if(cnt)ans.push_back({pos,cnt});
    }   
    sort(ans.begin(),ans.end());
    for(auto i:ans){
        if(i.second==1){
            cout<<"(x"<<(i.first>0?"+":"")<<i.first<<")";
        }else{
            cout<<"(x"<<(i.first>0?"+":"")<<i.first<<")"<<"^"<<i.second;
        }
    }
    return 0;
}