DivisibleSequence | Topcoder Archive

Problem Statement

A divisible sequence with starting value N and length H is a sequence of positive integers with the following properties:

The sequence has H elements, labeled A[0] through A[H-1].
A[0] equals N.
For each i between 0 and H-2, inclusive, A[i+1] divides A[i].

You are given the ints N and H. Let C be the count of all divisible sequences with starting value N and length H. Return the value (C modulo 1,000,000,009).

Definition

Class:: DivisibleSequence
Method:: count
Parameters:: int, int
Returns:: int
Method signature:: int count(int N, int H)
(be sure your method is public)

Constraints

N will be between 1 and 1,000,000,000, inclusive.
H will be between 1 and 1,000,000,000, inclusive.

Examples

```
5
```
```
3
```
```
Returns: 3
```
The three possible sequences are: 5, 5, 5 5, 5, 1 5, 1, 1
```
6
```
```
3
```
```
Returns: 9
```
The nine possible sequences are: 6, 6, 6 6, 6, 3 6, 6, 2 6, 6, 1 6, 3, 3 6, 3, 1 6, 2, 2 6, 2, 1 6, 1, 1
```
10
```
```
2
```
```
Returns: 4
```
A[1] can be equal to each of the divisors of the number 10. That is, A[1] can be 1, 2, 5, or 10.
```
1
```
```
10000
```
```
Returns: 1
```
The only possible sequence consists of all ones.
```
30
```
```
4
```
```
Returns: 64
```
```
25883
```
```
100000
```
```
Returns: 991000009
```

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.