Todos os problemas algorítmicos que vemos nos concursos das Olimpíadas requerem saber alguma matemática. Esta frase é um pouco vaga, visto que quase tudo requer alguma matemática e matemática é uma área muito diversa. Apesar de já termos visto vários conceitos matemáticos escondidos nos artigos anteriores, vamos ver um sumário de alguns temas que devem saber. Todos estes temas inserem-se no tópico de matemática discreta, ou seja, a matemática que diz respeito a objetos discretos (e no nosso caso também finitos). É difícil de definir isto mais formalmente (e fora do nosso interesse), por isso não se preocupem muito com isso.

Um pequeno aviso antes de continuarmos, este artigo apenas contém um sumário muito breve destes temas, com ênfase no que é útil para concursos algorítmicos. Para saberem mais sobre os diferentes temas é aconselhado que olhem para um livro de matemática discreta (sugerimos alguns no próximo artigo).

Somas e produtos

Vamos começar com alguma notação matemática e algumas fórmulas úteis. Suponhamos que temos uma sequência de números que indicaremos com a letra $s$. Usamos a notação $s_i$ ($i$ em sub-índice) para indicar o $i$-ésimo elemento da sequência. Podemos pensar em $s$ como uma array e fazer s[i] é equivalente a $s_i$ em notação matemática. Se quisermos indicar a soma dos primeiros $n$ elementos da sequência podemos usar o símbolo de soma, ou seja, podemos escrever o seguinte: $\sum_{i = 1}^n s_i$. O símbolo $\sum$ indica uma soma dos elementos que se seguem e a notação $i = 1$ indica que vamos somar sobre a variável $i$ a começar em 1 até ao valor indicado no topo da soma, neste caso $n$. Ou seja, temos que $\sum_{i = 1}^n s_i = s_1 + s_2 + \ldots + s_n$. Assim como temos um símbolo de soma, também temos um símbolo de produto, nomeadamente o símbolo $\prod$. Isto é, podemos escrever o seguinte: $\prod_{i = 1}^n s_i = s_1 \cdot s_2 \cdot \ldots \cdot s_n$. Esta notação é muito útil e será recorrente em textos sobre algoritmos.

Vamos ver como resolver duas somas comuns. Considerem a soma $\sum_{i = 1}^n i$, ou seja, a soma de todos os números de 1 até $n$. É das somas mais comuns, aparece em quase todo lado. Como podemos arranjar uma fórmula simples para ela? Vamos primeiro assumir que $n$ é par e vamos agora agrupar termos em pares: o 1 com o $n$, o 2 com o $n - 1$, etc. Há $n / 2$ grupos destes e cada um tem soma $n + 1$, ou seja, o total é $n (n + 1) / 2$. E para $n$ ímpar? Se fizerem as contas podem ver que a mesma fórmula se aplica! Ou seja, temos que $\sum_{i = 1}^n i = n (n + 1) / 2$. Considerem agora a soma $\sum_{i = 0}^n a \cdot k^i$ (reparem que a soma começa em 0 agora), dados dois números $a$ e $k$, ou seja, $a + ak + ak^2 + \ldots + ak^n$. Vamos chamar $S$ à soma que nos interessa, ou seja $S = \sum_{i = 0}^n a \cdot k^i$. Reparem agora que $Sk = \sum_{i = 1}^n a \cdot k^i$ (o valor inicial de $i$ é agora 1), por isso podemos ver que $Sk - S = ak^{n + 1} - a$, visto que todos os termos se cancelam tirando o primeiro de $S$ e o último de $Sk$. Podemos agora resolver esta equação e ficar com $S = (ak^{n + 1} - a) / (k - 1)$, ou seja, $\sum_{i = 0}^n a \cdot k^i = (ak^{n + 1} - a) / (k - 1)$ e temos a nossa fórmula curta para a soma.

Há muitas mais somas e produtos de interesse, mas o objetivo desta secção era introduzir a notação e mostrar alguns exemplos.

Logaritmos

Já vimos a expressão logaritmo aparecer várias vezes nos últimos artigos, mas alguns de vocês podem não saber bem o que isto significa. O logaritmo é a operação inversa à exponenciação. Um logaritmo escreve-se da seguinte forma $\log_b a$ para indicar o logaritmo de $a$ de base $b$ e temos que $\log_b a = x$ se $b^x = a$. Uma outra maneira de pensar no logaritmo anterior é que $x$ é o número de vezes que precisamos de dividir $a$ por $b$ para obtermos 1. Naturalmente o logaritmo pode não ser um inteiro, por exemplo, $\log_3 8 = 1.892789260714372...$.

Os logaritmos têm várias propriedades interessantes, por exemplo:

  • $\log_b (xy) = \log_b (x) + \log_b (y)$, o logaritmo do produto é a soma dos logaritmos;
  • $\log_b (x^n) = n \log_b (x)$, por aplicação da regra anterior $n$ vezes;
  • $\log_b (x / y) = \log_b (x) - \log_b (y)$, o logaritmo da divisão é a diferença dos logaritmos;

Uma coisa que devem ter reparado é que quando usámos a notação big-O com logaritmos, nunca mencionámos a base. A maior parte dos logaritmos são de base 2, mas nem isso mencionámos. A razão é porque o seguinte se verifica: $\log_b x = (\log_k x) / (\log_k b)$, para qualquer $k$, o que significa que podemos mudar a base de um logaritmo ao multiplicar (ou dividir) por um número constante, por isso não temos de nos preocupar com isso dentro da notação big-O.

Teoria de conjuntos

Uma das unidades mais importantes em matemática é o conjunto. Já conhecemos muitos conjuntos, como o conjunto dos números naturais $\mathbb{N}$ ou o dos números inteiros $\mathbb{Z}$, mas vamos ver um pouco da notação associada a conjuntos. Um conjunto é uma coleção de elementos distintos, normalmente denotada usando chavetas, por exemplo, o conjunto $S = {1, 2, 4}$ é o conjunto de três elementos que contém os números 1, 2 e 4. Usamos a notação $\varnothing$ ou ${}$ para denotar um conjunto vazio e a notação $|S|$ para denotar o número de elementos de $S$. Usamos ainda a notação $x \in S$ para indicar que o conjunto $S$ contém o elemento $x$ e a notação $x \notin S$ para indicar que não contém $x$.

Podemos fazer várias operações com conjuntos, por exemplo, dados dois conjuntos $A$ e $B$:

  • $A \cap B$, indica a interceção dos conjuntos, ou seja, o conjunto de elementos que se encontra em $A$ e em $B$;
  • $A \cup B$, indica a união dos conjuntos, ou seja, o conjunto de elementos que se encontra em $A$ ou em $B$;
  • $A \setminus B$, indica a diferença dos conjuntos, ou seja, o conjunto de elementos que se encontra em $A$ mas não em $B$;

Finalmente, dizemos que um conjunto $A$ é um subconjunto de outro conjunto $B$ se todos os elementos de $A$ se encontram em $B$, e escrevemos isto como $A \subset B$.

Teoria de números

Teoria de números é a área de matemática que lida com números inteiros, ou seja, números em $\mathbb{Z}$. Comecemos com algumas definições que já devem saber da escola básica.

Um número $a$ diz-se um divisor ou fator de outro número $b$ se $a$ divide $b$, o que formalmente significa que existe um número $c$ tal que $a \cdot c = b$ (novamente, todos os números desta secção são inteiros, isto inclui $a, b, c$). Usamos a notação $a | b$ para indicar que $a$ é um divisor de $b$ e $a \nmid b$ para indicar que $a$ não é um divisor de $b$. Naturalmente, se $a | b$, então $b$ é um múltiplo de $a$. As seguintes 4 propriedades são factos sobre a divisibilidade:

  • Se $a | b$ então para qualquer número $c$ também é verdade que $a | bc$;
  • Se $a | b$ e $b | c$ então também é verdade que $a | c$;
  • Se $a | b$ e $a | c$ então para quaisquer números $s$ e $t$ também é verdade que $a | sb + tc$;
  • Para todos os números $c \neq 0$, $a | b$ se e só se $ca | cb$;

Um número $p > 1$ é primo se os únicos divisores positivos são o 1 e o próprio número $p$, por exemplo, $73$ é primo, mas $21 = 3 \cdot 7$ não. Uma das propriedades que tornam os números primos tão interessantes é que todos os números admitem uma fatorização em primos, ou seja, dado qualquer número $n$ temos que $n = p_1^{a_1} p_2^{a_2} \ldots p_k^{a_k}$ onde $p_1, p_2, \ldots, p_k$ são $k$ números primos distintos e $a_1, a_2, \ldots, a_k$ são $k$ inteiros positivos diferentes de 0, para algum inteiro $k > 0$. Esta fatorização é única, ou seja, há apenas uma fatorização deste género para qualquer número. Isto significa que se tivermos um número $n$ e a lista de primos menores ou iguais a este número, um algoritmo para fatorizar $n$ consiste em verificar quantas vezes $n$ é divisível por 2, ou seja, quantas vezes podemos dividir $n$ por 2 e obter sempre um inteiro, repetir para 3, 5, etc. O código seguinte faz exatamente isto.

// assumimos que temos uma lista de primos de nome
// primos e comprimento comprimento_lista
for (i = 0; i < comprimento_lista; i++) {
  while (n % primos[i] == 0) {
    fatores[numero_fatores++] = primos[i];
    n /= primos[i];
  }
}

Estamos a guardar os fatores primos numa array fatores. Notem que estamos a usar um pequeno truque para ver quantas vezes um número é fator de $n$, se sabemos que $n$ é divisível pelo $i$-ésimo primo, então agora só temos de fatorizar $n / \text{primos}[i]$.

A fatorização mencionada é interessante por várias razões, por exemplo, imaginemos que queremos saber quantos divisores tem um número $n$ e nos é dada a fatorização em primos. Então podemos calculá-lo ao avaliar a seguinte expressão: $\prod_{i = 1}^k (a_i + 1)$. Devem pensar um pouco para perceber porque é que esta fórmula está correta, mas reparem que qual quer divisor de $n$ tem uma fatorização em primos que é $p_1^{a'_1} p_2^{a'_2} \ldots p_k^{a'_k}$, onde $0 \leq a_i' \leq a_i$ (esta expressão é um pouco difícil de decifrar à primeira vista, mas se lerem com atenção podem ver que não diz nada de especial).

Uma outra propriedade importante dos números primos é que há infinitos números primos. Como é muito fácil provar isto, apesar de não estarmos a mostrar provas de nenhuma das coisas que vimos até agora, esta será a única exceção. Vamos supor que só há $n$ primos, $p_1, \ldots, p_n$. Então o seguinte número $p_1 \cdot p_2 \ldots p_n + 1$ ou é primo ou é divisível por pelo menos um primo $p_i$, para algum $i$. Então $p_i$ divide $p_1 \cdot p_2 \ldots p_n + 1$ mas também $p_1 \cdot p_2 \ldots p_n$ (é trivial ver porquê). Como vimos anteriormente (a terceira propriedade da lista acima sobre divisibilidade), se um número divide outros dois também divide a sua diferença (basta escolher $s = 1$ e $t = -1$), logo $p_i$ divide a diferença dos dois números mencionados, que é 1. Nenhum número primo divide 1, ou seja, chegámos a uma contradição ao que assumimos, o que significa que o número de primos não pode ser finito.

Aritmética modular

Vamos rever o teorema da divisibilidade, que diz que para quaisquer números (novamente, estamos a trabalhar com números inteiros aqui!) $a$ e $b$, onde $b \neq 0$, existem números $q$ e $r$ tal que $a = bq + r$, onde $0 \leq r < |b|$, onde $|b|$ designa o valor absoluto de $b$ (recordem que números inteiros podem ser negativos). Adicionalmente, sabemos que os números $q$ e $r$ são únicos. Este aparentemente complexo teorema apenas nos diz que podemos sempre dividir um número por outro, é exatamente o que aprendemos na escola primária, mas usando termos um pouco mais formais. O valor $q$ chama-se o quociente e o valor $r$ o resto da divisão.

Aritmética modular refere-se ao sistema de aritmética do resto da divisão (veremos o que isto significa). Reparem que já usámos o resto da divisão várias vezes anteriormente. Quando queremos testar divisibilidade de um número $a$ por outro $b$ o código que escrevemos é a % b == 0, o que o operador % nos diz é o resto da divisão de $a$ por $b$, que se for 0 significa que $a$ é divisível por $b$ (relembrem a definição de divisibilidade que vimos no início desta secção). Em matemática, usamos a relação módulo, escrevendo $a \equiv r \mod b$, o que significa que $a$ é igual a $r$ módulo $b$. O que o anterior significa é que $a$ e $r$ têm o mesmo resto de divisão quando divididos por $b$, o que é obviamente verdade se $r$ for o resto da divisão, mas mais geral. Por exemplo, $13 \equiv 13 \mod 4$, mas também $13 \equiv 5 \mod 4$ e $13 \equiv 1 \mod 4$. Dizemos que dois números $a$ e $b$ são congruentes módulo $n$ se tiverem o mesmo resto de divisão, ou seja, se $a \equiv b \mod n$.

Uma forma alternativa de pensar num sistema de relógio. Imaginem que queremos saber qual é o resto da divisão de $a$ por $b$, podemos imaginar um relógio de $b$ horas com um ponteiro inicialmente nas $b$ horas (ou nas 0 horas, o ponteiro a apontar no sentido norte). Agora, esse ponteiro vai avançar $a$ horas, potencialmente dando a volta ao relógio várias vezes. A hora que o ponteiro apontar quando terminar a sua rotação indica o resto da divisão de $a$ por $b$. Isto significa que podemos escrever um algoritmo simples para determinar o resto da divisão de dois números, embora muito pouco eficiente (nunca usem este código, é apenas ilustrativo):

while (a > b) {
  a -= b;
}
int resto = a;

Com esta ideia do relógio podemos deduzir um conjunto de propriedades que são muito úteis:

  • Se $a \equiv b \mod n$ e $c \equiv d \mod n$ então $a + c \equiv b + d \mod n$, isto implica que (a + b) % n é igual a ((a % n) + (b % n)) % n;
  • Se $a \equiv b \mod n$ e $c \equiv d \mod n$ então $a - c \equiv b - d \mod n$;
  • Se $a \equiv b \mod n$ e $c \equiv d \mod n$ então $a \cdot c \equiv b \cdot d \mod n$, isto implica que (a * b) % n é igual a ((a % n) * (b % n)) % n;

Duas notas muito importantes sobre as propriedades anteriores. Primeiro, devem ter reparado que temos uma propriedade de adição, uma de subtração e uma de multiplicação, então e dividir? De modo geral não existe uma propriedade de divisão, em certos casos é possível dividir em módulo (usando algo chamado o "pequeno teorema de Fermat" ou outras identidades de teoria de números), mas não vamos abordar esse tema aqui. A segunda nota é que não temos uma igualdade usando o operador % para a subtração, na verdade temos mas é um pouco diferente: (a - b) % n é igual a ((a % n) - (b % n) + n) % n, notem o fator extra de +n no fim, este tem de ser incluído porque se a diferença em módulo for negativa a implementação do operador % tem um comportamento diferente (não nos interessa muito saber porquê).

Vamos ver duas aplicações de aritmética modular que são muito úteis. A primeira é no chamado "algoritmo de Euclides", um dos algoritmos mais antigos que conhecemos! Vamos supor que queremos calcular o máximo divisor comum de dois números, ou seja, o maior número $g$ tal que $g | a$ e $g | b$. Uma forma de o calcular é usando a fatorização em primos que discutimos anteriormente. Mas vamos ver uma forma mais eficiente.

Primeiro vamos introduzir uma notação simples, nomeadamente escrevemos o máximo divisor comum de $a$ e $b$ como $\text{gcd}(a, b)$ (o acrónimo "gcd" vem do inglês "greatest common divisor"). Agora observemos duas propriedades simples (para simplificar vamos considerar que estamos sempre a trabalhar com inteiros positivos para esta parte):

  • $\text{gcd}(a, 0) = a$;
  • $\text{gcd}(a, b) = \text{gcd}(a - b, b)$, se $a > b$;

A primeira identidade é óbvia, 0 é divisível por qualquer número. Para a segunda recordem as propriedades da divisão, se um número divide dois, também divide a sua diferença. Isto significa que um algoritmo muito simples para calcular o máximo divisor comum de dois números é repetidamente subtrair o mais pequeno ao maior até um deles ser 0. Mas podemos melhorar esta ideia ainda mais! Recordem que o algoritmo muito simples que vimos anteriormente para calcular o resto da divisão funciona exatamente por subtrair repetidamente um número ao outro. Isto indica-nos que o seguinte também é verdade:

  • $\text{gcd}(a, b) = \text{gcd}(a \mod b, b)$, se $a > b$ (onde mod é o operador %);

Com isto o algoritmo final que calcula o máximo divisor comum é aplicar repetidamente o operador %, como o seguinte código mostra:

while (b != 0) {
  if (b > a)
    swap(a, b); // se o b for o maior, trocamos o a com b
  else
    a = a % b;
}
int g = a;

O segundo uso que vamos ver para aritmética modular é trabalhar com números grandes. É claro que não é possível representar o número $2^{1000}$ usando um int ou ainda um long long int, o número é demasiado grande para estas representações. Mas o número $2^{1000} \mod n$, para um valor de $n$ suficientemente pequeno para caber num int já é possível! Para calcular este valor podemos aplicar a propriedade de multiplicação que vimos antes e assim o seguinte código faz exatamente isso:

int dois_levantado_a_mil = 1;
for (int i = 0; i < 1000; i++) {
  dois_levantado_a_mil *= 2;
  dois_levantado_a_mil %= n;
}

Vamos usar isto num problema onde a resposta seria um número muito grande, mas vamos pedir a resposta módulo um outro número.

O João é dono de um dos maiores restaurantes da zona. Todos vão ao seu restaurante e por isso há sempre muita procura por pratos novos. Para sistematizar a criação de pratos, o João agrupou os vários ingredientes que tem disponível em $N$ grupos, onde cada ingrediente encontra-se em exatamente um grupo. O i-ésimo grupo tem exatamente $g_i$ ingredientes. Para criar um prato, o João pode escolher um ingrediente de cada grupo, mas não mais que 1. Nota que não é preciso escolher ingredientes de todos os grupos, mas é preciso escolher pelo menos 1 ingrediente. O João quer saber o número de pratos diferentes que este sistema lhe permite criar. Como este número pode ser muito grande, o João quer saber o seu valor módulo 12345.

Vamos ver um exemplo simples. Suponhamos que há $N = 3$ grupos, onde o primeiro grupo tem 2 ingredientes (por exemplo, cogumelos e bacon), o segundo tem 1 (por exemplo, abacate) e o terceiro tem 2 (por exemplo, queijo e fiambre). Então há 17 pratos possíveis: cogumelos, cogumelos+abacate, cogumelos+queijo, cogumelos+fiambre, cogumelos+abacate+queijo, cogumelos+abacate+fiambre, bacon, bacon+abacate, bacon+queijo, bacon+fiambre, bacon+abacate+queijo, bacon+abacate+fiambre, abacate, abacate+queijo, abacate+fiambre, queijo, fiambre.

Há várias maneiras de contar este número mas a maneira mais simples é a seguinte: para o primeiro grupo temos $g_1 + 1$ escolhas de ingredientes, ou escolhemos um dos $g_1$ ou não escolhemos nenhum ingrediente; para o segundo temos $g_2 + 1$ escolhas, ... ou seja, só temos de considerar o produto de todos estes números. Temos ainda de ter cuidado pois isto inclui o caso em que não escolhemos nenhum ingrediente, por isso temos de subtrair 1 ao valor anterior. Assim, a fórmula do resultado é $\left(\prod_{i = 1}^N (g_i + 1) \right) - 1$ (reparem que a fórmula é muito semelhante a que vimos para calcular o número de divisores de um número dada a sua fatorização, o raciocínio é o mesmo). Com esta fórmula apenas nos resta calcular isto módulo 12345 e para isso teremos de aplicar as propriedades que vimos, assim como no exemplo do $2^{1000}$. Deixamos essa tarefa para vocês.

Problema L: Restaurante do João

Este problema está disponível no Mooshak de treino como o problema L