Complex Number Fundamentals

Representations

A complex number $z$ admits three canonical forms:

1. Cartesian: $z = a + bi$, where $i^2 = -1$
2. Polar: $z = r(\cos\theta + i\sin\theta)$, with $r = |z|$ and $\theta = \arg(z)$
3. Euler: $z = re^{i\theta}$ via Taylor expansion equivalence

De Moivre's Theorem

For multiplication and powers: $$(r(\cos\theta + i\sin\theta))^n = r^n(\cos n\theta + i\sin n\theta)$$ $$(r_1e^{i\theta_1})(r_2e^{i\theta_2}) = r_1r_2e^{i(\theta_1+\theta_2)}$$ Geometrically, multiplication scales magnitudes and adds phases.

Roots of Unity

The $n$-th roots of unity are solutions to $z^n = 1$, denoted $\omega_n^k = e^{2\pi ik/n}$ for $k = 0, \dots, n-1$. Critical properties include:

• Periodicity: $\omega_n^n = \omega_n^0 = 1$
• Halving: $\omega_n^k = \omega_{2n}^{2k}$
• Symmetry: $\omega_{2n}^{k+n} = -\omega_{2n}^k$

C++ Complex Type

#include <complex>
using cd = std::complex<double>;
cd z(3.0, 4.0);          // 3+4i
cd z2(std::cos(t), std::sin(t)); // Euler form
double real = z.real();
double imag = z.imag();
cd conj_z = std::conj(z);
cd product = z * z2;

Polynomial Representations

Coefficient Form

A degree-$(n-1)$ polynomial $P(x) = \sum_{i=0}^{n-1} a_ix^i$ is uniquely determined by vector $\mathbf{a} = (a_0, a_1, \dots, a_{n-1})$.

Point-Value Form

By the Fundamental Theorem of Algebra, $n$ distinct points $(x_i, P(x_i))$ uniquely determine $P$. To multiplication $R(x) = P(x) \cdot Q(x)$, point-value representation enables $O(n)$ pairwise multiplication versus $O(n^2)$ convolution in coefficient form.

Transformation Complexity

Naive conversion between forms requires $O(n^2)$ operations. The Fast Fourier Transform achieves $O(n \log n)$ by exploiting special evaluation points: the roots of unity.

The FFT Algorithm

Given $P(x)$ of degree $n-1$ (where $n$ is a power of 2), decompose by parity: $$P(x) = P_{\text{even}}(x^2) + x \cdot P_{\text{odd}}(x^2)$$

where $P_{\text{even}}$ contains even-indexed coefficients and $P_{\text{odd}}$ contains odd-indexed coefficients.

Evaluate at $\omega_n^k$ where $k < n/2$: $$P(\omega_n^k) = P_{\text{even}}(\omega_{n/2}^k) + \omega_n^k \cdot P_{\text{odd}}(\omega_{n/2}^k)$$

Using the symmetry property for $k + n/2$: $$P(\omega_n^{k+n/2}) = P_{\text{even}}(\omega_{n/2}^k) - \omega_n^k \cdot P_{\text{odd}}(\omega_{n/2}^k)$$

This butterfly recurrence computes $n$ point-values from $n/2$ values recursively, yielding $O(n \log n)$ complexity via the Master Theorem.

Inverse FFT

The DFT matrix $V$ with entries $V_{jk} = \omega_n^{jk}$ has inverse: $$V^{-1} = \frac{1}{n}\overline{V}$$

where $\overline{V}$ uses conjugate roots $\omega_n^{-k} = e^{-2\pi ik/n}$. Thus, IFFT executes an FFT with:

1. Conjugate twiddle factors
2. Final division by $n$

This recovers coefficients from point-values in $O(n \log n)$.

Algorithmic Optimizations

Real Polynomial Packing

To compute DFTs of two real polynomials $A(x)$ and $B(x)$ simultaneously:

1. Construct $C(x) = A(x) + iB(x)$
2. Compute $\text{DFT}(C)$
3. Extract: $\text{DFT}(A)_k = \frac{1}{2}(\hat{C}k + \overline{\hat{C}{n-k}})$ and $\text{DFT}(B)_k = \frac{1}{2i}(\hat{C}k - \overline{\hat{C}{n-k}})$

Iterative Bit-Reversal

Recursive FFT incurs overhead. Observe that $\omega_n^k$'s final position equals $k$ with bits reversed (e.g., $001 \to 100$ in 3-bit). Precomputing this permutation enables an iterative bottom-up approach:

1. Permute input array by bit-reversed indices
2. Merge length-$m$ DFTs into length-$2m$ DFTs iteratively for $m = 1, 2, 4, \dots$

Implemantation

Polynomial multiplication for large integers (treating digits as coefficients):

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

using comp = complex<double>;
const double PI = acos(-1);

void dft(vector<comp>& signal, bool invert) {
    int n = signal.size();
    
    // Bit-reversal permutation
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(signal[i], signal[j]);
    }
    
    // Iterative butterfly
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        comp wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            comp w(1);
            for (int j = 0; j < len / 2; ++j) {
                comp u = signal[i + j];
                comp v = signal[i + j + len/2] * w;
                signal[i + j] = u + v;
                signal[i + j + len/2] = u - v;
                w *= wlen;
            }
        }
    }
    
    if (invert) {
        for (auto& x : signal) x /= n;
    }
}

vector<int> multiply_polynomials(const vector<int>& a, const vector<int>& b) {
    vector<comp> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < (int)a.size() + (int)b.size()) n <<= 1;
    fa.resize(n);
    fb.resize(n);
    
    dft(fa, false);
    dft(fb, false);
    for (int i = 0; i < n; ++i) fa[i] *= fb[i];
    dft(fa, true);
    
    vector<int> result(n);
    for (int i = 0; i < n; ++i) result[i] = round(fa[i].real());
    return result;
}

int main() {
    string num1, num2;
    cin >> num1 >> num2;
    
    vector<int> coeff1(num1.size()), coeff2(num2.size());
    for (int i = 0; i < (int)num1.size(); ++i)
        coeff1[i] = num1[num1.size() - 1 - i] - '0';
    for (int i = 0; i < (int)num2.size(); ++i)
        coeff2[i] = num2[num2.size() - 1 - i] - '0';
    
    vector<int> prod = multiply_polynomials(coeff1, coeff2);
    
    // Handle carry
    int carry = 0;
    for (int i = 0; i < (int)prod.size(); ++i) {
        prod[i] += carry;
        carry = prod[i] / 10;
        prod[i] %= 10;
    }
    while (carry) {
        prod.push_back(carry % 10);
        carry /= 10;
    }
    
    // Trim leading zeros
    int last = prod.size() - 1;
    while (last > 0 && prod[last] == 0) --last;
    
    for (int i = last; i >= 0; --i) cout << prod[i];
    return 0;
}