Eu estava resolvendo o URI1371 e encontrei uma propriedade interessante.
Suponha que você queira saber o número de divisores de um número natural a. Com o Teorema Fundamental da Aritmética, você pode decompor a em seus fatores primos, desse modo:
O número de divisores de a vai ser o resultado do produto dos expoentes, somados 1, dos fatores primos, ou seja, sendo d o número de divisores:
Quando elevamos a ao quadrado, obtemos:
Note que, agora, todos os expoentes são pares, ou seja, quando calcular o número de divisores de a2, teremos um produto de ímpares, logo todo quadrado perfeito tem um número ímpar de divisores.