Introdução
Polinômios são expressões algébricas compostas pela soma de monômios. Cada monômio é um termo composto por coeficientes e variáveis elevadas a potências inteiras não negativas. A potência mais alta em um polinômio define seu grau.
Existem duas representações principais para polinômios:
Representação por Coeficientes
Um polinômio de grau $n-1$ pode ser representado por uma lista de seus coeficientes: $f(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$ Isso pode ser denotado como ${a_0, a_1, \dots, a_{n-1}}$.
Representação por Pontos (Valores)
Um polinômio de grau $n-1$ é univocamente determinado por $n$ pontos distintos em um plano. Essa representação é expressa como um conjunto de pares $(x_i, f(x_i))$: ${(x_0, f(x_0)), (x_1, f(x_1)), \dots, (x_{n-1}, f(x_{n-1}))}$
Números Complexos
Números complexos são da forma $z = a + bi$, onde $a$ é a parte real, $b$ é a parte imaginária e $i$ é a unidade imaginária com a propriedade $i^2 = -1$. Geometricamente, um número complexo pode ser representado como um ponto em um plano cartesiano, onde o eixo horizontal representa a parte real e o eixo vertical, a parte imaginária.
Propriedades importantes incluem:
- Módulo: $|z| = \sqrt{a^2 + b^2}$, a distância do ponto à origem.
- Argumento (Ângulo Polar): $\theta$, o ângulo entre o vetor que liga a origem ao ponto e o eixo real positivo.
- Conjugado: $\bar{z} = a - bi$.
Operações com números complexos:
- Adição: $(a+bi) + (c+di) = (a+c) + (b+d)i$.
- Multiplicação: $(a+bi)(c+di) = (ac - bd) + (ad + bc)i$. Geometricamente, a multiplicação de complexos envolve a multiplicação de seus módulos e a soma de seus argumentos.
Transformada Discreta de Fourier (DFT)
A DFT é um método para transformar um polinômio de sua representação por coeficeintes para sua representação por pontos. Avaliar um polinômio em $n$ pontos arbitrários leva a uma complexidade de $O(n^2)$. No entanto, se avaliarmos em pontos especiais, como as raízes da unidade, o cálculo pode ser otimizado.
Raízes da Unidade
As raízes $n$-ésimas da unidade são complexos $w$ tais que $w^n = 1$. Em um plano complexo, elas formam os vértices de um $n$-ágono regular inscrito no círculo unitário. Representadas como $w_n^k = e^{i \frac{2\pi k}{n}}$ para $k = 0, 1, \dots, n-1$.
Propriedades úteis:
- $w_n^k = \cos\left(\frac{2\pi k}{n}\right) + i \sin\left(\frac{2\pi k}{n}\right)$
- $w_n^{k+n/2} = -w_n^k$
- $w_n^0 = w_n^n = 1$
Transformada Rápida de Fourier (FFT)
A FFT é um algoritmo eficiente para calcular a DFT, reduzindo a complexidade de $O(n^2)$ para $O(n \log n)$. Ele utiliza uma abordagem de "dividir para conquistar".
Um polinômio $A(x) = \sum_{i=0}^{n-1} a_i x^i$ pode ser separado em termos de potências pares e ímpares: $A(x) = (a_0 + a_2x^2 + \dots) + (a_1x + a_3x^3 + \dots)$ $A(x) = A_1(x^2) + xA_2(x^2)$ Onde $A_1$ e $A_2$ são polinômios de grau $(n/2)-1$.
Aplicando uma raiz da unidade $w_n^k$, temos: $A(w_n^k) = A_1(w_n^{2k}) + w_n^k A_2(w_n^{2k})$ $A(w_n^{k+n/2}) = A_1(w_n^{2k+n}) + w_n^{k+n/2} A_2(w_n^{2k+n})$ $A(w_n^{k+n/2}) = A_1(w_{n/2}^k) - w_n^k A_2(w_{n/2}^k)$
Isso mostra que os valores de $A(x)$ para $w_n^k$ e $w_n^{k+n/2}$ podem ser calculados a partir dos valores de $A_1$ e $A_2$ em $w_{n/2}^k$.
Transformada Rápida de Fourier Inversa (IFFT)
Para converter a representação por pontos de volta para a representação por coeficientes, a FFT inversa é utilizada. Isso pode ser feito substituindo as raízes da unidade por seus conjugados e dividindo o resultado por $n$.
Exemplo de código FFT recursivo: Código FFT Recursivo
#include <vector>
#include <cmath>
#include <complex>
using namespace std;
const double PI = acos(-1.0);
// Estrutura para representar um número complexo, similar a std::complex
struct Complex {
double real, imag;
Complex(double r = 0.0, double i = 0.0) : real(r), imag(i) {}
Complex operator+(const Complex& other) const { return Complex(real + other.real, imag + other.imag); }
Complex operator-(const Complex& other) const { return Complex(real - other.real, imag - other.imag); }
Complex operator*(const Complex& other) const {
return Complex(real * other.real - imag * other.imag, real * other.imag + imag * other.real);
}
};
void fft(vector<Complex>& a, bool invert) {
int n = a.size();
if (n <= 1) return;
vector<Complex> a0(n / 2), a1(n / 2);
for (int i = 0; i < n / 2; ++i) {
a0[i] = a[2 * i];
a1[i] = a[2 * i + 1];
}
fft(a0, invert);
fft(a1, invert);
double ang = 2 * PI / n * (invert ? -1 : 1);
Complex w(1), wn(cos(ang), sin(ang));
for (int i = 0; i < n / 2; ++i) {
a[i] = a0[i] + w * a1[i];
a[i + n / 2] = a0[i] - w * a1[i];
w = w * wn;
}
if (invert) {
for (int i = 0; i < n; ++i) {
a[i].real /= 2;
a[i].imag /= 2;
}
}
}
Multiplicação de Polinômios
A multiplicação de dois polinômios de grau $n$ usando a representação por coeficientes tem complexidade $O(n^2)$. No entanto, com FFT, podemos obter uma solução mais eficiente:
- Converte-se ambos os polinômios para a representação por pontos usando FFT.
- Multiplicam-se os valores correspondentes em cada ponto (complexidade $O(n)$).
- Converte-se o polinômio resultante de volta para a representação por coeficientes usando IFFT.
A complexidade total se torna $O(n \log n)$.
Código completo de exemplo para multiplicação de polinômios usando FFT: Código de Multiplicação de Polinômios com FFT
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const double PI = acos(-1.0);
struct Complex {
double real, imag;
Complex(double r = 0.0, double i = 0.0) : real(r), imag(i) {}
Complex operator+(const Complex& other) const { return Complex(real + other.real, imag + other.imag); }
Complex operator-(const Complex& other) const { return Complex(real - other.real, imag - other.imag); }
Complex operator*(const Complex& other) const {
return Complex(real * other.real - imag * other.imag, real * other.imag + imag * other.real);
}
Complex operator/(double scalar) const { return Complex(real / scalar, imag / scalar); }
};
void fft(vector<Complex>& a, bool invert) {
int n = a.size();
if (n <= 1) return;
vector<Complex> a0(n / 2), a1(n / 2);
for (int i = 0; i < n / 2; ++i) {
a0[i] = a[2 * i];
a1[i] = a[2 * i + 1];
}
fft(a0, invert);
fft(a1, invert);
double ang = 2 * PI / n * (invert ? -1 : 1);
Complex w(1), wn(cos(ang), sin(ang));
for (int i = 0; i < n / 2; ++i) {
a[i] = a0[i] + w * a1[i];
a[i + n / 2] = a0[i] - w * a1[i];
w = w * wn;
}
if (invert) {
for (int i = 0; i < n; ++i) {
a[i].real /= 2.0; // Use 2.0 for double division
a[i].imag /= 2.0;
}
}
}
vector<long long> multiply(vector<int>& a, vector<int>& b) {
int n = 1;
while (n < a.size() + b.size()) n <<= 1;
vector<Complex> fa(n), fb(n);
for (int i = 0; i < a.size(); ++i) fa[i] = Complex(a[i]);
for (int i = 0; i < b.size(); ++i) fb[i] = Complex(b[i]);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; ++i) fa[i] = fa[i] * fb[i];
fft(fa, true);
vector<long long> result(n);
for (int i = 0; i < n; ++i) result[i] = round(fa[i].real);
return result;
}
// Exemplo de uso
int main() {
vector<int> poly1 = {1, 2, 3}; // Representa 1 + 2x + 3x^2
vector<int> poly2 = {4, 5}; // Representa 4 + 5x
vector<long long> product = multiply(poly1, poly2);
cout << "O produto dos polinômios é: ";
for (int i = 0; i < product.size(); ++i) {
if (product[i] != 0) {
cout << product[i] << (i > 0 ? "x^" : "") << (i > 1 ? to_string(i) : "") << (i < product.size() - 1 && product[i+1] != 0 ? " + " : "");
}
}
cout << endl;
return 0;
}
Transformada Rápida de Teoria dos Números (NTT)
A FFT utiliza números complexos e ponto flutuante, o que pode introudzir imprecisões. A NTT é uma alternativa que usa aritmética modular para evitar problemas de precisão. Ela substitui as raízes da unidade complexas por raízes da unidade em um campo finito (geralmente módulo um número primo grande).
Ordem de um Elemento
Em um grupo multiplicativo $(\mathbb{Z}/p\mathbb{Z})^*$, onde $p$ é primo, a ordem de um elemento $a$ (coprimo com $p$) é o menor inteiro positivo $n$ tal que $a^n \equiv 1 \pmod{p}$.
Raiz Primitiva
Uma raiz primitiva módulo $p$ é um elemento $g$ cuja ordem é $\phi(p)$ (onde $\phi$ é a função totiente de Euler). Se $p$ é primo, $\phi(p) = p-1$. Uma raiz primitiva $g$ satisfaz $g^{p-1} \equiv 1 \pmod{p}$.
A NTT utiliza uma raiz primitiva $g$ para construir "raízes da unidade" modulares. Por exemplo, $g^{(p-1)/n} \pmod{p}$ pode atuar como a $n$-ésima raiz da unidade.
Código de exemplo para NTT: Código NTT
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
// Um módulo primo comum para NTT
const int MOD = 998244353;
// Uma raiz primitiva para MOD
const int PRIMITIVE_ROOT = 3;
ll power(ll base, ll exp) {
ll res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
void ntt(vector<ll>& a, bool invert) {
int n = a.size();
if (n <= 1) return;
vector<ll> a0(n / 2), a1(n / 2);
for (int i = 0; i < n / 2; ++i) {
a0[i] = a[2 * i];
a1[i] = a[2 * i + 1];
}
ntt(a0, invert);
ntt(a1, invert);
ll root = power(PRIMITIVE_ROOT, (MOD - 1) / n);
if (invert) root = power(root, MOD - 2); // Modular inverse of root
ll w = 1;
for (int i = 0; i < n / 2; ++i) {
ll t = (w * a1[i]) % MOD;
a[i] = (a0[i] + t) % MOD;
a[i + n / 2] = (a0[i] - t + MOD) % MOD; // Ensure positive result
w = (w * root) % MOD;
}
if (invert) {
ll inv_n = power(n, MOD - 2);
for (int i = 0; i < n; ++i) {
a[i] = (a[i] * inv_n) % MOD;
}
}
}
// Função para calcular a inversa modular de um número
ll modInverse(ll n) {
return power(n, MOD - 2);
}
// Adaptação da multiplicação para NTT
vector<ll> multiply_ntt(vector<int>& a_coeffs, vector<int>& b_coeffs) {
int sz = a_coeffs.size() + b_coeffs.size() - 1;
int n = 1;
while (n < sz) n <<= 1;
vector<ll> fa(n, 0), fb(n, 0);
for (int i = 0; i < a_coeffs.size(); ++i) fa[i] = a_coeffs[i];
for (int i = 0; i < b_coeffs.size(); ++i) fb[i] = b_coeffs[i];
ntt(fa, false);
ntt(fb, false);
for (int i = 0; i < n; ++i) fa[i] = (fa[i] * fb[i]) % MOD;
ntt(fa, true);
vector<ll> result(sz);
for (int i = 0; i < sz; ++i) result[i] = fa[i];
return result;
}
A NTT é preferível em cenários onde a precisão é crítica ou quando os coeficientes do reusltado são esperados dentro de um módulo específico.