Olá meus amigos nerds, mais uma vez, vamos ver como coisas que aparentemente são fáceis podem se tornar um pouco mais difíceis quando estamos lidando com entradas de tamanho um pouco maior. Para isso, vamos resolver o problema 2844. Você pode dizer 11, que nos pede para verificar se um número é divisível por 11.
Solução
Trivial. Infelizmente não é assim que funciona. A entrada pode conter números de até 1000 dígitos, enquanto um uint64_t tem mais ou menos 18 dígitos. Ai você se lembra, que tem a disposição a sua biblioteca de big int, vai lá copia e cola o código dela e tenta de novo e recebe, como resultado por não ter pensado bem a respeito, um belo de um TLE.
Lição dada é lição aprendida. Sempre tenha cuidado quando o problema envolver entradas grandes o suficiente, pois elas sempre podem trager surpresas.
Nesse momento, é hora de nos lembrarmos daqueles critérios de divisibilidade, que nos permitem saber se um número é divisível por outro sem a necessidade de fazer a conta. E para nossa sorte, o critério de divisibilidade por 11 não só existe, como também é linear no número de bits do número.
Um número é divisível por 11 caso a soma dos algarismos de ordem par menos a soma dos algarismos de ordem ímpar seja divisível por 11. A prova dessa regra é bem simples e envolve aritmética modular.
10 = 11 - 1 <=> 10 == -1 mod 11
qualquer número pode ser escrito como uma soma de potências de 10
10^n*a_n + 10^(n-1)*a_(n-1) ... + 10*a_1 + a_0
ou tomando essa soma em mod 11
(-1)^n*a_n + (-1)^(n-1)*a_(n-1) ... + (-1)*a_1 + a_0 ==
- a_n + a_(n-1) - ... - a_1 + a_0 == soma dos dígitos pares - soma dos dígitos ímpares
Nenhum comentário:
Postar um comentário