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

标签：

相关文章