BZOJ1053: [HAOI2007]反素数ant(爆搜)

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4163  Solved: 2485
[Submit][Status][Discuss]

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

这题跟数论有啥关系？

好像就用到约数定理

然后一波爆搜就A了

一开始读错题了以为约数相同时求最大的wa了一发

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#define LL long long

#define int long long

using namespace std;

const int MAXN = 1e5 + , INF = 1e9 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int prime[MAXN], vis[MAXN], tot = ;

void GetPrime(int N) {

    vis[] = ; prime[] = ;

    for(int i = ; i <= N; i++) {

        if(!vis[i]) prime[++tot] = i;

        for(int j = ; j <= tot && prime[j] * i <= N; j++) {

            vis[i * prime[j]] = ;

            if(!i % prime[j]) break;

        }

    }

}

int N, Ans = , Ansnum = ;

void dfs(int i, LL sum, int num) {

    if(i >  || sum > N) return ;

    if((num > Ansnum) ||(num == Ansnum && sum < Ans)) Ans = sum, Ansnum = num;

    for(int j = ; j <=  && sum * prime[i] <= N; j++)

        dfs(i + , sum *= prime[i], num * (j + ));

}

main() {

#ifdef WIN32

    //freopen("a.in", "r", stdin);

#endif

    GetPrime();

    N = read();

    dfs(, , );

    printf("%d", Ans);

    return ;

}