Problema A - Alice no País dos Primos

Tipo de problema: Matemática
Autor do Problema: Pedro Ribeiro (DCC/FCUP)

O Problema

Dado um número primo P e um conjunto de números inteiro Q_i, a tua tarefa é descobrir quais os Q_i-ésimos digitos da sequência formada pela concatenação de S^P₁, S^P₂, S^P₃, .... (e por aí adiante), onde S^P_n é a sequência dos n primeiros primos a começar no primo P.

Restrições
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Solução Base:
A solução mais simples possível para este problema seria para cada número Q_i ir gerando cada sequência (que implica ir gerando cada primo) e contando os dígitos de cada primo. Quando chegássemos ao número que continha o Q_i-ésimo dígito simplesmente imprimiamo-lo. Para gerar cada primo basta começar no primo anterior e fazer um ciclo que incrementa o número até este ser primo. O teste de primalidade é feito procurando um divisor entre 2 e o número - 1, se não existir nenhum então o número é primo.

Vamos agora partir desta solução base e ir melhorando os vários passos seguidos até chegar a uma solução ótima.

Esta seria uma solução que daria aproximadamente 30 pontos.

Pré-Calcular Primos:
Uma ideia simples mas importante seria pré-calcular a lista de primos. A ideia é evitar calcular o mesmo primo duas vezes e em vez de calcular um novo primo basta ver o próximo nesta lista.

Notem que em termos de complexidade esta ideia não melhora muito a solução anterior (deve dar mais 5-10 pontos no máximo), mas será importante na solução final.

Melhorar o Cálculo dos Primos:
Uma parte importante da solução é o cálculo dos primos, por isso, melhorá-la implica uma solução muito mais rápida. Uma opção simples e eficiente a usar é usar o Crivo de Eratóstenes. O Crivo de Eratóstenes é um algoritmo simples que gera um conjunto de primos até um valor pré-definido. Começa-se com uma matriz unidimensional vazia, onde cada elemento i dessa matriz representa se um número é primo ou não. Inicialmente marcamos todos os números como primos (exceto o 0 e o 1). De seguida começamos no primeiro primo marcado (que é o 2) e desmarcamos todos os múltiplos dele (ou seja, marcamos o 4, 6, 8, 10, ..., como não primos) até ao valor máximo que queremos calcular. De seguida fazemos o mesmo para o próximo primo marcado até chegarmos ao valor máximo. A imagem seguinte ilustra o processo.

A complexidade deste passo não é fácil de cálcular, mas é muito próxima de O(N) e por isso é muito melhor que as soluções anteriores.

Esta seria uma solução que daria aproximadamente 60 pontos.

Melhorar o Cálculo da Sequência:
O próximo passo é melhorar a maneira como se gera a sequência. Se pensarmos bem, não são necessários todos os elementos de cada sequência, apenas quantos elementos ela tem (neste caso quantos dígitos). Por isso podemos recorrer a somas acumuladas. Somas acumuladas aqui implica ter duas matrizes: list[i] e seq[j], onde list[i] contém a soma de todos os dígitos dos primos até ao i-ésimo primo (que equivale ao número de dígitos na i-ésima sequência), exclusivé, e seq[j] contém a soma de todos os dígitos de todas as sequências até à j-ésima sequência, exclusivé. Temos que list[i] = list[i - 1] + <número de dígitos do i-ésimo primo>, para onde definimos que list[0] = 0 (notem que isto implica que a lista de primos começa no primo número 1, não no primo 0). E para calcular seq[j], temos: seq[j] = seq[j - 1] + list[j], onde temos que seq[0] = 0.

Agora é importante mudar um bocadinho a solução base na parte da pesquisa. Depois de ter as matrizes cálculadas, a pesquisa faz-se da seguinte maneira: primeiro encontra-se a sequência à qual pertênce o dígito Q_i, esta corresponde à sequência cuja soma dos dígitos de todas as sequências anteriores (ou seja, o valor de seq[]) é o maior valor estritamente menor que Q_i, ou seja, começando na sequência 1, vai se testando todas as sequências até passar Q_i e a sequência pretendida será a anterior. Agora é necessário econtrar o primo à qual pertence esse dígito. Assumindo que a sequência que queremos é a sequência a, então encontrar esse dígito corresponde a encontrar o (Q_i - seq[k])-ésimo elemento dessa sequência, que por outras palavras é ignorar os dígitos das sequências anteriores. Para encontrar este dígito fazemos a mesma coisa, encontramos o maior primo cuja soma dos dígitos dos primos anteriores seja estritamente inferior a (Q_i - seq[k]). Finalmente, assumindo que esse primo é o, basta imprimir o (Q_i - seq[k] - list[o])-ésimo dígito do o-ésimo primo (que é trivial), por outras palavras, é discartar todos os dígitos dos primos anteriores a o e das sequências anteriores a k.

Esta seria uma solução que daria aproximadamente 80 pontos.

Melhorar a Pesquisa:
O último passo em direção à solução ótima é melhorar a pesquisa. Para isso recorremos a Pesquisa Binária para encontrar k e o. O resto da solução é equivalente à anterior, mas muito mais eficiente visto que cortamos um fator linear para um logarítmico.

A pesquisa binária aqui funciona de maneira simples: iniciamos os limites a e b a 0 e o número máximo de elementos na lista a procurar (pode ser seq[] ou list[]), respetivamente. Agora consideramos med = (a + b) / 2, se o med-ésimo valor da lista a procurar for superior ou igual ao índice a procurar (que pode ser (Q_i) ou (Q_i - seq[k]) para a seq[] e a list[], respetivamente) então colocamos b = med - 1, caso contrário, colocamos a = med. Para evitar ciclos infinitos, se no ínicio do ciclo a for igual a med (que pode acontecer quando a e b diferem por uma unidade) colocamos med = med + 1 (pois já pesquisámos para med = a, logo queremos um valor diferente, outra maneira de evitar isto seria arredondar (a + b) / 2 para cima, em vez de para baixo). Fazemos isto até que a seja igual a b, onde podermos considerar que o valor que procuramos é a ou b (no fim da pesquisa, claro).

Notem que evitamos falar em complexidade pois são mais díficeis de calcular do que é o problema de resolver, mas podemos dizer que para a solução ótima o cálculo dos primos é quase linear (mas feito uma só vez) e o cálculo de cada dígito Q_i é logarítmico (mas feito C vezes).

Esta seria uma solução que daria aproximadamente 100 pontos.

Ligações interessantes:

• Crivo de Eratóstenes na Wikipedia.
• Somas Acumuladas na Wikipedia.
• Pesquisa Binária na Wikipedia e no TopCoder.