Due to the tutorial in this contest's blog said:

"I will add tutorial later. But I will give you a hint: number of numbers with maximal prime divisor<=100 is near 3000000 numbers."

But 13 years passed, he didn't add it 'later'. So I tried to add a tutorial.

In this problem, the only way to change A is A *= B. That means the goal number can only be obtained by add B to the goal number's divisor and *=B. We can perform B++ and A *= B for at most 100 times in total, so we all the prime divisor of the goal number should be less than 100.

If you write a simple DFS you will find the conclusion that maximal prime divisor<=100 is near 3e6 numbers. However, you will also find the DFS runs very quickly. So DFS is a possible solution to this problem.

While searching, memory search could be used. While a situation [a,b] is visited, it should not be visit again. Of course, [a,b+1], [a,b+2] or more should not be visit again.

So just remember every [a] with [b]. While visit an [a] with a larger [b], it will be skipped.

However, an array of 1e9 is too large-size. Hash table could be O(1), so it is the best choice. Both unordered_map and map will TLE.

Complexity: O(answer)

Code: 374287802

P.S. While searching the answer, the bigger divisors are better than the smaller ones in some times. For example, 64 could be 4*4*4(7 steps) instead of 2*2*2*2*2*2(8 steps). So we should consider all the numbers, not only the primes.