Problema
Algumas frações unitárias são decimais exatos (1/4 = 0,25) e as demais são dízimas periódicas: 1/6 = 0,1666... repete um bloco de 1 dígito e 1/7 = 0,142857142857... um bloco de 6. Entre d = 2, 3, ..., limit, encontre o d cujo 1/d tem o maior bloco repetido (o período). Faça a divisão longa no código, como no papel: os dígitos começam a se repetir assim que um resto volta a aparecer.
Implemente longest_recurring_cycle(limit).
Entrada
limit: o maior denominador a testar.
Saída
Retorne o d com o maior período. Uma fração com decimal exato tem período 0. Em caso de empate, retorne o menor d.
Restrições
2 ≤ limit ≤ 2000
Exemplos
Entrada:
limit = 8
Saída esperada:
expected = 7
Entrada:
long long limit = 8;
Saída esperada:
long long expected = 7;
Entrada:
long limit = 8;
Saída esperada:
long expected = 7;
Explicação
Os períodos de 2 a 8 são 0, 1, 0, 0, 1, 6, 0, então a resposta é 7.
Entrada:
limit = 5
Saída esperada:
expected = 3
Entrada:
long long limit = 5;
Saída esperada:
long long expected = 3;
Entrada:
long limit = 5;
Saída esperada:
long expected = 3;
Explicação
1/3 repete um dígito, enquanto 1/2, 1/4 e 1/5 são exatos, então a resposta é 3.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Cada novo dígito de 1/d sai do resto multiplicado por 10.
Dica 2
Guarde o passo em que cada resto apareceu pela primeira vez.
Dica 3
Se o resto virar 0, o decimal é exato; caso contrário, o período é a distância entre duas aparições do mesmo resto.
Complexidade esperada
tempo O(limit²), espaço extra O(limit)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.