POI 2001 Antiprime Numbers 反質數

本題關鍵在於挖掘“反質數”的隱含意義,如果一個數X是反質數,則它的約數的個數大於所有Y(X>Y)的約數的個數。根據定義我們可以看出, 在一個具有相同約數個數的正整數集合中,最小的正整數是反質數。例如約數個數爲6的正整數集合{12,18,45,75,175...},只有12是反質 數。因爲任何一個比12大且約數個數等於6的數,都不滿足反質數定義。所以,尋找不大於N的最大反質數問題可以轉化成,尋找不大於N的約數個數最多的最小 正整數。

求一個數的約數個數可以用乘法原理,例如75=3^15^2,則75有(1+1)(2+1)=6個約數。對於這道題我們可以採取搜索的方法。按照質因數從小到大依次枚舉指數,找出最多的約數個數情況下最小的正整數。

/* 
 * Problem: POI2001 ant
 * Author: Guo Jiabao
 * Time: 2009.1.27 17:59
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int P[10]={2,3,5,7,11,13,17,19,23,29};

int Limit,opt,Ans;

void init()
{
    freopen("ant.in","r",stdin);
    freopen("ant.out","w",stdout);
    scanf("%d",&Limit);
}

void dfs(int base,int div,long long num)
{
    if (div > opt)
        opt=div,Ans=0x7FFFFFFF;
    if (div==opt && num<Ans)
        Ans=num;
    if (base>=10) return;
    for (int i=0;num<=Limit;num*=P[base],i++)
        dfs(base+1,div*(i+1),num);
}

int main()
{
    init();
    dfs(0,1,1);
    printf("%d",Ans);
    return 0;
}
<h2><span class="mw-headline">反質數 </span></h2>

題意描述

如果一個自然數n,滿足:所有小於n的自然數的約數個數都小於n的約數個數,則n是一個反質數。例如:1, 2, 4, 6, 12, 24。

任務

編一個程序完成以下操作:
  • 從輸入文件中讀入自然數n。
  • 計算不大於n的最大的反質數。
  • 將結果輸出到中。

    輸入格式

    輸入文件只有一個整數,n(1≤n≤2000000000)。

    輸出格式

    輸出文件只有一個整數,即不大於n的最大的反質數。

    樣例輸入

    1000
    樣例輸出
    840

相關日誌