描述

對于任何正整數x，其約數的個數記作g(x)。例如g(1)=1、g(6)=4。
如果某個正整數x滿足：g(x)>g(i) 0 < i < x，則稱x為反質數。例如，整數1，2，4，6等都是反質數。
現在給定一個數N，你能求出不超過N的最大的反質數么？

---

分析

• 一個數約數個數=所有素因子的次數+1的乘積

• 一個2000000000以內的數字不會有超過12個素因子

• 較小的數的指數一定大于等于較大的數的指數

• 準備工作: 預處理出前12個素數.

• 然后就可以暴搜了, 將遞歸層數設定為第 dep 個素數. 枚舉該素數選擇多少個, 下一層的素數一定不會超過這個值.

• 當dep == 12時更新答案并返回. 如果當前數大于當前答案并且因數個數多于答案, 更新答案; 如果當前數小于答案但是因數個數多于答案, 那么也要更新, 因為原有答案不再合法.

---

代碼

https://code.csdn.net/snippets/616418

總結

以上是生活随笔為你收集整理的BZOJ-1053-反素数ant的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。