POI 2001 Antiprime Numbers 反質數

本文正體字版由OpenCC轉換

本題關鍵在於挖掘“反質數”的隱含意義，如果一個數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
```

上次修改時間 2017-02-03

相關日誌