连分数(分数类模板) uva6875

  1 //连分数(分数类模板) uva6875
  2 // 题意：告诉你连分数的定义。求连分数，并逆向表示出来
  3 // 思路：直接上分数类模板。要注意ai可以小于0
  4 
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <cstring>
  8 #include <cstdio>
  9 #include <vector>
 10 #include <cmath>
 11 #include <map>
 12 #include <queue>
 13 using namespace std;
 14 #define LL long long
 15 typedef pair<int,int> pii;
 16 const int inf = 0x3f3f3f3f;
 17 const int MOD = 998244353;
 18 const int N = 1020;
 19 const int maxx = 200010; 
 20 #define clc(a,b) memset(a,b,sizeof(a))
 21 const double eps = 0.025;
 22 void fre() {freopen("in.txt","r",stdin);}
 23 void freout() {freopen("out.txt","w",stdout);}
 24 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
 25 
 26 struct fr{
 27     LL a,b;
 28     fr(LL a_,LL b_){
 29         LL g=__gcd(a_,b_);
 30         a=a_/g;
 31         b=b_/g;
 32     }
 33     fr operator + (const fr &x){
 34         return fr(a*x.b+b*x.a,b*x.b);
 35     }
 36     fr operator -(const fr &x){
 37         return fr(a*x.b-x.a*b,b*x.b);
 38     }
 39     fr operator *(const fr &x){
 40         return fr(a*x.a,b*x.b);
 41     }
 42     fr operator /(const fr &x){
 43         return fr(a*x.b,b*x.a);
 44     }
 45     void add(LL x){
 46         a+=b*x;
 47     }
 48     LL split(){
 49         LL r=a/b;
 50         a%=b;
 51         if(a<0){
 52             r--;
 53             a+=b;
 54         }
 55         return r;
 56     }
 57     void inv(){
 58         std::swap(a,b);
 59         if(b<0){
 60             a=-a;
 61             b=-b;
 62         }
 63     }
 64     operator bool(){
 65         return a;
 66     }
 67 };
 68 LL in[11];
 69 int n,m;
 70 int main(){
 71     int cas=1;
 72     while(~scanf("%d%d",&n,&m),n&&m){
 73         for(int i=1;i<=n;i++) scanf("%lld",&in[i]);
 74         fr x(0,1);
 75         for(int i=n;i>=1;i--) {
 76            x.add(in[i]);
 77            if(i!=1)x.inv();
 78         }
 79 
 80         for(int i=1;i<=m;i++) scanf("%lld",&in[i]);
 81         fr y(0,1);
 82         for(int i=m;i>=1;i--) {
 83             y.add(in[i]);
 84             if(i!=1) y.inv();
 85         }
 86 
 87         fr ad=x+y,sub=x-y,mul=x*y,div=x/y;
 88         printf("Case %d:
",cas++);
 89         
 90         ad.inv();
 91         while(ad){
 92             ad.inv();
 93             printf("%lld",ad.split());
 94             if(ad){
 95                 printf(" ");
 96             }
 97         }
 98         printf("
");
 99 
100         sub.inv();
101         while(sub){
102             sub.inv();
103             printf("%lld",sub.split());
104             if(sub){
105                 printf(" ");
106             }
107         }
108         printf("
");
109 
110         mul.inv();
111         while(mul){
112             mul.inv();
113             printf("%lld",mul.split());
114             if(mul){
115                 printf(" ");
116             }
117         }
118         printf("
");
119 
120         div.inv();
121         while(div){
122             div.inv();
123             printf("%lld",div.split());
124             if(div){
125                 printf(" ");
126             }
127         }
128         printf("
");
129     
130     }
131     return 0;
132 }