085e72a21b 2011-07-09        kinaba: import java.math.*;
085e72a21b 2011-07-09        kinaba: import java.util.*;
085e72a21b 2011-07-09        kinaba: 
085e72a21b 2011-07-09        kinaba: public class ZenoDivision {
085e72a21b 2011-07-09        kinaba: 	static BigInteger ZERO = BigInteger.ZERO;
085e72a21b 2011-07-09        kinaba: 	static BigInteger ONE  = BigInteger.ONE;
085e72a21b 2011-07-09        kinaba: 	static BigInteger TWO  = BigInteger.valueOf(2);
085e72a21b 2011-07-09        kinaba: 	static BigInteger TEN  = BigInteger.TEN;
085e72a21b 2011-07-09        kinaba: 
085e72a21b 2011-07-09        kinaba: 	public String cycle(String a_, String b_)
085e72a21b 2011-07-09        kinaba: 	{
085e72a21b 2011-07-09        kinaba: 		BigInteger a = new BigInteger(a_);
085e72a21b 2011-07-09        kinaba: 		BigInteger b = new BigInteger(b_);
085e72a21b 2011-07-09        kinaba: 
085e72a21b 2011-07-09        kinaba: 		if( b.remainder(TWO).equals(ZERO) )
085e72a21b 2011-07-09        kinaba: 			return "impossible";
085e72a21b 2011-07-09        kinaba: 		if( a.equals(ZERO) && b.equals(ONE) )
085e72a21b 2011-07-09        kinaba: 			return "-";
085e72a21b 2011-07-09        kinaba: 		if( a.equals(ONE) && b.equals(ONE) )
085e72a21b 2011-07-09        kinaba: 			return "*";
085e72a21b 2011-07-09        kinaba: 
085e72a21b 2011-07-09        kinaba: 		int x = 1;
085e72a21b 2011-07-09        kinaba: 		while( !TWO.modPow(BigInteger.valueOf(x),b).equals(ONE) ) {
085e72a21b 2011-07-09        kinaba: 			x++;
085e72a21b 2011-07-09        kinaba: 			if( x >= 61 )
085e72a21b 2011-07-09        kinaba: 				return "impossible";
085e72a21b 2011-07-09        kinaba: 		}
085e72a21b 2011-07-09        kinaba: 
085e72a21b 2011-07-09        kinaba: 		BigInteger z = TWO.pow(x).subtract(ONE).divide(b);
085e72a21b 2011-07-09        kinaba: 		String str = a.multiply(z).toString(2);
085e72a21b 2011-07-09        kinaba: 		while( str.length() < x )
085e72a21b 2011-07-09        kinaba: 			str = "0" + str;
085e72a21b 2011-07-09        kinaba: 
085e72a21b 2011-07-09        kinaba: 		String answer = "";
085e72a21b 2011-07-09        kinaba: 		for(int i=0; i<str.length(); ++i)
085e72a21b 2011-07-09        kinaba: 			answer += (str.charAt(i)=='1' ? "*" : "-");
085e72a21b 2011-07-09        kinaba: 		return answer;
085e72a21b 2011-07-09        kinaba: 	}
085e72a21b 2011-07-09        kinaba: };