连分式是形如下面的分式,已知a,b和迭代的次数n,求连分式的值。
第一行是一个整数T(1≤T≤1000),表示样例的个数。 每行一个样例,为a,b,n(1≤a,b,n≤9)
每行输出一个样例的结果,使用x/y分式表达,并保证x,y互质。
3 1 2 1 1 2 9 5 9 9
1/2 985/2378 321047030/611590599
AC代码
#include<stdio.h>
#define ll long long
ll gcd(ll a,ll b){
int t;
while(a%b!=0){
t=a%b;
a=b;
b=t;
}
return b;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
ll a,b,n,i;
scanf("%I64d%I64d%I64d",&a,&b,&n);
ll g,fz=a,fm=b;
for(i=2;i<=n;i++){
ll t=fz;
fz=a*fm;
fm=fm*b+t;
}
g=gcd(fz,fm);
fz/=g;
fm/=g;
printf("%I64d/%I64d\n",fz,fm);
}
}
找规律即可,与1374连分数类似。