学步园

Timus 1014. The Product of Digits 要求给出一个最小整数，其各位数字的乘积等于指定的数。

---

1014. The Product of Digits

Time Limit: 1.0 second
Memory Limit: 16 MB

Your task is to find the minimal positive integer number Q so that the product of digits of Q is exactly equal to N.

Input

The input contains the single integer number N (0 ≤ N ≤ 10⁹).

Output

Your program should print to the output the only number Q. If such a number does not exist print −1.

Sample

input	output
10	25

Problem Source: Ural State University Internal Contest '99 #2

---

解答如下：

 1 using System;
 2 using System.IO;
 3 
 4 namespace Skyiv.Ben.Timus
 5 {
 6   // http://acm.timus.ru/problem.aspx?space=1&num=1014
 7   class T1014
 8   {
 9     static void Main()
10     {
11       new T1014().Run(Console.In, Console.Out);
12     }
13 
14     void Run(TextReader reader, TextWriter writer)
15     {
16       Out(writer, GetDigits(int.Parse(reader.ReadLine())));
17     }
18 
19     int[] GetDigits(int n)
20     {
21       int[] digits = new int[11];
22       if (n == 0) digits[10] = 1;
23       else if (n == 1) digits[1] = 1;
24       else
25       {
26         for (int i = 9; i > 1; i--)
27         {
28           while (n > 1 && n % i == 0)
29           {
30             n /= i;
31             digits[i]++;
32           }
33         }
34         if (n != 1) digits = null;
35       }
36       return digits;
37     }
38 
39     void Out(TextWriter writer, int[] digits)
40     {
41       if (digits == null) writer.WriteLine(-1);
42       else
43       {
44         for (int i = 0; i < digits.Length; i++)
45         {
46           int n = digits[i];
47           while (n-- > 0) writer.Write(i);
48         }
49         writer.WriteLine();
50       }
51     }
52   }
53 }
54 

这题的解法还是比较直接的。但是要注意当输入 N = 0 时，输出的答案应该是 10，而不是 -1。

---

返回目录