连分数(分数类模板) uva6875

 //连分数(分数类模板) uva6875
// 题意:告诉你连分数的定义。求连分数,并逆向表示出来
// 思路:直接上分数类模板。要注意ai可以小于0 #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
#define LL long long
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const int MOD = ;
const int N = ;
const int maxx = ;
#define clc(a,b) memset(a,b,sizeof(a))
const double eps = 0.025;
void fre() {freopen("in.txt","r",stdin);}
void freout() {freopen("out.txt","w",stdout);}
inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-; ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;} struct fr{
LL a,b;
fr(LL a_,LL b_){
LL g=__gcd(a_,b_);
a=a_/g;
b=b_/g;
}
fr operator + (const fr &x){
return fr(a*x.b+b*x.a,b*x.b);
}
fr operator -(const fr &x){
return fr(a*x.b-x.a*b,b*x.b);
}
fr operator *(const fr &x){
return fr(a*x.a,b*x.b);
}
fr operator /(const fr &x){
return fr(a*x.b,b*x.a);
}
void add(LL x){
a+=b*x;
}
LL split(){
LL r=a/b;
a%=b;
if(a<){
r--;
a+=b;
}
return r;
}
void inv(){
std::swap(a,b);
if(b<){
a=-a;
b=-b;
}
}
operator bool(){
return a;
}
};
LL in[];
int n,m;
int main(){
int cas=;
while(~scanf("%d%d",&n,&m),n&&m){
for(int i=;i<=n;i++) scanf("%lld",&in[i]);
fr x(,);
for(int i=n;i>=;i--) {
x.add(in[i]);
if(i!=)x.inv();
} for(int i=;i<=m;i++) scanf("%lld",&in[i]);
fr y(,);
for(int i=m;i>=;i--) {
y.add(in[i]);
if(i!=) y.inv();
} fr ad=x+y,sub=x-y,mul=x*y,div=x/y;
printf("Case %d:\n",cas++); ad.inv();
while(ad){
ad.inv();
printf("%lld",ad.split());
if(ad){
printf(" ");
}
}
printf("\n"); sub.inv();
while(sub){
sub.inv();
printf("%lld",sub.split());
if(sub){
printf(" ");
}
}
printf("\n"); mul.inv();
while(mul){
mul.inv();
printf("%lld",mul.split());
if(mul){
printf(" ");
}
}
printf("\n"); div.inv();
while(div){
div.inv();
printf("%lld",div.split());
if(div){
printf(" ");
}
}
printf("\n"); }
return ;
}
上一篇:设计模式之Builder(建造者)(转)


下一篇:css tips: 清除float影响,containing的div跟随floated sub等