Viết hàm lặp O(Log y) tính pow(x, y) C++

Trong bài toán này, cho hai số nguyên x và y. Nhiệm vụ tạo hàm tương đương pow(x,y) dùng cách lặp với độ phức tạp O(log y).

Ví dụ:

Input

x = 7, y = 3

Output

343

Hàm lặp pow(x,y): lặp và cập nhật kết quả cho y lẻ (nhân x), cập nhật x = x^2 mỗi lần lặp.

Ví dụ minh họa

#include <iostream>
using namespace std;

void calcPower(int x, unsigned int y) {
    int result = 1;
    while (y > 0) {
        if (y & 1)
            result *= x;
        y = y >> 1;
        x = x * x;
    }
    cout << result;
}

int main() {
    int x = 7;
    unsigned int y = 3;
    cout << x << " mũ " << y << " là ";
    calcPower(x, y);
    return 0;
}

Kết quả

7 mũ 3 là 343