In this problem you just need to loop through the integers i from 1 to n determine, is i lucky, if yes, then try, if n mod i = 0, then answer is "YES". If there are no such i, answer is "NO".
Notice, that answer is either one digit or -1. So, if there are no 4 and 7 digits, then answer is -1. Else, if there is more or equel number of digits 4, then answer is 4, else answer is 7.
Let generate all lucky number between 1 and 1010. Consider all segment [1;L0], [L0 + 1;L1], [L1 + 1;L2] ... Then the result equals to product of intersection of segments [1;L0] and [1;n] by L0 plus size of intersection of [L0 + 1;L1] and [1;n] multiplied by L1 and so on.
Notice, that if there exits such i that i mod 2 = 0 and d i = 4 and d i + 1 = 7 and d i - 1 = 4 then after that operation there will be a loop. So, let we simple do all operation from left ro right, and, when we will win our loop, just return a rusult (which variates by k mod 2 ( k is one that leaves after operation from left side).
If n ≤ 14 let find out, is k more than n! or not? If yes, then return -1. Then, notice, that since k ≤ 109, then at most 13 elements from right (suffix) will change. So, element from left of this part (prefix) will not change (then we can just find a number of lucky numbers on than range). To find result for the rest of the permutation (suffix) we need to find k-th permutation of number from 1 to t ( t is maximun integer, such that t! ≤ k). After we find that permutation, we can just loop through that permutation and count result.
Lei calculate arrays L and R. Let for all lucky i, L[i] = number of operation needed to move every segment, which's right end is to left from i to i. R[i] = number of operation needed to move every segment which left end is to right to i. How to calculate such array? Just use a sorting. Let arrange array A of pairs of integers, first - number, second equals to 0, if that number end of some segment, 1 if that number is lucky. Then, iterate from left to right, counting number of segment end we counted and s i, s i = s i - 1 + (A i - A i - 1) * c i. The same way you can use to R. Now, to find the answer we must find (using method of two pointers of binary search) pair of indexes x and y, such that i ≤ j, L j + R i ≤ k, Lucky j - Lucky i + 1 ≤ min_size_of_input_segment. Also, is this problem you should arrange function Mul(a, b), which return min(a * b, INF). Since simple multiplication overflows, then you can use multipling modulo 264 or double or min-long-arithmetic.
In this problem you can use many different algorithms, here is one of them. Obviously, number of different lucky number is 30, because A i always is ≤ 10000. Let D i - difference between minimum lucky number which is greater than or equal to A i and A i. Now, we need to have 5 (but you can use less number) of operation on D: Subtract(l, r, d) - subtract number d from all A i (l ≤ i ≤ r), Minimum(l, r) - minumum number of all D i (l ≤ i ≤ r), Count(l, r) - how many times that minimum occared in that interval, Left(l, r) = leftmost occarence of that minimum, Set(i, d) - assign d to D i ( D i = d). Now, we can do our operations. If our operation is "count", then we need to find minimum number d ( d = Minimum(l, r)), if it is equal to 0, then answer is Count(l, r, 0), otherwise, answer is 0. If out operation is "add", then we need to Subtract(l, r, d), but now some D i might be less than 0. So, while, Minimum(l, r) ≤ 0, let j = Left(l, r), assign D j new value (use Set(j, D j')), which can be calculated with complaxity O(1).
Complexity of this algorithm is O(m * log(n) + n * log(n) * C), where C is equal to 30.