Consider a sequence , in which let and . Apparently there are a lot of sequences like that. For each , is selected randomly with equal possibilities among the divisors of . Let's denote the expected value of . What is ? Read the problem statement.

For example, we have and need to calculate . All possible sequences of are:

Can we simply calculate the average value of ?, in this case:

No we can't, because the possibilities for the sequences to happen are not all the same. For example, the possibility of is , while that of is only .

Consider (prime factorization). The process of choosing (which is a divisor of ) can be interpreted as independent steps (events). In step , we choose as a random number from 0 to . After all steps, we have .

This means, instead of dealing with the problem above with any number , we can break it down into (the number of prime factors of ) smaller problems. Each small problem requires finding the expected value of given , in other word, finding . Suppose that , then:

How do we calculate ? This should be done easily with dynamic programming or recursion. We consider the probability for the -th term of the sequence to equal :

Then the rest is straightforward:

Factorizing takes . Calculating takes . Since , the overall complexity is .

See my solution written in C++.