/*
Program: poly-integer-root-v2.c (Report comments/bugs to chikh@yuntech.edu.tw)
Function: 計算多項式的整數根，程式接受鍵盤輸入的多項式，輸出結果把輸入的多項式以最精簡的形式呈現(係數與指數若為1可省略)
	，且需顯示解得的整數根；若整數根不存在，則顯示訊息告知
Notes: 
	1) 本程式透過鍵盤讀入多項式，而poly-integer-root-v1.c把多項式直接設於程式內，彈性較受限
	2) 程式接受鍵盤輸入的形式可為 
		1x^2-100x^0
		1x^3-2x^2-1x^1+2x^0
		1x^3-7x^2+4x^1+12x^0
		1x^4+3x^3-66x^2+52x^1+120x^0
		3x^4+9x^3-198x^2+156x^1+360x^0
*/

#include <stdio.h>	/* for scanf(), sscanf() */
#include <stdlib.h>	/* for malloc(), abs() */
#include <math.h>	/* for pow() */

#define MAX 256

void compact(char str[]) /* 移除str當中的空白，使變得緊實 */ 
{
    int i, j;
    
    for (i = j = 0; str[i]; i++, j++) {
    	for (; str[i]==' '; i++);
    	str[j] = str[i];
	}
	str[j] = '\0';
	printf("\n移除空白後的字串：%s\n",str);
}

int readPoly(int p[])	/* 讀入運算式字串，把各項之指數與係數分別儲存於陣列，回傳非零項個數 */ 
{
	int  i = 1, argCount;
	char str[MAX];
	
	gets(str); 		/* 建議改用 fgets(str,MAX,stdin) 以避免造成輸入資料過長而造成鍵盤緩衝區爆掉產生錯誤 */ 
	compact(str); 	/* 移除str當中的空白，使變得緊實 */ 
	
	do { 
    	if ((argCount=sscanf(str,"%dx^%d%s",&p[i+1],&p[i],str))==2) break; /* 從str只讀到2個數據，之後再也沒有東西可消化(轉存入str)，意味字串已讀盡，將跳離迴圈 */ 
		if (argCount == 1) {	/* 最末項讀到常數表示式，譬如 3 或 -5 (未寫成3x^0仍能處理) */
    		p[i] = 0;
    		break;
		}
      	i += 2;
  	} while (1); 
	
	return (p[0] = (i+1)/2);	/* 回傳非零項個數 */
}

int findRoot(int p[], int q[]) /* 找根，所得解存入q[]，回傳根的個數 */ 
{
	int r, c = 0, i, j, k, sum;
	int sign[2] = {1,-1};
	
	if (p[2*p[0]]%p[2] != 0) return 0;	/* 最末項的係數不能被最高階項的係數整除，則不存在整數解 */ 
	
	r = abs(p[2*p[0]]/p[2]);  		/* 正規化後，最高階項之係數為1，最末項的係數為r */ 
	for (i = 1; i <= r; i++) {		/* 考慮能整除r的因數i，須注意正負號 */ 
		if (r%i != 0) continue;		/* 不能整除r的i將略過，繼續考慮下一個i */ 
		for (j = 0; j < 2; j++) {	/* j為0，代表考慮+i的情境；j為1，代表考慮-i的情況 */
			for (sum = 0, k = 1; k <= 2*p[0]; k+=2)	/* 計算每一項的結果值(係數*x^指數)並累加到sum之中 */ 
				sum += p[k+1]*(int)(pow(sign[j]*i,p[k]));
			if (sum == 0) q[c++] = sign[j]*i;  /* bingo! 發現合乎條件的整數根，將其寫入q陣列 */ 
		}
	}
	
	return c;
}

void show(int p[], int n, int mode)
{
	int i;
	
	if (mode == 0) { /* 顯示方程式 */ 
		printf("方程式p(x)= ");
		for (i = 1; i <= n; i += 2) {
			if (abs(p[i+1])>1) 		/* 係數>1或<-1，則顯示該係數值 */ 
				printf("%s%d",p[i+1]>1? "":"\b",p[i+1]);	/* 若係數為負值，把前導的+號塗掉 */ 
			else if (p[i+1]==-1)	/* 係數為-1，僅顯示-號即可 */ 
				printf("%s",p[i]==0? "\b-1":"\b-");
			else
				printf("%s",p[i]==0? "1":"");
			switch(p[i]) {
				case 0: 
					printf("+");
					break;
				case 1:
					printf("x+");
					break;
				default:
					printf("x^%d+",p[i]);
			}		
		}
		printf("\b ");
	}
	else { /* mode==1，顯示所得解 */ 
		for (i = 0; i < n; i++) printf("%d、",p[i]);
		if (n > 0) printf("\b\b  ");
	}
}

int main()
{
	int p[101] = {0};
	int c, *q; 
	
	printf("\n*** 解多項式之整數根 ***\n\n輸入多項式 ==> ");
	c = readPoly(p);	/* 鍵盤讀取多項式子 */ 
	q = (int *)malloc(p[1]*sizeof(int)); /* p[1]紀錄最高階項之指數，依此值創建足夠元素空間的陣列存放所求得的整數根 */ 
	show(p,2*p[0],0);
	c = findRoot(p,q);
	if (c > 0) {
		printf("\n\n解得整數根為：");
		show(q,c,1);  
	}
	else
		printf("\n\n整數根不存在\n");
	
	free(q);
	return 0;
}