BZOJ1053 [HAOI2007]反素数ant 数论

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

传送门 - BZOJ1053

题目描述

　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？

（1<=N<=2,000,000,000）

题解

　　对于任何一个数 $p$ ，令 $p=prod_limits{iin {prime} } i^{q_i}$ ，则总有 $ g(p)=prod_limits{iin {prime} } (q_i+1)$ 。

　　命题1：如果 $p$ 是一个反素数，那么必然满足 $forall i,jin{prime} $ 如果 $i<j$ ，则 $q_igeq q_j$ 。

　　我们可以简单的证明这一点。即：若 $q_i<q_j$ 则 $i^{q_i}j^{q_j}geq i^{q_j}j^{q_i}$ ，所以至少存在一个数 $q^prime$ ，在满足 $g(q)=g(q^prime)$ 的情况下，使得 $q^prime < q$ 。这与之前 “$q$ 是反素数” 的定义相悖，所以命题1 得证。

　　但是，可以见得，上述命题虽然具有充分性，但是不具有必要性。

　　譬如：

　　$a=2^13^15^1$

　　$b=2^35^1$

　　它们的因数个数都是 $8$ 。

　　由于我们在证明了命题1 之后，很容易发现可能的反素数非常少。所以我们只要暴搜就可以了。

　　建议判掉类似于上面举的例子的这种情况。

代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const LL prime[11]={2,3,5,7,11,13,17,19,23,29};
LL n,ans,cnt;
void dfs(LL times,int pos,int ysz,int maxv){
    if (ysz>cnt)
        ans=times,cnt=ysz;
    else if (ysz==cnt&&times<ans)
        ans=times,cnt=ysz;
    for (int i=1;i<=maxv;i++){
        times*=prime[pos];
        if (times>n)
            return;
        dfs(times,pos+1,ysz*(i+1),i);
    }
}
int main(){
    scanf("%d",&n);
    ans=cnt=0;
    dfs(1,0,1,33);
    printf("%lld",ans);
    return 0;
}