Chương trình tính lũy thừa của số phức trong O(log n) trong C++

Cho số phức a + bi và số nguyên n. Tính (a + bi)^n trong O(log n) bằng phương pháp chia để trị (binary exponentiation).

Công thức nhân số phức

(a+bi)(c+di) = (ac - bd) + (ad + bc)i

Thuật toán

• Hàm cmul(x, y): nhân hai số phức (dạng mảng 2 phần tử).
• Hàm power(x, n):
  • n=0 → trả về 0+0i (hoặc 1+0i tùy định nghĩa).
  • n=1 → trả về x.
  • Đệ quy: half = power(x, n/2).
  • Nếu n chẵn: trả về cmul(half, half).
  • Nếu n lẻ: trả về cmul(x, cmul(half, half)).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll* cmul(ll* a, ll* b) {
    ll* res = new ll[2];
    res[0] = a[0]*b[0] - a[1]*b[1]; // thực
    res[1] = a[0]*b[1] + a[1]*b[0]; // ảo
    return res;
}

ll* power(ll* x, ll n) {
    if (n == 0) {
        ll* z = new ll[2]{0, 0}; // 0+0i
        return z;
    }
    if (n == 1) return x;
    ll* half = power(x, n/2);
    ll* sq = cmul(half, half);
    if (n % 2 == 0) return sq;
    return cmul(x, sq);
}

int main() {
    ll* x = new ll[2]{10, -11}; // 10 - 11i
    int n = 4;
    ll* ans = power(x, n);
    cout << ans[0] << " + i(" << ans[1] << ")" << endl;
    // Giải phóng bộ nhớ (tránh leak)
    delete[] x; delete[] ans; // cần quản lý cẩn thận hơn trong code thực
    return 0;
}

Kết quả

-47959 + i(9240)

Lưu ý: Code dùng cấp phát động new đơn giản hóa, thực tế nên dùng struct Complex hoặc std::complex để an toàn bộ nhớ.