問題は、以下のとおりです。
要するに求めるのは、与えられたIDがすべて０にするのか、それとも約数が奇数個ある値に変換するかどちらか変更する数値の数の少ない手番数を答えなさいというもの。
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.
情けないことに、約数が奇数個ある。というものがどんな数値なのか思いつきませんでした。（１つ１つ書いてみればわかったかもしれない）
地道に書いてみると以下のようになる。
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
