POJ 2325 - Persistent Numbers

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

概要

数が与えられたとき、その数を十進で表記して各桁の数字の積を次の数とする。 例えば 679 の次の数は 6 x 7 x 9 = 378 である。

ある数 \(X\) が与えられたとき、次の数が \(X\) であるような数のうち、最も小さいものを答える。 そのような数が存在しないときは「There is no such number.」と答える。

制約

解法

\(X < 10\) のときは \(10 + X\) が答え。

そうでないときは、9から2の順にできるだけ割っていき、その割った数の列を逆順にしたものが答えである。

 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     final BigInteger eof = BigInteger.valueOf(-1);
 8     while (true) {
 9       BigInteger n = cin.nextBigInteger();
10       if (n.equals(eof)) {
11         break;
12       }
13 
14       if (n.compareTo(BigInteger.TEN) < 0) {
15         System.out.println("1" + n);
16       } else {
17         StringBuilder sb = new StringBuilder();
18         for (int i = 9; i >= 2; i--) {
19           final BigInteger x = BigInteger.valueOf(i);
20           while (!n.equals(BigInteger.ONE)) {
21             BigInteger[] qr = n.divideAndRemainder(x);
22             if (qr[1].equals(BigInteger.ZERO)) {
23               sb.append(i);
24               n = qr[0];
25             } else {
26               break;
27             }
28           }
29         }
30         if (n.equals(BigInteger.ONE)) {
31           System.out.println(sb.reverse().toString());
32         } else {
33           System.out.println("There is no such number.");
34         }
35       }
36     }
37   }
38 }
poj/2325.java