POJ-1930, UVa-10555, SPOJ-DEADFR, TJU-1430, ZOJ-1933 : Dead Fraction

問題概要

循環小数が与えられる。ただし循環の単位は分からない。分母が最小になるように有理数で表す問題。

解法

反復単位がどうなってるか全探索する。制約がよく分からなかったので多倍長で。

acceptされたコード

import java.math.BigInteger;
import java.util.Scanner;

public class Main{
	
	void run(){
		Scanner in = new Scanner(System.in);
		for(;in.hasNext();){
			String line = in.next();
			if(line.equals("0")){
				break;
			}
			int n = line.length();
			if(n < 6){
				System.out.println("0/1");
				continue;
			}
			if((new BigInteger(line.substring(2, n-3))).equals(BigInteger.ZERO)){
				System.out.println("0/1");
				continue;
			}
			BigInteger ay = BigInteger.ZERO, ax = BigInteger.TEN.pow(100);
			for(int l=1; l<=n-5; ++l){
				String first = line.substring(n-3-l-(n-5-l),n-3-l), second = line.substring(n-3-l, n-3);
				BigInteger x = BigInteger.TEN.pow(first.length() + second.length()).subtract(BigInteger.TEN.pow(first.length()));
				BigInteger y = (new BigInteger(first + second)).subtract(first.length() > 0 ? (new BigInteger(first)) : BigInteger.ZERO);
				BigInteger d = x.gcd(y);
				x = x.divide(d);
				y = y.divide(d);
				if(x.compareTo(ax) < 0){
					ax = x;
					ay = y;
				}
			}
			System.out.println(ay + "/" + ax);
		}
	}
	
	public static void main(String args[]){
		new Main().run();
	}
}