1541 . 打呼魔人的連續技
TopCoder
Tags
Description
おれの財宝か？
欲しけりゃくれてやるぜ…
探してみろ
この世のすべてをそこに置いてきた
<ゴール・D・ロジャー>
胖胖天－一位生於大海賊時代的年輕人，在耳聞魯夫的光榮事蹟之後，覺得魯夫實在是太帥太神勇了，所以他也決定出海成為一位海賊。
旅居海上不久，他發現了一個惡魔果實，沒想到吃下去之後身體劇變----原來是吃了一種叫打呼果實的超強果實。
因此他的絕招往往跟打呼有關，例如: 打呼死光，打呼飛彈，打呼炮擊，打呼光波，打呼光束...等等。
每個絕招都有一個固定的攻擊力值pi。
並且他的絕招往往有合成效果，每當他想使出連續技的時候，這些連續技的攻擊力會有倍增的效果，也就是連續技攻擊力 = 各個攻擊力的乘積。因為連續技基本上是一種合成技，所以與招式的發動順序無關。
但是發動連續技的條件是，必須要合成技攻擊力為完全平方數才行，不然會因為非完全平方數的不穩定性，造就自身受到傷害或副作用(例如睡覺會被自己呼聲吵醒之類的XD)。
現在他想知道，他有幾種連續技可以發動，你能否幫他計算呢?
Input Format
輸入一數n(1<=n<=1000)，代表絕招的數量。
接下來有n行，每行為一正整數pi(1<=pi<=10500),代表第i個攻擊的攻擊力。
註: 因為每個絕招也是由小絕招合成而來，所以對於所有的pi，不會出現>1000的質因數。
Output Format
請輸出一數，代表胖胖天有幾種連續技可以發動。
Sample Input 1
132
1
385
30
30
35574
33
Sample Output 1
Sample Input 2
1428
154
95625
11900
3185
46410
221
9438
23205
55
Sample Output 2
Hints
Sample #1 Explanation:
七種絕招攻擊力分別是:
132 = 22 * 3 * 11
1 = 1
385 = 5 * 7 * 11
30 = 2 * 3 * 5
30 = 2 * 3 * 5
35574 = 2 * 3 * 72 * 112
33 = 3 * 11
顯而可見(茶)
七種可發動連續技的攻擊力分別是:
3920400 = 132 * 1 * 30 * 30 * 33
4356 = 132 * 1 * 33
3920400 = 132 * 30 * 30 * 33
4356 = 132 * 33
1 = 1
900 = 1 * 30 * 30
900 = 30 *30
Problem Source
原TIOJ1541 / Problem Setter: math120908
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 12 |
| 2 | 1 | 12 |
| 3 | 2 | 12 |
| 4 | 3 | 12 |
| 5 | 4 | 12 |
| 6 | 5 | 12 |
| 7 | 6 | 12 |
| 8 | 7 | 16 |