主題

ZeroJudge - f586: 數字D×D 解題心得

Not In My Back Yard | 2021-01-02 00:00:05 | 巴幣 0 | 人氣 70

題目連結:


題目大意:
輸入第一列給定一正整數 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 之情況。

由於根據做法的不同可能會要建質數表,建法可以參見這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

場外第一邊緣人
其實不用質因數分解,在函數Initialize()裡就可以順便算,假設mu[i]是i分類後的結果,如果i是質數mu[i]一定是1,if (!(i % primes[j]))代表mu[i*primes[j]]=0,否則mu[i*primes[j]]=-mu[i],但過的人似乎都不是這樣做,雖然大大花的時間卻還比我少(我想不通為什麼)
2021-01-02 00:34:16
Not In My Back Yard
剛剛試了一下,建表比較慢XD
2021-01-02 01:06:44
Not In My Back Yard
看來測資 T 的數量不夠大,無法體現建表的威力。
2021-01-02 01:07:39
Not In My Back Yard
對了,i 如果是質數的話,mu[i] 應為 -1 喔(上面誤植了XD)。
2021-01-02 01:08:30
場外第一邊緣人
說個題外話這題其實是求莫比烏斯函數的值
2021-01-02 00:38:11
Not In My Back Yard
原來是莫比烏斯函數,感謝補充。
2021-01-02 01:06:16

相關創作

更多創作