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