Блог пользователя haribhatt34

Can't Understand this Question
Автор haribhatt34, история, 6 лет назад, По-английски

I am having trouble understanding this question. Sorry the images are not quite clear, it's a snapshot from the PC. This question was asked previous year by a company which came to our college for recruitment.

The input example given are more like the multiple of 5. But I think there is more the question I am missing.

Thanks

UPDATE Don't know why images are not getting uploaded. Image 1, part 1 Image 1, part 2

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 10   Проголосовать: нравится 0 Проголосовать: не нравится

Note that F(X) is the power of 5 in the prime number factorization of X.

In the given example, 250 = 21.53 is the prime number factorization of 250. Therefore, F(250) = 3.

If X is not divisible by 5, then F(X) = 0.

Let p be the largest integer such that

.

Then, the answer to the query N is 5p.

S(p) can be computed iteratively as

S(p) = S(p - 1) + F(5p), where p ≥ 1, and the base case is S(0) = 0.

Finally, the sequence S(0), S(1), S(2), ... is strictly increasing, as it is guaranteed that F(5p) ≥ 1. Therefore, the sequence can be stored in an int array or a vector<int> C++ object when the maximum value of N is known, and the standard library function lower_bound() can be used to find the answer to each query using binary search.

→ Ответить