關于反素數的概念參考題目鏈接

• 素數是因子最少的數，那么反素數就是因子多的數，如果在一個數之前所有的數因子數量小于這個數的因子數量，那么這個數就是一個反素數
• 那么怎么解這個問題呢？
  要求解這個問題，首先要知道幾個結論，
• 首先是唯一分解定理：任何數都可以拆成n個素數乘積的形式，且唯一
• 如果一個數可以寫成2³3²5¹這種形式，那么它有多少個因子呢？根據排列組合的知識，可以明白是4*3*2=24個，也就是選擇多少個2，多少個3，多少個5的問題
• 將一個數的最小質因子按照從小到大的順序排列起來，如果這個數是反素數。那么它們的指數應該是從大到小的。因為如果不是這樣，那么它之前一定有某個數的因子數比它多，這樣他就不是反素數了
  總結一下就是：x的因數應該最多，且如果存在因數相等的情況，那么x應該是最小的那一個（如果取大的那一個，那么就存在一個更小的數因數和它相等，這樣不符合反素數嚴格大于的性質）
• 如果理解了這樣幾個結論，那么對于這個問題，題目的n最大是2e9，這個數介于2的30次方和31次方之間，所以質因子指數和最大也就是30，可以使用搜索的方法進行爆搜，找到小于n的最大反素數，這需要記錄當前找到的數的因子個數，從而不斷更新答案

#include <iostream> using namespace std; int n; typedef long long ll; const int MAXN = 2e5 + 100; int p[MAXN]; int vis[MAXN]; ll ans; int num;//ans表示答案,num表示當前答案的因子數 int prime;//質數個數 int Prime(){int tot = 0;for(int i=2;i<=50;i++){if(!vis[i]) p[tot++] = i;for(int j=0;j<tot&&i*p[j]<=50;j++){vis[i*p[j]] = 1;if(i % p[j] == 0) break;}}return tot; } void dfs(ll now, int number, int m){//now表示當前數是多少,number表示當前因數數量,m表示到第幾個質數了 if(m >= prime) return;//因數數量小于當前顯然需要更新為當前//如果因數個數和當前相等,那么答案應該更新為小的那一個（反素數因子個數嚴格大于前面的數的性質） if(number > num || number == num && ans > now){ans = now;num = number;}for(int i=1;i<=31;i++){if(p[m] * now > n) break;now *= p[m];dfs(now, number * (i + 1), m + 1);//這里的number進行的改動就是在前面我說的排列組合//如果i為1,那么說明p[m]的指數為1，那么就有i+1=2種情況 } } int main(){prime = Prime();cin>>n;dfs(1, 1, 0);cout<<ans; return 0; }

如果還有問題可以看這個視頻講解

總結

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

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