VerySmoothDecompositions | Topcoder Archive

Problem Statement

You are given a String[] digits. Concatenate its elements to obtain a very large positive integer D.

We are interested in very smooth decompositions of D; that is, the ways in which D can be written as a product of numbers not exceeding 16.

(In the product, each factor must be greater than 1. The order of factors does not matter, i.e., 24=3*8 is the same decomposition as 24=8*3.)

Your method must return the number of very smooth decompositions of D, modulo 1,000,000,009.

Definition

Class:: VerySmoothDecompositions
Method:: solve
Parameters:: String[]
Returns:: int
Method signature:: int solve(String[] digits)
(be sure your method is public)

Constraints

digits will contain between 1 and 50 elements, inclusive.
Each element of digits will contain between 1 and 50 characters, inclusive.
Each character of each element of digits will be a digit ('0'-'9').
Character 0 of element 0 of digits will not be '0'.

Examples

```
{"47"}
```
```
Returns: 0
```
No valid decompositions.
```
{"2"}
```
```
Returns: 1
```
The only valid decomposition is the one with a single factor equal to 2.
```
{"10"}
```
```
Returns: 2
```
Two valid decompositions: 10 and 2*5.
```
{"36"}
```
```
Returns: 7
```
All decompositions of 36 are: 36 = 2*18 = 3*12 = 4*9 = 6*6 = 2*2*9 = 2*3*6 = 3*3*4 = 2*2*3*3. The first two of these (36 and 2*18) contain a factor larger than 16. The other seven decompositions are very smooth.
```
{"1","21"}
```
```
Returns: 1
```
Here the only valid decomposition is 11*11.
```
{"1024"}
```
```
Returns: 23
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.