約数の数

先日、Topcorder Single Round Match 466 DIV 2の500ポイントの問題を考えていましたが、解き方が全くわかりませんでした。

問題は、以下のとおりです。

Bob likes to play the lottery, but it's so hard to win without cheating. Each lottery ticket has an identifier which contains exactly n decimal digits. If an identifier contains only '0's, it is considered a winning ticket. Otherwise, the identifier is interpreted as a positive integer X written in decimal notation (possibly with leading zeros). If X has an odd number of positive integer divisors, it is a winning ticket, otherwise, it is not. A positive integer is a divisor of X if it divides X evenly.  Unfortunately, Bob only has enough money to buy one ticket, and he cannot see the identifier before buying a ticket. Therefore, he decides to cheat by buying a ticket and modifying its identifier to make it a winning ticket. In a single change operation, he can choose one digit, erase it, and print some other digit in the same position. No other types of modifications are allowed. He can perform any number of these change operations, but he wants to perform as few as possible to minimize the risk of getting caught.  You are given a String ID, the initial identifier on Bob's ticket. Return the minimal number of change operations necessary to transform the identifier into a winning one. If the initial identifier is already a winner, return 0.

要するに求めるのは、与えられたIDがすべて０にするのか、それとも約数が奇数個ある値に変換するかどちらか変更する数値の数の少ない手番数を答えなさいというもの。

情けないことに、約数が奇数個ある。というものがどんな数値なのか思いつきませんでした。（１つ１つ書いてみればわかったかもしれない）

地道に書いてみると以下のようになる。

1 = 1
2 = 1, 2
3 = 1, 3
4 = 1, 2, 4
5 = 1, 5
6 = 1, 2, 3, 6
7 = 1, 7
8 = 1, 2, 4, 8
9 = 1, 3, 9
10 = 1, 2, 5, 10
11 = 1, 11
12 = 1, 2, 3, 4, 6, 12
13 = 1, 13
14 = 1, 2, 7, 14
15 = 1, 3, 5, 15
16 = 1, 2, 4, 8, 16
17 = 1, 17
18 = 1, 2, 3, 6, 9, 18

ちなみに約数の数を数えるには、素因数分解をすると良いらしい。
18 = 2^1 * 3^2   ( 2 * 3 = 6個　累乗の数＋１同士をかけると約数のパターン数がでる）

１〜１８までの値で、約数が奇数となるのは、以下のとおり
１，４，９，１６

規則性を見つけるとしたら、
1^2, 2^2, 3^2, 4^2, ..... となるから、ある値の2乗の値は、約数が奇数であることになる。

数学的な証明は目的としないので省略しますが・・・

これがわかると、あとは約数が奇数の数値に変えるのが手番が少ないのか、すべて0にするのが手番が少ないのかを考えればよいだけになる。

頭の硬くなった年代にはちょっとむずかしい問題でした・・・orz