How to approach this problem

help
1

Unique Birthday Gift

Your birthday is coming soon and one of your friends, Alex, is thinking about a gift for you. He knows

that you really like integer arrays with interesting properties.

He selected two numbers, N and K and decided to write down on paper all integer arrays of length K

(in form a[1], a[2], …, a[K]), where every number a[i] is in range from 1 to N, and, moreover, a[i+1] is

divisible by a[i] (where 1 < i <= K), and give you this paper as a birthday present.

Alex is very patient, so he managed to do this. Now you’re wondering, how many different arrays are

written down on this paper?

Since the answer can be really large, print it modulo 10000.

Input:

The first line contains an integer, n, denoting the maximum possible value in the arrays.

The next line contains an integer, k, denoting the length of the arrays.

Sample cases:

Input

2 1

2 2

3 2

Output:

2 The required length is 1, so there are only two possible arrays: [1] and [2].

3 All possible arrays are [1, 1], [1, 2], [2, 2]. [2, 1] is invalid because 1 is not divisible by2.

5 All possible arrays are [1, 1], [1, 2], [1, 3], [2, 2], [3, 3].

2

It is a tough problem especially for your level and I think you should skip it for now. I’ve seen somebody already ask about the problem and get an O(K \cdot N^2) DP solution, which is obviously not optimal, unless constraints are N, K < 500. I’ll try to explain an O(N \log N) and O(N \sqrt{N}) solution here.

Let’s consider P_n to be the number of sequences ending at n, formally A_k = n. The final answer will obviously be \sum_{i=1}^{N}{P_i}.

How do we calculate this value though? Notice that if A_i = X, A_{i + 1} = X \cdot p, such that \frac{n}{X} is divisible by p, where n is the final term of sequence. This means that all we actually care about is at what positions in final sequence we’ll distribute divisors of n.

In conclusion we should find a way to distribute instances of every prime divisor of n over the given K places. This can be easily done using the stars and bars technique, so supposing p occurs c times as a divisor of n, we multiply answer of n by {K - 1 + c}\choose{c}. Finally repeat this step for every one of its divisors. You can use sieve or go up to the square root most likely, as I don’t suspect the constraints to be above 10^5, but in case it is 10^6, sieve gets the job done.

Just one final detail, in case you opt to use sieve, you’ll need to keep track of smallest prime factors, because this way prime factorization is done in O(\log n), otherwise it’s pointless to use it.

I hope I could help, but as I previously said, this problem is far beyond your current level and you shouldn’t focus on trying to understand every part of it. :slight_smile:

1 Like