834-Continued Fraction-solution hints

https://uva.onlinejudge.org/external/8/834.pdf

This problem seems to be hard but not hard at all . It's a mathematical problem . You can easily implement this code if you know clearly about Using Euclid's GCD algorithm to make a continued fraction . Please go through the following link to know details about Euclid's GCD algorithm :

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html#section3

solution steps :

1 . Take two input as N & D which indicate nominator and denominator.

2 . Now divide the N by D and put it to an array .

3 . Now mode N by D to get the remaining part also assign D to N and the remaining part to D .

4 . go back to step 2 until the remaining part becomes 0 .

Note : Once again try to get Euclid's algorithm clearly otherwise you can't get the r8 path to solve this problem .

An accepted code is given below :

~1st try yourself if you can't then just take idea never copy paste code~

#include<bits/stdc++.h>
#define q 10000
using namespace std;

int main()
{
    long long int N,D,s,m,i,j;

    while(scanf("%lld%lld",&N,&D)==2)
    {
        i=0;
        m=1;
        long long int arr[q]={0};

        while(m!=0)
        {

        s=N/D;
        m=N%D;

        arr[i++]=s;

        N=D;
        D=m;
        }

        printf("[%lld;",arr[0]);

        for(j=1;j<i;j++)
        {
            if(j==(i-1))
            {
                printf("%lld]\n",arr[j]);
            }
            else
            {
            printf("%lld,",arr[j]);
            }
        }

    }

    return 0;

}