bzoj 1053: [HAOI2007]反素数ant 搜索

2022-09-13 10:26:41

1053: [HAOI2007]反素数ant

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1497 Solved: 821
[Submit][Status]

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

　　這種題應該是通過看數據範圍和解的密度可以發現這是打表，而實際證明連打表都不用，直接暴力構造搜索就行了，搜索中避免如下數字：質因數不連續，質因數過大。這樣解的空間就很小了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<string>

#include<queue>

using namespace std;

#ifdef WIN32

#define LL "%I64d"

#else

#define LL "%lld"

#endif

#define MAXN 11000000

#define MAXV MAXN*2

#define MAXE MAXV*2

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3fLL

#define MAXL 2100000000

typedef long long qword;

inline int nextInt()

{

        char ch;

        int x=;

        bool flag=false;

        do

                ch=getchar(),flag=(ch=='-')?true:flag;

        while(ch<''||ch>'');

        do x=x*+ch-'';

        while (ch=getchar(),ch<='' && ch>='');

        return x*(flag?-:);

}

int n,m;

int seq[MAXN],tops=-;

int prime[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

struct aaa

{

        int v,x;

}a[MAXN];

bool cmp_x(aaa a1,aaa a2)

{

        return a1.x<a2.x;

}

int topa=-;

void search_m(qword now,int l,int tot)

{

        int i;

        int x;

        if (l== || now>=MAXL)return ;

//        cout<<now<<" "<<tot<<endl;

        a[++topa].x=now;

        a[topa].v=tot;

        l++;

        x=;

        for (i=;i< && now<MAXL;i++)

        {

                now*=prime[l];

                x++;

                search_m(now,l,tot*x);

        }

}

int main()

{

        freopen("input.txt","r",stdin);

        //freopen("output.txt","w",stdout);

        int i,j,k;

        int x,y,z;

        int tot;

        int mx=;

        scanf("%d",&n);

        search_m(,-,);

        sort(a,a+topa+,cmp_x);

        for (i=;i<=topa;i++)

        {

                if (a[i].v>mx)

                {

                        mx=a[i].v;

                        if (a[i].x>n)

                        {

                                cout<<x<<endl;

                                return ;

                        }

                        x=a[i].x;

                }

        }

        return ;

/*        x=1;

        mx=0;

        for (i=1;i<=n;i++)

        {

                tot=0;

                for (j=1;j<=i;j++)

                {

                        if (i%j==0)tot++;

                }

                if (tot>mx)

                {

                        mx=tot;

                        cout<<i<<" "<<tot<<" "<<endl;

                        x=i;

                }

        }

        cout<<endl;*/

        return ;

}

码农公寓