Pré-requisitos

Para uma variável (x) e um módulo (p), se definimos (x = kp + b), então (x \equiv b ,(\mod p)), e simultaneamente (f(x) \equiv f(b) ,(\mod p)).

A partir disso, podemos concluir que: sob o módulo p, uma condição necessária para (f(x) = 0) é que (f(x \mod p) = 0). Quando o módulo é suficientemente grande ou consideramos múltiplos módulos, se (f(x \mod p) = 0), é muito provável que (f(x) = 0) seja verdadeiro (similar a uma tabela de hash).

Algoritmo de Qin Jiushao

Em geral, a avaliação de um polinômio de grau n requer ((n+1) \times n \div 2) multiplicações e (n) adições. O algoritmo de Qin Jiushao, por outro lado, necessita apenas de (n) multiplicações e (n) adições, simplificando significativamente o processo de cálculo.

Um polinômio de grau (n):

[f(x) = a_0 + a_1x^1 + \ldots + a_{n-1}x^{n-1} + a_nx^n]

pode ser reescrito na forma:

[\begin{aligned} f(x) &= a_0 + a_1x + \ldots + a_{n-1}x^{n-1} + a_nx^n \ &= a_nx^n + a_{n-1}x^{n-1} + \ldots + a_1x + a_0 \ &= (a_nx^{n-1} + a_{n-1}x^{n-2} + \ldots + a_2x + a_1)x + a_0 \ &= ((a_nx^{n-2} + a_{n-1}x^{n-3} + \ldots + a_3x + a_2)x + a_1)x + a_0 \ &\vdots \ &= (\ldots((a_nx + a_{n-1})x + a_{n-2})x + \ldots + a_1)x + a_0 \end{aligned}]

Implementação do Algoritmo de Qin Jiushao

#include <iostream>
#include <vector>
using namespace std;

const int MAX_GRAU = 1001;

int main() {
    int grau, valor, modulo;
    cin >> grau >> valor >> modulo;
    
    vector<int> coeficientes(grau + 1);
    
    // Lê os coeficientes do polinômio
    for (int i = 0; i <= grau; i++) {
        cin >> coeficientes[i];
    }
    
    // Aplica o algoritmo de Qin Jiushao
    int resultado = coeficientes[grau];
    for (int i = grau - 1; i >= 0; i--) {
        resultado = (resultado * valor + coeficientes[i]) % modulo;
    }
    
    cout << resultado << endl;
    return 0;
}

Aplicação Prática

Vamos resolver um problmea específico usando esses conceitos. O objetivo é encontrar todas as raízes inteiras de um polinômio dentro de um determinado intervalo.

#include <iostream>
#include <vector>
using namespace std;

const int MODULO_PRIMO = 1000000007;
const int MAX_GRAU = 101;

vector<int> coeficientes(MAX_GRAU);

// Função para ler números eficientemente
void lerCoeficiente(int posicao) {
    long long num = 0, sinal = 1;
    char caractere;
    
    while (true) {
        caractere = getchar();
        if (caractere >= '0' && caractere <= '9') {
            num = (num * 10 + (caractere - '0')) % MODULO_PRIMO;
        } else if (caractere == '-') {
            sinal = -1;
        } else {
            break;
        }
    }
    
    coeficientes[posicao] = num * sinal;
}

int main() {
    int grau, limite_superior;
    cin >> grau >> limite_superior;
    
    // Lê todos os coeficientes do polinômio
    for (int i = 0; i <= grau; i++) {
        lerCoeficiente(i);
    }
    
    vector<int> raizes;
    int contador_raizes = 0;
    
    // Testa cada valor no intervalo
    for (int x = 1; x <= limite_superior; x++) {
        long long valor_resultante = coeficientes[grau] % MODULO_PRIMO;
        
        // Aplica o algoritmo de Qin Jiushao
        for (int j = grau - 1; j >= 0; j--) {
            valor_resultante = (valor_resultante * x + coeficientes[j]) % MODULO_PRIMO;
        }
        
        // Se o resultado for zero, encontramos uma raiz
        if (valor_resultante == 0) {
            contador_raizes++;
            raizes.push_back(x);
        }
    }
    
    // Exibe os resultados
    cout << contador_raizes << endl;
    for (int raiz : raizes) {
        cout << raiz << endl;
    }
    
    return 0;
}