题目来源：2016 CCPC 长春站
题意：青蛙先生想计算一个式子的值，输入两个数列a[],b[]求出最后的分子和分母
思路：一开始看到这个图片首先想到的是递归实现，递归部分始终计算的是右下部分
/*************************************************************************
> File Name: A.cpp
> Author: WArobot
> Mail: 768059009@qq.com
> Created Time: 2017年04月15日 星期六 21时10分45秒
************************************************************************/
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
long long n,a[100],b[100];
long long p,q;
void fun(long long step,long long z,long long m){
long long t1 = m*b[step-1] , t2 = m*a[step-1]+z;
if(step==1) {
p = t1 ; q = t2 ;
return;
}
fun(step-1, t1 , t2 );
}
int gcd(long long a,long long b){
return b==0?a:gcd(b,a%b);
}
int main(){
int t,kase = 0;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
for(int i=0;i<n;i++) scanf("%lld",a+i);
for(int i=0;i<n;i++) scanf("%lld",b+i);
p = q = 0;
if(n<=1) p = b[0] , q = a[0];
else fun(n-1,b[n-1],a[n-1]);
int d = gcd(p,q);
if(d!=0){
p /= d; q /= d;
}
printf("Case #%d: %lld %lld
",++kase,p,q);
}
return 0;
}
后来一想为啥非得要用递归做......
/*************************************************************************
> File Name: A2.cpp
> Author: WArobot
> Mail: 768059009@qq.com
> Created Time: 2017年04月16日 星期日 20时35分55秒
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
int t , kase = 0 , n;
int a[100] , b[100];
int p,q; // p为分子 q为分母
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
void solve(){
p = b[n-1] , q = a[n-1];
for(int i=n-2;i>=0;i--){
int t1 = p , t2 = q;
p = t2*b[i];
q = t2*a[i] + t1;
}
int d = gcd(p,q);
p /= d; q /= d;
}
int main(){
int kase = 0;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",a+i);
for(int i=0;i<n;i++) scanf("%d",b+i);
solve();
printf("Case #%d: %d %d
",++kase,p,q);
}
return 0;
}