POJ 3197 - Continuous Fractions

http://poj.org/problem?id=3197

概要

整数 \(p, q\) が与えられるので，\(\frac{p}{q}\) を連分数展開したものを答える．

制約

解法

連分数展開するにはユークリッドの互除法を使えばよい． 出力の整形がかなり面倒．

 1 import java.util.*;
 2 import java.math.*;
 3 
 4 public class Main {
 5   public static void main(String[] args) {
 6     Scanner cin = new Scanner(System.in);
 7 
 8     for (int Ti = 1;; Ti++) {
 9       BigInteger p = cin.nextBigInteger();
10       BigInteger q = cin.nextBigInteger();
11       if (q.equals(BigInteger.ZERO)) {
12         break;
13       }
14       System.out.printf("Case %d:\n", Ti);
15       System.out.printf("%s / %s\n", p.toString(), q.toString());
16 
17       ArrayList<BigInteger> a = new ArrayList<BigInteger>();
18       int width = 0;
19       while (!p.mod(q).equals(BigInteger.ZERO)) {
20         BigInteger[] qr = p.divideAndRemainder(q);
21         a.add(qr[0]);
22         width += qr[0].toString().length() + 3;
23         p = q;
24         q = qr[1];
25       }
26       p = p.divide(q).subtract(BigInteger.ONE);
27       width += p.toString().length() + 4;
28       a.add(p);
29 
30       int indent = 0;
31       for (BigInteger n : a) {
32         String s = n.toString();
33         int frac = width - indent - s.length() - 3;
34         for (int i = 0; i < indent + s.length() + 3 + (frac-1)/2; i++) {
35           System.out.print(".");
36         }
37         System.out.print("1");
38         for (int i = 0; i < frac/2; i++) {
39           System.out.print(".");
40         }
41         System.out.println("");
42         for (int i = 0; i < indent; i++) {
43           System.out.print(".");
44         }
45         System.out.print(s);
46         System.out.print(".+.");
47         for (int i = 0; i < frac; i++) {
48           System.out.print("-");
49         }
50         System.out.println("");
51         indent += s.length() + 3;
52       }
53       for (int i = 0; i < width-1; i++) {
54         System.out.print(".");
55       }
56       System.out.println("1");
57     }
58   }
59 }
poj/3197.java