#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define MAX 10

// 儲存每一項的結構
struct Term {
    int coefficient;  // 係數
    int exponent;     // 指數
};

//計算可能的解 
void count_root(int arrR[],int arrL[],int ans[],int countF,int countL ,int *len_ans){
  int i , j ,k=0;
  for(i=0;i<countF;i++){
    for(j=0;j<countL;j++){
      if((arrL[j]%arrR[i])==0){
        ans[k++] = arrL[j]/arrR[i];
      }	
    }		
  }*len_ans =k;
}

//將最高次係數與常數的因數加入負號 
void plus_root_negative(int arr[],int *len){
  int i , j=0;
  for(i=0;i<*len;i++){
    arr[*len+j]=-(arr[i]);
    j++;
  }*len=*len+j;
}

//找最高次係數與常數的因數 
void find_factor(int P[], int facF[], int facL[], int len, int *count1, int *count2) {
    int i, j = 0;
    for (i = 1; i <= abs(ceil(P[2] / 2)); i++) {  
        if (abs(P[2]) % i == 0) {
            facF[j++] = i;
        }
    }
    facF[j++] = fabs(P[2]);  // 包含 P[2] 本身
    *count1 = j;  // 設定找到的因數個數

    j = 0;
    for (i = 1 ; i <= abs(ceil(P[len-1] / 2)); i++) {  
        if (abs(P[len-1]) % i == 0) {
            facL[j++] = i;
        }
    }
    facL[j++] = fabs(P[len-1]);  // 包含 P[len] 本身
    *count2 = j;  // 設定找到的因數個數
}

//把根代入方程式
int evaluate_polynomial(int A[], int len, int x) {
    int result = 0;
    int i;
    for (i = 2; i < len; i += 2) {
        result += A[i] * pow(x, A[i-1]);
    }
    return result;
}

//把根代入方程式 求答案 
void Substitute(int len_root, int arr[], int ans[], int A[], int len_A, int *len_ans) {
    int i, j = 0, result;
    for (i = 0; i < len_root; i++) {
        result = evaluate_polynomial(A, len_A, arr[i]);
//        printf("x = %d, result = %d\n", arr[i], result);
        if (result == 0) {
            ans[j++] = arr[i];
        }
    }
    *len_ans = j;
}

//移除重複的答案 
void remove_duplicates(int A[], int len, int new_A[], int *new_len) {
    int i, j, k;
    int is_duplicate;

    *new_len = 0; // 初始化新的陣列長度為0

    // 遍歷原始陣列
    for (i = 0; i < len; i++) {
        is_duplicate = 0; // 假設當前元素沒有重複

        // 檢查是否在結果陣列中出現過
        for (j = 0; j < *new_len; j++) {
            if (A[i] == new_A[j]) {
                is_duplicate = 1; // 如果發現重複，標記為1
                break;
            }
        }

        // 如果沒有重複，將其加入結果陣列
        if (!is_duplicate) {
            new_A[*new_len] = A[i];
            (*new_len)++; // 更新結果陣列的長度
        }
    }
}

//顯示方程式
void output(int *A,int len){
  int i ,j,flag_Max=0,flag_x=0, flag_const=0 ;
  printf("\n方程式p(x)= ");
  //A[i]為指數 A[i+1]為係數
  //i從1開始數 一次讀取一個指數與係數 
  //len為A[]的長度  
  //flag_Max 為最高次項的旗標
  //flag_x 為1次項的旗標	
  //flag_const 為常數項的旗標	
  
  for(i=1;i<len;i++){
  	if(A[i]==1){ //若指數項=1 觸發一次項旗標 
  		flag_x=1; 
	}else if(A[i]==0){ //若指數項=0  觸發常數項旗標
		flag_const=1;
	}
	
     if(flag_Max==0){ //第一項 
     	if( A[i]>1 && A[i+1]!=1){ //指數大於1 係數不等於1 
     		printf("%dx^%d",A[i+1],A[i]);
		 }else if(A[i]>1 && A[i+1]==1){
		 	printf("x^%d",A[i]); //指數大於1 係數等於1 
		 }else if(A[i]==1 && A[i+1]!=1){ //指數=1 係數不等於1      
		 	printf("%dx",A[i+1]);
		 }else if(A[i]==0 && A[i+1]!=1){ //指數=0 係數不等於1 
		 	printf("%d",A[i+1]);
		 }else if(A[i]==1 && A[i+1]==1){ //指數=1 係數=1 
		 	printf("x");
		 }else if(A[i]==1 && A[i+1]==-1){ //指數=1 係數=-1 
		 	printf("-x");
		 }flag_Max = 1; //高次項的旗標=1
  	}else if(flag_x == 1 && flag_const==0){// x一次項
  		if(A[i+1]>0){ // x一次項為正 
  			if(A[i+1]==1){
  				printf("+x",A[i+1]); 
			}else{
				printf("+%dx",A[i+1]); 
			}	 
		}else if(A[i+1]<0){ //x一次項為負 
			if(A[i+1]==-1){
				printf("-x",A[i+1]);
			}else{
				printf("%dx",A[i+1]);
			}	
		} 
  	}else if(flag_const==1){  // 常數項
  		if(A[i+1]>0){ //常數項>0 
			printf("+%d",A[i+1]);
		}else if(A[i+1]<0) { //常數項<0  
			printf("%d",A[i+1]);
		}
	}else if(flag_Max==1 && flag_x==0 && flag_const==0) { //多項式中間的部分 
		if(A[i+1]>0){ //係數>1
			if(A[i+1]==1){ //係數=1 
  				printf("x^%d",A[i]);
			}else{ //係數不等於1  
				printf("+%dx^%d",A[i+1],A[i]);
			}
		}else if(A[i+1]<0){ //係數<1
			if(A[i+1]==-1){ //係數=-1 
				printf("-x^%d",A[i]);
			}else{ //係數不等於1   
				printf("%dx^%d",A[i+1],A[i]);
				}	
			}	
		}i++;
	}
	printf("\n");
}

int main() {
    int i,j, len, countF, countL, len_root, len_ans ,len_new ;  
    char input[100];
    struct Term terms[MAX];
    int term_count = 0;
	printf("\n*** 解多項式之整數根 ***\n");

    // 1. 讀取輸入
    printf("\n請輸入多項式： ");
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;  // 移除換行符

    // 2. 處理每一項
    char *ptr = input;
    while (*ptr && term_count < MAX) {
        int coef = 0, exp = 0;
        int is_negative = 0;

        // 檢查負號
        if (*ptr == '-') {
            is_negative = 1;
            ptr++;
        } else if (*ptr == '+') {
            ptr++;
        }

        // 跳過空白字符
        while (isspace(*ptr)) ptr++;

        // 3. 解析每一項
        if (sscanf(ptr, "%dx^%d", &coef, &exp) == 2) {
            // 完整的 ax^b 形式
            ptr = strchr(ptr, '^') + 1;
        } else if (sscanf(ptr, "%dx", &coef) == 1) {
            // ax 形式，指數為1
            exp = 1;
            ptr = strchr(ptr, 'x') + 1;
        } else if (sscanf(ptr, "x^%d", &exp) == 1) {
            // x^b 形式，係數為1
            coef = 1;
            ptr = strchr(ptr, '^') + 1;
        } else if (strncmp(ptr, "x", 1) == 0) {
            // 單獨的 x，係數為1，指數為1
            coef = 1;
            exp = 1;
            ptr++;
        } else {
            // 假設是常數項
            sscanf(ptr, "%d", &coef);
            exp = 0;
            while (isdigit(*ptr)) ptr++;
        }

        // 4. 處理負號
        if (is_negative) {
            coef = -coef;
        }

        // 5. 儲存結果
        terms[term_count].coefficient = coef;
        terms[term_count].exponent = exp;
        term_count++;

        // 輸出當前項的信息（用於調試）
//        printf("項 %d: 係數 = %d, 指數 = %d\n", term_count, coef, exp);

        // 移動到下一個 '+' 或 '-' 符號
        while (*ptr && *ptr != '+' && *ptr != '-') ptr++;
    }

//	int *A = (int*)malloc(((term_count*2)+1) * sizeof(int)) ;
  len = ((term_count*2)+1);
  int A[len];

//	printf("term_count=%d\n",term_count);
//	printf("((term_count*2)+1)=%d\n",((term_count*2)+1));
//	printf("sizeof(A)=%d\n",sizeof(A));

  A[0]=term_count;
  for (i = 1 , j=0 ; i < term_count*2 ; i++ , j++ ){
    A[i]= terms[j].exponent;
    A[i+1]= terms[j].coefficient;
//		printf("A[%d]=%d\n",i,terms[j].exponent);
//		printf("A[%d]=%d\n",i+1,terms[j].coefficient);
    i++;
  }

//	printf("A[]= ");
//	for (i = 0; i < len; i++) {
//		printf(" %d ",A[i]);
//    }
//    printf("\n");

// 1x^3-2x^2-1x^1+2x^0  
// 1x^5-1x^3-1x^2-1x^1+1x^0
// 1x^2-100x^0 1x^1+100x^0
// 3x^4+9x^3-198x^2+156x^1+360x^0

    int facF[30], facL[30], root[60], ans[60] ,new_ans[8];
    find_factor(A, facF, facL, len, &countF, &countL);

//    printf("最高次方項因數為: ");
//    for (i = 0; i < countF; i++) {
//        printf("%d ", facF[i]);
//    }
//    printf("\n常數項因數為: ");
//    for (i = 0; i < countL; i++) {
//        printf("%d ", facL[i]);
//    }
//    printf("\n");

    count_root(facF, facL, root, countF, countL, &len_root);  
    plus_root_negative(root, &len_root);

//    printf("可能的根：\n");
//    for (i = 0; i < len_root; i++) {
//        printf("root[%d] = %d\n", i, root[i]);
//    }
  
  //輸出多項式
  output(A,len);
  // 計算可能的解
  Substitute(len_root, root, ans, A, len, &len_ans); 

  //移除多餘的解 
  remove_duplicates(ans,len_ans,new_ans,&len_new); 

  if(len_new==0){
      printf("\n整數根不存在");
      return 1 ;
  }

    if(len_new>0){
    printf("\n解得整數根為：");
        for (i = 0; i < len_new; i++) {
            if(i<len_new-1) {
            printf("%d、",new_ans[i]);
        }else if(i==len_new-1) {
          printf("%d", new_ans[i]);
          }
        }
    }
    return 0;
}