2013年6月30日 星期日

2013/6/30 TIOJ 1040 C.連分數

// http://218.210.35.237:8080/JudgeOnline/showproblem?problem_id=1040
#include<cstdio>
#include<iostream>
using namespace std;
void solve(int p,int q)
{
   
    int o = p/q;
    p -= o*q;
    printf("%d+",o);  
    if( p == 1 )
    {
        printf("%d/%d", p, q);  
    }
   
    else
    {
        printf("1/{");
        solve(q,p);
        printf("}");
    }
}
int gcd(int a,int b)
{
    int t;
    if( a < b ){ t = a; a = b; b = t; }
    while( a != 0 && b != 0 )
    {
        a %= b;
        if( a < b ){ t = a; a = b; b = t; }  
    }
    return a;
}
int main()
{
    int n; scanf("%d", &n);
    while( n-- )
    {
        int p, q; scanf("%d %d", &p, &q);
        int o = gcd(p,q);
        printf("%d/%d = ", p, q);
       
        p/=o; q/=o;
        if(q!=1){solve(p,q);}
        else{ printf("%d", p); }
        printf("\n");
    }  
}

沒有留言:

張貼留言