[Codeforces] 1031F Familiar Operations

LINK：http://codeforces.com/contest/1072/problem/F

SOL：http://codeforces.com/contest/1072/submission/44824735

這題看了就沒想法，花了一小時多才終於看懂解了。

首先會想到質因數表示法，然後可以將其表示為一個vector，注意到這個向量在題目的要求下，sort完後等價於原本的，所以將1e6以下的所有數字所表示的vector sort後會發現數量其實很少。

接者問題就變成了兩個vector之間最少需要多少次操作才能相等。
錯誤解：floyd-warshall，因為操作過程中的向量有可能是在1e6以下表示不出來的 ( 像是2^20 )

觀察題目要求，它要求我們要將兩個數字的vector的個元素相乘後相等，所以可以試著bruteforce每個vector變成每種乘積最少需要多少操作，估計一下乘積後會發現最大值一定在1000以下，因為2*3*5*7*11*13*17 > 1e6，對1000以下的所有數字，bruteforce每種乘積的不同表示法，並對所有vector求出最小所需操作，這樣我們就有每種vector到每種乘積所需的最小操作步數了。

最後對於題目詢問的x, y，去bruteforce兩個向量元素乘積變成哪個數字比較好。

總結：
我認為牽扯到"相乘等於多少"、"質數"......之類的題目的複雜度都不好估，像是這題雖然範圍高達1e6，但其實不等價的向量竟然只有300個，還有1000以下分成少於等於10個數字乘積的分法，這個直觀來看也不好估；總之題目可能會出一些等價的東西來混淆視聽，要多加注意！

話說這題那個1000，我試了幾個數字後發現512也可以過；分成10個數字乘積，我改成7個數字也是能過。