DivisibleSequence
SRM 565 · 2012-06-05 · by gojira_tc
SRM 565 · 2012-06-05 · by gojira_tc · Math
Problem Statement
Problem Statement
A divisible sequence with starting value N and length H is a sequence of positive integers with the following properties:
int s 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).
- 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].
Constraints
- N will be between 1 and 1,000,000,000, inclusive.
- H will be between 1 and 1,000,000,000, inclusive.
Examples
0)
5 3 Returns: 3
The three possible sequences are: 5, 5, 5 5, 5, 1 5, 1, 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
2)
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.
3)
1 10000 Returns: 1
The only possible sequence consists of all ones.
4)
30 4 Returns: 64
Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DivisibleSequence with a public method int count(int N, int H) · 98 test cases · 2 s / 256 MB per case