Artifact 49868c43512ca5f3c70daaf9633fe345ed185123:
0000: 69 6d 70 6f 72 74 20 6a 61 76 61 2e 6d 61 74 68 import java.math
0010: 2e 2a 3b 0d 0a 69 6d 70 6f 72 74 20 6a 61 76 61 .*;..import java
0020: 2e 75 74 69 6c 2e 2a 3b 0d 0a 0d 0a 70 75 62 6c .util.*;....publ
0030: 69 63 20 63 6c 61 73 73 20 5a 65 6e 6f 44 69 76 ic class ZenoDiv
0040: 69 73 69 6f 6e 20 7b 0d 0a 09 73 74 61 74 69 63 ision {...static
0050: 20 42 69 67 49 6e 74 65 67 65 72 20 5a 45 52 4f BigInteger ZERO
0060: 20 3d 20 42 69 67 49 6e 74 65 67 65 72 2e 5a 45 = BigInteger.ZE
0070: 52 4f 3b 0d 0a 09 73 74 61 74 69 63 20 42 69 67 RO;...static Big
0080: 49 6e 74 65 67 65 72 20 4f 4e 45 20 20 3d 20 42 Integer ONE = B
0090: 69 67 49 6e 74 65 67 65 72 2e 4f 4e 45 3b 0d 0a igInteger.ONE;..
00a0: 09 73 74 61 74 69 63 20 42 69 67 49 6e 74 65 67 .static BigInteg
00b0: 65 72 20 54 57 4f 20 20 3d 20 42 69 67 49 6e 74 er TWO = BigInt
00c0: 65 67 65 72 2e 76 61 6c 75 65 4f 66 28 32 29 3b eger.valueOf(2);
00d0: 0d 0a 09 73 74 61 74 69 63 20 42 69 67 49 6e 74 ...static BigInt
00e0: 65 67 65 72 20 54 45 4e 20 20 3d 20 42 69 67 49 eger TEN = BigI
00f0: 6e 74 65 67 65 72 2e 54 45 4e 3b 0d 0a 0d 0a 09 nteger.TEN;.....
0100: 70 75 62 6c 69 63 20 53 74 72 69 6e 67 20 63 79 public String cy
0110: 63 6c 65 28 53 74 72 69 6e 67 20 61 5f 2c 20 53 cle(String a_, S
0120: 74 72 69 6e 67 20 62 5f 29 20 0d 0a 09 7b 0d 0a tring b_) ...{..
0130: 09 09 42 69 67 49 6e 74 65 67 65 72 20 61 20 3d ..BigInteger a =
0140: 20 6e 65 77 20 42 69 67 49 6e 74 65 67 65 72 28 new BigInteger(
0150: 61 5f 29 3b 0d 0a 09 09 42 69 67 49 6e 74 65 67 a_);....BigInteg
0160: 65 72 20 62 20 3d 20 6e 65 77 20 42 69 67 49 6e er b = new BigIn
0170: 74 65 67 65 72 28 62 5f 29 3b 0d 0a 0d 0a 09 09 teger(b_);......
0180: 69 66 28 20 62 2e 72 65 6d 61 69 6e 64 65 72 28 if( b.remainder(
0190: 54 57 4f 29 2e 65 71 75 61 6c 73 28 5a 45 52 4f TWO).equals(ZERO
01a0: 29 20 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 22 ) ).....return "
01b0: 69 6d 70 6f 73 73 69 62 6c 65 22 3b 0d 0a 09 09 impossible";....
01c0: 69 66 28 20 61 2e 65 71 75 61 6c 73 28 5a 45 52 if( a.equals(ZER
01d0: 4f 29 20 26 26 20 62 2e 65 71 75 61 6c 73 28 4f O) && b.equals(O
01e0: 4e 45 29 20 29 0d 0a 09 09 09 72 65 74 75 72 6e NE) ).....return
01f0: 20 22 2d 22 3b 0d 0a 09 09 69 66 28 20 61 2e 65 "-";....if( a.e
0200: 71 75 61 6c 73 28 4f 4e 45 29 20 26 26 20 62 2e quals(ONE) && b.
0210: 65 71 75 61 6c 73 28 4f 4e 45 29 20 29 0d 0a 09 equals(ONE) )...
0220: 09 09 72 65 74 75 72 6e 20 22 2a 22 3b 0d 0a 0d ..return "*";...
0230: 0a 09 09 69 6e 74 20 78 20 3d 20 31 3b 0d 0a 09 ...int x = 1;...
0240: 09 77 68 69 6c 65 28 20 21 54 57 4f 2e 6d 6f 64 .while( !TWO.mod
0250: 50 6f 77 28 42 69 67 49 6e 74 65 67 65 72 2e 76 Pow(BigInteger.v
0260: 61 6c 75 65 4f 66 28 78 29 2c 62 29 2e 65 71 75 alueOf(x),b).equ
0270: 61 6c 73 28 4f 4e 45 29 20 29 20 7b 0d 0a 09 09 als(ONE) ) {....
0280: 09 78 2b 2b 3b 0d 0a 09 09 09 69 66 28 20 78 20 .x++;.....if( x
0290: 3e 3d 20 36 31 20 29 0d 0a 09 09 09 09 72 65 74 >= 61 )......ret
02a0: 75 72 6e 20 22 69 6d 70 6f 73 73 69 62 6c 65 22 urn "impossible"
02b0: 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 42 69 67 49 ;....}......BigI
02c0: 6e 74 65 67 65 72 20 7a 20 3d 20 54 57 4f 2e 70 nteger z = TWO.p
02d0: 6f 77 28 78 29 2e 73 75 62 74 72 61 63 74 28 4f ow(x).subtract(O
02e0: 4e 45 29 2e 64 69 76 69 64 65 28 62 29 3b 0d 0a NE).divide(b);..
02f0: 09 09 53 74 72 69 6e 67 20 73 74 72 20 3d 20 61 ..String str = a
0300: 2e 6d 75 6c 74 69 70 6c 79 28 7a 29 2e 74 6f 53 .multiply(z).toS
0310: 74 72 69 6e 67 28 32 29 3b 0d 0a 09 09 77 68 69 tring(2);....whi
0320: 6c 65 28 20 73 74 72 2e 6c 65 6e 67 74 68 28 29 le( str.length()
0330: 20 3c 20 78 20 29 0d 0a 09 09 09 73 74 72 20 3d < x ).....str =
0340: 20 22 30 22 20 2b 20 73 74 72 3b 0d 0a 0d 0a 09 "0" + str;.....
0350: 09 53 74 72 69 6e 67 20 61 6e 73 77 65 72 20 3d .String answer =
0360: 20 22 22 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 "";....for(int
0370: 69 3d 30 3b 20 69 3c 73 74 72 2e 6c 65 6e 67 74 i=0; i<str.lengt
0380: 68 28 29 3b 20 2b 2b 69 29 0d 0a 09 09 09 61 6e h(); ++i).....an
0390: 73 77 65 72 20 2b 3d 20 28 73 74 72 2e 63 68 61 swer += (str.cha
03a0: 72 41 74 28 69 29 3d 3d 27 31 27 20 3f 20 22 2a rAt(i)=='1' ? "*
03b0: 22 20 3a 20 22 2d 22 29 3b 0d 0a 09 09 72 65 74 " : "-");....ret
03c0: 75 72 6e 20 61 6e 73 77 65 72 3b 0d 0a 09 7d 0d urn answer;...}.
03d0: 0a 7d 3b 0d 0a .};..