// Write a program that calculates A*B for non-negative integers A, B

// spending O(log(min(A,B))). 

// The only arithmetic operations that can be used are +, -, /2 and parity check (%2).

using System;

​

public class Program

{

    public static int InputInt(string prompt)

    {

        Console.Write("Enter " + prompt + ": ");

        return Convert.ToInt32(Console.ReadLine());

    }

    public static int IntProd(int a, int b)

    {

        int x, y;

        if(a < b)

        {

            x = a;

            y = b;

        }

        else

        {

            x = b;

            y = a;

        }

        // x*y = a*b and x = min(a,b)

        int r = 0;

        // inv: r = a*b - x*y and x >= 0

        while (x != 0)

        {

            // x > 0

            if (x % 2 != 0)

            {

                x--; 

                r += y;

            }

            // r = a*b - x*y and x>=0 and x is even

            x /= 2;

            y += y;

        }

        return r;

        // r = a*b - x*y and x = 0 => r = a*b

        // Time complexity: original x = min(a,b) decreased twice on each iteration => O(log(min(a,b)))

    }

    public static void Main()

    {

        int a = InputInt("a");

        int b = InputInt("b");

        Console.WriteLine("a * b = " + IntProd(a, b));

    }

}