codevs 2461 反质数(题解)

时间:2022-10-14 11:01:22

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 Input

1000

样例输出 Sample Output

840


这道题坑了我一天……哎……打了个表,过了60,至于打表还得向飞哥学习 
 
言归正传,这道题是一道数论题,首先引入反质数:

反素数的定义:对于任何正整数codevs 2461 反质数(题解),其约数个数记为codevs 2461 反质数(题解),例如codevs 2461 反质数(题解),如果某个正整数codevs 2461 反质数(题解)满足:对任意的正整

            数codevs 2461 反质数(题解),都有codevs 2461 反质数(题解),那么称codevs 2461 反质数(题解)为反素数。

 

从反素数的定义中可以看出两个性质:

 

(1)一个反素数的所有质因子必然是从2开始的连续若干个质数,因为反素数是保证约数个数为codevs 2461 反质数(题解)的这个数codevs 2461 反质数(题解)尽量小

(2)同样的道理,如果codevs 2461 反质数(题解),那么必有codevs 2461 反质数(题解)

 

 

在竞赛中,最常见的问题如下:

 

(1)给定一个数codevs 2461 反质数(题解),求一个最小的正整数codevs 2461 反质数(题解),使得codevs 2461 反质数(题解)的约数个数为codevs 2461 反质数(题解)

(2)求出codevs 2461 反质数(题解)中约数个数最多的这个数


本题是枚举质数的指数,然后回溯得到结果,代码如下:  


<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