題目連結：
題目大意：
輸入第一列給定一正整數 T （T ≦ 1000），代表有 T 筆測試資料，每筆佔一列。每列給定一正整數 N （N ≦ 1000000），試問正整數 N 的分類為何？
分類的規則如下：
1 分類為 1 ；
若 N 有任一因數為一完全平方數，則分類為 0 ；
若以上皆非，則計算其相異質因數之個數 k ，則其分類為 (-1) ^ k 。
範例輸入：
5
1
2
3
4
39
範例輸出：
1
-1
-1
0
1
解題思維：
可以看到「0」的分類代表著：正整數 N 的質因數分解中，某個質數的次方會超過 1 。
因此，我們可以遵循著一般質因數分解的作法（這題、這題、這題等等）。然後看是否有任何質因數之次方超過 1，有的話則給定的正整數 N 之分類即為 0；反之則計算有多少個相異的質因數 k ，然後計算 (-1) ^ k 即可知道分類。整數 1 會落於這邊，且其計算出來的分類恰好為 1 （其 k = 0），所以不用額外考慮整數 1 之情況。
由於根據做法的不同可能會要建質數表，建法可以參見這題。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
