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
```

上次修改时间 2017-02-03

相关日志