Editorial for COCI '22 Contest 2 #2 Ekspert

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Suppose $y < x$ $y < x$ . The product $x \cdot y$ $x \cdot y$ can be represented as the sum of at most $\log_2 y$ $\log_{2} y$ numbers. We can do that in the following way:

$x \cdot y = \sum 2^i \cdot x$ $x \cdot y = \sum 2^{i} \cdot x$ for each $i$ $i$ where the $i^\text{th}$ $i^{th}$ position in the binary representation of $y$ $y$ is $1$ $1$ .

For example: $14 \cdot 13 = 2^0 \cdot 14 + 2^2 \cdot 14 + 2^3 \cdot 14$ $14 \cdot 13 = 2^{0} \cdot 14 + 2^{2} \cdot 14 + 2^{3} \cdot 14$

Such a solution uses at most $2 \log_2 y$ $2 \log_{2} y$ operations: $\log_2 y$ $\log_{2} y$ for storing the result in a register, and $\log_2 y$ $\log_{2} y$ for auxiliary operations.

Comments

There are no comments at the moment.