Informatica Online Judge

  고대 이집트 곱셈 (a la russe recursion) [1080 / 0438]

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


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

[JeongHJ]

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]