Answer is $$$floor(sqrt(r)) — floor(sqrt(l — 1))$$$.

Alternatively you can use binary search to calculate square root.

You always can make all bits less or equal to the most significant bit set to $$$1$$$. Also you cant make most significant bit greater.

Just go through numbers and find the minimal most significant bit.

Answer is number with all bits less or equal to minimal most significant bit set to $$$1$$$.

Best way to choose the integer is the $$$gcd$$$ of all elements in the array except for element you want to change.

So you just need to calculate the $$$gcd$$$ of all elements in the array except for one in some fast way.

You can use pre-calculated prefix/suffix $$$gcd$$$ to do it.

Also take care about the case $$$n = 1$$$, The answer for this case will be always $$$10^9$$$.

We can imagine that Alice and Bob are on different sides of the river. It's obvious that in this case best path is just straight line between Alice and Bob.

So you can just negate $$$y$$$ coordinate for Bob and calculate the Euclidean distance of the obtained point with the other point, It can be proven that the obtained distance is the shortest possible

It's obvious that you can change bases in original formula to their last digits.

After you can just check some cases.

$$$1^{10x+1}$$$ mod $$$10$$$ is always $$$1$$$
$$$2^{10x+2}$$$ mod $$$10$$$ is switching between $$$4$$$ and $$$6$$$
$$$3^{10x+3}$$$ mod $$$10$$$ is switching between $$$7$$$ and $$$3$$$
$$$4^{10x+4}$$$ mod $$$10$$$ is always $$$6$$$
$$$5^{10x+5}$$$ mod $$$10$$$ is always $$$5$$$
$$$6^{10x+6}$$$ mod $$$10$$$ is always $$$6$$$
$$$7^{10x+7}$$$ mod $$$10$$$ is switching between $$$3$$$ and $$$7$$$
$$$8^{10x+8}$$$ mod $$$10$$$ is switching between $$$6$$$ and $$$4$$$
$$$9^{10x+9}$$$ mod $$$10$$$ is always $$$9$$$
$$$0^{10x+0}$$$ mod $$$10$$$ is always $$$0$$$

First, for a set $$$S_{i}$$$ imagine splitting $$$\frac{F(Si)}{P(Si)}$$$

For example, if my set is $$$S = {1, 2, 3}$$$.

Then my splitting for $$$\frac{F(S)}{P(S)}$$$ will be : $$$1 ∗ (\frac{1}{1∗2∗3})$$$ $$$+$$$ $$$2 ∗ (\frac{1}{1∗2∗3})$$$ $$$+$$$ $$$3 ∗ (\frac{1}{1∗2∗3})$$$.

. Every such split has some coefficient of every number from 1 to n . In this example coefficients are (16,16,16,0,0..) .

What would be the coefficient of some number i in my entire sum? It will be the in form ∑(1Pj) , where Pj means the product of a subset having i . I sum this over all subsets containing i . So, imagine selecting some numbers from a bunch of (11,12,13,...1n) under the condition that 1i must be selected, then adding them up. It is easy to see it will be (1+11)(1+12)(1+13)..(1i)..(1+1n) . This is because while multiplying, every number t (except i ) has a choice of getting selected or rejected (hence, 1 or 1t ). However, we gotta select 1i , so I multiply my 1i .

So, now we got the coefficient of number i . Final answer will be:

∑i∗Ci where, Ci=(1+11)(1+12)(1+13)..(1i)..(1+1n)