洛谷 P1463 [POI2002][HAOI2007]反素数

题目链接

题目描述

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。

如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。

现在给定一个数N，你能求出不超过N的最大的反质数么？

题目分析

根据反质数的概念和算术基本定理，我们可以知道，若x为反质数，则x=∏p_i^a_i(p_i为质数，p_i>p_i-1，a_i<=a_i-1)（对于最后一项限制的说明：若存在a_i>a_i-1，则交换a_i与a_i-1所得的数与原来的数因数个数相等，但比原来的数小，故原数非反质数）。

这样，我们只需要从小到大枚举质数，对于每一个质数枚举它的指数进行搜索，判断生成的数是否是满足条件的最大反质数即可，注意如果当前生成的数因数个数与记录的最大因数个数相等，但数本身比记录值小，需要更新记录值，因为原来的数已经不是反质数了。

对于枚举质数的范围，因为2×3×5×7×11×13×17×19×23×29大于N的最大值，故只需枚举这几个质数即可。同时，由于2³¹也已经大于N的最大值，所以指数的上界为31。

代码

 #include<cstdio>

 using namespace std;

 const int prime[]={,,,,,,,,,,};

 unsigned long long n,max_factor,ans;

 void dfs(unsigned long long step,unsigned long long sum,unsigned long long factor,unsigned long long maxn)

 {

     if(step>||sum>n)

         return;

     if(max_factor<factor)

     {

         max_factor=factor;

         ans=sum;

     }

     else if(max_factor==factor&&ans>sum)

         ans=sum;

     unsigned long long t=;

     for(unsigned long long i=;i<=maxn;++i)

     {

         t*=prime[step];

         dfs(step+,sum*t,factor*(i+),i);

     }

     return;

 }

 int main()

 {

     scanf("%llu",&n);

     dfs(,,,);

     printf("%llu",ans);

     return ;

 }

反素数

巴特西

洛谷 P1463 [POI2002][HAOI2007]反素数

题目链接

题目描述

题目分析

代码

最新文章

热门文章