Qualificação ONI 2005: Problema B - Dizimação Completa

O problema B da qualificação das ONI 2005 chama-se Dizimação Completa.
Dados A e B com 0 < A < B e B ≤ 1024, o problema consiste em determinar a representação do número A / B. Alguns números têm representação exacta, mas outros têm dizimas infinitas.
Dos que não têm representação finita, alguns têm uma parte fixa e outros não.

Exemplos:

• 1 / 2 = 0.5
• 127 / 128 = 0.9921875
• 1 / 7 = 0.142857142857... não tem parte fixa e o período “142857” repete­-se indefinidamente.
• 19 / 44 = 0.43181818... a parte fixa é “43” e a parte periódica é “18”.

Assim, o objectivo é apresentar o número no formato "parte_fixa#período".

Análise

Este problema faz-nos regressar aos tempos da escola primária onde fazíamos a divisão à mão.

A diferença entre as fracções com representação finita e infinita é que na finita atingimos resto zero na divisão do numerador e do denominador, e na infinita não.

No fundo, o que queremos fazer é simular a divisão como aprendemos na primária e parar se nos depararmos com um resto da divisão já calculado anteriormente, pois quer dizer que temos uma dízima infinita periódica.

Parece simples mas convém ter alguns cuidados. É normalíssimo cometer erros a detectar o período.
Exemplo: 1 / 330 = "00#30"

Mais um caso de teste: 1 / 1023 = "#000977517106549364613880742913".

A resposta pode ser longa. O número 1 / 1021 tem um período com 1020 dígitos!