Egyptian multiplication
Statement
Goal
You have to multiply two integers (a&b) by means of a method used in Ancien Egypt, described in Rhind’s hieratic papyrus written circa −1650 by Ahmes. This method is still used in Russia.First, sort the two numbers.
Then follow the steps below, the algorithm uses base-2 decomposition of the biggest number.
We multiply 12 by 5, here is what you have to print, excepted the comments after hashes.
12 * 5
= 12 * 4 + 12 # Divide 5 by 2, the remain is 1 and 5=2×2+1, thus 12*5=12*(2*2+1)=12*2*2+12=24*2+12
= 24 * 2 + 12 # Divide 2 by 2, 2=1*2+0 and 12*5=24*(1*2+0)+12=48*1+12
= 48 * 1 + 12 # Divide 1 by 2, 1=0*2+1 and 12*5=48*(0*2+1)+12=12+48
= 48 * 0 + 12 + 48 # End of the algorithm
= 60
Input
Two integers separated by a space.
Output
The description of the successive operations.
Constraints
0<= a, b <= 32768
Example
Input
3 12
Output
12 * 3 = 12 * 2 + 12 = 24 * 1 + 12 = 24 * 0 + 12 + 24 = 36
Tags
Difficulty
Test cases
Simple a<b Test
Input
3 12
Output
12 * 3
= 12 * 2 + 12
= 24 * 1 + 12
= 24 * 0 + 12 + 24
= 36
Validator 1 Validator
Input
7 28
Output
28 * 7
= 28 * 6 + 28
= 56 * 3 + 28
= 56 * 2 + 28 + 56
= 112 * 1 + 28 + 56
= 112 * 0 + 28 + 56 + 112
= 196
Simple a>b Test
Input
20 2
Output
20 * 2
= 40 * 1
= 40 * 0 + 40
= 40
Validator 2 Validator
Input
19 4
Output
19 * 4
= 38 * 2
= 76 * 1
= 76 * 0 + 76
= 76
Zero Test
Input
0 1
Output
1 * 0
= 0
Validator 3 Validator
Input
0 180
Output
180 * 0
= 0
Bigger numbers Test
Input
7675 179
Output
7675 * 179
= 7675 * 178 + 7675
= 15350 * 89 + 7675
= 15350 * 88 + 7675 + 15350
= 30700 * 44 + 7675 + 15350
= 61400 * 22 + 7675 + 15350
= 122800 * 11 + 7675 + 15350
= 122800 * 10 + 7675 + 15350 + 122800
= 245600 * 5 + 7675 + 15350 + 122800
= 245600 * 4 + 7675 + 15350 + 122800 + 245600
= 491200 * 2 + 7675 + 15350 + 122800 + 245600
= 982400 * 1 + 7675 + 15350 + 122800 + 245600
= 982400 * 0 + 7675 + 15350 + 122800 + 245600 + 982400
= 1373825
Validator 4 Validator
Input
7675 179
Output
7675 * 179
= 7675 * 178 + 7675
= 15350 * 89 + 7675
= 15350 * 88 + 7675 + 15350
= 30700 * 44 + 7675 + 15350
= 61400 * 22 + 7675 + 15350
= 122800 * 11 + 7675 + 15350
= 122800 * 10 + 7675 + 15350 + 122800
= 245600 * 5 + 7675 + 15350 + 122800
= 245600 * 4 + 7675 + 15350 + 122800 + 245600
= 491200 * 2 + 7675 + 15350 + 122800 + 245600
= 982400 * 1 + 7675 + 15350 + 122800 + 245600
= 982400 * 0 + 7675 + 15350 + 122800 + 245600 + 982400
= 1373825
Solution language
Solution
Stub generator input