一道神祕題

給你兩個數字，A, B（A, B <= 10000）

你可以把他們各自拆成乘積:

33 -> 3, 11
24 -> 2, 3, 4
18 -> 2, 9

拆完的數字，由小排到大，計算差的平方和

EX:

33 40

-> 3, 11, 5, 8 -> 3, 5, 8, 11 -> (3-5)^2+(5-8)^2+(8-11)^2

= 22

而剛好這也就是所有拆法的「差的平方和」的最小值

給兩數字，求「差的平方和」的最小值

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

這種，近乎nHm的怪異題型，碰到就要先試試看DP

以某個數字X結尾的序列，A還剩A'沒拆，B還剩B'沒拆

最少的cost 為 DP[X][A'][B']，這樣。

可知A'會是A的因數，B'也是，X則是其一的因數

在1 ~ 10000裡，因數最多的數字也只有64個

所以DP的空間複雜度是64^3

至於要怎麼轉移，其實就看倒數第二是誰就行了

全部的複雜度是64^4。

但是，問題是他會問1000次：

1000 * 64^4 = 16777216000 = 10^10，就GG了




那要怎麼辦呢？

其實只要壓掉一個64就可以了

不是什麼性質，也沒有什麼怪東西

這裡不要想太多，簡單的DP優化而已 :)

http://ideone.com/hCStyp