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{i\in \{prime\} } i^{q_i}$ ，则总有 $ g(p)=\prod_\limits{i\in \{prime\} } (q_i+1)$ 。

　　命题1：如果 $p$ 是一个反素数，那么必然满足 $\forall i,j\in\{prime\} $ 如果 $i<j$ ，则 $q_i\geq 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[]={,,,,,,,,,};

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=;i<=maxv;i++){

        times*=prime[pos];

        if (times>n)

            return;

        dfs(times,pos+,ysz*(i+),i);

    }

}

int main(){

    scanf("%d",&n);

    ans=cnt=;

    dfs(,,,);

    printf("%lld",ans);

    return ;

}