PKU2406-Power Strings

題目：http://poj.org/problem?id=2406

(這真是一道傻人有傻福的題目…)
定義字串的冪次例如s^n就是把字串s拼接n次
例如"abc"^3 就是"abcabcabc"
給定一個字串S，試著把它還原成s^n的形式，問最大可行的n是多少？
(長度最多1000000)

程式碼：http://codepad.org/X6gCYsUK
我本來試著認真想一下怎麼樣才能二分答案？
要不要取x前綴，找找看後面重複了幾次x(或用子序列比對有幾次x符合)

不不不…我明明高一有作過這一題，但是它的作法該不會是…
沒錯
就是直接檢驗字串長度n所有的因數是否合乎要求，結束！非常的快！

不用後綴數組！不用DC3！不必KMP！
還是天真可愛的初學者最適合這樣的題目了-▽-
(換個角度想，可以拿這題來測KMP和SA模板，測資容易構造容易驗證)

至於它的時間複雜度是多少呢？我想不到符號來表示，
就暫且說字串長度N它有k的因數吧。O(Nk)

現在問題變成了，不大於1000000的正整數中，因數最多的數是甚麼？它有幾個因數？

回想起高一學過的數論"算因數個數的公式"

很簡單的想出那就把質數表上前7個數字相乘2*3*5*7*11*13*17=510510，它有2^7=128個因數
有沒有更多呢？試試2*2*3*3*5*5*7*11*13=900900，有3*3*3*2*2*2=216個因數
(所以到底怎麼樣才能構造出這種因數組合？有沒有DP？還是根本很貪心？
構造方法待補)

發現這個k對於1000000的N來說，大概只有數百左右，是很吉祥的數字
於是這個傻人有傻福的算法才能順利AC

(這篇到底要歸類在哪裡呢？我想根據我的作法…就放數學吧)