Exercise: fast exponentiation

Write a function long long power(long long base, int exp) that returns base raised to the power exp. The number of multiplications must grow as O(log exp), not as O(exp). For an even exponent, power(b, 2 * k) equals p * p, where p is the value of power(b, k). For an odd exponent, power(b, exp) equals b * power(b, exp - 1).

• power(2, 10) → 1024
• power(3, 13) → 1594323
• power(-2, 5) → -32

Constraints: exp is at least 0, and any number to the power 0 is 1. The base may be negative, and the result always fits in a long long.

Do not add extra #include lines unless the task says so explicitly.