Beyond the Void
BYVoid
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

相关日志