PROBLEM LINK:
Author: Nazarbek Altybay
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu
DIFFICULTY:
Simple
PREREQUISITES:
basic maths
PROBLEM:
You are given up to 10^5 queries. In each query, you are given a number N < 10^9, you have to transform N to a number with maximum trailing zeroes by multiplying it with lucky numbers(any number of times). The decimal value of such a number should be minimum. A number is called lucky number if its decimal representations contain only lucky digits 4 and 7.
QUICK EXPLANATION:
Keep setting N = N * 4(since 4 is lucky) until y > x where x and y are powers of 2 and 5 respectively, in prime factorization of N.
EXPLANATION:
================
Observations

The most basic observation here is that trailing zeroes are nothing but powers of 10. So, if a number has prime factorization of form 2^x * 5^y ..., the number of trailing zeroes is extrm{min}(x, y) because for one trailing zero we need one 2 and one 5.

Let’s see what kind of prime factors Lucky Numbers have. We only have interest in prime factors 2 and 5. For any number with 5 as one of the prime factor, it should have a 5 or 0 as the last digit. So no lucky number has 5 as prime factor. Lucky numbers can have 2 as prime factor when the number ends in digit 4.
Now, let’s see how using above observations we arrive to our solution. Say, prime factorization of N is of form 2^x * 5^y .... We know lucky numbers cannot provide more 5's, so our only way to increase number of trailing zeroes is to add more 2's if y > x. If y \le x, we cannot increase trailing zeroes in any way by multiplying with Lucky numbers.
Also, since our aim is to get smallest possible number with most number of trailing zeroes, we will try to multiply those Lucky numbers which contribute 2's only, so we multiply with 4 until x < y.
Following pseudo code summarizes the solution:
scan N; //cnt 2 is power of 2, cnt5 is power of 5 cnt2 = cnt5 = 0; temp = N; while ((temp % 2) == 0) { cnt2++; temp /= 2; } temp = N; while ((temp % 5) == 0) { cnt5++; temp /= 5; } ans = N; while (cnt5 > cnt2) { ans *= 4; cnt2 += 2; //since we multiply with a 4 ie. 2 to the power 2 } print ans;
COMPLEXITY:
For each query, the complexity can be said as O( extrm{max}(x, y)), where x and y are powers of 2 in prime factorization of N. So complexity is, O( extrm{log} N) per query.