This is a quite simple problem about probability but it costs me 20 minutes to varify the correctness of my method. Fortunately, I got Accepted at the first try. BTW, my code runs in about 0 seconds(cuz time complexity is O(32 * 32)). As described, every integer in this sequence are independent and their possibility to be a specific integer are equal. Assuming that we already collect i bits out of 32 bits then we take another integer from the sequence and how many different kind of bits we can get now. It’s simple to figure out the fomula.

As we only need calculate the number of divisors for integers 1 < n < 10^7, It says possible to bruteforce whose running time is $O(n \times \sqrt{n})$. Of course this method is far from satisfy. My code runs in 0.869 seconds. The insights is that for every number n we have $n = p_1^{m_1} \times p_2^{m_2} \times … \times p_i^{m_i}$ and the number of factors of n is $m_1 \times m_2 \times … \times m_i$.

This is an easy problem with only 25% difficulty rating and it costs me about 10min to code. My code runs in 0s. The idea is so simple that we can calculate rad(n) for every n from 1 to 100000. As an optimization, a priority queue is used to keep the first 10000 smallest values.

It’s too hard for me that didn’t figure out the answer until refer to others’ solution.

First of all, we can find that the number of moves is n(n + 2)refer to A005563 then what we need is to solve integes solution of equation n*(n+2) = t(t+1)/2 using this tool.

After reading problem description, It is evident that we need generate Grundy numbers from 1 to 10^6. But it will take a long period to do this. So what should we do in this case is to find if there is a pattern in Grundy numbers sequence. Brute-force to get the first several Grundy numbers and find that if we ignore non-zero values then it is a pattern.

It’s really a hard problem for me but it forces me to learn a new algorithm that computing sum of all primes below n. My code runs in 550 seconds after using OpenMP as an optimization. In order to solve this one, you’d better take a look at the method of counting primes that introduces a dp method to count the number of primes not exceeding n. This algo’s running time complexity is $O(n^{0.75})$ which is fast enough for this problem. The most important thing this problem brings to me is that there are methods to compute sum of primes without generating all primes first.

This problem can be solve using dynamic programming. My code runs in nearly 0.0 seconds. It is also works to enumerate all distinct permutations generated by given digits. Tha total amount of permutations should be 20!/(2^10) but I didn’t calculate what exactly the factorial is. I think it’s not difficult to figure out the dp solution.

Such problems are very straight forward, but if you want to make your code runs fast it needs several optimizations. My code runs in 4.04655s and I am not going to optimize it anymore. There are several observations here: 1. n + 1 must be a prime. 2. n must be an even number cuz (n + 1) wouldn’t be a prime if n is an odd. 3. n is a squarefree number.