[TIOJ] 1040. C.連分數

題目連結:http://tioj.infor.org/problems/1040

---

這題算是數學題吧(?，但也不是什麼難的數學，先說連分數的基本求法就是直接算$\lfloor \frac{a}{b} \rfloor$這東東就會是第一個整數，那顯然的$\frac{a}{b} - \lfloor \frac{a}{b} \rfloor$會是後面那串分數，那就再看$\frac{1}{\frac{a}{b} - \lfloor \frac{a}{b} \rfloor}$(=$\frac{b}{a - b \lfloor \frac{a}{b} \rfloor}$)然後用跟上面同樣的方法算下去，直到$\frac{a}{b} - \lfloor \frac{a}{b} \rfloor = 0$時停止，但是我們在實作時不能真的用double之類的，不然你可能會被浮點數誤差搞死(或許只是我太廢拉XD，所以要做一點基本的數學運算，這邊就不贅述，大概從我的code應該就可看出來在幹嘛了。 溫馨小提示(?有可能一開始b就是0

#include <stdio.h>

void weirdGCD(int,int,bool);

int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		int a, b;
		scanf("%d%d",&a,&b);
		printf("%d/%d = %d",a,b,a/b);
		weirdGCD(a,b,0);
		puts("");
	}
}

void weirdGCD(int a,int b,bool tf){
	if(b==0)return;
	int c=a/b;
	if(!tf){
		weirdGCD(b,a-b*c,1);
	}else if(a-b*c == 0){
		printf("+1/%d",c);
		return;
	}else{
		printf("+1/{%d",c);
		weirdGCD(b,a-b*c,1);
		putchar('}');
	}
}