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^\text{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$

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.