ACM数论----连分数问题

　

连分数

Description

一个高为n的连分数定义为 。

给出2个数，一个用p/q的方式表达，另一个用高度为n的连分数来表示，请你判断他们是否相等。

Input

输入有多组，每组包含两部分用来表示两种形式的分数：第一部分是p和q（1 ≤ q ≤ p ≤ 10^18），表示分数p/q；然后是一个数字n（1 ≤ n ≤ 90）和由n个数 ai（1 ≤ ai ≤ 10^18）代表的连分数。

Output

如果相等请输出“YES”，否则输出“NO”。

Sample Input

9 4

2

2 4

9 4

3

2 3 1

Sample Output

YES

YES

类似这种：                         

————————————————————————————————————————————————————

思路：把数字存起来，从最后一个开始循环往前不断地加前一个数字取倒数，不用约分，最后分子分母若同时取余pq为零而且除以pq的结果相同，则认为相等。

代码：

#include <stdio.h>
unsigned long long int num[100];
unsigned long long int continued_fraction[3];
int main()
{
    unsigned long long int p,q;
    int n;
    while(scanf("%llu%llu",&p,&q)!=EOF)
    {
        scanf("%d",&n);
        int i,j;
        for(i=0; i<n; i++)
            scanf("%llu",&num[i]);
        continued_fraction[0]=1;//第一个分数的分子
        continued_fraction[1]=num[n-1];//第一个分数的分母
        unsigned long long int temp;
        for(j=n-2; j>=0; j--)
        {
            continued_fraction[1]=continued_fraction[1];
            continued_fraction[0]=continued_fraction[0]+continued_fraction[1]*num[j];//通分当前分数与下一个整数相加
            if(j>0)//最后一个整数不取倒数
            {
                temp=continued_fraction[1];
                continued_fraction[1]=continued_fraction[0];//取倒数
                continued_fraction[0]=temp;
            }
            //printf("%llu/%llu\n",continued_fraction[0],continued_fraction[1]);
        }
        if(continued_fraction[1]/q==continued_fraction[0]/p&&continued_fraction[1]%q==0&&continued_fraction[0]%p==0)//判断条件
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;

}

相关阅读