Generate all the divisors and check whether at least one of them is a lucky number or not.
This is an implementation problem. As the length of the string is quite small, every step can be trivially implemented, without any worrying of TLE.
Instead of directly computing each next[i], we previously find out all the lucky numbers, and equivalently enumerate the lucky numbers. The total number of lucky integers that are less than 109 is about 1024, and we can use bitmask to generate all of them. Nevertheless, we still need one more lucky integer, i.e., 4444444444, which is the value of next[i] for all i > 777777776. It is obvious that for any integer i between two lucky integers, next[i] is always equal to the second lucky imteger. Therefore, we can calculate how many integers belong to the interval of two neighboring lucky integers, and update the answer.
Let us see what happens when we meet the first “47”. If it is changed into “44”, then we can move on to find the next “47”. If it is changed into “77”, then we should check the digit before this “77”. If it is not “4”, then we can move on again; otherwise we have “477” now. It can be seen that we will get stuck into a loop, i.e., we should change “477” into “447” while later change it back into “477” again. For this case, the final result depends on whether the number of operations is odd or even.
To find the k-th lexicographic small permutation, it is sufficient to consider the last 13 digits, since 13! > 109. Then, the main issue is to find out the k-th lexicographic small permutation. There is a standard algorithm to solve this problem, referred to as Cantor Expansion, and one can search a lot of information and materials on the Internet.
Comments (0)
