seo点击软件哪个好用/成都sem优化

1053: [HAOI2007]反素数ant

Description

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x

，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么

？

Input

　　一个数N（1<=N<=2,000,000,000）。

Output

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

Sample Input

1000

Sample Output

840

HINT

Source

 

 

【分析】

　　GDXB教我的反素数【一开始看错题了，表示不会求n以内的反素数个数。。。

　　反素数，仔细想想就有两个重要性质，对dfs有巨大帮助：

　　

　　（1）一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为的这个数尽量小

　　（2）同样的道理，如果，那么必有

　　【想一下交换两个指数造成的影响就好了

 

　　然后一开始搞错了一个地方，看了黄学长的判断：

　　

　　if(x>id&&as>ans) ans=as,id=x;
　　else if(x<=id&&as>=ans) ans=as,id=x;

　　你可能会觉得第一句的话替换出来的不一定是反素数，但我们可以肯定即使如此我们后面也会用真正的反素数替换它的，所以正确性应该可以确定吧。

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long

LL pri[15]={10,2,3,5,7,11,13,17,19,23,29,31,37,41};

LL ans=0,id=0,n;

void dfs(LL x,LL nw,LL bf,LL cnt,LL as)
{
    if(x>n||nw>13) return;
    if(x>id&&as>ans) ans=as,id=x;
    else if(x<=id&&as>=ans) ans=as,id=x;
    
    if(cnt<bf) dfs(x*pri[nw],nw,bf,cnt+1,as/(cnt+1)*(cnt+2));
    dfs(x,nw+1,cnt,0,as);
}

int main()
{
    scanf("%lld",&n);
    dfs(1,1,30,0,1);
    printf("%lld\n",id);
    return 0;
}

 

好像不用LL 有点迷