首页 > 代码库 > BZOJ1053 [HAOI2007]反素数ant 数论

BZOJ1053 [HAOI2007]反素数ant 数论

2024-11-26 01:27:38   203人阅读

欢迎访问~原文出处——博客园-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=2q1×3q2×5q3×7q4...
　　而且q1>=q2>=q3>=q4>=...
　　小小的证明：
　　前置技能：对于任何一个数p=x1y1×x2y2×x3y3×x4y4....
　　有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;
}

 

 
 

 

BZOJ1053 [HAOI2007]反素数ant 数论


联系
我们