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=2^q1×3^q2×5^q3×7^q4...
　　而且q1>=q2>=q3>=q4>=... 　　小小的证明： 　　前置技能：对于任何一个数p=x1^y1×x2^y2×x3^y3×x4^y4.... 　　有p的因数个数为(y1+1)(y2+1)(y3+1)(y4+1)  ……
　　如果不满足q1>=q2>=q3>=q4>=... 　　假设qx<qy(x<y) 　　那么必然存在一个q序列，交换qx和qy，使得这个数a的因数个数和p相等，且a<p，那么就就有g(a)=g(p)，p>a，不满足g(p)>g(a)，于是不成立。 　　然后毕竟这样，还是会有一些因数个数相同的情况。 　　比如数a的因数个数式子为： 　　(y1+1)(y2+1)(y3+1)... 　　构造b，是的b的式子为： 　　(y1+y2+1)(y3+1)... 　　所以我们还是要判断一下的。 　　 　　但是不考虑这个特殊情况，可以找出来的数已经很少了，所以我们可以dfs一下。

---

代码

#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;
}