Informatica Online Judge

  Ancient Egyptian multiplication(a larusse Ag.) [0127 / 007F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 1574   Total Tried : 1781


The Champion of this Problem (C++) : gs17074 - ms / 81byte
My Best Submission (C++) : N/A

[]

Background

a larusse 알고리즘이란 컴퓨터에서 곱셈을 빠르고 쉽게 할 수 있는 알고리즘이다.
이 알고리즘은 오직 덧셈과 쉬프트 연산만을 이용해서 이루어진다. 두 정수 a, b를 곱하는 알고리즘은 다음과 같다.

(1) declare n1, n2, n3
(2) set n1 = a, n2 = b, n3 = 0
(3) if n1 is odd then n3 = n3 + n2
(4) n1 = n1 >> 1, n2 = n2 << 1 ( << = left shift, >> = right shift )
(5) if n1 != 0 then goto (3)
(6) print n3

위 알고리즘을 이용하여 입력받은 두 정수의 곱을 구하는 프로그램을 작성하시오.

Input

두 정수 a, b가 공백으로 구분되어 입력된다. (두 정수의 곱이 2^31-1보다 크지 않다.)

Output

계산된 결과를 출력한다.

IO Example

입력
6 3

출력
18

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]