You’re given array D of size N and Q queries X. In each query you have to compute the result of the program

read X
for i = 1..N:
X = floor(X / D[i])
print X

QUICK EXPLANATION:

You should consider only O(\log X) terms such that D_i\neq 1.

EXPLANATION:

You may keep keep first \min(2\cdot\log_2 X, N) terms of D which aren’t equal one. If there are more non-one terms than X wiil definitely be equal zero at the end of procedure.

ALTERNATIVE SOLUTION:

You can keep product P of non-one terms of D instead of keeping this terms and divide X by P. But you should check then that you output zero if there are too much such terms.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

Hey GUYS, PLz Give it a look , when i was doing this question i came to know an interesting fact that if i was using floor func then it’s giving TLE for subtask 2 , and if I was using int then it’s giving correct ans
NOTE: always use int type only.
SOLN :

/* AUTHOR : fad_coder00000 “FAD means enthusiasm for something” *

Can anyone explain how alternative solution given in editorial is correct.

Also if ceil is considered (instead of floor) in the question, is the alternative solution (divide the given number with the product of array elements and then take ceil) still works?

[[x/a]/b]=[x/(a*b)], where [y] means the greatest integer not greater than y. Prove it

So, [[[x/d1]/d2]/…]/dn] = [[[x/(d1d2)]/d3]/…]/dn] = … [x/(d1d2…*dN)], the only one problem is that d1 * d2 * d3 * … * dn can not fits in long long, so you need to take min(d1 * d2 * … * dn, 1e18), but you need accurately do that.

long long INF = (long long)1e18 + 1;

if (curMul * di > INF) curMul = INF; // curMul * di can overflow, cause curMul < 1e18, di < 1e9.