本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}