-
反素數
鎖定
對於任何正整數x，其約數的個數記作g(x)。例如g(1)=1、g(6)=4。
如果某個正整數x滿足：g(x)＞g(i) 0＜i＜x，則稱x為反質數。例如，整數1，2，4，6等都是反質數。
- 中文名
- 反素數
- 外文名
- Anti-prime number
- 類 型
- 數學
- 性 質
- 從2開始連續的質數
- 分 類
- 術語
反素數性質
性質一:一個反素數的質因子必然是從2開始連續的質數.
性質二:
必然
反素數算法實現
- 優化前
考慮直接暴力枚舉
以及
的因數，時間複雜度約為
。
- 優化後
還是考慮直接暴力枚舉xx，但是我們可以通過優化枚舉因數的時間複雜度來降低整個程序的時間複雜度，這種方法的時間複雜度約為
。
100分（滿分）思路：
什麼是反素數？
反素數就是區間內約數個數最多的那個數。根據題目要求，如果有多個滿足，選取最小的一個。
上文的引用部分摘自@stupid_one的博客園，有刪改。
很顯然題目要求的區間就是
。那麼我們怎麼求反素數呢？
如果我們設
為指數，
為指數的話，那麼如果一個數
可以被分成如下形式。
那麼
的因數個數就是
。
如果設
嚴格遞增，並且
也算在內，則如果
並且
，那麼顯然這個數不可能是反素數，因為交換
和
會更好。 所以當
遞增時
是遞減的，這個數
才可能是反素數。
所以我們可以據此搜索。
素數表可以篩一波，也可以這樣：
因為前12個素數的積
，所以最多用到12個素數，手動打素數表即可。
思路和代碼分別來自@羅愷的博客以及@Goes的博客。
優化前的40 分代碼（用時7000ms）：
#include <cstdio>
int yz(int t) {
int ans=0;
for(int i=1; i<=t; i++) {
if(t%i==0) {
ans++;
}
}
return ans;
}
bool pd(int x) {
int dz=yz(x);
for(int i=1; i<=x-1; i++) {
if(yz(i)>=dz) {
return false;
}
}
return true;
}
int main() {
int n=0;
scanf("%d",&n);
for(int i=n; ; i--) {
if(pd(i)==true) {
printf("%d",i);
break;
}
}
return 0;
}
優化後的40分代碼（用時6104ms ）：
#include <cstdio>
#include <cmath>
int yz(int t) {
int ans=0;
int mj=sqrt(t);
for(int i=1; i<=mj; i++) {
if(t%i==0) {
ans+=2;
}
}
if(mj*mj==t) {
ans--;
}
return ans;
}
bool pd(int x) {
int dz=yz(x);
for(int i=1; i<=x-1; i++) {
if(yz(i)>=dz) {
return false;
}
}
return true;
}
int main() {
int n=0;
scanf("%d",&n);
for(int i=n; ; i--) {
if(pd(i)==true) {
printf("%d",i);
break;
}
}
return 0;
}
100分代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long p[20]= {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
long long maxn=-1,ans=-1;
long long n=0;
void get(long long m,long long f,long long t,long long pr) {
//f為當前質數的編號，當前指數<pr
//t為當前約數的個數， m表示當前可能成為最優解的數
if(t>maxn || (t==maxn && m<ans)) { //更新最優解
ans=m,maxn=t;
}
long long i=m,j=0;
long long nt=0;
while(j<pr) { //j表示的是當前正在搜索的指數
j++;
if(n/i<p[f]) { //若不滿足條件就跳出循環（i表示的是當前的m）
break;
}
nt=t*(j+1),i*=p[f];//更新新數以及它的因子個數。
if(i<=n) { //若i（即當前的m）在區間[1,n]內就繼續搜索。
get(i,f+1,nt,j);
}
}
}
int main() {
scanf("%lld",&n);
get(1,1,1,30);
printf("%lld",ans);
return 0;
}
- 參考資料
-
- 1. [HAOI2007]反素數 ．luogu[引用日期2018-04-20]
