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 10

^{10}. Consider all segment [1;*L*0], [*L*0 + 1;*L*1], [*L*1 + 1;*L*2] ... Then the result equals to product of intersection of segments [1;*L*0] and [1;*n*] by*L*0 plus size of intersection of [*L*0 + 1;*L*1] and [1;*n*] multiplied by*L*1 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*≤ 10^{9}, 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 2^{64}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.
dfrom allD_{i}"D_{j}new value" - if you update those where Minimum(l, r) = 0, then the Count queries will fail right?Lucky Array (Div1 E) ,

How to implementSegment_Tree?

Who can explain the solution in detail ?

In

Problem 122A, A. Lucky Division, what is the meaning of evenly divided, because this has been accepting the answers for 49 as YES. I don't understand why it should be a YES?Because 49 is divided by 7

Yeah, I do understand that, but what is the meaning of term

evenly dividedin the problem statement. I didn't understand the context of this word because 7 divides 49, 7 times which isn't even."Evenly" means "exactly" here

Lucky Array 121E — 72 testcases and still passes O(n*m*log(10^4)) :0 Code

It's actually faster than $$$O(n\cdot m\cdot log(n))$$$ because you only update the BIT when a number becomes or "unbecomes" lucky, this can only happen at most 60 times per number, so it's actually $$$O(n(m+60 \log n))$$$.

Still more than 4 sec. :D

It's a perfectly valid solution, the heaviest part $$$O(nm)$$$ has a small constant because it's very simple and cache-friendly. I have just written a blog post about this, I believe people will find it useful.

I have implemented the same code and it passed all test cases, and worst time was around 2 secs.

Submission

IN problem Div1(A) or Div2(c) how to create those lucky numbers from 1 to 10^10?

For each length of number L, the are only 2^L possible lucky numbers (since there are 2 possibilities for each digit: 4 or 7).

Generate instead all possible bitmasks of length L (for L = 1 to 10), and replace 0s with 4s, 1s with 7s. Note that you need to include bitmasks with leading zeros.

Python implementation: https://paste2.org/YfMYvaXe

Solution of Lucky Division — 122A beta round 91 With Full Explanationhttps://codeforcer.blogspot.com/2023/05/lucky%20division.html