本文主要是介绍xtu oj 1374 连分数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
x=b1a1+b2a2+b3a3+⋯
比如 n=3,a1=1,a2=2,a3=3,b1=3,b2=2,b3=1时
x=31+22+13=2113
给定n,ai,i=1,2,…,n,请求x,并按最简方式表示x。
输入
第一个行是一个整数T(1≤T≤100),表示样例的个数。 以后每个样例的第一行为整数n(1≤n≤9); 第二行为n个整数,为ai,(1≤ai≤100); 第三行为n个整数,为bi,(1≤bi≤100)。
输出
按顺序输出一个样例的结果,如果结果为整数,输出整数;如果结果为分数,格式为"分子/分母",保证分子与分母互质。
样例输入
3 3 1 2 3 3 2 1 3 1 2 3 4 7 1 9 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 99
样例输出
21/13 1 1060072063970000499/1081277664009800500
AC代码
#include<stdio.h>
long long gcd(long long a,long long b){long long t;while(a%b!=0){t=a%b;a=b;b=t;}return b;
}
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);int a[105]={},b[105]={};int i;for(i=0;i<n;i++){scanf("%d",&a[i]);}for(i=0;i<n;i++){scanf("%d",&b[i]);}long long fz=b[n-1],fm=a[n-1];long long g;for(i=n-2;i>=0;i--){long long t=fz;fz=b[i]*fm;fm=a[i]*fm+t;}if(fz%fm==0)printf("%I64d\n",fz/fm);else{g=gcd(fz,fm);fz/=g;fm/=g;printf("%I64d/%I64d\n",fz,fm);}}
}
注意,要在最后一步进行化简。从内层开始找规律。
这篇关于xtu oj 1374 连分数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!