2461 反质数
2006年省队选拔赛浙江
题目描述 Description对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足:g(x)>g(i) 0<i<x,则称x为反质数。例如,整数1,2,4,6等都是反质数。
现在给定一个数N,你能求出不超过N的最大的反质数么?
输入描述 Input Description输入文件只有一行,一个数N(1<=N<=2,000,000,000)。
输出描述 Output Description输出文件也只有一行,为不超过N的最大的反质数。
样例输入 Sample Input1000
样例输出 Sample Output840
这道题坑了我一天……哎……打了个表,过了60,至于打表还得向飞哥学习
言归正传,这道题是一道数论题,首先引入反质数:
反素数的定义:对于任何正整数,其约数个数记为,例如,如果某个正整数满足:对任意的正整
数,都有,那么称为反素数。
从反素数的定义中可以看出两个性质:
(1)一个反素数的所有质因子必然是从2开始的连续若干个质数,因为反素数是保证约数个数为的这个数尽量小
(2)同样的道理,如果,那么必有
在竞赛中,最常见的问题如下:
(1)给定一个数,求一个最小的正整数,使得的约数个数为
(2)求出中约数个数最多的这个数
本题是枚举质数的指数,然后回溯得到结果,代码如下:
<span style="font-size:18px;">#include <iostream>
#include <cstdio>
using namespace std;
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
unsigned long long ans,n;
int Max;
void dfs(int dep,unsigned long long now,int num)
{
if(dep >= 16) return; //到叶子结点,返回
if(num > Max)//num记录因子个数,如果遇到因子数更大的更新
{
Max = num;
ans = now;
}
if(num==Max&&ans>now)ans=now;//当因子个数相同时,取值最小的
for(int i=1;i<=63;i++) //枚举指数
{
if(p[dep]*now>n) break;
dfs(dep+1,now*=p[dep],num*(i+1));
}
}
int main()
{
cin>>n;
ans=~0ULL;
Max=0;
dfs(0,1,1);
cout<<ans<<endl;
return 0;
}</span>
另外,补充一些知识,以备日后所用 http://blog.csdn.net/ACdreamers/article/details/25049767