luoguP1463:反素数ant（打表心得☆）

题目描述

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

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

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

输入输出格式

输入格式：

一个数N（<=N<=,,,）。

输出格式：

不超过N的最大的反质数。

输入输出样例

输入样例#：

输出样例#：

题目

Step 1

这个是在openjudge上（7591）能A的代码（原题：输出l~r的所有反素数），因为那时n<=2e7啊。

当然也要讲一下原理。对于数的因子个数，不得不提唯一分解定理——n=a1^p1*a2^p2*…………其中a为该数的质因数，p为它的个数，比如49=7^2，其中a1=7,p1=2。于是因子个数为（p1+1）*（p2+1）*……（49有2+1=3个因子，1,7,49）。那么搜索的目的就很明显了，枚举质因子凑数字，凑出来的那一刻已经得到了它的因子个数！

给质数打个表，打多少呢？前十几个质数虽然都很小，但乘起来肥肠肥肠恐怖啊（不信你自己试一试），所以后面都不用了。

继续剪枝，举个栗子，2^3*3^2=72,2^2*3^3=108,它们的因子个数都为（2+1）*(3+1)=12，72明显小于108，也很明显如果把3的次方给2匀一个答案更优。同样的道理，2*3=6 < 2*5=10，如果质因数的组合不连续则一定存在更小的数比当前更优。

最后我们画一棵解答树，第一层是2^1、2^2、2^3……它们的分支都有3^1、3^2、3^3……之后还有5、7、11等等接着找（具体参考程序，id为第几个质因数，now是数的大小，tot是因子数）。

#include<cstdio>

#include<algorithm>

using namespace std;

int maxn,L,R,f,ans[],p[]={,,,,,,,,,,,,,,,,};

void dfs(int id,int now,int tot)

{

    ans[now]=tot;

    for(int i=;now*p[id]<=R;++i) dfs(id+,now*=p[id],tot*(i+));

}

int main()

{

    scanf("%d%d",&L,&R);

    dfs(,,);

    for(int i=;i<L;++i) maxn=max(maxn,ans[i]);

    for(int i=L;i<=R;++i)

        if(ans[i]>maxn){

            maxn=ans[i];

            f?printf(","):f=;

            printf("%d",i);

        }

    if(!f) puts("NO");

    return ;

}

Step 2

如果能做到第一步，你就已经有一个不错的爆搜程序了，但对于2e9的范围来说还是弱了不少。仔细读题，发现这两道题还是有点区别的，我们不必求出这个范围内的所有反素数，只用找到那个最大的。既然这样，那我们就直奔答案寻找新的优化。更新条件有两个注意不要漏（估计只有像我这样头不好的人才会两次都写错……），之后参考Step 1的剪枝，我们尽量让小质数的次方数大，这也就意味着对于2^p1*3^p2*5^p3,满足p3<=p2<=p1。开个use数组记录一下p就好了。

 #include<cstdio>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #define ll long long

 #define inf 1<<29

 using namespace std;

 int n,p[]={,,,,,,,,,,,},use[];

 ll maxt,ans;

 void dfs(ll id,ll now,ll tot)

 {

     if(tot>maxt||(tot==maxt&&now<ans)) ans=now,maxt=tot;

     use[id]=;

     while(now*p[id]<=n&&use[id]+<=use[id-]){

         use[id]++;

         now*=p[id];

         dfs(id+,now,tot*(use[id]+));

     }

 }

 int main()

 {

     scanf("%d",&n);

     use[]=<<;

     dfs(,,);

     printf("%lld",ans);

     return ;

 }

Step 3

用我之前的程序可以打出比较小的表（2e8以内），观察一下，发现反素数其实很少，而且越往后它们的间隔越大（147026880~183783600，△=3e7+）。这也就意味着我们不用一个一个数去枚举小于它的最大的反质数。于是，先记录2e9的答案为1396755360，再把它减一输入程序，不断重复该操作与小的表接起来。我们终于打出最后的表了。（不容易啊QAQ~~~~~）

 #include<cstdio>

 #include<algorithm>

 #define ll long long

 using namespace std;

 int n,biao[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<;++i)

         if(biao[i]>n){

             printf("%d",biao[i-]);

             return ;

         }

     printf("%d",biao[]);

     return ;

 }

巴特西

luoguP1463:反素数ant（打表心得☆）

Step 1

Step 2

Step 3

最新文章

热门文章