二 03
本题关键在于挖掘“反质数”的隐含意义，如果一个数X是反质数，则它的约数的个数大于所有Y(X>Y)的约数的个数。根据定义我们可以看出， 在一个具有相同约数个数的正整数集合中，最小的正整数是反质数。例如约数个数为6的正整数集合{12,18,45,75,175…}，只有12是反质 数。因为任何一个比12大且约数个数等于6的数，都不满足反质数定义。所以，寻找不大于N的最大反质数问题可以转化成，寻找不大于N的约数个数最多的最小 正整数。
求一个数的约数个数可以用乘法原理，例如75=3^1*5^2，则75有(1+1)*(2+1)=6个约数。对于这道题我们可以采取搜索的方法。按照质因数从小到大依次枚举指数，找出最多的约数个数情况下最小的正整数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | /* * 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; } |
反质数
题意描述
如果一个自然数n，满足：所有小于n的自然数的约数个数都小于n的约数个数，则n是一个反质数。例如：1, 2, 4, 6, 12, 24。
任务
编一个程序完成以下操作：
- 从输入文件中读入自然数n。
- 计算不大于n的最大的反质数。
- 将结果输出到中。
输入格式
输入文件只有一个整数，n（1≤n≤2000000000）。
输出格式
输出文件只有一个整数，即不大于n的最大的反质数。
样例输入
1000样例输出
840
据说可以用DP做，望大牛研究，我很不解
[回复]
质数表为啥只到29？
[回复]